星图
题目背景
可怜的 lzh 宝宝被联合省选2026中星图这道题创飞了,事后补题的时候写的四元环算法。
他目前写的是如果有四元环就消四元环,否则再去消长度为 3 的链,优化还没来得及加。
他突然比较好奇这个做法的操作次数真的是 O(n2) 的吗。
题目描述
这是一道提交答案题,没有输入,只需要输出。
构造一个无向简单图,要求点数不超过 1000,且不存在由四个不同顶点构成的四元环。顶点从 1 到 n 编号。图中不能有自环或重边,同一条边换序后仍是同一条边。
输出格式
将答案写入 starmap.out,放在一个 ZIP 压缩包的根目录后提交。
第一行两个整数 n,m,分别表示点数和边数。
接下来 m 行每行两个整数 u,v,表示一条连接 u,v 的无向边。
评分
如果输出图不合法,获得 0 分。
否则,获得的分数是 f(m),其中函数 f(x) 为一个分段函数,前期为指数 >1 的幂函数,中期为指数 <1 的幂函数,后期为指数 >1 的幂函数。
$$f(x) =
\begin{cases}
25 \cdot \left(\frac{x}{2000}\right)^{2.5} & 0 \le x < 2000 \\
25 + 35 \cdot \left(\frac{x - 2000}{13000}\right)^{0.75} & 2000 \le x < 15000 \\
60 + 40 \cdot \left(\frac{x - 15000}{904}\right)^{20} & 15000 \le x < 15904 \\
100 & x \ge 15904
\end{cases}$$
下方给一些具体的数值表,保留到三位小数。
| x |
f(x) |
x |
f(x) |
x |
f(x) |
x |
f(x) |
x |
f(x) |
x |
f(x) |
| 0 |
5000 |
36.653 |
10000 |
49.318 |
15000 |
60 |
15845 |
70.371 |
15895 |
92.746 |
| 500 |
0.781 |
5500 |
38.082 |
10500 |
50.449 |
15800 |
63.471 |
15850 |
71.670 |
15896 |
93.485 |
| 1000 |
4.419 |
6000 |
39.460 |
11000 |
51.564 |
15805 |
63.932 |
15855 |
73.122 |
15897 |
94.241 |
| 1500 |
12.178 |
6500 |
40.795 |
11500 |
52.663 |
15810 |
64.450 |
15860 |
74.746 |
15898 |
95.012 |
| 2000 |
25 |
7000 |
42.094 |
12000 |
53.748 |
15815 |
65.033 |
15865 |
76.560 |
15899 |
95.800 |
| 2500 |
28.040 |
7500 |
43.360 |
12500 |
54.820 |
15820 |
65.688 |
15870 |
78.581 |
15900 |
96.605 |
| 3000 |
30.112 |
8000 |
44.599 |
13000 |
55.878 |
15825 |
66.423 |
15875 |
80.838 |
15901 |
97.427 |
| 3500 |
31.929 |
8500 |
45.811 |
13500 |
56.925 |
15830 |
67.249 |
15880 |
83.353 |
15902 |
98.267 |
| 4000 |
33.598 |
9000 |
47.001 |
14000 |
57.960 |
15835 |
68.173 |
15885 |
86.155 |
15903 |
99.124 |
| 4500 |
35.164 |
9500 |
48.169 |
14500 |
58.985 |
15840 |
69.210 |
15890 |
89.275 |
15904 |
100 |
Hydro 按上式计算原始分值,并将得分向下取整。