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

秋季赛命题组

A. 数学题

第一问直接计算 $a+b$。

第二问答案为 $n-出现次数最多的数字的次数$。也可以贪心求解每次选出一个极长的上升子序列。

B. 小雅米的开门炮

1. 暴力枚举交换的字符，KMP 匹配
2. 建立 AC 自动机在自动机上匹配
3. 对 $26$ 个字符都建立 hash 串，每次枚举一个开头位置，并且找到 $26$ 个字符在该位置后第一次出现的位置，找到T串对应的字符，看是否 $hash$ 值一样，一样我们算成功配对一次。最后只能有一对字符配对成功，其他都应该完全相同。

C. ddc 的生日礼物

考虑 LIS 有一个基于贪心 $O(nlogn)$ 的做法，维护一个序列，每次加入一个数找到序列中刚好大于等于它的数，然后把它替换掉（如果没有则加入序列最后）。由于 LIS 长度最多为 $9$，且数字为 $0\sim 9$，考虑用一个二进制数来维护这个 LIS 的中间状态，然后用数位 DP 正常转移即可，最后只用比较一样二进制数中 $1$ 的个数是否为 $k$ 即可。

D. 摸鱼的刀客塔

我们可以转化一下要求的东西：

先不求最多的摸鱼次数，而是求在第 $i$ 次检查后最多能剩余 $rem_i$ 个未处理文件。

对于每次检查，有两种应对的策略：一种是被强迫办公；另一种是提前处理好文件，使得在该次检查时文件数不超过 $w$。

对于第一种策略，显然应该由 $rem_{i-1}$ 转移得来。

对于第二种策略，就是判断能否将超出的文件摊到之前的摸鱼时间。如果可以，那么这次检查后的剩余文件最大值为 $min(w,rem_i)$。

对两种策略做出来的答案取最大值即可。

而总的摸鱼次数就是 $n-(\sum a_i-rem_k)$。

E. 最大公约数

可以对时间分治或者先离线再维护一颗线段树时间复杂度 $O(nlogn)$。

F. 商人小雅米

如果来回一趟不能赚钱，直接结束程序。

否则每趟至少转 $1$ 块钱，那么至多 $10000$ 以后每次买最赚钱的 $50$ 个商品即可。

下面考虑前面几趟如何求解。用 $f[i][j]$ 表示已经放了 $i$ 个物品，当前花了 $j$ 元的最大收益。

计算总的 DP 后每一趟都是整个 DP 过程的一个子问题。

G. 小雅米的魔法阵

将魔法石按照变为 $0$ 的时间排序，用二维树状数组维护还剩余几块石头没有变成 $0$，他们初始能力和为多少。

H. 宝石挖掘

对每个点和每条边建一个点，最小割跑最大权闭合子图的模型即可。

I. 区间和

考虑固定左端点，对于数字 $x$ 前 $x$ 次出现的贡献都为 $x$ 后面的都为 $0$，这样对于每个右端点的询问计算一下前缀和即可。

移动左端点 $l$ 的时候,首先将 $a[l]$ 的贡献置为 $0$，并且将后面第 $a[l]$ 次出现的位置(如果存在的话）的贡献置为 $a[l]$。

J. $2n$ 个点

考虑一对交叉的线段交换他们会使答案变得更优，于是对两个点集跑最小完备匹配得到的答案一定不会相交。