第一届东南大学大学生程序设计竞赛（秋季）暨ICPC东南大学校队选拔赛 - 第二轮题解

秋季赛命题组

A. $2n$ 个数

$n=1$ 时暴力判断，否则对每个数字取对数后判断和即可(由于数据随机)。

B. 青春猪头少年不会梦到小雅米学姐

模拟退火入门题。

C. 由一道由一道水题引发的思考产生的另一道水题引发的思考产生的再一道水题

前两项之积即为答案。

D. 5G 时代

使用 Delaunay 三角剖分后在这上面做 MST 即可。

E. 化学题

生成函数入门题。

F. 小雅米的旅途

如果要买除2的票肯定越早越好，所以先枚举买几次除2的票，然后贪心即可。

G. Osu!Mania制霸计划

考虑用块状链表处理这个问题，将原序列$t$每$\sqrt{n}$分成一块。

对于每次$\{l_i,r_i,x_i\}$的平移，先将$[l_i,r_i]$这一段从块状链表上切出来，这个能在$O(\sqrt{n})$内做到。

然后判断是否能进行平移，即判断是否有元素在$[l_i+x_i,r_i+x_i]$，这也能在$O(\sqrt{n})$内做到。

如果不能平移，那么就将切出的一段接回去；如果可以，那么就将切出的序列内所有元素整体加上$x_i$，这可以用懒标记做到（多维护一个区间的整体增加量），然后再接到对应位置。

有可能在平移了很多次后，整体的块数比较大、使得扫一遍的效率降低。于是可以每$\sqrt{n}$次平移后进行贪心地合并，使得每一块的大小比较接近$sqrt{n}$。

这题的数据生成的比较简单，好像每块比较大就行了，不合并也不会超时。

H. 小雅米的舒服了

树链剖分+线段树即可，二分+树上差分也可以。

I. 小雅米和小妖女的游戏

对于每个质因数我们求出它的sg函数，然后求所有质因数的Nim和即可。

下面考虑如何求个某个质因数的sg函数，我们可以用状态压缩的方法其中第 $i$ 位代表是否存在 $p^i$ 这个因数，暴力转移即可。

J. 等比数列

我们可以枚举每个公比，然后算一下在这个公比下有多少满足条件的等比数列。