2026 河南省赛游记

· · 生活·游记

初中打星队。

队友：zhangruicong、qazxcvbnmko。

队名：【数据删除】

我因为不是队长，所以我在队里属于既不充分也不必要条件：我负责倒开和写游记。

坐在旁边的是 丘丘人 一队，认识其中一位。

热身赛不说了。

正赛，前一个小时过掉了 B,E,F,K。

我看了 A,C,D,G。

A:

对于一个序列 a，q 次询问 [l,r],k，求出 \sum_{l\le i\le r} \lfloor \frac{a_i}{k} \rfloor。

这道题貌似在哪里见过，记得是分块，不过我觉得我是写不出来，于是没写。

C:

一种编出来的约分方法和真的约分方法在分母小于 n 的真分数约分结果相同的有多少个。

n\le 10^5

直觉上可以写一个 n^2\log n 的暴力，又注意到这题答案可以在前一个答案上累加，所以不超过 60 秒就可以打完表，所以就将正确的小常数暴力写出来了，准备打表。

结果呢，我看到队友带的板子目录上有：O(nlogn)-O(1) gcd 求法，于是研究这个求法去了。

无果，也就把打表这事忘了（主要原因是中间去吃饭了）。

赛后，丘丘人 过了 C，问做法，结果他们拿 n^2\log n 飞过去的，跑不满，那一只 \log 可以当常数的。

我：#￥%……%

痛失一道题。

D:

很复杂的图论题，大概是对于一张图，找到改变一条路的方法，使得图中的最长路最长。多测。

n m\le10^6

这题乍一看人畜无害，我想了 10 分钟就想出来了 n m 做法，大概就是多遍拓扑排序。

我的方法：先进行一次拓扑排序找到环，再进行一次拓扑排序找到环，然后进行一次拓扑排序找到每个环可以到达的最远距离，接着进行拓扑排序将最远点回归到负环，并且从目标点拓扑找到连通块，再对每个点加入方向改变可达的最长路（三遍拓扑排序），最后枚举目标点联动块之间所有可能性所最长的路径。与此同时还有23个数组的清空赋值，我还 #define int long long 了，同时加上加入点和建图。

问：以上大概多少倍常数？

答：大约 80 倍。

我已经死了，鉴于不是少爷机，还有测评卡顿，我就不打算写了（已经写 189 行，5 个拓扑排序了），可惜这个算法的时间复杂度是 O(Tnm) 的了。也不知道对不对。

G:

有一个球心于原点半径为 r_1 的球，一球心于 (x,y,z) 半径为 r_2 的球，求它们相交的体积。

一切数小于 10^6 有 SPJ。

本来打算算两次积分，不过看旁边俩丘没做出来，遂放弃。

此时，队友找我调 L，题中：将答案四舍五入至整数。有两个点：

  1. 乘 1.0 这个是我干的，结果我少乘了一个，直接 WA 队友虚空调试半天。
  2. 最后在四舍五入，这个我们也虚空调试了半天，还好不是我犯得。

最后过 L 了，白吃131分钟罚时。

另一个队友调试 J 调了半天，未果。

最后是 Cu 了，名次 80 左右，不过原因都在我身上：

如果我没有忘乘 1.0 我们队是有 Ag 中间的排名的。

如果我把 C 暴力交上去，那是有 Ag 前几的。

如果以上都成立那么就有 Au 后几名的。

就这样吧，还我 Au。