2018年东南大学ACM/ICPC集训队选拔 - 题解

第一轮

A. 数学建模

我们假想一个虚拟地区 $0$，将建设核电站视为与 $0$ 号地区直接相连，这样一来所有地区通电就是它们都与 $0$ 号地区有一条路径相连。

所有地区都与 $0$ 号地区有一条路径相连，则任何两个地区(包括 $0$ 号地区)都相连(通过 $0$ 号地区为中转形成一条路径)。

而任何两个地区(包括 $0$ 号地区)都相连，则显然所有地区都与 $0$ 号地区有一条路径相连。

所以两个命题是等价的，而任何两个地区(包括 $0$ 号地区)都相连下的最小代价无疑就是求这个图的最小生成树。

本题中使用 Kruskal 算法的时间复杂度为 $\Theta(Tn^2\log n)$，而使用 Prim 算法的时间复杂度为 $\Theta(Tn^2)$，都可以通过。

B. 三次方求和

由费马大定理知，$n=2$ 时题目显然没有解，不过这种情况被排除了。

接下来在 $n=3$ 时，我们可以暴力找到以下解 $3^3+4^3+5^3=6^3$。

而在 $n=4$ 时，样例给出了以下解 $2^3+3^3+8^3+13^3=14^3$。

接下来对于 $n=i(i\geq 5)$ 的情况，我们由 $n=i-2$ 的情况推出一个解：

设 $n=i-2$ 的情况给出的解为 $a_1^3+a_2^3+\ldots+a_{i-2}^3=ans_{i-2}^3$。

将解同乘 $6^3$ 得 $(6a_1)^3+(6a_2)^3+\ldots+(6a_{i-2})^3=(6ans_{i-2})^3\ \cdots\cdots①$

将 $3^3+4^3+5^3=6^3$ 同乘 $a_{i-2}^3$ 得 $(3a_{i-2})^3+(4a_{i-2})^3+(5a_{i-2})^3=(6a_{i-2})^3\ \cdots\cdots②$

将 $②$ 式代入 $①$ 式得 $(6a_1)^3+(6a_2)^3+\ldots+(6a_{i-3})^3+(3a_{i-2})^3+(4a_{i-2})^3+(5a_{i-2})^3=(6ans_{i-2})^3$

可以发现，最后一个式子恰为 $n=i$ 时的解。

C. 排列组合

本题可转换成如下题目：

给定一个 $n$ 个点的无向图，$m$ 次加边或者删边操作。

在每次操作后统计有多少个匹配包含 $k = 1,\ 2,\ \ldots,\ \frac n2$ 条边。

设 $f[i][S]$ 表示前 $i$ 次操作之后，$S$ 集合的点已经匹配的方案数。

对于加边操作，显然 $f[i][S] = f[i − 1][S] + f[i − 1][S − u − v]$。

$i$ 这一维可以省略，从大到小遍历 $S$，$f[S] += f[S − u − v]$。 对于删边操作，注意到加边操作的顺序不影响结果，可以假设第 $i − 1$ 次操作是加入要删除的边。

将加边操作的更新倒过来，得到：从小到大遍历 $S$，$f[S]− = f[S − u − v]$。

时间复杂度 $\Theta(Tm2^n)$。

来源：HDU 2018 Multi-University Training Contest 3 - Problem C

D. 游戏

首先，我们可以针对每个棋子独立的考虑问题，否则，考虑一个能胜利的方案中在女生的步骤中去掉对除最后被移出的那个棋子外所有棋子的操作(对于有棋子“挡路”的情况，可以视作两个棋子标号互换)，仍然会是一个能胜利的方案。

对于一个棋子已经在靠近边沿的格子上且对应边沿没有被封住的情况，如果下一步是女生走则 cqh 必败，反之 cqh 下一步必须封住该边沿。

对于一般情况，女生每走一步，cqh 只需要把对应的边沿给封住即可，但是对于走到四角的情况，cqh 需要保证 $2$ 个边沿都被封住，额外的步数显然只能在女生将她的棋子移到靠近边沿的格子前完成。

所以，对于一个棋子距离边沿小于 $5$ 步(走到四周所需要的额外 $4$ 步和由于女生先走造成的额外 $1$ 步)的情况，女生就可以通过移出这个棋子来取胜，反之不能。

写个程序判断每个棋子的情况即可，时间复杂度 $\Theta(Tk)$。

E. 作业指导

由于数据量极其的小，我们可以直接暴力模拟在 $\Theta(Tn^2)$ , 由于实际上测试数据的 $n$ 值是随机生成的，常数上还要除 $6$ 倍，所以本题这样可过。

事实上，对于这样经典的约瑟夫环问题，我们可以进行倒推，记 $F_{n,m}$ 为问题在 $n$ 人，每 $m$ 个人会离开一人的前提下的答案减一。可知：

所以我们也可以在 $\Theta(Tn)$ 的时间内求出答案。

F. 概率作业

先考虑没有障碍物的情况，由于是无限长的时间，那么最开始的时间 RandomWalker 的走法是不会影响最终答案的，所以经过比较短的时间后，RandomWalker 可以出现在图上的任意地方，在这个时候到下一秒，RandomWalker 在不同格子能操作的数量是一个类似下面这个矩阵，而对于一个格子，能到这个格子的情况也是下面这个矩阵。

34443
45554
45554
45554
34443

也就是说，到下一秒的总情况数量就是上面这个矩阵的sum，合法的区域就是右下角这块的sum，在没有障碍物的情况下，概率就是这样了。

现在考虑上障碍物，一个格子放上障碍物，如果他旁边的格子没有障碍物，那么总情况就减少从其他格子到这个格子的情况，和从这个格子到其他格子的情况，如果旁边有障碍物，则不会有从其他格子到这个格子的情况，所以只要减去本身就可以了（事实上，没有减去这个 $1$ 是因为在计算旁边的障碍物时已经减去了）。也就是分母减去($self+tot$)，$tot$ 为旁边的障碍数。

最后算一下 $gcd$ 就可以了。

来源：2017ACM/ICPC亚洲区沈阳站 M题

G. 老师的考验

我们最终可以计算

其中

计算它需要的时间复杂度为 $O(\sqrt n\log n)$。

推到过程如下：

对于 $g(m)$ 用容斥原理计算：

因此我们有

其中最后一个求和的结果恰好为 $\phi(x)$。

来源：GDSOI 2016 T1

H. 巴啦啦能量

显然一个图是二分图的充要条件是不存在长度为奇数的环。 对于图中可能出现的每条边，记录它出现的某些区间，然后考虑分治。 Solve(l,r,U)表示处理[l,r][l,r]的答案，其中U表示出现区间在[l,r]内的边的集合。 用LCT维护图的连通，对于出现区间刚好等于[l,r]的边(x,y)，判断图中x与y是否连通。如果连通，再求出x到y的路径长度，如果是偶数，那么加入边(x,y)后会出现长度为奇数的环，[l,r]的答案全是NO。如果不连通，将x与y连上并分治求[l,mid],[mid+1,r] 。回溯时删除。

来源：http://codeforces.com/contest/813/problem/F

I. 斐丢波丢那陈契

Let’s first solve a simpler problem – when the sequence 𝑐 is cyclic, i. e. when 𝑐_𝑖 = 𝑐_{𝑖 𝑚𝑜𝑑 𝑁}, for 𝑖 ≥ 0.

This simpler version is similar to Fibonacci sequence. Actually, for 𝑁 = 1 and 𝑐₀ = 1, it is the Fibonacci sequence. To find the 𝐾^𝑡ℎ number of these kind of recursive sequences fast we should first write them in their matrix form. Matrix form of this sequence is:

Expanding this, we can see that

How do we calculate this efficiently? 

For relatively small 𝐾, and we will take 𝐾 < 𝑁 for this case, we can do this just by multiplying all the matrices.

For large 𝐾 (𝐾 ≥ 𝑁), we will take advantage of the fact that 𝑐 is cyclic. Since 𝑐 is cyclic with cycle of length 𝑁, we know that 𝐶_𝑁−1𝐶_𝑁−2 … 𝐶₁𝐶₀ =

𝐶𝑖𝑁+(𝑁−1)𝐶𝑖𝑁+(𝑁−2) … 𝐶𝑖𝑁+1𝐶𝑖𝑁 , for 𝑖 ≥ 0

(note that $C_0= \left( \begin{array}{ccc} c_{0} & c_{N-1}\\ 1 & 0 \end{array} \right)$)

Let’s define this product of matrices as 𝑆 = 𝐶_𝑁−1𝐶_𝑁−2 … 𝐶₁𝐶₀.

Now, we can write a formula for 𝐹_𝐾 that can be calculated quickly: (𝐹𝐾,𝐹𝐾-1)^T = 𝐶𝑎−1𝐶𝑎−2 … 𝐶1𝐶0𝑆𝑏𝐶𝑁−1𝐶𝑁−2 … 𝐶2𝐶1 (𝐹1,𝐹0)^T, where 𝑏 = (𝐾 −𝑁) 𝑑𝑖𝑣 𝑁 and 𝑎 = 𝐾 𝑚𝑜𝑑 𝑁.

We can calculate 𝑆^𝑏 in 𝑂(𝑙𝑜𝑔𝑏) steps using exponentiaton by squaring, and then we can just multiply everything in the expression to get 𝐹_𝐾 quickly.

Let’s get back to the full problem, when 𝑐 is almost cyclic. In this case, we cannot just use 𝑆^𝑏 in the formula above, because some matrices in

𝑆^𝑏 may not respect the cyclic property. Instead of 𝑆^𝑏, we will have something like

𝑆 ∙ 𝑆 ∙ … ∙ 𝑆 ∙ 𝐸₁ ∙ 𝑆 ∙ 𝑆 ∙ … ∙ 𝑆 ∙ 𝐸₂ ∙ … = 𝑆^𝑡1 ∙ 𝐸₁ ∙ 𝑆^𝑡2 ∙ 𝐸₂ ∙ 𝑆^𝑡3 ∙ … where 𝐸_i denotes the product of matrices of the cycle, with some matrices being different than the matrices of the original cycle. Also, 𝑖 ≤ 2𝑀 since each of the 𝑀 values of 𝑐 different than values of the original cycle appears in exactly two matrices, so at most 2𝑀 of cycles are affected. 

We can still calculate each 𝑆^𝑡𝑖 quickly, using exponentiation by squaring. Since there are at most 2𝑀 of those, total complexity of this would be

𝑂(𝑀𝑙𝑜𝑔𝐾).

Now we only need to calculate each 𝐸_𝑖. Naive way would be to just multiply all matrices of 𝐸_𝑖. Since the number of matrices is 𝑁, this would be 𝑂(𝑁𝑀) worst case, which is too slow. To quickly calculate 𝐸_𝑖 , we will initially create a segment tree of matrices, with matrices of original cycle in the leaves. Internal nodes of the tree will represent the product of their children. This means that the root will represent the product of all matrices in the cycle. To calculate 𝐸_𝑖, we will just update our segment tree with those values that are different than the original values of the cycle. We will do this by updating corresponding leaves of the tree, moving up to the root and updating the products in the internal nodes. After we’re done updating the tree with all of the matrices that are different than matrices of the original cycle, we will just use the product in the root of the tree. Finally, we will update the tree back with matrices of the original cycle in order to reuse the segment tree for 𝐸_𝑖+1.

Since there are 𝑂(𝑁) nodes in the segment tree, the complexity of updating is 𝑂(𝑙𝑜𝑔𝑁). The total complexity is then 𝑂(𝑀𝑙𝑜𝑔𝑁 + 𝑀𝑙𝑜𝑔𝐾). We should also mention that the constant factor is not very small, since we operate on matrices and not just integers.

Note that we need to find 𝐹_𝐾 𝑚𝑜𝑑 𝑃 and 𝑃 may not even be a prime number. However, this does not affect us since we only deal with operations of addition and multiplication throughout the whole procedure and we can just do them all modulo 𝑃.

来源：http://codeforces.com/contest/575/problem/A

J. 木棒♂游戏

First of all, comment on such type of games. In CS the game where two players are willing to maximize the difference between their own score and the score of their opponent is called a "zero-sum game". A useful knowledge is that problems for such a kind of games are usually solved using dynamic programming.

Note that at any moment the first sticker contains the sum of numbers on some prefix of an original sequence. This means that the state of a game is defined by a single number i: the length of an original sequence prefix that were summed into a single number.

Let's make two observations. First of all, for any state i the turn that current player will perform doesn't depend on scores of both players. Indeed, at any moment we may forget about the scores of both players since they add the constant factor to the resulting score difference, so we may virtually discard both players current scores. So, all we need to know about state i is what difference there will be between the current player score and his opponent score if the game would have started from the state i with zero scores.

Second observation is that the turn chosen by a player from the state i and the final difference of scores at the end does not depend from which player is currently making a turn (Petr or Gennady), i. e. the game is symmetric.

Denote as D[i] the difference between the first player score and the second player score if the game would have started from the state i with zero scores.

It is a convenient way to think about this game as if there were no separate scores of two players, but only a single balance value (difference) between them, and the first player is adding some numbers to the balance at his turn аnd second player subtracts some numbers from the balance. In such formulation D[i] is a balance change at the end of the game if the current player is willing to maximize it and he is currently in the state i. The answer for a problem will be, as one can see, D[1]. Note that if the current player would be willing to minimize balance, then the final balance change from the state i would be  - D[i] because the game is symmetric.

Let's calculate all D[i] using dynamic programming. At the end of the game, i. e. in the state n the value D[n] is equal to zero because the players won't be making any turns, and so the balance won't change.

Consider some state i. Suppose current player will take all the stickers up to the j-th (here j-th means the index in the original sequence). In such case he will change balance by S[j] (where S[j] is the sum of first j numbers in an original sequence), and game will move to the state j. After that his opponent will change the balance by  - D[j] (note that the balance change value is added with an opposite sign since the opponent will be playing from this state).

So, the final balance change when making such a turn will be S[j] - D[j]. In the DP definition we play for a player that is willing to maximize the balance, so

$D[i]=max_{i< j\leq n}(S[j]-D[j])$.

Such a formula produces a solution in O(n²), but one may find that that it's enough to keep the maximum value of S[j] - D[j] on suffix j > i, recalculating it in O(1) when moving from i to i - 1. So, we have the solution that works in O(n).

来源 ： http://codeforces.com/contest/731/problem/E

K. 翻转♂游戏

Since 1 ≤ a_i ≤ 2, it's equivalent to find a longest subsequence like 1 * 2 * 1 * 2 * . By an easy dynamic programming we can find it in O(n) or O(n²) time. You can see O(n²) solution in the model solution below. Here we introduce an O(n) approach: Since the subsequence can be split into 4 parts (11...22...11...22...) , we can set dp[i][j](i = 1...n, j = 0..3) be the longest subsequence of a[1...i] with first j parts.

来源：http://codeforces.com/contest/933/problem/A

其他说明

关于题面和测试数据，你可以在 本站 上下载到。

未标注来源的题目均为原创或过于经典的老题。

第二轮

A. Rescue

将边是否挖通作为状态压缩，对于每一个可达状态都尝试转移到所有可能的下一步状态。

所有可能的下一步边可由当前可访问点求出，当前可访问点可由当前可访问边求出，注意转移时限制增加的边的数目不超过 $k$ 个。

B. Computer

本题题面是 《Angel Beats!》 的一种可能剧情，题解是 Segment Tree Beats!，从而完成了从 A 题 到 下一题中出场人物 ST 的过渡。

线段树维护区间最大值及其出现次数和次大值，打标记更新时遇到 $x$ 不小于次大值就直接打上即可，否则 DFS 下去直至可以打上标记。

另外，由于本题数据范围不是特别大，常数较小的分块可能可以通过。

来源：2015 Multi-University Training Contest 2（有删减）

C. Mustache

本题是 https://github.com/qwerty472123/wxappUnpacker 中表达式还原功能的简化版。 由于输入是 JSON 格式，使用 JS 可以很快完成，当然，我们也可以利用递归了手动解析 JSON。

关于括号要尽可能少，我们只需要讨论一下表达式对应的树的每个节点和它的子节点上的运算的优先级关系即可。

D. Validation

本题简单运用 NOIP 2014 Day2 T3 解方程 的前 $70$ 分做法的思想，对计算结果模一个数即可。

本题随便卡了几个过于常见的素数和自然溢出，分析数据范围可知本题远远卡不完所有可行的素数，故随机选取几个素数即可。

E. Solder

对每两个线段判断线段是否相交(注意要使用叉积来避免除法运算带来的精度误差)，建图后 DFS 或直接用并查集维护联通性即可。

注意输入输出点相同时显然会短路的问题，要进行特判。

F. 选妃之争

本题先手必胜，证明如下：

若无视 t 姐姐先手必胜则先手按相同方法做即可，否则先手第一次选 t 姐姐，从而将自己转换为后手。

G. 大汉之战

本题相当于求所有数异或和与 $x$ 异或的结果(不妨记为 $y$)异或上前 $[l,\ r]$ 个数后最大是多少？也就是 $1\sim [l,\ r]$ 的前缀异或和中选取一个使得其异或上 $y$ 后最大的数。

在一些数中选异或某个数值后最大的数可用将数值的二进制内容视作字符串构建的 Trie 做，而选择指定一个区间的异或和可用可持久化完成。

H. 无脑之作

先构建出 AC 自动机，以当前字符串位置、对应 AC 自动机状态做动态规划即可。

I. 最强之队

现在树上做树形 DP 求出根节点选与不选的结果。

然后对于环随便选环上一点断开或选取该点、断开指向它的点做一下 DP 即可。

J. 轮回之命

构建出回文自动机后对所有本质不同串中取“命运值”最大即可。

其他说明

关于题面、标算和测试数据，你可以在 本站 上获取。

B 、J 题由于测试数据导致时间复杂度明显错误的程序可以通过，所以它们的测试数据分别在赛中和赛后更新。这一变更对部分选手的做题体验造成了较大的影响，在此我们致以诚挚的歉意。