第二届东南大学大学生程序设计竞赛（秋季） - 题解 - 帖子

第二届东南大学大学生程序设计竞赛（秋季）命题组

A. 姬哥的约会计划

令 $f_i,g_i,h_i$ 分别表示第 $i$ 天与一号约会、二号约会或者不约会时，前 $i$ 天最多能约会多少次,那么：

$f_i = max(f_{i-1},h_{i-1})$

$g_i = max(g_{i-1},h_{i-1})$

$h_i = max(f_{i-1},g_{i-1},h_{i-1})$

B. 姬哥的数学课

将序列 $a_n,b_n$ 分别分解到质因数上，然后若 $A$ 的每一个质因数的幂次的数列都大于等于 $B$ 的就说明 $A$ 是 $B$ 的倍数。

分解质因数是只需要分解到根号即可，因为每一个数至多含有一个大于根号的质因数。

C. Emmm: An Easy Programming Warm-up

由于本质不同的询问只有 $n$ 种，预处理出前缀和后 $O(n^2)$ 预处理出参数为 $i$ 的询问的答案，即可对每次询问 $O(1)$ 处理，复杂度 $O(n^2+m)$ 。

D. Mental Out

线段树维护区间乘积。

由于 $f(x)\leq \dfrac{x}{2},f(1)=1$ ，每个数被修改的次数不大于 $\log_2{a_i}$ ，因此修改时不需要处理全为 $1$ 的区间，对于大于 $1$ 的数暴力修改即可。

若使用根号级别复杂度的算法求 $f(x)$ 可能导致超时。

E. 梅园理发店

本题可以看成有两条流水线：剪头线和理头线。显然答案不小于两条线单独取最小值的较大值，也即 $max(\sum m + 2, 2*n)$ 。

下面给出一种可以取到该值的构造方案：

按m从小到大排序，所有人先在洗头线第一次洗头，剪头线按洗头线的顺序剪头，容易证明，剪头线会一直工作直到所有人都剪完。对于所有人的第二次洗头，排在第一次洗头人的后面，能洗就洗，第二次洗头的顺序和第一次洗头的顺序相同。构造完毕。

当然本题比较简单，只需输出最小花费时间，也即 $max(\sum m + 2, 2*n)$ ，时间复杂度 $O(n)$ 。

F. 阿畅和神符

显然，这道题需要分别计数的是每个结点的赏金神符会被取走的道路的条数。而对于任一道路和其上的某一结点 $i$ ，该结点的赏金神符被取走的条件是该条道路上没有神符价值比 $P_i$ 更大。

解法一：按照神符价值从大到小考虑每个结点。当一个结点被考虑过后，将该结点从树上删除，由此会将一棵树变成一座森林。对于正在计数的某个结点 $i$ ，只需要考虑森林中其所在的这一棵树，因为只有完全在这棵树内部且经过 $i$ 的道路会取走 $i$ 上的神符。那么，只要我们以 $i$ 作为树根，计算得到以 $i$ 的所有孩子为根的子树的大小，就可以得到道路的总数。为了计算每棵子树的大小，我们考虑该树在原来的树中的形状，则现在的以孩子为根的子树分为在原来树中也是以 $i$ 的孩子为根的子树和本来是以 $i$ 为根的子树的外部区域的一棵子树（则该子树的根是原来树中 $i$ 的父亲）。对于任一结点 $j$ ，我们维护原来树中以 $j$ 为根的子树中所有结点在现在的森林中仍然和 $j$ 连通在一棵树中的结点个数 $S_i$ ，或者维护被剥离出去成为新树的总的结点个数（两者之和就是以 $j$ 为根的子树的大小），那么对于在原来树中就是以 $i$ 的孩子为根的子树，现在的子树大小就是 $S_{son_i}$ ，另一方面，对于在外部的子树，我们可以求得现在的 $i$ 所在树在原来树中对应的根 $k$ （即 $k$ 是 $i$ 现在所在树中在原来的树里深度最小的那个结点），则 $S_k-S_i$ 即为所求。

要维护 $S$ 数组，我们只需在删除结点 $i$ 时，对于 $i$ 的所有祖先结点 $fa$ , 从 $S_{fa}$ 中减去 $S_i$ 就可以，直到某个祖先结点已经被删除为止（也就是做到结点 $k$ ）。这可以通过树链剖分实现。另一方面，求取 $k$ 的操作可以通过树的dfs序加线段树实现，维护每个结点的所有已被删除祖先中最近的那一个。

总时间复杂度： $O(nlog^2 n)$

解法二：按照神符价值从小到大考虑。对于正在被考虑的结点 $i$ ，有且只有经过它且只经过已考虑结点的道路会选择其上的神符。所以我们立刻想到通过并查集维护结点的连接关系。我们按照价值从小到大插入结点。当一个结点 $i$ 被插入时，我们枚举它所有相邻结点是否已被插入，是的话就将其所在连通块纳入考虑范围，按照前述方法可以计算出道路条数。之后，将所有连通块与 $i$ 连接成为新连通块。注意合并操作时同时维护连通块的大小。

总时间复杂度： $O(nα(n))$

G. Hmmm: A Tricky Counting Challenge

以下数列 $\{a_i\}$ 指的均是原数列的任意一种排列。设

b_1=a_1,b_n=a_n,b_i = \max(\min(\max_{j=1}^{i-1} a_j, \max_{j=i+1}^n a_j), a_i) (2 \le i \le n)

由 $\{a_i\}$ 得到 $\{b_i\}$ 的过程称为一次变换。对于任意一个数列 $a_i$ ，对 $(a_i,b_i)$ 进行排序使 $b_i$ 单调不升并且 $b_i$ 相同时 $a_i$ 单调不降，结果记做 $(a'_i,b'_i)$ ，则 $b'_i$ 仍是 $a'_i$ 经过变换后的序列。利用动态规划统计所有可能的 $\{b'_i\}$ 和有多少种取值即可。即用 $a_i$ 中的元素去填 $b_i$ ，满足填出的 $b_i$ 单调不降，并且第 $i$ 大的元素至少要在第 $i$ 个位置之后才可以出现。设 $f[t][i][j]$ 表示考虑了 $\{a_i\}$ 中前 $t$ 大的元素，每个元素可以不使用或使用一次或多次，填了 $b[1..i]$ ，这 $i$ 个数的和是 $j$ 时是否有可行的方案，转移类似完全背包，用 std::bitset 优化即可。

H. 姬哥带土豪

不难看出按照题设条件，姬哥用到的背包数量一定不会超过 $n$ ，因此不妨设有 $n$ 个背包，第 $i$ 个背包的剩余容量记为 $x_i$ 。初始时 $x_i=C(1\leq i\leq n)$ ，可以用线段树来维护 $x_i$ 的区间最大值。在线段树递归更新时，若当前节点的左子节点最大值大于等于当前钻石体积，则代表左半区间中必有背包的容量足够放下当前的钻石，此时向左递归；否则向右递归。最终答案即为 $\Sigma_{i=1}^n(x_i<C)$ ，算法复杂度为 $O(nlogn)$ 。

I. 姬哥与屋子

以最左边的点为中心对剩下 $2n-1$ 个点进行极角排序，选取最左边的点和排序后第 $n$ 个点即可。

J. 丢人的题目

本题实际上是求模 $p$ 意义下的二次剩余最多有多少个。（若 $x^2\equiv y(mod\ p)$ ，称 $x$ 为模 $p$ 意义下 $y$ 的二次剩余）

对于 $p$ 是一个奇素数的情形，若非零值 $x$ 是 $y$ 的二次剩余，那么 $p-x$ 也是。而 $1\sim p-1$ 中较小一半的数字都是不同数字的二次剩余（否则，存在 $x,y$ 使得 $x^2-y^2\equiv(x+y)(x-y)\equiv 0(mod\ p)$ ，且 $x-y\not\equiv 0(mod\ p)$ ，可见 $x+y\equiv 0(mod\ p)$ ；但注意到 $0<x+y<2\frac p2=p$ ，所以 $x+y\not\equiv 0(mod\ p)$ ，矛盾）。由此可见，这时 $0$ 有一个二次剩余，近半数字有 $2$ 个二次剩余，而余下数字没有二次剩余。

而对于一个无平方因子的奇合数，求其每个数字的二次剩余前可分别求模其每个素因子意义下的所有二次剩余(二次剩余的数目集合为 $\{0,1,2\}$ )，将模其每个素因子意义下的二次剩余均挑出一个来，再用中国剩余定理组合即可得到模这个奇合数意义下的一个二次剩余；而且由中国剩余定理可知每次挑选有一项不同则最后二次剩余必然不同。所以答案最多是 $2^n$ ( $n$ 为素因子个数)。注意到 $1$ 的二次剩余恰有 $2^n$ 个，所以它即为答案。

综上，本题答案即 $2^n (mod\ 998244353)$ ，用快速幂求解即可。(本题中复杂的 $p$ 构造描述仅为防止通过最直接的打表得到正确结论)

K. 背包问题·改

首先我们将物品按照自己的归属排个序并且把必选物品排在这一类的第一个。

设 $f_{i,j},g_{i,j}$ 分别表示考虑了前 $i$ 个物品，已经选择的物品体积是 $j$ 时第 $i$ 个物品所在类的必选物品已经放入了/没有放入时的最大价值,然后状态定义转移即可，转移方程略。

L. 函数重载

本题可先用树的结构存储 DeclareType 的定义的情况；接下来采用暴力预处理出所有情况的答案或者预处理欧拉环游序的方法实现对 A 类型是否是 B 类型的基类的常数时间判断；随后按多关键字具体度对所有 DeclareFunc 进行排序；对于每个询问直接输出具体度最高的定义即可，最终时间复杂度是平方级别的。

M. 姬哥与卖菜

可以发现，按 $a_i+b_i$ 为关键字对所有同学排序，即为最优解。排序后逐个统计破防值即可。

证明如下：

考虑队伍中 $a_M+b_M$ 最大的同学 $M$ ，下证其必然排于队尾。

假设其不排于队尾，则有同学 $N$ 排于同学 $M$ 后，且 $a_M+b_M\geq a_N+b_N$ 。考虑交换同学 $N$ 与同学 $M$ ，则其他同学的破防值显然不会改变。而同学 $M$ 的破防值由 $\Sigma_{i=1}^{M-1}a_i - b_M$ 变为 $a_N+\Sigma_{i=1}^{M-1}a_i - b_M$ ，同学 $N$ 的破防值由 $a_M + \Sigma_{i=1}^{M-1}a_i -b_N$ 变为 $\Sigma_{i=1}^{M-1}a_i - b_N$ 。

由 $a_M+b_M\geq a_N+b_N$ 可得不等关系：

\begin{align} a_N+\Sigma_{i=1}^{M-1}a_i - b_M &\leq a_M + \Sigma_{i=1}^{M-1}a_i -b_N\\ \Sigma_{i=1}^{M-1}a_i - b_M &\leq a_N+\Sigma_{i=1}^{M-1}a_i - b_M\\ \Sigma_{i=1}^{M-1}a_i - b_N &\leq a_M + \Sigma_{i=1}^{M-1}a_i -b_N \end{align}

故交换操作后，破防值的最大值减小或不变。可见无论其他同学如何排列，经过有限次交换操作后，最优解中同学 $M$ 必然在队尾。而队尾的同学 $M$ 实际上对其他同学的破防值无影响。由此通过归纳法可知，最优解为 $a_i+b_i$ 为关键字的升序排列。