#P15481. [2026四川省队集训]星图 (提交答案题)

    ID: 14696 提交答案题 尝试: 1 已通过: 1 难度: 8 上传者: 标签>图论组合数学CF2400构造数学算法基础模拟

[2026四川省队集训]星图 (提交答案题)

星图

题目背景

可怜的 lzh\text{lzh} 宝宝被联合省选2026中星图这道题创飞了,事后补题的时候写的四元环算法。

他目前写的是如果有四元环就消四元环,否则再去消长度为 33 的链,优化还没来得及加。

他突然比较好奇这个做法的操作次数真的是 O(n2)O(n^2) 的吗。

题目描述

这是一道提交答案题,没有输入,只需要输出。

构造一个无向简单图,要求点数不超过 10001000,且不存在由四个不同顶点构成的四元环。顶点从 11 到 nn 编号。图中不能有自环或重边,同一条边换序后仍是同一条边。

输出格式

将答案写入 starmap.out,放在一个 ZIP 压缩包的根目录后提交。

第一行两个整数 n,mn, m,分别表示点数和边数。

接下来 mm 行每行两个整数 u,vu, v,表示一条连接 u,vu, v 的无向边。

评分

如果输出图不合法,获得 00 分。

否则,获得的分数是 f(m)f(m),其中函数 f(x)f(x) 为一个分段函数,前期为指数 >1> 1 的幂函数,中期为指数 <1< 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}$$

下方给一些具体的数值表,保留到三位小数。

xx f(x)f(x) xx f(x)f(x) xx f(x)f(x) xx f(x)f(x) xx f(x)f(x) xx f(x)f(x)
00 50005000 36.65336.653 1000010000 49.31849.318 1500015000 6060 1584515845 70.37170.371 1589515895 92.74692.746
500500 0.7810.781 55005500 38.08238.082 1050010500 50.44950.449 1580015800 63.47163.471 1585015850 71.67071.670 1589615896 93.48593.485
10001000 4.4194.419 60006000 39.46039.460 1100011000 51.56451.564 1580515805 63.93263.932 1585515855 73.12273.122 1589715897 94.24194.241
15001500 12.17812.178 65006500 40.79540.795 1150011500 52.66352.663 1581015810 64.45064.450 1586015860 74.74674.746 1589815898 95.01295.012
20002000 2525 70007000 42.09442.094 1200012000 53.74853.748 1581515815 65.03365.033 1586515865 76.56076.560 1589915899 95.80095.800
25002500 28.04028.040 75007500 43.36043.360 1250012500 54.82054.820 1582015820 65.68865.688 1587015870 78.58178.581 1590015900 96.60596.605
30003000 30.11230.112 80008000 44.59944.599 1300013000 55.87855.878 1582515825 66.42366.423 1587515875 80.83880.838 1590115901 97.42797.427
35003500 31.92931.929 85008500 45.81145.811 1350013500 56.92556.925 1583015830 67.24967.249 1588015880 83.35383.353 1590215902 98.26798.267
40004000 33.59833.598 90009000 47.00147.001 1400014000 57.96057.960 1583515835 68.17368.173 1588515885 86.15586.155 1590315903 99.12499.124
45004500 35.16435.164 95009500 48.16948.169 1450014500 58.98558.985 1584015840 69.21069.210 1589015890 89.27589.275 1590415904 100100

Hydro 按上式计算原始分值,并将得分向下取整。