Shooting Game

出题人：吴霜
知识点：排序

纯签到题。

算出分数，对分数和序号比较大小即可。

A Number Theoretical Problem

出题人：施杰
知识点：数论

签到题

给出一个正整数x和一个质数p，求模p下x的逆元。简单的使用费马小定理求逆元即可。

设置一个小小坑点，x的范围并没有加以特殊限制，所以需要判断一下x是否存在逆元。也就是判断一下是不是倍数。

City Supplies

出题人：宋宏康
知识点：BFS

首都总是在点1,要求每个城市到首都的最短距离，因为可能有多余的边，所以直接以1为根节点，跑一遍BFS,得到一颗以1为根节点的树，用数组记录树上所有节点的深度，深度就是节点到根节点的最短距离。花费是 $2^x$ ,所以要求2的x次方，最远的距离是所有点在一条直线上，可以用数组预处理好2的x次幂，最后累加就可。

Moving stones

出题人：吴迪
知识点：策略，模拟

由于数据较小，只需要每次找到最少的那堆尝试加石头，直至所有堆达到平均数或者遇见违法操作
（尝试从石头数为0的堆里取石头），每次重新排序即可，最多1000次后，如果还无法满足要求，
输出No即可。判断的时候可以注意，n=1时一定输出yes，n>1时，如果石头数全相等（包括全0），
也可以直接输出yes，n=4, 1 1 1 5这种有很多小于平均数的数据，是会出现中间过程尝试从石头数
为0的堆里取石头的操作的，应该输出No。

高斯消元可以得到解（解是选定各堆石头的次数），但难以验证整个解空间，尤其是难以验证过程是否尝试从石头数为0的堆里取石头，所以很难通过所有测试数据

windmill

出题人：索文杰
知识点：数学几何，模拟

题意：在平面内有很多点，其中一个点在一条直线L上，现在给出点在平面位置，直线L穿过的点和L的角度。直线开始绕着直线上的点顺时针旋转，当直线旋转过程中碰到其他点的时候，直线将离开原本的“轴”，将新碰到的点作为轴继续顺时针旋转。问直线旋转一定角度后，直线上的点是哪一个。

题解：需要细心的观察直线旋转的过程。直线在旋转过程中，总是保持一种“平衡”。由于题目限制了没有三点共线，在直线“左”和“右”侧的点的个数是不会变化的。

根据结论，我们可以感受到，当直线旋转360°后将会回到原位。故我们可以利用该结论将旋转度数缩小到360度以内。

之后有两种解法：

1.由于旋转角只有360°，可以直接暴力模拟旋转过程。其中，由于点数有限，可以简单预处理每一个点到其他点的角度，随后模拟过程，利用预处理值找出这个点在该角度下旋转的下一个碰撞点，这样就可以快速找到答案。

2.上述结论还告诉我们，假设直线有方向，则直线左右的点个数不变。故我们计算初始状态下点的个数，在计算结束状态下每个点所处的左右位置关系，即可快速找到答案。可以利用角度的单位向量与点向量的向量叉乘来排序。

A Simple Game

出题人：郁宙
知识点：博弈游戏

首先考虑n=1的情况，这个时候只有一个字符串。比较明显的是如果字符串只有一个0，没有1，是没有办法进行任何操作的；同时观察操作一和操作二：操作一会把1变成0，也就是说该串的1的个数减一，操作二会把连续的0变成1，该串的1的个数加一，也就是说每进行一次操作，原串1的个数的奇偶性就会发生变化。由于偶数次操作无法改变1的个数的奇偶性，所以只需要查看字符串中1的个数，如果是奇数，就是Alice赢，因为有限次操作后一定是Bob面对只有一个0无法操作的局面；否则是Bob赢。

这时候考虑n>1的情况，当所有串含1的个数都是偶数时，无论你选择对哪些串进行操作，对方只要也选这些串进行操作，就能继续保证所有串含1的个数都是偶数。由于是Alice先动，所以只有当所有串含1的个数都是偶数时，Alice才会输，其他情况则是Bob落败。

GAMING WITH MIA

出题人：施杰
知识点：dp

给定一个长度为𝑛的 $-1/0/1$ 序列，两两之间填运算符 $’+’/’*’$ ，问运算结果最大是多少。（人类智慧题？）

有一些很明显的结论：我们肯定希望1尽可能做加法；0的作用肯定是消除-1，否则就直接做加法；-1与-1“结对”相乘，可以得到1（做加法），我们肯定希望这样的“结对”尽可能多……

观察以后，sj发现最多不超过5个数连乘。

比如2个数相乘的例子有： $(-1)*(-1)$ ， $0*(-1)$ ，……

那么3个数，4个数，5个数连乘分别是什么情况呢？

$(-1)*1*(-1)$
$(-1)*1*1*(-1)$
$(-1)*1*1*1*(-1)$

就只有上面这几种情况……为什么？如果是 $(-1)*1*1*1*1*(-1)$ ，做加法肯定更优。为什么会有上面的情况？比如类似： $0+(-1)*1*(-1)+(-1)*(-1)$ ，可以自行感受一下，0此时不需要消除-1。

有了上面的结论，这题就很好dp了（ $𝑑𝑝[𝑖]$ 表示前𝑖个数的最优值）：

$dp[0]=0$
$dp[i] = max_{1 \le 𝑘 \le \min(5,𝑖)}(𝑑𝑝[𝑖−𝑘]+𝑎[𝑖−𝑘+1]∗⋯∗𝑎[𝑖−1]∗𝑎[𝑖])$

复杂度：𝑂(𝑛)

HAPPY FAIRY

出题人：索文杰
知识点：主席树、LCA、二分

给一棵树（注意看树有多少条边），边上有权值，多次查询，问给定一个数𝐶，𝑃的最小值是多少，才能满足从𝑋到𝑌的唯一简单路径上，权值不在 $[𝐶 − 𝑃,𝐶 + 𝑃]$ 范围内的边数不超过𝐾条。

本题首先想到的，肯定就是对每次查询，二分答案𝑃，判断路径上不在范围内的数的个数是否超过 $K$ 个。然后就会想到主席树。难点就在于这不是序列，而是树。最后就会想到树链剖分，结果一算复杂度超时了。

是否有办法进一步加速呢？如果仔细观察会发现，树链剖分是没必要的，直接用“树上主席树”即可。

复杂度: $O(n*log(n)+m*log(n)*log(MAX))$

本题特意造了卡掉树链剖分的数据，避免“明明算出来复杂度超时的做法竟然可以通过本题”……但是很可惜，最终本题有人剖分过了，终究是没有卡住！

IRRATIONAL GRAPH

出题人：施杰
知识点：最短路、拓扑序

给定一个有向图，每条边的边权可以为正、可以为负、也可以是零，问从给定源点出发到图上所有点的最短路分别有多少种走法。

我们先考虑边权只能为正的情况。很显然，由于边权为正，所以最短路一定是DAG，所以我们求出最短路后，按最短路重新建图，跑拓扑序并累加贡献即可。

下面是个例子（已经按最短路重新建图，源点是1）：

拓扑序：1，2，3，4
初始化：令dp[1]=1；
分别累加dp[1]到dp[2]和dp[3]；
最后将dp[2]和dp[3]累加到dp[4]。

当边权可以为负，也可以为零时，除了引入了负环，更是引入了“零环”（负环是走一圈权值和为负，“零环”就是走一圈权值和为零）！负环会导致最短路不存在（为负无穷），“零环”会导致答案无穷大（因为可以反复走）

对于负环的消除，出题人使用Bellman-Ford算法，完整跑完𝑛次以后，所有负环都会形成环，然后用 $O(n^2)$ 时间暴力找环即可，Bellman-Ford算法复杂度 $𝑂(𝑚*𝑛)$ 。不要忘记，找到负环以后，所有负环上的点，以及与负环相连的点，都要置-1。

对于“零环”的消除，一个精心设计的DFS，可以在 $𝑂(𝑛)$ 时间内消除所有“零环”。

消除负环和“零环”以后，除了与源点不相连的点，剩下的就是最短路为DAG且答案一定存在的情况了，本步骤也可以在 $O(m)$ 时间内完成。

复杂度： $𝑂(𝑚*𝑛+𝑛^2)$

JUST A PURE DATA STRUCTURE PROBLEM

出题人：施杰
知识点：平衡二叉树

设计一种数据结构，可以维护序列插入、连续相同值的个数/值更改、单值更改/删除、单值查询功能。
对于本题，离线操作非常不容易，因为每个元素的位置是实时变化的。

相信大家读完题，直觉就是平衡二叉树（对于不知道的同学，补充说明一下：一般的二叉树维护的是数值，这里我们需要维护位置，方法就是在每个节点上维护子树大小即可，这与线段树主席树查询第𝑘小类似）。

实际上，本题的主要难点在于细节特别多，如果没有处理好相同值的合并，很有可能会导致各种意想不到的问题，比如RE。

复杂度： $𝑂(𝑚*\log(𝑛))$

语言描述起来不太方便，举个例子。
下图描述的就是序列：1,1,2,2,2,1,3,3,2

每个节点需要维护

1.保存的数
2.数的个数
3.子树大小

在二叉树上维护以上信息（同时要注意避免二叉树退化成链），就可以在 $𝑂(\log(𝑛))$ 时间内完成题目要求的所有操作。

注意：相邻节点保存的数一定是不同的！这样可以保证各种操作的效率，但是无疑给更新与维护增加了负担。

The Islands

出题人：施杰
知识点：BFS

本题真的只考察了单一知识点——BFS，没有参合其他知识点，而且本来定位是简单题（划掉）……应该有多种做法，只要能过就行，数据是随机的，每组都是1s，不卡时间。

先梳理一下题目中给出的定义：
水（water）：'.'；
陆地（land）：'#'；
边界（border）：最外圈的水，且最外圈一定是水；
岛（island）：连接在一起的陆地（上、下、左、右四个方向）；
受困水（trapped water）：无法流向边界的水（上、下、左、右四个方向）；
受困岛（trapped island）：岛上的人无法直接走水路到边界，也就是说，岛周围的水都是受困水；
环绕岛（surroundings）：困住水的岛（可能不止一个岛），这（些）岛环绕了一些水，使得这些水成为受困水；
国家（country）：环绕岛及相关受困水和受困岛或某个孤立的岛；
联盟（alliance）：如果国家之间含有土地，土地之间的曼哈顿距离小于等于k，则形成联盟。

现在给定地图和k，问有多少个联盟。

这里给个例子：

k=2
...................
..###....#.........
.#...#..#.#....#.#.
.#.#.#.#...#....#..
.#...#..#.#........
..###....#.....#.#.
...................

首先开一个和原图一样大的二维矩阵用来打标记，初值全是0。题目很有引导性，第一步就是找国家。从边界上任意一点开始沿着水流方向BFS，走过的地方都标记成1，那么就会得到国家（0的位置就是国家，无需区分受困岛和受困水，全当陆地就行）：

1111111111111111111
1100011110111111111
1000001100011110101
1000001000001111011
1000001100011111111
1100011110111110101
1111111111111111111

估计本题要是问国家有几个，大家应该都会？但本题硬核的地方就是，怎么合并形成联盟的国家。

不是特别建议暴力枚举，点数很多（随机数据，国家很多），很有可能会超时……

直观的想法是找到一个国家，向外BFS最大k步，看看能否找到没有访问过的国家。这样做的复杂度会变得有些无法估计，因为每个点（主要是水）的访问次数和国家与k都有关系。有同学可能认为，访问过的点（水）打上标记不再访问就可以控制复杂度，但这样做严格来说是错的，如上面的例子，我们取最右边的部分看：

如果从上面的3个国家开始扩张，扩张经过的点用2表示：

如果刚好遇到这样的情况，那么，对于下面2个国家来说，就没法合并了，因为下面两个国家的通路被之前的标记“挡住”了。

出题人的方法如下：

k'=k-1；
使用BFS将所有国家同时向外扩张[k'/2]（把水变陆地），[x]表示x取整数部分（向下取整）；
最后一遍BFS计数，如果k'是奇数，那么允许“隔空”跳一步。

上面的例子中k'=1，[k'/2]=0，由于第2步比较显然，所以就不演示了，就是一定得所有国家一起扩张，否则还是会发生被“挡住”的情况。第3步，由于k'是奇数，所以可以允许踩一次水，2表示尝试踩的水，一样的字母表示同一个联盟：

1122211112111111111
12aaa2112a211112121
2aaaaa22aaa2112b2b2
2aaaaa2aaaaa2112b21
2aaaaa22aaa21112221
12aaa2112a21112c2c2
1122211112111112121

至于“隔空”跳到底代码怎么写，留给聪明的大家思考啦~

“隔空”跳会使得一些水被多次访问，但是有限，最多周围3个点（4个点的话就变成受困水了），所以这样做的复杂度是O(mn)。

东华大学2020年程序设计竞赛——题解