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

春季赛命题组

A. Fluct Light Limit Exceeded?

由于本题只进行高精度的比较，所以我们可以考虑用字符串存储。在进行排序时，注意第一关键字是字符串，第二关键字是序号即可。

B. 时代变迁

这道题的背景是命题者曾经被人丢到过这道“网上没有题解”的题目，其中前一个点可以通过动态规划、构造、深度优先搜索辅助构造（虽然原命题人并没有在题解中说明第7、8个测试点可以不由“手玩”来完成，但事实上这两个点仍是被构造的）完成。

这道题的难点在于最后两个点，当然正如原题命题人在题解中描述的那样，现场写一个工业应用中的AI并不现实，所以这里主要是用一些小技巧来辅助暴力随机算法。而辅助的核心，就是原题命题人在题解中说的“手玩”的优势，也就是所谓的“前瞻性”。

一个很容易想到的思路是如果当前步骤下我们可以通过选择将建筑放在某些可以触发升级的点（当然这里选择尽可能联通更多的点，因为游戏结束时间远小于它给我们操作序列的长度），我们就优先选择那些点；接下来有些点能使得联通块更大，我们也将优先选择之。

但对于余下的情况，我们似乎很难有比较直观的做法。事实上，第 $10$ 个点比第 $9$ 个点更加简单，它的 STAR 操作很容易想到一个富有“前瞻性”的策略：后一定数量（通过调整参数来获得更优结果，此参数还应和当前空位数量有关）个将要被搭建的建筑如果不能使得当前变成大小为 $2$ 的联通块联通，我们就有一个较高的概率使用 STAR 来强行联通。而对于 BOMBER 操作，我们直接设定以当前空位数目小于特定值触发 BOMBER 删除特定数目个较小的点，通过调参并反复多次运行整个程序，我们就能完成该测试点的最高要求。

第 $9$ 个点由于没有 STAR 和 BOMBER，我们很难通过简单逻辑表述加入“前瞻性”。这时我们可以采用一个在程序设计竞赛中常用的操作（见NOI 2014团体对抗赛部分题解）即加入估价函数。我们可以通过快速计算完成某操作后按上述简单思路随机走到终局后的分值来评估当前是否应该进行该操作。当然我们会发现随机走终局的算法随机性太大，我们可以加入三点优化：

1. 如果当前有符合前述简单思路的点可以下，强制优先选择这些点而不考虑估价函数。

2. 将估价函数运行 $10\sim 100$ 遍有得到的最值作为我们最终的参考值。

3. 反复多次运行整个程序。

这样我们就可以完成第 $9$ 个点。

C. 抢后宫

这是一道简单的博弈论题。

对于日期直接的关系是一棵二叉树，然后用记忆化搜索解决，具体可以使用递推或者用sg函数。

另注： 为了防止爆栈，我们可以先分成几棵子树分别进行处理。

D：逆序对

记 $f_{i,j}$ 为考虑了 $i$ 个数字现在有 $j$个逆序对的结果。我们枚举最后一个数字放在倒数第几位，即它产生了几个逆序对，暴力转移即可。

E. 简单的减法

答案等于一部分的数和减去另一部分，实验发现两部分都不能为空，先把所有数字绝对值相加，如果全是正数或者全是负数，还要减去绝对值最小的数的两倍。

另外对于 $n=1$ 的特殊情况我们需要进行特判。

F. 飞扬的小鸟

本题题意为对给定一个长度为 $n+1$ 的数列 $a_i$，数列的权重为 $\sum_{i=1}^n{|a_{i+1}-a_i|}$，其中我们可以任意次数修改任意一个数，把 $a_i$ 改为 $a_i'$ 代价为 $|a_i-a_i'|$，求修改后的权重与修改的代价和最小值。

我们可以考虑进行贪心。对于相邻的三个数 $a_i,a_{i+1},a_{i+2}$，如果 $a_{i+1}>\max(a_i,a_{i+2})$，则把 $a_{i+1}$ 修改为 $\max(a_i,a_{i+2})$；如果 $a_{i+1}<\min(a_i,a_{i+2})$，则把 $a_{i+1}$ 修改为 $\min(a_i,a_{i+2})$。这样可以使权值尽可能小。最后求修改过的$\sum_{i=1}^n{|a_{i+1}-a_i|}$ 即可。

G. 最大子区间

对于本题，我们可以枚举最小值，在最小值确定的情况下区间显然越长越好，对此我们有如下解法：

1. 单调栈求出每个最小值的最长区间，使用 Sparse Table 维护区间最大值。
2. 从小到大添加数字，并查集合并区间，合并时维护区间最大值和区间和。
3. 建立笛卡尔树，按上述方法合并区间即可。

H. 女仆修行

由于本题每次询问的起点固定，所以可以考虑对右端点进行二分。二分时需要判断当前 $mid$ 是否合法，对于力量变化幅度的限制，可以考虑建一棵区间最大和一棵区间最小线段树，每次将 $[q_i,mid]$ 的最大值减最小值得到变化幅度；对于帮助次数的限制，由于右端越靠后，$[q_i,mid]$ 中受到的帮助次数越多，所以判断对于力量变化幅度二分得到的结果是否满足帮助次数即可。总复杂度为 $O(N\cdot (logN)^2)$。

I. 世界聚焦于你

本题要求对于给定 $n$，求最小的 $m$，使得 $n\ |\ \underbrace{7777\cdots7777}_{m个7}$。

由

则

即

即

即

由欧拉定理: $a^{\phi(n)}\ ≡ \ 1 \ (mod\ n)$

有如下推论：使得 $a^m \ ≡ \ 1 \ (mod\ n)$ 最小的 $m$ 为 $\phi(n)$ 的因数（证明略）

所以我们可以在 $\sqrt{\phi(\frac{9n}{gcd(7,n)})}$ 的复杂度下枚举 $\phi(\frac{9n}{gcd(7,n)})$ 的所有因数，用快速幂来判断。由于中间值可能大于 long long，我们需要用快速乘或者 __int128。

本题时间复杂度 $O(\sqrt{\phi(\frac{9n}{gcd(7,n)})} \ \times (\log_2(\ \phi(\frac{9n}{gcd(7,n)})\ )\ )^2\ )$。

J. 无限传送

首先非常抱歉本题从命题人的解题思路上就出现了问题。

本题最初的灵感来源于 UOJ NOI Round，该题大体是从树根向下走。某命题人在秋季赛时试图出一道从树枝向上走发现不会，遂改成送分（没有成功）状态压缩动态规划题。

然后另一命题人改变了部分条件，在今年构造出来了一个结论，然而是错误的：

首先每一个深度处的分枝数是单调不递减的，必然存在某一深度为分界，深度小于这个值的部分，可以在树的高度的时间内挖完，比这个深度深的位置可以保证每一只蚂蚁都有事做。然后就用分界上面的深度加上下面的总路径长度除以 $m$ 就是所需总时间。

在本次比赛结束后，选手殷开颜指出了上文结论的如下一个问题：

两部分分别的最大时间是没有问题的，但是如果部分蚂蚁在做剖开之后上面的树的工作，部分蚂蚁同时在下面部分的树上工作，上面的证明并不能说明哪种更优。

并且，他给出了如下结论：

假设树的深度为 $h$,路径总长度为 $s$。结果应该为 $\max(h,\frac sm)$。

我们可以举一些例子，发现符合上述结论。我们可以按如下方式构造解：

我们首先归一化问题：

如果树的树根有多于 $m$ 个孩子，显然结果是 $\frac sm$ 且这个值大于 $h$。

如果树的叶子小于 $m$ 个那么显然结果是h且大于 $\frac sm$。

剩下的情况都是树根孩子数小于 $m$ 树叶数大于 $m$ 的情况，如果 $h$ 大于 $\frac sm$ 则可以加叶子使 $s$ 增大，如果 $h$ 小于 $\frac sm$ 则必定存在一个深度以上的树满足 $h$ 和 $\frac sm$相等，下方直接满足使所有蚂蚁时刻有工作做即可。

下面问题简化为求一种构造方案，使得满足 $h$ 等于 $\frac sm$ 的树可以每时每刻蚂蚁都不闲着。就可以证明结论正确。

我们可以逆向构造，从树根向下每一个叶节点分配它的孩子数减 $1$ 个蚂蚁。这些蚂蚁满足在结束时刻到达这个节点，逆过来就是由这个节点向下走向叶子。直到所有蚁人在某一层不够用了。这个时候蚂蚁开始向下挖，这个过程是原过程的逆过程，因为前面的蚂蚁要负责比自己数目多的工作路径所以行走较慢，后面的蚂蚁一旦赶上前面的蚂蚁就开始分担他们的工作，与他们齐头并进则最后同时达到叶子没有一个蚂蚁闲着。

这个构造过程有一些抽象比较难理解，如有疑问可咨询该选手。

K. 你稳了

本题用到的结论是：如果能够确定平均数的值，那么使得方差最小的方案一定是，在满足单调不递减的条件下，使得左边的数尽量大，右边的数尽量少，中间不确定的数等于平均数。

那么只需要枚举平均数的区间就可以了。预处理出左右两边的数字按规则填好后对应的前后缀和，则可以求出平均数，如果平均数恰好处于这个区间，就得到解了。注意只有一个数确定或者没有数确定情况的需要特判。

L. 我们仍未知道那天所看见的字符串的长度

本题灵感来源为 2009 年 NOI 国家集训队论文《后缀数组——处理字符串的有力工具》中的例题。

把所有字符串拼接起来，中间用不同的没出现过的字符分隔开，然后对其计算一下后缀数组及其高度数组（LCP）。

接下来进行二分答案，每次对高度大于二分值的连续的一段上进行贪心，看是否存在每个字符串上都已经不重叠出现了至少 $k$ 次的子串。

由于每个后缀在一次二分中最多出现一次，所以复杂度 $O(nlogn)$。

M. START DASH！

首先非常抱歉数据中出现了一个题目描述中明确不存在的情况。

这是一道计算几何题。我们先判断两点是否穿过三角形，如果穿过则找三角形上任意一点，看两个点到该点连线是否穿过三角形，如果没有则更新最小值，再找任意两点，看两个点到这对应的点是否穿过三角形，不穿过则更新最小值即可。