4182_543_731`s blog

2020 集训队作业 题解

温馨提示：本文大概有 $10^5$ 字（不包含任何代码）。

这份题解编码一下可以作为一个字符串题的输入

2013-2014 ACM-ICPC, NEERC, Northern Subregional Contest

C. Correcting Curiosity

Problem

对于串 $a,b$ ，定义 $f(s,a,b)$ 为：

1. 如果 $s$ 中不包含 $a$ ，则 $f(s)=s$ 。
2. 如果 $s$ 包含 $a$ ，找到 $s$ 中 $a$ 第一次出现的位置，设此时 $s=s_l+a+s_r$ ，则 $f(s)=s_l+b+f(s_r,a,b)$

给定串 $s,t$，长度为 $n,m$，你需要找到一对 $a,b$ ，使得 $f(s,a,b)=t$ ，且 $|a|+|b|$ 最小。输出一个方案。

$n,m\leq 2000,s\neq t$

$2s,256MB$

Sol

显然需要进行替换，因此 $a$ 是 $s$ 的一个子串。

先枚举 $|a|$ ，求出所有长度为 $|a|$ 的子串的hash值。然后枚举这个长度的所有子串作为 $a$ ，可以通过替换 $a$ 的次数求出 $|b|$ ，然后可以通过字符串hash求出是否存在一个合法替换的方案。

复杂度 $O(n^2\log n)$

H. Heavy Chain Clusterization

Problem

给 $n$ 个字符串 $s_{1,...,n}$ ，你需要将它们划分成若干个集合，使得对于每一个集合，以下两个条件至少有一个被满足：

1. 集合中的所有串的前 $k$ 位相同。
2. 集合中的所有串的后 $k$ 位相同。

求集合个数最小的一个方案，输出构造的方案。

$n\leq 5000,k,|s_i|\leq 550$

$2s,256MB$

Sol

对于合法的一个集合，它一定能被表示成一个长度为 $k$ 的前缀/后缀，集合中的所有串都以它为前缀/后缀。

考虑先处理出所有可能出现的集合，可以发现一个点最多出现在两个集合中。

考虑两排点，第一排表示前缀对应的集合，第二排表示后缀对应的集合。对于每个点，从它的前缀对应的点向后缀对应的点连边。可以发现，每条边两侧的两个点对应的集合至少需要有一个存在。

因此答案为这个二分图的最小点覆盖。求出最大匹配直接构造即可。

具体来说，如果当前图有完美匹配，选一侧点即可。否则，找一个不在最大匹配中的点，它一定不在最小点覆盖中，因此与它相邻的点一定在最小点覆盖中。考虑删去与它相邻的点，则这些点在匹配上对应的点此时变为了不在现在的最大匹配中。一直做这个过程直到剩下一个完美匹配即可。

复杂度 $O(nk+n\sqrt n+\sum s_i)$

I. Intellectual Property

Problem

定义数独题目为一个 $9\times 9$ 的矩阵，其中每个位置为 $[1,9]$ 间的整数或空白。

定义以下几种变换：

1. 选择两个数字 $x,y$ ，将矩阵中所有为 $x$ 的位置改为 $y$ ，所有为 $y$ 的位置改为 $x$ 。
2. 选择两行 $x,y$ ，满足 $x,y$ 在同一组中(所有行被划分成三组( $\{1,2,3\},\{4,5,6\},\{7,8,9\}$ )，列同理) ，交换矩阵的第 $x$ 行和第 $y$ 行。
3. 选择 $x,y$ ，整体交换第 $x$ 组的行与第 $y$ 组的行，顺序不变。
4. 选择两列 $x,y$ ，满足 $x,y$ 在同一组中，交换矩阵的第 $x$ 列和第 $y$ 列。
5. 选择 $x,y$ ，整体交换第 $x$ 组的列与第 $y$ 组的列，顺序不变。
6. 将矩阵沿左上到右下的对角线翻转

给出 $n$ 个这样的矩阵，求出它们两两之间是否可以通过变换使得两个矩阵相等。若相等构造一个方案。

$n\leq 20$

$2s,256MB$

Sol

考虑快速判断只有操作1是否合法。考虑记录每种数所在的位置的集合的hash，再对这些hash做一个无序hash。如果两个矩阵这样做出来hash相等则可以通过1操作做到相等。

显然6操作最多有一次，且剩下的操作之间顺序不重要。考虑对剩下的操作折半。对于每个矩阵，枚举它的列变换，算出hash值用hashtable维护。然后枚举每个矩阵，枚举是否翻转对角线，再枚举行变换，求出hash值，如果能对应上某个矩阵之前算出的hash值则可以从这个矩阵通过操作变到那个矩阵，否则一定不行。

为了保证复杂度，对于每个矩阵，不能向hashtable中插入相同的hash值。

复杂度 $O(n^2*6^4*9^2)$

J. J

Problem

$2s,256MB$

Sol

定义 $x^2=\{x_1^2,x_2^2,x_3^2,...,x_n^2\},...,x^i=\{x_1^i,x_2^i,x_3^i,...,x_n^i\}$

将计算中的向量表示成 $\sum a_ix^i$ 的形式，考虑所有操作：

对于向量加标量的情况，可以看成加 $ax^0$ 。

对于向量相加，可以看成多项式相加。向量相乘可以看成多项式相乘，向量平方同理。

可以发现一个表达式的complexity即为运算结果的最大次数。

考虑折叠操作，因为次数不超过 $10$ ，可以直接预处理 $\sum x_i^k$ 后求值。

可以先求出表达式中括号的匹配情况，然后直接计算即可。

复杂度 $O(10^2*n)$

L. Lonely Mountain

Problem

水平面上有一座山峰，山峰在两个垂直于水平面且互相垂直的平面上的投影都形如一个山峰 -- 投影由若干个点 $(x_0,y_0),(x_1,y_1),...,(x_{n+1},y_{n+1})$ 组成，满足 $x_0<x_1<x_2<...<x_{n+1},y_0=y_{n+1}=0,y_i\geq 0$ 。

给出山峰在两个平面上的投影，求出山峰的最大体积或报告不存在合法的山峰。

设 $n,m$ 为两个投影分别的点数，$n,m\leq 10^5$

$2s,256MB$

Sol

如果两个投影的最高高度不同，显然无解。

考虑将每个点的高度设为两个投影上对应位置的高度的最小值，可以发现这样在最高高度相同的情况下一定合法，且得到的一定是最大值。

考虑从高度一维上计算，设 $f(a)$ 表示第一个投影高度大于等于 $a$ 的区域长度， $g(a)$ 表示第二个投影高度大于等于 $a$ 的区域长度，那么体积为

$\int_{x=0}^{\infin}f(x)g(x)$

可以发现 $f,g$ 都是分段一次函数，直接算即可。

复杂度 $O((n+m)\log (n+m))$

2014-2015 ACM-ICPC, NEERC, Northern Subregional Contest

C. Combinator Expression

Problem

设表达式长度为 $n$ ，$n\leq 3\times 10^4$ 。

$2s,256MB$

Sol

注意到如果没有 K ，每次只能消掉一个字符，此时操作次数固定。想让操作次数最小，显然需要让每个 K 消掉尽量多的东西。

因为表达式内部进行操作后长度只会变小，所以最优解一定满足所有被 K 消掉的区域内部不进行操作。

可以发现，从左向右直接进行化简得到的解满足这一条件，因此它是最优的，模拟这个过程即可。

复杂度 $O(n)$

E. Expression

不会

F. Fragmentation

Problem

给一个长度为 $n$ 的序列，你需要将其划分成若干段，满足将这些段之间重新排序后，可以使得整个序列递增。

求出一种段数最少的方案。

$n\leq 10^5$

$2s,256MB$

Sol

如果分在两个相同的数之间，一定可以调整使得分到旁边。这样可以使得最优解不在两个相同的数之间分段。

将相同的相邻数缩起来。考虑现在相邻的两个数 $u,v$ ：

1. 如果 $u>v$ ，显然需要分开。
2. 如果 $u<v$ 但还有数在 $[u+1,v-1]$ 直接，也需要分开。

处理完一定分开的数后，考虑剩下的位置，可以发现还有两个限制：

1. 对于所有相邻的 $(x,y)(x\neq y)$ ，最多只能有一对 $(x,y)$ 不被分开。
2. 对于同一段内相邻的 $(a,b,c)$ ，若 $[a+1,c]$ 中还有其它数，则这两对中最多有一对不被分开。

可以发现，满足上面的所有条件后，得到的划分方案一定合法。

考虑 $dp$ ，设 $dp_{i,j}$ 表示考虑了前 $i$ 对 $(x,y)$ ，第 $j$ 段中的上一对没有分开，只考虑前面部分最少需要分开多少段。显然这样的状态数为 $O(n)$ 。

考虑转移，如果 $a\neq b$ ，则一定可以从 $dp_{i,a}$ 转移到 $dp_{i+1,b}$ ，只需要判断是否可以从 $dp_{i,a}$ 转移到 $dp_{i+1,a}$ ，这可以 $O(1)$ 判断。

复杂度 $O(n)$

H. Hiking in the Hills

Problem

给一个山峰，山峰的表面由 $n$ 个三角形组成。保证不存在中空的情况，也不存在一个三角形与水平面垂直。

给出你现在所在的位置以及你想要到达的位置，找到一条从现在的位置到目标位置路线使得路线上的最高高度最小。输出这样的方案。

$n\leq 2000$

$2s,256MB$

Sol

除了起点终点外，如果经过了一个三角形的内部，考虑改为沿着三角形的边走，一定存在一种方式使得最高高度不会增加。

因此在中间部分只会沿着边走，可以发现起点终点只会向所在的三角形的顶点走。

因此现在的边数只有 $O(n)$ 条，排序后并查集维护即可。

复杂度 $O(n\log n)$

K. Kebab House

Problem

你需要处理 $n$ 个物品，处理第 $i$ 个物品需要 $a_i$ 秒，每一秒你都会进行一次操作。

但是你可能忘记进行操作，你在任意 $t+1$ 次相邻的操作中最多忘记一次。

如果你在处理第 $i$ 个物品时进行了至少 $b_i$ 次操作，则这样的操作是合法的。

求出合法的操作情况的总数，模 $10^9+7$

$n\leq 1000,t\leq 100,a_i\leq 250$

$2s,256MB$

Sol

考虑dp，设 $dp_{i,j}$ 表示处理完前 $i$ 个物品，上一次忘记是在 $j$ 秒前 (若 $j>t$ ，则全部看成 $j=t+1$ ) 的方案数。

转移时枚举下一个物品最后一次忘记的时间，然后相当于求出一段时间内忘记不超过 $a_i-b_i-1$ 次的方案数，可以组合数+前缀和求出。

复杂度 $O(v^2+nt^2)$

2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest

D. Distribution in Metagonia

Problem

给定 $n$ ，你需要将 $n$ 划分成若干个数 $a_1,...,a_k$ ，满足：

1. $\sum a_i=n$
2. $\forall i,\exists p_i,q_i\in \N,a_i=2^{p_i}3^{q_i}$
3. $\forall i\neq j,a_i\not|a_j$

构造任意一个合法方案。

多组数据，$T\leq 1000,n\leq 10^{18}$

$2s,256MB$

Sol

如果 $3|n$ 则构造 $\frac n3$ 的解并全部乘上 $3$

考虑找到最大的 $k$ ，使得 $2^k\leq n$

如果 $3|n-2^k$ ，则选出 $2^k$ ，构造 $\frac{n-2^k}3$ 的解，并将这些数全部乘上 $3$ 。

否则，一定有 $3|n-2^{k-1}$ ，可以发现 $\frac{n-2^{k-1}}3<2^{k-1}$ ，所以使用同样的方式构造即可。

复杂度 $O(T\log n)$

F. Fygon

Problem

$2s,256MB$

Sol

容易证明，有 $k$ 个题目中描述的循环的程序的复杂度不超过 $O(n^k)$ 。

因此答案一定是一个不超过 $6$ 次的多项式，考虑枚举 $n=1,...,7$ ，算出答案并插值。

总的运行次数不超过 $9^6$ ，因此直接模拟循环即可。

复杂度 $O(7*9^6)$

G. Graph

Problem

给一个 $n$ 个点 $m$ 条边的DAG，你需要再加不超过 $k$ 条边，使得这个图还是一个DAG且它字典序最小的拓扑序的字典序最大。

输出满足条件的方案和字典序。

$n,m,k\leq 10^5$

$2s,256MB$

Sol

考虑逐位确定，如果当前有多个点度数为0，考虑向最小的一个点连一条边(连向它的点暂时不决定)，这样最小的值会变大。

维护当前所有连了这种边的点的集合，对于每一位，依次考虑：

1. 如果当前有多个点度数为0并且还有边，向最小的一个点连一条边。
2. 如果当前没有点度数为0，将集合中最大的点设为从拓扑序上一个点连向它，此时它变为度数为0的点。
3. 如果集合中最大的点比当前度数为0的点还要大并且还有边，将集合中最大的点拿出来，然后进行操作1。

这样就保证了每一位最优。

复杂度 $O(n\log n)$

I. Insider’s Information

Problem

给定 $n,m$ ，给 $m$ 个三元组 $(a,b,c)$ ，对于一个排列 $p$ ，这个三元组被满足当且仅当排列中 $b$ 在 $a,c$ 中间。

求一个排列 $p$ ，使得至少有一半的三元组被满足。

$n,m\leq 10^5$

$2s,256MB$

Sol

如果能找到一个排列，使得对于每个三元组， $b$ 不在 $a,c$ 的后面，那么接下来每次贪心放满足尽量多的限制即可。

但是我不会找这个排列

考虑随机化爬山，每次随机一个数，把它放到使得满足数最大的位置上。

使用一些数据结构维护，修改一个数的复杂度为这个数所在的三元组个数。然后跑得飞快。

K. Kingdom Trip

Problem

有 $n$ 个点 $p_{1,...,n}$ ，你能从 $i$ 走到 $j$ 当且仅当 $i<j$ ，且对于所有 $k\in(i,j)$ ，$p_k$ 到线段 $p_ip_j$ 的距离不超过 $d$ 。

求从 $1$ 走到 $n$ 最少需要走几次。

$n\leq 2000$

$2s,256MB$

Sol

考虑如何判断到射线 $p_ip_j$ 的距离不超过 $d$ 。枚举 $i$ ，再依次考虑每一个 $j$ 。如果 $dis(p_i,p_j)\leq d$ 则 $p_j$ 到射线的距离不会大于 $k$ ，否则它会限制射线的角度在一个区间内。

因此直接扫过去，维护当前所有区间的并。因为一个区间不超过180度所以区间的交只有一个区间。

然后再反向做一遍，求出是否每个点到射线 $p_jp_i$ 的距离不超过 $d$ 。可以发现如果两个条件都满足则满足到线段距离不超过 $d$ 。

复杂度 $O(n^2)$

2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest

B. Boys and Girls

Problem

$n$ 个人排成一个环，其中有一些是男生有一些是女生。你需要构造一个方案，使得有 $a$ 个人至少和一个男生相邻，有 $b$ 个人至少和一个女生相邻。构造一个方案或输出无解。

$n\leq 10^5$

$2s,256MB$

Sol

将两种人看成 RB 。

特判 $a=0$ 或 $b=0$ 的情况，剩下的情况必定两种人都有出现。

考虑一个长度为 $k$ 的极长连续 R 段：

1. 如果 $k>1$ ，则这一段会贡献 $k$ 个与 R 相邻， $2$ 个与 B 相邻。
2. 否则，则这一段会贡献 $0$ 个与 R 相邻， $1$ 个与 B 相邻。

一个 $k>1$ 的段会使 $a+b$ 增加 $k+2$ ，否则增加 $k$ ，因此可以根据 $a,b,n$ 算出 $k>1$ 的段数（奇偶性不同则无解）。设这个段数为 $t$ 。

这 $t$ 段至少会贡献 $2t$ 个 $a,b$ ，因此 $a,b<2t$ 无解。

若 $t$ 为偶数，则放 $t$ 段形成一个环，然后把剩下的 BR 放到某些段里面即可。

否则，需要额外一个长度为 $1$ 的段。可以发现只有一个时是最优的。枚举长度为 $1$ 的段是哪个，然后判一下即可。

复杂度 $O(n)$

D. Digital Addition

Problem

$2s,256MB$

Sol

从低到高考虑每一位。可以发现后面的位只有最左边的一排会影响前面的结果。

考虑dp，设 $dp_{i,0/1,s}$ 表示填了后 $i$ 位的数，当前后面的加法是否进位，当前后面最左边一排的情况为 $s$ ，是否可以到达这样的状态。

然后记录转移输出方案即可。

复杂度 $O(n)$

E. Easy Reading

Problem

给一个长度为 $n$ 的字符串，选定这个字符串的一个子串，依次考虑子串的每一个字符。

你初始在 $(0,0)$ ，如果当前字符为 u , d , l , r，则你向上/下/左/右走一步，否则不进行操作。

在考虑完所有字符后，将所有你经过过的位置涂成黑色，这样可以得到一个图形。

给一个 $w\times h$ 的图形，你需要找到一个子串，使得考虑这个子串后得到的图形经过平移与给定图形相同，或说明无解。

$n,w\times h\leq 10^5$

$2s,256MB$

Sol

考虑从串的开头开始走，但只把选定区间内经过的位置染色。

可以发现这样得到的结果平移之后就是题目中方式的结果。

考虑从小到大枚举 $r$ ，维护当前每个位置上次出现的时间。设给出的图形有 $k$ 个染色的格子，则只需要判断上次出现时间最近的 $k$ 个位置是否能组成合法的图案即可。

考虑记录 $\sum a^xb^y \bmod p$ 作为hash值，选择 $k$ 个位置中的一个，将整个图形平移使得这个位置移动到 $(0,0)$ ，这时的hash值即为之前的值除以一个数的结果。

预处理出将给出图形的每个染色位置平移到 $(0,0)$ 时得到的hash值，如果上面得到的值与其中的一个相同则这个图形可以通过平移得到原图形。

复杂度 $O(n\log n)$

G. Gangsters in Central City

Problem

给一棵 $n$ 个点以 $1$ 为根的有根树，初始所有点都是白色。 $q$ 次询问，每个选择一个叶子，翻转它的颜色。

每次询问之后你需要找到一个删边的方案，使得删边后根不与任意一个黑点连通。你需要满足删的边尽量少，在这个基础上根所在的连通块尽量大。输出最优方案的删边数与此时不与根连通的白点数量。询问之间独立。

$n,q\leq 10^5$

$2s,256MB$

Sol

考虑根的每个子树，如果子树内有黑点则这个子树至少需要删一条边，否则不需要删边。

因此每个有黑点的子树需要删一条边，显然这条边应该是子树内所有黑点的LCA与它父亲的连边最优。

于是维护黑点的dfs序顺序，取最大最小做LCA即可。

复杂度 $O(n\log n)$

H. Hard Cuts

Problem

给一个 $n\times m$ 的矩阵，你需要将它分割成若干个边长为正整数的正方形，使得正方形的个数最少。输出方案。

多组数据

$T\leq 3600,n,m\leq 60$

$2s,256MB$

Sol

可以写点dfs，然后优先放边长大的，并在dfs的过程中通过估算至少需要的正方形数进行剪枝。

有一个显然不对的dp：枚举一条分割线分开。但可以通过这个dp得到的上界加速剪枝。

这时可以发现这个dfs需要跑三四个小时，但总的输出只有 $120kb$，压缩成字符后只有 $50kb$，打个表就过了。

I. Integral Polygons

Problem

给一个 $n$ 个点，所有点坐标都是整数的凸多边形。求有多少条对角线满足沿对角线切开后得到的两个凸多边形面积都是整数。

$n\leq 2\times 10^5$

$2s,256MB$

Sol

特判整个多边形面积不是整数的情况，之后只需要考虑一侧面积为偶数的方案数。

设点为 $p_{1,...,n}$ ，分隔线为 $(i,j)$ ，那么一侧的面积为 $\frac 12\sum_{k=i}^{j-1}(p_k-p_i)\times(p_{k+1}-p_i)$ ( $\times$ 表示叉积 )

注意到这个值只和 $p_k,p_i$ 的坐标奇偶性有关，考虑枚举 $p_i$ 两维坐标的奇偶性，算出每个 $k$ 的贡献 $v_k$ 。

然后相当于对于每个合法的 $i$ 求出有多少个 $j$ 满足 $\sum_{k=i}^{j-1}v_k$ 是偶数，对 $v$ 前缀和即可。

复杂度 $O(n)$

J. Java2016

Problem

$2s,256MB$

Sol

考虑设 $a=? \max ? \max ...\max ?$ ，在取 $2^{13}$ 个的情况下，可以使得它有大约 $1-10^{-14}$ 的概率取 $255$ 。构造 $a$ 可以使用倍增构造。

然后再用若干个 $255$ 加起来得到 $c$ 即可。这部分也可以倍增构造。总的步数为 $O(\log c)$

2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest

C. Consonant Fencity

Problem

给一个长度为 $n$ 的字符串，你需要给除去 aeiouwy 的每种字符分配一个大小写，使得相邻且都不是 aeiouwy ，且大小写不同的字符对数尽量多。输出方案。

$n\leq 10^6$

$3s,512MB$

Sol

预处理两种字符相邻的对数，然后直接枚举大写的字符集合。

复杂度 $O(n+19^2*2^{19})$

D. Dividing Marbles

Problem

有一堆 $n=2^a+2^b+2^c+2^d$ 个石头，你每次可以选择一堆石头，将其分成两份。每次操作后，如果有多于一堆石头的数量相同，则只会保留一堆。当只剩下一堆一个石头时游戏结束。

你需要求出最少的操作次数以及一个方案。

多组数据

$a,b,c,d\leq 20,T\leq 500$

$3s,512MB$

Sol

考虑反向做这个过程，依次记录每次操作的数，可以得到一个序列 $a_{1,...,k}$ ，满足：

1. $a_1=1$
2. $\forall i>1,\exists j,k<i,a_i=a_j+a_k$

依次考虑每一个bitcount:

若 $bitcount(n)=1$ ，因为每一次最后一个数最多乘2，所以次数最少为 $\log_2 n$ 次。这显然可以达到。

若 $bitcount(n)=2$ ，可以发现次数最少为 $1+\log_2 n$ 次，先倍增 $\log_2 n$ 次，最后一次加即可。

若 $bitcount(n)=3$ ，使用类似刚才的方式可以得到 $2+\log_2 n$ 次的做法。如果存在 $1+\log_2 n$ 次的做法，则考虑第一个满足 $bitcount=2$ 的数，这之后每一个数的 $log_2$ 必须加一。可以发现这时无法构造出 $bitcount=3$ 的数，因此上面的方式为最优解。

若 $bitcount(n)=4$ ，直接构造为 $3+\log_2 n$ 步，但存在一些数可以用 $2+\log_2 n$ 步求出 (比如 $2^1+2^2+2^3+2^4$ )。

考虑直接dfs出所有可能的 $a$ 。因为可以构造出 $3+\log_2 n$ 步的方案，因此只需要搜 $2+\log_2 n$ 步的情况。可以剪枝消去大量无用情况，这样可以通过。

同时也可以正向dfs，通过类似的方式剪枝。可以发现每个时刻最多有两堆石头，因此可能的状态数非常少，也可以通过。据说直接打表可能的情况都能卡进200kb

E. Equal Numbers

Problem

有 $n$ 个数 $a_{1,...,n}$ ，你可以进行若干次操作，每次你可以将一个数乘上一个正整数。

对于 $k=0,...,n$ ，求出进行 $k$ 次操作后，现在的数的种类数的最小值。

$n,a_i\leq 10^6$

$3s,512MB$

Sol

设初始的数中最后不存在的数的集合为 $S$ 。

如果对于每一个 $i\in S$ ，都存在 $a_j,a_j\not\in S,i|a_j$ 。则可以将每一个 $i$ 乘上一个数变成 $a_j$ ，这样不会多出别的数。

否则，一定做不到不多出别的数。因此可以将所有需要换掉的数变成它们的LCM。

首先考虑第二种情况的最优解，此时所有数都可以选，按照每种数出现次数排序然后贪心即可。

对于第一种情况，如果 $a_i$ 满足 $\forall a_j\neq a_i,a_i\not|a_j$ ，则此时一定不能选 $i$ 。

如果 $a_i<a_j,a_i|a_j$ ，看成连一条 $(i,j)$ 的有向边。这样得到的是一个DAG，且上面的数是所有度数为0的点。可以发现剩下的数全部放入 $S$ 是合法的。因此不考虑上面的那些数再做一次贪心就是情况一的答案。

复杂度 $O(n\log n+v\log v)$

F. Fygon 2.0

Problem

$3s,512MB$

Sol

设所有的循环变量为 $v_{1,...,n}$ ，对于一个 for $v_i$ in range($v_j,v_k$) 的语句，相当于要求 $v_j\leq v_i\leq v_k$ 。

那么 $f(n)$ 相当于满足所有上面的条件的 $v$ 的解数量。

考虑没有等号的情况，$n\to\infin$ 时，可以看成所有数都在实数上随机，因此此时只需要考虑所有 $n!$ 种大小关系并判断哪些合法。这个可以使用状压dp+位运算做到 $O(n2^n)$ 。

对于存在等号的情况，可能出现若干个数必须相等的限制。先进行一次强连通分量求出所有必须相等的变量，然后缩起来后用上面的做法即可。

复杂度 $O(n2^n)$

G. Grand Test

Problem

给一个 $n$ 个点 $m$ 条边的无向图，你需要找到两个点，使得这两个点之间存在三条除起始点外点不相交的路径。输出无解或找出一种方案。

多组数据，$\sum n,\sum m\leq 10^5$

$3s,512MB$

Sol

先选出一个生成森林，找出剩下的边的端点在生成森林上的路径。

如果任意两条路径都边不相交，则图中的任意一个点双都是一个环，此时一定无解。

否则，找到两条相交的路径 $(a,b),(c,d)$ ，找出它们的交 $(u,v)$ 。

选择 $u,v$ 为起点终点，第一条路径为树上路径，第二条为经过 $(a,b)$ 的路径，第三条为经过 $(c,d)$ 的路径。

复杂度 $O(n)$

H. Hidden Supervisors

Problem

给一个 $n$ 个点有向生成森林，$1$ 为根。你需要给剩下的没有父亲的点选一个父亲，使得得到的是一棵以 $1$ 为根的有根树，且这个有根树的最大匹配最大。输出最优解以及方案。

$n\leq 10^5$

$3s,512MB$

Sol

假设确定好了树，则求最大匹配的过程可以dfs一次，每次贪心选最深的一对。

先求出每一个连通块的最优解。然后对于每个连通块，求出贪心匹配中根有没有被选以及没有被匹配的点数。

考虑剩下的连通块，如果一个连通块的根会被选，那么可以发现它的父亲无论是谁不影响答案。因此可以先贪心将这些接上去。

然后考虑根没有被选的，它们连到一个没有被匹配的点则会使答案+1。因此考虑优先连这种情况。

如果它连到一个被匹配的点，则上面的若干个贪心匹配会向下移动。但因为上面已经确定，所以不移动匹配得到的结果相同。

考虑贪心放，每次选出剩下的连通块中没有被匹配的点数最大的，将它连到前面，尽量连没有被匹配的点。这样可以得到更多的没有被匹配的点。可以发现这样是最优的。

复杂度 $O(n\log n)$

J. Joker

Problem

有一个长度为 $n$ 的序列 $a_{1,...,n}$ ，设当前所有正数的和为 $v_1$ ，所有负数的绝对值的和为 $v_2$ 。

定义 $b_{1,...,n}$ ：若 $a_i>0$ ，则 $b_i=\frac{a_i}{v_1}$ ，否则 $b_i=\frac{a_i}{v_2}$ 。

有 $q$ 次操作，每次修改一个 $a_i$ ，你需要求出一个 $k$ 满足 $\sum_{i=1}^kb_i$ 是 $\{b_1,b_1+b_2,...,b_1+b_2+...+b_n\}$ 中最大的。若有多个选 $k$ 最小的。

$n,q\leq 5\times 10^4,v_1,v_2\leq 10^9$

$3s,512MB$

Sol

对于每个 $i$ 记录前 $i$ 个数中正数的和 $s_i$ ，负数的绝对值的和 $t_i$ 。那么询问相当于求出 $\frac{s_i}{v_1}-\frac{t_1}{v_2}$ 的最大值。

考虑对序列分块，对于每一块内部，维护只考虑内部的数，所有 $(s_i,t_i)$ 构成的凸壳。这样修改时只用暴力重构一块，因为 $s_i$ 递增所以重构复杂度线性。

对于一个询问，先求出 $v_1,v_2$ ，在每一块的凸包内二分找到最大的点即可。

复杂度 $O(n\sqrt{n\log n})$

2013-2014 ACM ICPC Central European Regional Contest

A. Rubik's Rectangle

Problem

给一个 $n\times m$ 的矩阵，你可以进行若干次操作，每次翻转矩阵的一行或一列。

你需要使 $\forall i,j$ ，矩阵的第 $i$ 行第 $j$ 列的元素为 $(i-1)*m+j$ 。构造一组方案或输出无解。

多组数据， $n,m\leq 100$

$15s,256MB$

Sol

将 $(i,j),(i,m-j+1),(n-i+1,j),(n-i+1,m-j+1)$ 看做一组。可以发现每次操作不会改变每一组内的元素集合。因此组内元素不正确无解。

考虑只交换某一个组内元素的方式。将这一组的元素标号为

$\begin{matrix}1&2\\4&3\end{matrix}$

考虑先翻转第 $i$ 行，再翻转第 $j$ 列，再翻转第 $i$ 行，再翻转第 $j$ 列，可以发现此时其余元素没有变化，而这四个元素的顺序变为:

$\begin{matrix}2&4\\1&3\end{matrix}$

因此对于一组，可以对三个元素进行旋转操作。可以发现这样每次操作不会改变排列的奇偶性，所有的偶排列都可以通过这种方式还原到初始情况。

接下来考虑每一组的排列奇偶性，称 $(i,j),(i,m-j+1),(n-i+1,j),(n-i+1,m-j+1)$ 在第 $i$ 行第 $j$ 列上。可以发现每次翻转一定会改变在一行或一列上的所有组的排列奇偶性。

这时相当于一个 $\frac n2\times \frac m2$ 的01矩阵，每次可以将一行或一列异或1，需要将整个矩阵变成0.

枚举第一行是否被翻转，然后可以知道每一列是否翻转，然后判断剩下的行是否合法即可。

将所有组变为偶排列后使用上面的方式求解即可。

复杂度 $O(nm)$

D. Subway

Problem

有 $n$ 条地铁线路，第 $i$ 条会依次经过 $k$ 个站点。每一条线路都有双向行驶的列车，但到达终点站后换另外一个方向的列车算乘坐另外一次列车。

你需要从一个点到另外一个点，你需要乘坐列车的次数最少，在此基础上经过的站点数最多。求出最少次数和最多的站点数。

多组数据

$n\leq 10^5,\sum k\leq 10^6$

$10s,256MB$

Sol

首先处理掉极其过分的输入

考虑先求出到达每个站点的最少乘坐列车次数。对于每一条线路上的点，它们可以用一次互相到达。使用类似bfs的方式，当一条线路上一个点被访问到时更新整条线路上的点即可。

然后考虑算答案。设 $dp_i$ 为到达 $i$ 最多的站点数。对于一条线路上的点，到达它们的最少乘坐次数相差不超过1。在这条线路上只能从次数小的点出发，到次数大的点。考虑按照次数从小到大处理，对于一条线路上的更新，从两个方向扫一遍即可。

复杂度 $O(\sum k)$

E. Escape

Problem

有一棵 $n$ 个点的树，除了 $1$ 外每个点上有一个数。你初始在 $1$，你有一个值 $v$ ，初始为 $0$ 。

你可以沿着树边走，第一次经过一个点时，你的 $v$ 会加上这个点上的数。如果 $v<0$ 则你失败，随后这个点上的数变为 $0$ 。

求你是否可以走到 $x$ 并不失败。

多组数据

$n\leq 2\times 10^5$

$15s,256MB$

Sol

向 $x$ 加入一个儿子，权值为 $\infin$ 。则问题变为是否能经过所有点且不失败。

将每个数表示成 $(-a,+b)$ 的形式，表示到达这个点先 $-a$ 再 $+b$ 。

考虑如何比较两个数哪个更优。根据贪心可以发现 $b>a$ 的优于 $b\leq a$ 的，对于所有 $b>a$ 的，可以发现 $a$ 更小的放在前面更优。对于 $b\leq a$ 的，倒过来考虑，可以发现 $b$ 更大的放在前面更优。

考虑当前最优秀的一个数，显然选择它父亲后下一步会选择它。因此可以将它与它父亲合并乘一个数。这样一直合并直到只剩一个数即可。此时有解当且仅当 $a=0$ 。

复杂度 $O(n\log n)$

G. History course

不会

H. Chain & Co

Problem

在三维空间中有 $n$ 个正方形框架，框架的宽度不计，没有两个框架相交且每个框架的所有边都与 $x,y,z$ 轴中的一个平行，所有框架大小相同。

你需要求出是否可以将这些框架分成两组，使得从两组中分别选出一个框架，这两个框架都不是分离的。

多组数据

$n\leq 10^6$

$10s,256MB$

Sol

可以将框架分成三种：与 $Oxy$ 平行的，与 $Oxz$ 平行的，与 $Oyz$ 平行的。

可以发现同一类中的两个框架一定是分离的，所以同一类的必须在同一组中。

因此此时只有三种方案。考虑对于每两种框架，求出在两种中各选一个，是否它们都不分离。

考虑固定了两种框架，设框架大小为 $l$ ，可以发现，两个框架不分离当且仅当一个框架的左下角在另外一个框架左下角的 $2l\times l\times l$ 的区域内。因此求出所有区域的交即可。

复杂度 $O(n)$

J. Captain Obvious and the Rabbit-Man

Problem

定义序列 $F_i:F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2}$ 。

给定 $k$ ，定义序列 $v_i:v_i=\sum_{j=1}^kc_iF_j^i$ ，其中 $c_i$ 为整系数。

给出质数 $p$ ， $v_{1,...,k}\bmod p$ ，求 $v_{k+1}\bmod p$

保证 $F_{1,...,k}$ 模 $p$ 两两不同余

多组数据

$k\leq 4000$

$5s,512MB$

Sol

可以发现 $v$ 是一个 $k$ 阶线性递推，且特征根方程的所有根为 $F_1,...,F_k$ 。因此特征根方程的为 $(x-F_1)(x-F_2)...(x-F_k)=0$

先暴力求出特征根方程的系数，然后可以 $O(k)$ 推出下一项。

复杂度 $O(k^2)$

2014-2015 ACM-ICPC, Central Europe Regional Contest

A. Parades

Problem

给一棵 $n$ 个点的树，每个点度数不超过 $k$ 。有 $m$ 条路径，你需要选出若干条路径，使得选出的路径边不相交。求最多能选出多少条路径。

多组数据

$n\leq 1000,k\leq 10,m\leq \frac{n(n-1)}2$

$2s,512MB$

Sol

考虑dp，设 $dp_i$ 表示 $i$ 子树内能选出的最大路径数。为了转移再记录 $f_{i,j}$ 表示 $i$ 子树内，不能选 $j$ 到 $i$ 的最大路径数。

考虑 $u$ 点上的转移。枚举每一条以 $u$ 为 LCA 的路径，设路径为 $i,j$ ，它们分别在 $x,y$ 子树内，假设选了若干条路径，则要求所有的 $x,y$ 互不相同，且这时的路径数为 $\sum_{v\in son_u}dp_v+\sum (f_{x,i}+f_{y,j}+1-dp_x-dp_y)$

可以发现如果 $f_{x,i}+f_{y,j}<dp_x+dp_y$ 则这条路径没有用。又因为 $f_{x,i}\leq dp_x$ ，所以只需要记录是否等于，只有两边都是等于才会使得路径增加1。

然后相当于有若干对 $(x,y)$ ，需要找到最多的对数使得每个 $x$ 只出现一次。这部分是一个二分图最大匹配，范围很小可以直接做。

然后再考虑转移 $f$ ，可以发现这相当于钦定一个点不选的二分图匹配。同样做即可。

复杂度 $O(n^2+nk^22^k)$

B. Mountainous landscape

Problem

给定 $n$ 个点 $(x_1,y_1),(x_2,y_2),...,(x_n,y_n)(x_1<x_2<...<x_n)$ 组成的折线，对于每一个 $i$ ，求出最小的 $j>i$ ，满足射线 $x_ix_{i+1}$ 与线段 $x_jx_{j+1}$ 有交(交点为 $x_jx_{j+1}$ 上端点时认为无交)。

多组数据

$n\leq 10^5$

$4s,512MB$

Sol

考虑如何判断一条直线是否在一条折线的上方。求出这条折线的上凸壳，若直线与凸壳有交且交不是一个点则直线不在折线的上方。

问题相当于对于每个 $i$ ，找到右侧第一条线段，满足直线不在线段上方。

使用线段树，维护每个区间的上凸壳，然后在线段树上二分找。将所有射线按照斜率排序后按顺序线段树二分，则线段树每个点上的询问都满足斜率单调，因此可以均摊 $O(1)$ 询问。

复杂度 $O(n\log n)$

E. Can't stop playing

Problem

给出 $n$ 个数 $v_{1,...,n}$ ，每个数都是 $2$ 的非负整数次幂。有一个初始为空的序列，你会进行 $n$ 次操作，第 $i$ 次操作可以将 $v_1$ 放到序列的任意一侧。若序列中存在两个相邻的相同元素，则这两个元素会合并成一个值等于原来元素值两倍的元素，并继续可能的合并过程。你需要使最后序列中只有一个元素。求出任意一个方案或输出无解。

多组数据

$n\leq 1000,\sum v_i\leq 2^{13}$

$4s,512MB$

Sol

任何时刻如果序列中出现相邻三个元素满足 $a>b<c$，则之后 $a,c$ 只可能变大，因此 $b$ 不可能再合并，这种情况无解。

因此任意时刻序列是单峰的，因为每个元素都是2的非负整数次幂，这样的序列可以使用两个不超过 $\sum v_i$ 的二进制数表示。且总状态数不超过 $(\sum v_i)^2$ 。

因为合并时元素和不变，因此每个状态如果可以达到，则达到它时操作的次数固定。因此dp的总状态数不超过 $(\sum v_i)^2$ 。直接dp并记录转移即可。

复杂度 $O((\sum v_i)^2)$

G. Virus synthesis

Problem

初始有一个空串，每次可以进行如下操作：

1. 向串的一侧加入一个字符
2. 设当前串为 $s$ ，将当前串变为 $ss^r$ 或 $s^rs$ ，其中 $s_r$ 为 $s$ 翻转后的串

给定一个串 $S$ ，求将空串变为它的最小操作次数。

多组数据

$|S|\leq 10^5$

$18s,512MB$

Sol

每次2操作后得到的都是回文串，考虑只记录每次2操作后的结果，对回文串dp。

考虑从回文串 $a$ 开始经过若干次操作1，最后一次操作2变为回文串 $b$ ，存在这样的操作当且仅当存在字符串 $x,y$，满足 $b=xayy^rax^r$ 。

因此相当于存在回文串 $z$ ，满足：

1. $b=xzx^r$
2. $a$ 为 $z$ 的回文后缀，且 $|a|\leq\frac12|z|$ 。

考虑将dp看成最短路的形式，对于第一种情况，相当于对于每一个回文串 $s$ 和字符 $c$ ，连边 $s->csc$ ，边权为1。

对于第二种情况，相当于对于每一个 $a,z$ ，连边 $a->z$ ，边权为 $\frac12|z|-a$ 。

此时一个转移可以看出若干步第一种边后再走一条第二种边。

可能的回文串一定是 $S$ 的字串，建 $S$ 的回文树，只考虑偶回文串，第一类边即为回文树的转移边。

对于第二类边，能转移到 $z$ 的边即为 $z$ 在fail树上的祖先中长度不超过 $\frac12|z|$ 的串。这显然是一段前缀，可以进行树上前缀和优化连边。

然后最短路求出dp，因为合法路径必须以2操作的路径结尾，所以可以在最短路是额外记录一个值。

最后答案即为 $min_sdp_s+|S|-|s|$。

复杂度 $O(|S|\log|S|)$

J. Pork barrel

Problem

给一个 $n$ 个点 $m$ 条边的图，$q$ 个询问，每次给定 $l,r$ ，求出只保留边权在 $[l,r]$ 的边时，得到的边数最大的生成森林的边权和最小值。强制在线。

多组数据

$n\leq 1000,m\leq 10^5,q\leq 10^6$

$15s,512MB$

Sol

显然 $[l,r]$ 边的最小生成森林的边为 $[l,+\infty]$ 边的最小生成森林中边权不超过 $r$ 的所有边。

将边排序从大到小加入，使用LCT维护最小生成树。这样即可维护每一个 $l$ 的最小生成树。

然后使用主席树维护边权的变化即可在线询问。

复杂度 $O((n+m+q)\log (n+m))$

K. The Imp

Problem

有 $n$ 个物品，第 $i$ 个的价值为 $v_i$ ，费用为 $c_i$ 。两人进行博弈：

第一个人可以选择一个物品（也可以不选择直接结束），支付 $c_i$ 的费用，此时第二个人可以：

1. 删去第一个人买的物品，之后让第一个人重新操作。这种操作最多进行 $k$ 次。
2. 不操作，此时游戏结束，第一个人的收益为最后选择物品的 $v_i$ 减去过程中所有选择的物品的 $c_i$ 的和。

第一个人希望最大化收益，第二个人希望最小化收益。求双方最优策略时的收益。

多组数据

$n\leq 1.5\times 10^5,k\leq 9,0\leq a_i,c_i\leq 10^6$

$5s,512MB$

Sol

问题可以看成第一个人选一个长度为 $k+1$ 的序列 $a_{1,...,k+1}$，第二个人选一个 $i$ 使得 $v_{a_i}-\sum_{j=1}^{i-1}c_{a_j}$ 最小。最后的收益即为这个值。

对比相邻元素可以发现，此时将第一个人的序列按照 $v_i$ 从小到大排序最优。

因此可以将所有物品排序后从后向前 $dp$，设 $dp_{i,j}$ 表示后 $i$ 个元素选 $j$ 个的最大收益，转移显然为 $dp_{i,j}=\max(dp_{i+1,j},min(v_i,dp_{i+1,j-1}-c_i))$，最后的答案即为 $dp_{1,k+1}$。

复杂度 $O(nk)$

L. Outer space invaders

Problem

有 $n$ 个事件，第 $i$ 个事件的出现时间为区间 $[l_i,r_i]$，它有一个权值 $v_i$。

你可以在任意时刻选择一个正整数 $v$，花费 $v$ 的代价，完成当前存在且权值不超过 $v$ 的所有事件。

求让所有事件都完成需要的最少代价。

多组数据

$n\leq 300,1\leq l_i,r_i,v_i\leq 10^4$

$5s,512MB$

Sol

首先对时间离散化，此时只剩 $O(n)$ 个时间点。

设 $f_{l,r}$ 表示完成在时间区间 $[l,r]$ 内的所有事件的最小代价。考虑区间中权值最大的事件，一定会进行一次操作完成这个事件。此时所有经过操作时间点的事件都会被完成，因此剩余的问题为两个子问题。使用记忆化搜索dp即可。

复杂度 $O(n^3)$

2015-2016 ACM-ICPC, Central Europe Regional Contest

C. Cow Confinement

Problem

给一个 $10^6\times 10^6$ 的网格，有 $k$ 个栅栏，每个栅栏的形状为一个矩形的边界。任意两个栅栏没有公共点。

有 $n$ 头牛和 $m$ 朵花，每头牛只能向右或下走，且不能经过栅栏。求出每头牛能到达的花的数量。

$n,m,k\leq 2\times 10^5$

$3s,512MB$

Sol

对于每个栅栏内的情况分开做，先做一遍扫描线+线段树求出所有东西分别被哪个栅栏包含，这部分为 $O(n\log n)$。

然后只需要考虑一个栅栏的情况，它内部的栅栏都可以看成实心障碍。

考虑从每一朵花的位置反向走，考虑一直向左，在不能向左的时候向上得到的路径，以及一直向上，在不能向上的时候向左得到的路径。

因为障碍没有公共点，这两条路径不会交错，因此这两条路径中间的部分除去障碍都是能走到的。

对向左的路径的下方减一，向上的路径右方减一，再对右下角减一，整体加一。则此时只有能走到的部分有加一。

分别处理四种情况。后两种非常简单。对于向左的路径，从右向左扫描线，维护扫描线右侧的所有花的位置开始向左走到这里的位置的权值线段树。显然加入一个障碍时相当于区间内的所有数全部移到一个端点的一侧。因此可以在 $O(n\log n)$ 的时间内维护这个变化。询问一个位置单次显然是 $O(\log n)$，另外一种情况同理。

复杂度 $O(n\log n)$

E. Export Estimate

Problem

给一张 $n$ 个点 $m$ 条边的简单图，每条边有边权 $v_i$ 。

给 $q$ 个询问，每次给定 $x$ ，每次进行如下操作：

1. 删去所有边权小于 $x$ 的边。
2. 删去所有度数为 $0$ 的点。
3. 如果当前有一个度数为 $2$ 且这两条边不是自环的点，则删去这个点并将这两条边连成一条边。重复执行这一步操作直到不存在合法的点。

求出操作后图的点数和边数。询问之间独立。

$n,m,v_i,q\leq 3\times 10^5$

$2s,512MB$

Sol

通过记录每个点相邻的边中边权最大的 $3$ 条边，可以通过前缀和求出不进行最后一步的边数。

如果所有 $2$ 度点都能被缩，则每个 $2$ 度点会使点数和边数减一。唯一不能缩完的情况是存在一个由 $2$ 度点组成的环。

只考虑每个点边权最大的两条出边，通过dfs可以找出可能出现的由 $2$ 度点组成的环。

复杂度 $O(n+m+q+\max v_i)$

F. Frightful Formula

Problem

有一个 $n\times n$ 的矩阵 $v$ ，给定 $v$ 第一行和第一列的值，对于剩余的部分，有：

$v_{i,j}=a*v_{i,j-1}+b*v_{i-1,j}+c$

求出 $v_{n,n}$，答案模 $10^6+3$

$n\leq 2\times 10^5$

$3s,512MB$

Sol

首先考虑算出第一行第一列每个数对 $v_{n,n}$ 的贡献，可以看成向右走一步权值为 $a$ ，向下走一步权值为 $b$。则可以发现贡献形如 $a^xb^yC_{x+y}^y$，因此这部分可以在 $O(n)$ 时间内算出。

然后算出每个 $c$ 对答案的影响，这部分为：

$c*\sum_{i=0}^{n-2}\sum_{j=0}^{n-2}a^ib^jC_{i+j}^j$

然后写个MTT就可以做完了

考虑看成倒过来走，则变为从 $(n,n)$ 向左向上走若干步，不能经过第一行第一列。

算出走不超过 $2n$ 步的方案数减去出界的方案数。因为出界就再也不能走回来，枚举出界的位置，可以发现出界之前的方案是一个组合数，出界后就没有其他限制，没有限制走若干步的方案可以递推。

复杂度 $O(n)$

G. Greenhouse Growth

Problem

有一个长度为 $n$ 的序列 $v_i$ ，进行 $q$ 次操作，每次操作为以下两种之一：

1. 从左向右依次考虑每个位置 $i$ ，如果 $v_i<v_{i-1}$，则让 $v_i$ 加一。
2. 从右向左依次考虑每个位置 $i$ ，如果 $v_i<v_{i+1}$，则让 $v_i$ 加一。

求出操作后的序列。

$n,q\leq 3\times 10^5$

$2s,512MB$

Sol

维护所有 $v_i$ 相同的连续的段以及相邻两段的差。

对于一次1操作，如果一段满足这一段左右的值都大于它，则这一段与下一段的差会减少1，一段满足这一段左右的值都小于它，则这一段与下一段的差会减少1。

对于一次2操作，可以得到类似的答案。

可以求出每一对相邻的段在两种操作时差会不会减少。在两种操作的时候，可以找出所有差变为0的段，此时合并两段，并修改左右段的差的情况。

复杂度 $O(n\log n)$

I. Ice Igloos

Problem

给 $n$ 个圆，第 $i$ 个圆的圆心为 $(x_i,y_i)$，半径为 $r_i$。其中 $x_i,y_i$ 都是整数。

$q$ 次询问，每次给定一条线段，求与这条线段有交的半径个数。

所有圆圆心不同

$n,q\leq 10^5,0\leq x_i,y_i\leq 500,r_i\leq 1$

$10s,512MB$

Sol

因为 $r_i\leq 1$ ，与一条线段可能有交的圆心位置只有 $O(x+y)$ 个。

枚举圆心的 $x$，可以得到可能的 $y$ 区间，然后直接枚举即可。

复杂度 $O(q(x+y))$

J. Juice Junctions

Problem

给一个无向图，每个点度数不超过 $3$ ，求所有点对间最大流之和。

$n\leq 3000,m\leq 4500$

$7s,512MB$

Sol

显然最大流等于最小割。

最大流等于 $0$ 的情况非常简单，考虑一个连通块的情况。

取一棵生成树，考虑边双的做法，将所有非树边对应的树上路径覆盖。只留下树边中被覆盖的边，则此时还连通的点对最小割大于等于 $2$ ，否则为 $1$。

考虑什么时候最小割等于 $2$，第一种情况为割一条树边和割一条非树边的情况，可以发现此时割掉的树边一定是覆盖一次的边，且这些边都可以被割掉，因此可以分出这种情况下最小割为 $2$ 的点对。

第二种情况为割两条树边。此时两条树边分出了三部分，这种情况下只需要考虑中间部分和剩余部分被分开的情况。

枚举一条边 $a$ ，让另外一条边不在 $a$ 的子树中，考虑一个点在子树中的情况。考虑所有 $a$ 子树内连向 $a$ 子树外的边，另外一条边割去后与 $a$ 相连的部分不能有这些边的另外一个端点。此时找到以 $a$ 为根它们的LCA，一定需要割去LCA的子树。此时相当于能割掉的边只可能在一条链上。

同时，还需要满足不考虑 $a$ 子树内连向 $a$ 子树外的边和 $a$ 子树内，割去这条边后能把两部分隔开。这个可以直接打标记解决。

因为一个点在子树中，只需要求出可能在中间部分的点。只需要找到最远的一条合法的割边，然后相当于子树内的点到中间区域的点最小割都是 $2$。枚举每个中间的点，然后对 $u$ 打标记，最后将标记下传。

同时，再对另外一条边在 $a$ 的子树中的情况使用相同的方式找出中间部分，这部分打标记的区间为dfs序的一段前缀和一段后缀，可以前缀和+后缀和解决。

最后所有没有被标记的点对最小割都是 $3$！!1

复杂度 $O(nm)$

L. Looping Labyrinth

Problem

给一个 $n\times m$ 的模板网格，其中有一些格子为障碍，剩余位置可以通过。

有一个无限大小的二维网格，其中位置 $(x,y)$ 的状态等于模板中 $(x\bmod n,y\bmod m)$ 位置的状态。

给定 $q$ 个询问，每次给一个空位 $(x,y)$，求出从 $(0,0)$ 是否能到达 $(x,y)$

$n,m\leq 100,q\leq 2\times 10^5$

$3s,512MB$

Sol

考虑在模板上加入若干条边，其中 $(a,m)$ 向 $(a,1)$ 连边权为 $y$ 的有向边，反向边权为 $-y$， $(1,b)$ 向 $(m,b)$ 连边权为 $x$ 的有向边，反向边权为 $-x$，将这两条边看成一条无向边，图中原先的边边权为 $0$ 。

可以发现，能到达 $(a,b)$ 当且仅当存在一条路径以 $(a\bmod n,b\bmod m)$ 结尾且路径上的边权和为 $\frac{a-(a\bmod n)}nx+\frac{b-(b\bmod m)}my$

首先将边权为 $0$ 的边缩起来，并删去与原点不连通的所有部分。此时只剩下 $O(n+m)$ 个点和边。

取出图的一棵生成树，考虑剩余的每条非树边在树上组成的环。可以发现，所有从原点出发到自己的路径都可以表示为这些环的一个线性组合。因此求出每个环的边权和。而从原点出发到一个点的路径可以表示为原点到这个点的树上路径加上所有环的线性组合。因此问题变为给定 $O(n+m)$ 个二维向量，询问一个向量是否能被这些向量通过线性组合表示。

可以发现，对于若干个二维向量，一定存在 $a,b,c$，使得 $ax+by,cy$ 两个向量通过线性组合表示的向量集合等于给定的二维向量能表示的向量集合。

考虑加入一个向量 $cx+dy$，先将 $ax+by,cx+dy$ 做 $x$ 维上的辗转相除，可以得到两个向量 $a^{'}x+b^{'}y,c^{'}y$。然后再对两个 $y$ 上的向量做gcd即可。最后询问显然可以 $O(1)$ 求出。

复杂度 $O(nm+q)$

2016-2017 ACM-ICPC, Central Europe Regional Contest

B. Bipartite Blanket

Problem

给一个两边分别有 $n,m$ 个点的二分图，每个点有点权，求出有多少个点集满足：

1. 点权和大于等于 $k$
2. 存在一个二分图的匹配，使得点集中的每个点都在匹配中

$n,m\leq 20$

$1.5s,512MB$

Sol

若一个点集满足条件2，则一定满足点集中左侧点部分存在一个到右侧点的完美匹配，右侧点部分同理。

如果一个点集满足这两个条件，考虑在第一个匹配中从左侧向右侧匹配点连边，在第二个匹配中从右侧向左侧匹配点连边。这样得到了一个每个点入度出度不超过 $2$ 的二分图。

如果图中存在一个长度大于 $2$ 的链，则显然端点不在点集中，一定可以将链换为若干个长度为 $2$ 的环。

如果图中存在一个长度大于 $2$ 的环，则因为它是二分图，可以将它换成若干个长度为 $2$ 的环。

此时得到的都是长度为 $2$ 的环，因此可以合并为一个匹配。因此满足这两个条件的点集就是合法的。

此时一个点集合法只需要点集中左侧点部分合法且右侧点集合法。由Hall定理，左侧一个点集存在完美匹配当且仅当任意子集满足右侧与这个子集相邻的点集大小大于等于子集大小。可以先求出每个集合是否满足与这个子集相邻的点集大小大于等于子集大小，然后再fwt即可对于所有点集求出是否存在完美匹配。

然后将左右两侧合法的点集按照权值大小分别排序，然后扫过去即可。

复杂度 $O(n*2^n+m*2^m)$

D. Dancing Disks

Problem

有一个 $6\times 6$ 的柱子矩阵，初始时左上角的柱子上放了 $n$ 个大小不同的盘子。你可以进行若干次操作，每次选出一根柱子以及上面的若干个盘子，你可以将这若干个盘子拿出，翻转顺序，再放入它正下方或正右方的柱子。

你需要在操作后，所有盘子都在右下角的柱子上，且此时所有盘子按照大小排好了序。给出初始柱子上从上到下盘子的大小，求出一个方案。
$n\leq 4\times 10^4$

$1.5s,512MB$

Sol

考虑将若干个盘子在 $(x,y)$ 位置从小到大排序，可以先将盘子分成若干类，在所有的 $(i,j)(i\leq x,j\leq y,(i,j)\neq (x,y))$ 处从大到小排序。然后再通过多路归并的方式合并到 $(x,y)$ 上。从大到小的方式类似。

考虑这样能排序多少个位置。设 $f_{i,j}$ 表示 $i$ 行 $j$ 列能排序多少个盘子，则有：

$f_{1,1}=1,f_{x,y}=\sum_{i\leq x,j\leq y,(i,j)\neq (x,y)}f_{i,j}$

可以得到 $f_{6,6}=26928$。但注意到通过特判 $f_{1,2},f_{2,1}$ 的情况，这两种情况都可以做到排序两个盘子。

此时可以得到 $f_{6,6}=42960$。因此使用这种方式可以通过。

复杂度 $O(n)$

E. Easy Equation

Problem

给定 $n,k$，找到 $n$ 个正整数三元组 $(a,b,c)$ ，满足：

$a^2+b^2+c^2=k(ab+bc+ca)+1$

且每个数最多在所有三元组中出现一次，所有数不能超过 $10^{100}$。

$2\leq n,k\leq 1000$

$0.5s,512MB$

Sol

首先可以得到一个初始解 $a=1,b=k,c=k^2+k$。

考虑对这个解进行迭代，设 $a<b<c$ ，固定 $b,c$ ，可以发现 $a^2-k(b+c)a+b^2+c^2-kbc-1=0$

因此另外一个解为 $a^{'}=k(b+c)-a$ ，因此可以直接迭代。

但直接迭代的解位数达到 $1000$ 位以上，注意到也可以对 $b$ 进行迭代，得到的数不会变小。因此通过bfs的方式，每次对一组解的最小两个数迭代，如果与之前的解不同则算入解。此时的位数非常小但仍然需要高精。

复杂度 $O(n)$

G. Geohash Grid

Problem

定义 $f(x,y)=f(\lfloor\frac x2\rfloor,\lfloor\frac y2\rfloor)*4+(y\bmod 2)*2+(x\bmod 2)$，即将 $x,y$ 的二进制表示交替写下的结果。

给一个 $2^n\times 2^n$ 的矩阵，其中第 $i$ 行第 $j$ 列的值为 $f(i,j)$，这里行列从 $0$ 开始编号。显然编号是不重复的。

给一个 $m$ 个点组成的多边形，每条边平行于坐标轴。

给出 $q$ 个询问，对于每一个询问，给出 $k$ ，你需要找到不超过 $k$ 个区间，满足：

1. 对于每一个多边形内部的位置，它的值都被至少一个区间包含。
2. 这些区间中包含的整数数量尽量小

求出这些区间中包含的最小整数数量。

$n\leq 30,m\leq 200,q\leq 10^5$

$2.5s,512MB$

Sol

将多边形内的点标为 $1$ ，剩余标为 $0$。

求出所有两侧都有 $1$ 的极长 $0$ 段的长度，显然选 $k$ 个区间的最优解是少选最长的 $k-1$ 个极长 $0$ 段。因此只需要求出这些 $0$ 段的长度。

考虑类似四分树的做法，将矩阵分成四份，显然每一份中值的大小为一段连续区间。因此可以求出每一份内的极长 $0$ 段以及每一份中最小和最大的 $1$ 位置值，然后合并，在当前区域全0或全1时停止。

但如果给出一个 $1\times 2^n$ 的矩形，四分树的复杂度就是 $O(2^n)$ 的。

在分治过程中，可以只维护所有的边界。如果边界中只包含横向边或只包含纵向边，则此时分出的四个部分中横向/纵向部分一定相同，只有 $2$ 种不同的部分，可以将相同的部分合并，递归一次并将求出的每一个极长 $0$ 段的次数乘 $2$，可以将乘 $2$ 的系数放在分治过程中。且若两部分都不是全 $0$ 或全 $1$ ，则这些边界一定分成了两部分。否则只用递归一部分或不用递归。

因为只有 $m$ 个顶点，只要区域内没有顶点就一定只包含一种方向的边，因此会分出 $O(nm)$ 个这样的区域。每个区域向下递归最多再分 $m$ 部分，每部分只会递归 $n$ 步，因此总的复杂度为 $O(n^2m^2)$

然后询问前缀和预处理+二分即可。

复杂度 $O(n^2m^2+q\log n^2m^2)$

I. Invisible Integers

不会

J. Jazz Journey

Problem

有 $n$ 个城市，你想要通过飞机进行一个长度为 $m$ 的旅行，给出旅行的每一个点 $a_1,a_2,...,a_n$，你会依次经过每个点，且你一定会乘坐直达的飞机。

有 $m$ 种机票，第 $i$ 种机票从 $a_i$ 到达 $b_i$ ，价格为 $c_i$ ，它还有一个种类 $t_i$：

若 $t_i=1$ ，则这张机票只能从 $a_i$ 到 $b_i$ 一次。

若 $t_i=2$ ，则在使用机票从 $a_i$ 到 $b_i$ 后，还可以再使用一次从 $b_i$ 到 $a_i$ ，但必须先从 $a_i$ 到 $b_i$ 。

求出完成旅行的最小花费或输出无解。

$n,m,d\leq 3\times 10^5$

$2.5s,512MB$

Sol

显然只需要考虑每一对 $(a,b)$ 之间的情况，可以使用map处理出每一对之间四种机票的最小费用和这两点之间的旅行。

可以用 $t_i=2$ 的票替代 $t_i=1$ 的票。现在问题变为，给出一个 $ab$ 组成的序列（ $a$ 代表一个方向的旅行，$b$ 代表另外一个方向），给出子序列 $a,ab,b,ba$ 的代价，你需要将序列划分成若干个这样的子序列使代价和最少。

初始全部使用单程票，然后考虑加入双向的票，此时问题变为分别给出匹配 $ab,ba$ 的收益，你需要在序列中匹配若干个 $ab,ba$ ，每个字符只能匹配一次，求出最大收益。显然最大的匹配对数一定是两种字符中出现次数最少的一种的出现次数。

可以发现，若钦定一个方向，先贪心匹配这个方向尽量多的对数，然后再贪心匹配另外一个方向，这样一定能匹配完。因此先贪心匹配收益大的方向，这样一定能让总收益最大。

复杂度 $O((n+m)\log n)$

L. Lost Logic

Problem

有一个 $n$ 个变量的 2-SAT 问题，给出这个问题唯一的三组解，求出一个限制不超过 $m$ 条的 2-SAT 问题，满足它只有这三组解或输出无解。

$n\leq 50,m=500$

$0.5s,512MB$

Sol

根据在三组解中的值，可以发现只有 $8$ 种不同的变量。

考虑求出每一种变量有没有出现过，每种变量只留下一个。然后贪心加入所有满足条件的限制。如果此时解的数量大于 $3$ 显然无解，否则可以得到此时的解。这部分限制不超过 $8*8*2*2$ 个。

对于每种剩下的变量，考虑加入 $x->y,y->x$ ，则这两个变量必须相同。因此只需要两个限制即可加入一个变量

复杂度 $O(2^8*8^2+n)$，操作步数不超过 $2n+256$

2017-2018 ACM-ICPC, Central Europe Regional Contest

B. Buffalo Barricades

Problem

有一个网格图，有 $m$ 个关键点。

$n$ 个人依次来到网格图上，第 $i$ 个人的位置为 $(x_i,y_i)$。所有人的横纵坐标不会相同。

每一个人会从自己位置向左，向下放栅栏，一直碰到别的栅栏或边界为止。定义这个人所在的区域为它的栅栏内部的连通块。

对于每个人，求出它到达时它所在的区域中的关键点数。

$n,m\leq 3\times 10^5$

$5s,512MB$

Sol

首先考虑求出最后每个人区域内的点数，从右向左扫描线，维护当前线上的每个位置属于哪个人。显然每个人只会占一段区间，使用set维护分界点，很好维护加入人和计算关键点的操作。这部分复杂度 $O(n\log n)$

然后考虑算出真正的答案，对于每个点，它加入时会减少原先包含这个点区域的点的答案。显然此时包含这个点的点为它右上角加入时间大于它的最小点。使用set维护支持在中间加入点的单调栈即可求出这个值。这部分复杂度也是 $O(n\log n)$

然后按照时间顺序计算答案即可。

复杂度 $O(n\log n)$

C. Cumulative Code

Problem

给一棵深度为 $k$ 的满二叉树，点 $i$ 的两个儿子为 $2i,2i+1$，根编号为 $1$。求出它的prufer序（每次删编号最小的叶子，每次删去点的父亲编号形成的序列），设序列为 $v$。

$q$ 次询问，每次给定 $a,b,c$ ，求出 $\sum_{i=0}^{c-1}v_{a+ib}$

$k\leq 30,q\leq 300,a\leq b$

$7s,512MB$

Sol

首先考虑构造prufer序的过程，考虑两种情况：

1. 一个深度为 $k$ 的满二叉树，根向父亲有连边（即根最后被删去），此时因为左子树任意编号小于右子树最小的叶子编号，因此一定是先做左子树深度为 $k-1$ 的情况 $1$ ，然后是右子树深度为 $k-1$ 的情况 $1$ ，最后删去根。
2. 一个深度为 $k$ 的满二叉树，根向父亲无连边，此时先删左子树，再删根再删右子树，因此为先做左子树深度为 $k-1$ 的情况 $1$ ，然后删去根，最后是右子树深度为 $k-1$ 的情况 $2$ 。

因此可以在 $O(k)$ 的时间内找到prufer序中一个位置对应原来的点，这样的复杂度为 $O(ck)$

再考虑一个 $dp$ ，设 $f_{i,j}$ 表示情况 $1$ 中一个深度为 $i$ 的满二叉树构造的prufer序中，所有编号模 $b$ 余 $j$ 的位置的值的和。

dp过程中，根的值可能会变，但可以注意到若根的权值为 $x$ ，则任意的 $f_{i,j}$ 都可以表示为 $ax+b+c\lfloor\frac x2\rfloor(c\in\{0,1\})$ 的形式。只需要维护这个形式即可。

考虑 $f$ 的转移，情况 $1$ 中为先做左子树再做右子树，最后做根。因此将 $f_{i-1}$ 中的 $x$ 换为 $2x$ 可以得到左子树的情况，将 $x$ 换为 $2x+1$ 可以得到右子树的情况，然后可以 $O(b)$ 合并。因此可以 $O(bk)$ 求出所有 $f$。

然后再设 $g_{i,j}$ 表示情况 $2$ 中一个深度为 $i$ 的满二叉树构造的prufer序中，所有编号模 $b$ 余 $j$ 的位置的值的和。此时 $g$ 可以表示为 $ax+b$ 的形式。它的转移与 $f$ 类似。

因为 $a\leq b$ ，计算的一定是位置编号模 $p$ 余 $a$ 的一段前缀。因此在二叉树上向下找到前缀的结尾节点，然后一次计算左侧的所有子树的贡献即可。

这样的复杂度为 $O(bk)$，因为 $bc\leq 2^k$ ，因此综合两种方式，单次询问复杂度为 $2^{\frac k2}k$ ，总复杂度为 $O(qk2^{\frac k2})$

D.Donut Drone

Problem

给一个 $n\times m$ 的矩阵，矩阵的两维都是循环的，每个格子有一个权值。

有一个人初始在 $(1,1)$ ，他每次走一步会走到下一列中与它的横向距离不超过 $1$ 的三个位置中权值最大的位置。

给出 $q$ 次操作，每次操作为以下两种之一：

1. 修改一个位置的权值
2. 让这个人走若干步，求出他现在的位置。

保证任何时刻一个位置向后的三个位置不会出现权值相同的情况。

$n,m\leq 2000,q\leq 5000$

$5s,512MB$

Sol

显然一次修改最多改 $3$ 个位置的出边，因此可以维护每个点出边构成的基环树森林。

使用lct维护一棵有根树，并维护根是否有一条环边。在link和cut的时候判断是否有新的环边或者一条原来的环边变成了树边的情况。然后移动的时候判断是否会到根，到根之后在环上走即可。

复杂度 $O((nm+q)\log nm)$ 比Yazid的棋好写三倍

E. Embedding Enumeration

Problem

给一个 $n$ 个点的树，你需要将每个点映射到 $2\times n$ 的网格上的一个点，使得映射满足：

1. 点 $1$ 映射到 $(1,1)$
2. 树上不同的点映射到网格上不同的点
3. 树上相邻的点对应的点在网格上相邻

求出映射的方案数，模 $10^9+7$

$n\leq 3\times 10^5$

$1s,512MB$

Sol

考虑从 $1$ 到映射中最靠右的点构成的一条链，可以发现，树上除去这条链外，每个点最多有一个支链，每条支链只可能在分出去时分叉一次（ $1$ 的支链不能在分叉），否则无解。

考虑找出这条链，考虑所有度数为 $3$ 的点（有度数大于 $3$ 的显然无解），此时除了最后一个度数为 $3$ 的点有多种情况，其余支链上度数为 $3$ 的点都可以按顺序找到。

考虑 $dp$ ，可以发现每个度数为 $3$ 的点处的情况只有以下几种（其中 .... 表示主链上部分， .. 表示支链部分：

....---x---....    ....---x---....    ....---O           ....---x---....    ....---x---..
       |                  |                  |                  |                  |
  ..---O                  O---..        ..---X---....      ..---O---..        ..---x---....

如果决定了每一个点的情况，那么最后的方案数只需要计数每一对相邻的点间的方案数，因此可以设 $dp_{i,j}$ 表示第 $i$ 个度数为 $3$ 的点状态为 $j$ 时前面的方案数，转移可以做到 $O(1)$。

最后讨论结尾的若干种情况即可。

复杂度 $O(n)$

I. Intrinsic Interval

Problem

给一个长度为 $n$ 的排列， $q$ 次询问，每次给出一段区间，求出包含这段区间的长度最小的连续段。

$n,q\leq 3\times 10^5$

$2s,512MB$

Sol

显然在析合树上求出区间端点的LCA后根据LCA是析点还是合点分别判一下即可，可以做到 $O(n)$ 甚至 $O(n\log n)$。

考虑一个相对简单的做法，注意到如果两个连续段相交但不包含，则它们的交也是连续段。因此对于一个询问 $[l,r]$，只需要找到最大的 $i\geq r$ ，使得存在一个以 $i$ 结尾且包含 $[l,r]$ 的连续段，则以 $i$ 结尾一定是最优的。

首先求出 $r_i$ 表示以 $i$ 结尾的连续段最小的开头，因为连续段满足 $\max-\min=r-l$，且非连续段一定取大于，可以单调栈维护max和min，在线段树上找最小值即可 $O(n\log n)$ 求出。

然后可以对于每个询问找到答案的结尾 $r$ ，再做一遍上面的做法，在每个 $r$ 出枚举所有结尾为这个位置的询问，只需要找到 $l$ 左侧第一个合法的左端点即可，这个也可以线段树上求。

复杂度 $O(n\log n)$

K. Kitchen Knobs

Problem

给 $n$ 个长度为 $7$ 的数字串，你可以进行若干次操作，每次你可以将一个区间内的串循环位移相同数量的位。

你需要使得每个串都取到所有它循环位移串中字典序最大的串，求最少操作次数。

$n\leq 501$

$2s,512MB$

Sol

如果一个串的循环节为 $1$ ，则这个串无论如何都是最优，可以直接删掉。

否则，这个串循环节一定为 $7$ ，因此只存在一个最优解。因此可以看成一个长度为 $n$ 的串，你可以将一段区间内的数加上一个值，使得所有数都是 $7$ 的倍数。

考虑差分，那么相当于有 $n$ 个数，每次选择两个数以及一个 $k$ ，让一个加 $k$ 另外一个减 $k$ ，使所有数都是 $7$ 的倍数。

考虑将操作过的两个数连边，显然一个连通块内所有数和是 $7$ 的倍数，且一个大小为 $m$ 的连通块至少需要 $m-1$ 步操作。

因此可以看成将这些数划分成最少个数的集合，每个集合和都是 $7$ 的倍数，可以将所有数看成 $0,1,2,...,6$。显然 $0$ 可以单独分开。

如果一个集合中有两个和为 $7$ ，则将它们分出来更优。如果有两个集合中分别有一个数，它们和为 $7$ ，则可以将这两个数分出来一个集合，两个集合剩下部分合并。这样不会变差。因此存在一个最优解，使得每一对和为 $7$ 的数都被单独分出。

此时最多还剩下 $3$ 种数，可以 $dp$ 求出此时的最优解。

复杂度 $O(n^3)$

L. Lunar Landscape

Problem

给 $n$ 个正方形，第 $i$ 个正方形的中心坐标为 $(x_i,y_i)$，它有两种情况：

1. 它的所有边平行于坐标轴，边长为 $r_i$
2. 它的所有边与坐标轴夹角为 $45$ 度，对角线长为 $r_i$

求出它们的面积并。

$n\leq 2\times 10^5,|x_i|,|y_i|,r_i\leq 1000,2|r_i$

$2s,512MB$

Sol

首先考虑只有第一种正方形的情况，可以看成在中心位置附近的四个格子分别放一个可以向八个方向扩散 $\frac {r_i}2-1$ 步的点，所有的扩散结束后被扩散到的格子就是被覆盖的格子。

扩散的过程可以使用bfs，记录每个格子上还能再扩散多少步，从大到小做即可。复杂度 $O(n+v^2)$

然后考虑第二种情况，可以看成在中心附近四个位置向四个格子放一个向四个方向扩散 $\frac {r_i}2-2$ 步的点，此时除了边界上不会被这个正方形完全覆盖的格子外都会覆盖了。

然后考虑剩下的部分。只考虑第二种情况覆盖的格子，对于一个没有非覆盖的格子，如果它附近两个连续的方向（例如左上）的格子都在之前被覆盖了，如果这两个格子属于同一个正方形，则可以标记这个格子这个方向的一个角被覆盖了，否则，这个格子四个方向都被覆盖了，则这个格子无论如何都会被完全覆盖，因此也可以标记。最后对每个格子四个方向的标记情况可以算出这个格子被覆盖的面积。

复杂度 $O(n+v^2)$，只需要bfs两次。之前写了个bfs五次的做法然后没跑过去

2013-2014 ACM-ICPC Northeastern European Regional Contest

A. ASCII Puzzle

Problem

$4s,256MB$

Sol

直接写一个dfs，如果当前已经填的部分中有不能被填上的空位就判断无解，然后就能过了。

因为角块已经确定，边块只可能同一对互换，因此可能的状态数只有 $2^4*4!$。因此直接dfs是可行的。

C. Cactus Automorphisms

Problem

给一个 $n$ 个点 $m$ 条边的仙人掌，求有多少个点的排列 $p$，使得图中 $(i,j)$ 间有边当且仅当 $(p_i,p_j)$ 间有边。即计算这个图的自同构数。

你需要输出答案因式分解后的结果。

$n\leq 5\times 10^4$

$4s,256MB$

Sol

对于树的情况，考虑取出重心，对于每个点，只可能整体交换它的儿子。

使用树hash求出每个子树的hash值，对于每个点，如果它两个儿子的hash值相同则可以交换。显然最后交换的方案数为若干个阶乘的乘积。

如果树有两个重心，则还需要计算交换重心的情况。

考虑仙人掌上的情况，建出圆方树，考虑圆方树上做树同构，此时与树hash不同的情况如下：

1. 对于一个方点，它的儿子顺序只能翻转不能打乱。因此计算点hash值时不能对子树hash排序，只能在两种顺序中取一个较小的。
2. 圆点和方点的权值必须不同。
3. 若存在双重心的情况，只有是两个圆点的情况才能互相交换。
4. 若只存在一个重心且重心为方点，则此时需要计算重心所在的环上进行旋转的方案数。这个可以使用 KMP hash求出循环节并算出方案。

显然，最后的答案仍然是若干个阶乘的乘积再乘上1~2个数。对于阶乘的分解可以暴力，复杂度 $O(n\log\log n)$

总复杂度 $O(n\log n)$

D. Dictionary

不会

E. Easy Geometry

我可能会但我不想写

G. Green Energy

Problem

某地的地平线可以看成一条由 $n$ 个点 $(x_i,y_i)$ 组成的折线 $(x_i<x_{i+1})$ 。在这里，太阳光线与水平线的夹角为 $\alpha$ 度，从左向右照射 $(1\leq \alpha\leq 89)$ 。

有 $m$ 个太阳能板，第 $i$ 个可以看成一个高为 $h_i$ 的线段，它只能垂直于水平线放置。

太阳能板和地平线都会遮挡光线，你需要构造一种方案，使得被光线照射到的太阳能板长度和最大。输出最大长度和方案。

$n,m\leq 10^4$

$4s,256MB$

Sol

考虑光线水平的情况。此时的最大长度不会超过太阳能板最高的高度和能照射到的最低高度的差。

最低高度显然为地平线第一个点的高度，最高高度不会超过地平线最高点加上最长的板的长度。

因此答案不会超过所有板长度的和和这个差的最小值。

拿出最高的一块板，考虑贪心放其它的。将第一块板放在第一个点，然后将第二块板放在第一个会被照射到的地平线位置上，剩余同理。然后将最高的板放在最高的位置上。

易证这样放可以取到最优值。在放的过程中记录之前的板的最高高度即可 $O(n+m)$ 的求出方案。

在非水平的情况时，可以通过对坐标做一个变换，得到不改变答案的水平的情况。因此上述做法对于非水平的情况也是正确的。

复杂度 $O(n+m)$

H. Hack Protection

Problem

给一个长度为 $n$ 的序列 $a$ ，求它有多少个非空区间满足区间的xor值等于区间的and值。

$n\leq 3\times 10^5,0\leq a_i<2^{31}$

$4s,256MB$

Sol

枚举右端点，记 $s_i=\oplus_{j=1}^{i}a_j$ ，则 $[i,j]$ 的xor值等于 $s_j\oplus s_{i-1}$。

显然，以 $j$ 结尾的区间，不同的and值最多有 $\log v$ 种，且每一种取值的左端点形成一段区间。

枚举每一个区间，那么相当于询问区间中 $s_j$ 等于某个数的数量。可以使用各种数据结构解决。

复杂度 $O(n\log^2 v)$

I. Interactive Interception

Problem

交互题，给出 $n,m$ ，交互器在 $[1,n],[1,m]$ 中分别选出一个数 $a,b$，有一个数 $x$ 初始等于 $b$。

你可以向交互库进行询问，你可以给出 $l,r$ ，交互库会返回 $x$ 是否在区间 $[l,r]$ 中，随后将 $x$ 加上 $a$。

你可以进行不超过 $100$ 次询问，你需要求出当前 $x$ 的值。

$n,m\leq 10^5$

$4s,256MB$

Sol

考虑二分，设当前时刻为 $t$，找出当前所有未被排除的解中 $at+b$ 的中位数，然后询问 $x$ 是否小于等于中位数。这样期望只需要 $O(\log nm)$ 轮。

记录每个 $a$ 对应的合法的 $b$ ，它一定是一段区间。然后找中位数的过程可以二分。

询问次数 $O(\log nm)$ ，复杂度 $O(n\log^2 nm)$ 。

也可以直接取平均数询问。因为剩余的图形是一个凸包，因此取平均数询问近似于取一条经过凸包重心的直线，它也能在 $O(\log nm)$ 轮求出答案，这样的复杂度为 $O(n\log nm)$ 。

K. Kabaleo Lite

Problem

有 $n$ 个位置，$m$ 个人，$c$ 种颜色。初始时每个位置有一个颜色。

$m$ 个人每个人有一个颜色，每人轮流操作，每个人可以选择一个位置将这个位置的颜色换为自己的颜色。

第一个人胜利当且仅当颜色 $k$ 出现的次数严格最多。求出第一个人所有的可能的操作，使得这样操作后剩下的人无论怎么操作第一个人都必胜。

$n,m,c\leq 10^6$

$4s,256MB$

Sol

对于 $n=1$ 的情况，可以特判。

对于 $n>1$ 的情况，考虑最差操作。考虑让每个其他的人都去覆盖一个颜色 $k$ 的位置。如果最后只剩不超过 $1$ 个颜色 $k$ 则显然无解。否则一定每次都能覆盖一个颜色 $k$ 。

如果此时有解，则可以发现这种情况必胜。可以发现第一个人的操作只会改变两种颜色的出现次数。且是一个增加一个减少。因此可以只记录覆盖后颜色 $k$ 的出现次数和另外的颜色中出现次数最多的两种。

然后可以得到操作后得到的覆盖后颜色 $k$ 的出现次数和另外的颜色中出现次数最多的一种的出现次数。这样即可 $O(1)$ 判断一种操作是否必胜。

复杂度 $O(n+m+c)$

2014-2015 ACM-ICPC Northeastern European Regional Contest

C. Cactus Generator

$3s,256MB$

Sol

首先考虑求出这个仙人掌。因为边数有限，因此暴力模拟的复杂度是对的。可以使用dfs的方式，设 $solve(l,r,v)$ 表示处理字符串 $s_{l,...,r}$ 构成的图，其中所有变量的值为 $v$ 是构造图的过程。除构造这部分外只需要再返回这部分的FL两个点即可。

预处理括号匹配，合并FL节点时使用并查集，这部分的复杂度为 $O(m)$ ，其中 $m$ 为构造出的边数。

然后考虑将其分成最少条数的路径。显然最小路径条数为 $\max(1,\frac{oddcnt}2)$ ，其中 $oddcnt$ 为奇点的数量。

将奇点两两配对，每一对连边。这样得到的图不存在奇点，因此存在欧拉回路。对于一个欧拉回路，将之后加入的边删掉可以得到若干条路径。可以发现这些路径满足题目要求的条件。

因此问题只剩求出一个图的欧拉回路。先从每个点开始dfs，得到从每个点出发的环。然后再从一个环开始，将所有的环拼接起来。

复杂度 $O(n+m)$

D. Damage Assessment

Problem

给一个立体图形。图形中间为长度为 $l$ ，圆的直径为 $d$ 的圆柱体，两侧均为一个半径为 $r$ 的球的球切，满足切面的直径为 $d$ 。

将图形如图摆放，其中圆柱两个上下面的圆心高度差为 $t$ ，将高度不高于下面圆的最低点高度加上 $h$ 的部分称为阴影部分。求出阴影部分的体积，绝对误差不超过 $10^{-2}$。

$1\leq d,l\leq 100$，$r\leq 100,2r\geq d$，所有数字只有两位小数。

$3s,256MB$

Sol

考虑以圆柱体分三部分，对于下面一部分算空的体积，对于上两部分算满的体积。

然后这个体积还是很难算，考虑 Simpson 积分，算截面的面积可以各种分类讨论之后求出，然后直接 Simpson。

复杂度不会证但是跑得挺快的

E. Epic Win!

Problem

两个人在用自动机进行游戏，游戏的操作有三种，称为 $0,1,2$ ，其中 $0$ 胜 $1$，$1$ 胜 $2$，$2$ 胜 $0$。若双方操作相同则这轮平局。

自动机上的每个状态包含这个状态上进行的操作 $v_i$，以及对手这次操作为 $0,1,2$ 时下一个状态的编号 $nt_{i,0/1/2}$。

给出对手的自动机，对手的自动机一共有 $n$ 个点。你需要构造一个不超过 $5\times 10^4$ 个点的自动机，满足若你的自动机以 $1$ 为起始状态，无论对手自动机的起始状态是哪一个，你都能在前 $10^9$ 轮中至少赢 $9.9\times 10^8$ 轮。

$n\leq 100$

$3s,256MB$

Sol

将构造的自动机的每一个状态设为此时对手可能所在的点的集合。起始状态的集合即为全集。

考虑构造一个点集对应的状态的转移。如果对手可能在的点的集合中的 $v_i$ 不同，则这一步操作任意，否则，这一步走能赢对手的 $v_i$ 的操作。

之后根据对手不同操作将点集分成三部分，每一部分作为一个后继状态集合。对于每一个状态递归构造。

若存在对手操作不同的情况，则集合一定会分裂，分裂最多有 $n-1$ 次，因此一定能赢 $10^9-n+1$ 次。

但如果集合一直不分裂，通过构造一些长度不同的环，状态循环的长度可能达到 $10^8$ 级别。

但可以注意到此时操作一定会循环，操作循环节不会超过 $n$ ，因此若对于一个集合向后 $n$ 步都没有分裂，则找出循环节连边即可。

复杂度 $O(n^3)$，点数 $O(n^2)$

G. Gomoku

不会

H. Hidden Maze

Problem

给一棵有边权的树，求出所有长度为奇数的路径的边权中位数之和除以长度为奇数的路径数量的值。

保证树随机生成。生成方式为每次随机一条边，若能加入则加入。

$n\leq 3\times 10^4$

$3s,256MB$

Sol

考虑转成 $01$ 上的问题，相当于初始边权全为 $-1$ ，每次把一条边权改为 $1$ ，求出此时新增的长度为奇数且边权和大于 $0$ 的路径数量。

可以发现，新增的值即为经过这条边且修改后边权为 $1$ 的路径数量。

考虑 $dp$ ，设 $f_{i,j}$ 表示 $i$ 子树内到 $i$ 的路径权值和为 $j$ 的路径数。

在修改一条边时，先在它的所有祖先中减去子树内贡献的 $f_i$ ，然后加上修改后的 $f_i$。

然后考虑算新增的贡献，依次枚举路径的LCA，再枚举子树内的边权和即可计算。

可以发现计算一次的复杂度为以这个点为根子树内最大深度乘以这个点的深度。

通过我不会的证明，可以得到随机情况下这个值为 $O(n\sqrt n)$

复杂度 $O(n\sqrt n)$

I. Improvements

Problem

给一个长度为 $n$ 的排列 $p$，你可以进行若干次修改，每次可以修改一个位置的值，可以将其改成任意实数。

定义序列 $p$ 是合法的，当且仅当考虑所有区间 $(0,p_1),(p_1,p_2),...,(p_{n-1},p_n)$，它们中的任意两个区间要么不相交，要么一个包含另外一个。

求出让它合法的最小修改次数。

$n\leq 2\times 10^5$

$3s,256MB$

Sol

考虑未被修改的部分。可以发现将区间 $(p_i,p_{i+1}),...,(p_{j-1},p_j)$ 替换为区间 $(p_i,p_j)$ 时，若替换前合法则替换后一定合法。因此只保留未被修改的点必须合法。

同时如果将所有被修改的位置都改为与上一个未被修改的位置相同的值，则若只保留未被修改的位置合法，则这个方案一定合法。因此只需要求出可能的最多的未被修改的点数。

使用归纳法可以证明，对于合法的序列，一定满足每个位置都是后缀最大值或后缀最小值。因此它的权值构成一个 > 型。

此时可以发现将原序列翻转后接在原序列后，则每一个这样的序列都对应一个LIS。求这个序列的LIS即可。

复杂度 $O(n\log n)$

2015-2016 ACM-ICPC Northeastern European Regional Contest

B. Binary vs Decimal

Problem

定义一个数是好的，当且仅当它为非负整数，且它的十进制表示是它的二进制表示的后缀。

求出第 $n$ 小的好数。

$n\leq 10^4$

$2s,256MB$

Sol

因为 $2^x|10^x$ ，因此改变十进制的一位只会改变二进制在这之前的位。因此一个数合法当且仅当它的每一个后缀合法。

因此可以枚举答案的位数，维护这个位数上所有可行的后缀。向下一个位数转移时只需要枚举十进制下一位填0还是1，手写高精度即可。

设答案位数为 $v$ ，则直接做高精的复杂度不超过 $O(nv^2)$。可以发现 $n=10^4$ 时 $v=163$。

C. Cactus Jubilee

Problem

给一个 $n$ 个点 $m$ 条边且连通的仙人掌，你需要删去一条边再加上一条不同边，使得得到的图是一个无重边且连通的仙人掌。

输出可能的操作方案数。

$n\leq 5\times 10^4,m\leq 10^5$

$2s,256MB$

Sol

考虑去掉不同边的限制，这时答案会增加 $m$，减去这些值即可。

对图建圆方树，考虑这条边的情况：

首先考虑删去割边的情况，此时两侧不连通，一定需要加边将两部分连接起来。求出两边点数即可。在圆方树上很好维护。

然后考虑删去环上边的情况，此时剩余的图还是一个仙人掌。需要在仙人掌上加一条边。可以发现如果一条边的两个端点在圆方树上的路径经过了方点，则加入这条边时会使图不是仙人掌。否则图还是仙人掌。

删去圆方树上所有方点，方案数即为每个连通块内连边的方案数之和。因为此时的连通块是树，显然一个 $n$ 个点的连通块的方案数为 $\frac{(n-1)(n-2)}2$。

可以发现删去一个环边后只有这个环不再是环，因此此时这个环上的所有圆点会连通。枚举删去边的环，算出将环上点的连通块合并后的方案数即可。

复杂度 $O(n+m)$

D. Distance on Triangulation

Problem

给一个 $n$ 个点的凸多边形以及它的 $n-3$ 条对角线。这些对角线形成了一个凸多边形的三角剖分。

只考虑多边形的边和对角线形成的边。设所有边权都为 $1$ ，$q$ 次询问每次询问两点间最短路。

$n,q\leq 10^5$

$2s,256MB$

Sol

考虑分治。取出一条对角线，这条对角线可以将多边形划分成两部分。分别求出对角线端点到多边形内部的最短路。

对于两个点在两部分的情况，它的最短路一定经过这条对角线的端点。因此可以直接算出它的最短路。

否则，它的最短路如果经过另外一部分，则一定经过这条对角线的端点。因此可以算出这种情况下的最短路，对于不经过另外一部分的情况，它的最短路在这部分内，因此可以分治下去做。

考虑这个图的对偶图，它是一个每个点度数不超过 $3$ 的树。通过一条对角线将其划分成两部分相当于删一条边。可以发现对于 $n$ 个点的数，一定存在一种删边方式使得两部分中较小的部分点数不少于 $\frac{n-1}3$。因此分治只会进行 $O(\log n)$ 层。在每一层中可以枚举每条对角线找到两部分中较小的部分点数最多的对角线。

复杂度 $O(n\log n)$

H. Hypercube

不会

I. Iceberg Orders

Problem

$3s,512MB$

Sol

显然除去输出答案时，不同类订单之间的GP顺序不重要。

考虑维护所有订单的所有权值以及它们的GP，维护当前所有存在的订单的价格种类。对于每一类，维护这一类价格的所有订单按照GP从小到大的一个循环链表。因为每次操作的是GP最少的，操作完它又会变为GP最大的。因此匹配订单后维护GP顺序时只需要将链表头后移一位即可。

通过维护的所有价格种类，可以看成若干次一个订单和一类价格相同的订单匹配的操作。考虑一次这样的操作：

这一类订单构成的循环链表可以看成一个有向环。操作可以看成在上面依次匹配。

首先考虑在环上匹配一轮，此时如果中途订单的量已经变为 $0$ 则提前结束这个过程。此时产生的交易数量的和即为最后输出的数量。因此这部分复杂度正确。

若这一轮结束后订单的量还大于 $0$ ，因为已经产生了环长数量的交易，因此可以以环长相关的复杂度处理匹配。

二分环上匹配的轮数，可以算出匹配若干轮后的交易量。因此可以求出能够完整匹配多少轮。然后再在环上匹配最后的部分即可。可以求出这样匹配完后所有GP的变化情况。

这部分的复杂度为环长乘上 $\log v$，因此设输出条数为 $s$ ，这部分复杂度不超过 $s\log v+s\log m$。

复杂度 $O((m+s)\log m+s\log v)$

J. Jump

Problem

交互题。

有一个长度为 $n$ 的 $01$ 串 $s$ 。保证 $2|n$。

你可以给交互库一个长度为 $n$ 的 $01$ 串 $t$ ，如果 $s,t$ 中相同的位置数量为 $\frac n2$ 或 $n$ ，则交互库会返回相同的位置数量，否则交互库返回 $0$。

你需要在不超过 $n+500$ 次询问中求出 $s$。

$n\leq 1000$

$2s,512MB$

Sol

先随机询问，直到出现非零答案。这里的询问次数期望为 $\frac{2^n}{C_n^{n/2}+1}$，在 $n=1000$ 时期望大约为 $40$ 次。此时可以找到答案或找到一个有一半位置相同的串 $t$。

翻转 $t$ 中的两个位置询问，如果返回 $\frac n2$ 则说明这两个位置一个对一个错。否则说明这两个位置对错相同。

因此对于所有 $2\leq i\leq n$ 都翻转 $1,i$ 进行询问，即可求出所有位置的对错关系。此时根据 $1$ 位置的正确性即可确定 $s$ ，只剩两种可能。两种各询问一次即可。

询问次数期望为 $n+1+\frac{2^n}{C_n^{n/2}+1}$

K. King’s Inspection

Problem

给一个 $n$ 个点 $m$ 条边的有向图，保证 $m-n\leq 20$。求出这张图的任意一个哈密顿回路或输出不存在哈密顿回路。

$n\leq 10^5$

$2s,256MB$

Sol

如果有解，每个点入度出度一定不为 $0$。

考虑取一个生成树，然后通过剩余的边的端点建出虚树。可以发现虚树每条边对应的原树上的链缩起来不影响哈密顿回路。这样之后剩余的点数不超过 $83$，边数不超过 $102$。

然后在图上直接dfs，复杂度 $O(能过)$

L. Landscape Improved

Problem

给一个长度为 $n$ 的正整数序列 $a$ ，你可以进行不超过 $m$ 次操作。

每次操作为选出一个 $i$ 满足 $1<i<n,a_{i-1}\geq a_i,a_{i+1}\geq a_i$ ，然后将 $a_i$ 加一。

求出操作后 $\max a_i$ 的最大值。

$n\leq 10^5,m\leq 10^{18},a_i\leq 10^9$

$2s,256MB$

Sol

考虑二分答案，设当前二分的答案为 $mid$，只考虑 $mid>\max a_i$ 的情况，考虑枚举这个高度所在的位置 $x$。

考虑让这个位置达到最优的最少步数的方案。此时因为需要在 $x$ 位置进行操作，因此 $x-1$ 位置的高度至少需要为 $mid-1$。如果 $a_{x-1}<mid-1$，则需要在 $x-1$ 位置进行操作，因此 $x-2$ 位置的高度至少需要为 $mid-2$，...

因此，考虑找到最大的 $j$ 满足 $j<x,a_j\geq mid-(x-j)$。如果不存在，则上面的过程最后会推出必须在位置 $1$ 操作，这显然不可能。因此这时不存在合法方案。否则，上述过程会在最大的满足条件的 $j$ 处停止。这部分需要的最少操作数即为 $\sum_{i=j+1}^xmid-(x-i)-a_i$。

对于 $x$ 右侧的部分，可以类似的找到最小的 $j$ 满足 $j>x,a_j\geq mid-(j-x)$。如果两侧都合法，则最少操作数为两侧的最少操作数和。

在左侧的情况中，可以发现使得一个 $j$ 满足条件的 $x$ 一定是一段后缀，因此可以预处理+前缀和对于每个 $x$ 求出对应的 $j$ 。对于右侧情况同理。

复杂度 $O(n\log n)$

2016-2017 ACM-ICPC Northeastern European Regional Contest

B. Binary Code

Problem

给 $n$ 个由 01? 组成的串，第 $i$ 个串的长度为 $s_i$。每个串中最多包含一个 ?。

你需要将所有 ? 换成 01 中的一个，使得不存在一个串是另外一个串的前缀。输出任意方案或输出无解。

$n,\sum s_i\leq 5\times 10^5$

$2s,512MB$

Sol

每个串只有一个 ?，因此每个串只有两种可能。

考虑 2-SAT，将所有可能出现的串插入01trie，则若一个串被选中，所有它的前缀和以它为前缀的串都不能被选中，即需要选这些串的另外一种。

因此如果将每个串对应的不选这个串（选另外一个串）对应的点放在01trie上这个串的位置处，然后对于选一个串的点向所有它的前缀和以它为前缀的串连边即可。这部分放在01trie上即为它的祖先和子树。

祖先部分和子树部分可以树上前缀和优化连边。但因为一个串不能连向自己不选对应的点，因此在01trie上的每一个位置中，这个位置上的点可以连向除了自己外其它串不选的点。对于每个点前缀和优化连边即可。

复杂度 $O(\sum s_i)$

C. Cactus Construction

Problem

给一个 $n$ 个点 $m$ 条边的仙人掌，你需要通过如下的操作构造出这个仙人掌：

初始有 $n$ 个图，第 $i$ 个图中只有一个编号为 $i$ 的点。初始时每个点颜色为 $1$，总共有 $4$ 种颜色。有三种可用操作：

1. 将两个图合并，不加入新的边。
2. 对于一个图，将图中所有颜色为 $x$ 的点的颜色改为 $y$。
3. 对于一个图，将图中所有颜色为 $x$ 的点向图中所有颜色为 $y$ 的点连边。

你需要操作结束后，只剩一个图，且图中的边与仙人掌的边相同。点的颜色不做限制。

$n\leq 5\times 10^4$，操作次数不能超过 $10^6$

$2s,512MB$

Sol

首先考虑一棵树的情况，注意到任意子树中只有根会向上连边，因此可以得到一个使用三种颜色的方式：

1. 对于当前子树，将树根颜色改为 $3$ ，然后构造根的所有子树。

2. 将所有子树和根合并，随后执行颜色 $2,3$ 间的连边操作。因为子树中只有树根颜色为 $2$ ，这样连好了树根和所有儿子的边，因此完成了子树内连边。

3. 将图内颜色 $2$ 的点改为颜色 $1$，颜色 $3$ 的点改为颜色 $2$。此时子树中只有树根颜色为 $2$。

考虑将这个方式扩展到仙人掌上，只需要考虑一个环的方式即可。因此可以得到如下方式：

1. 考虑删去环的根（圆方树的上这个环的子树的根）后，构造环上剩余的点形成的链，再将链合并为环。
2. 先使用和之前相同的方式，构造环上所有点除去环之外的子树。
3. 将链的左端点染色为 $3$，右端点染色为 $4$ 。考虑加入链的一个端点的过程，先合并图，做颜色 $2,4$ 间的连边，然后将颜色 $4$ 改为颜色 $1$ ，颜色 $2$ 改为颜色 $4$，即可完成向链加入右端点的过程。
4. 将环上其余点连成链后，合并图，做颜色 $2,4$ 间的连边，做颜色 $2,3$ 间的连边，将颜色 $3,4$ 改为颜色 $1$。此时子树内的边都完成了，且只有根的颜色为 $2$。

复杂度 $O(n)$ ，操作步数 $O(n)$

D. Delight for a Cat

Problem

给定 $n$，有一个长度为 $n$ 的序列，你需要给每个位置染红色或蓝色，使得任意一个长度为 $m$ 的区间中红色不少于 $a$ 个，蓝色不少于 $b$ 个。

给出每个位置染红色和蓝色分别的收益，求出合法且收益最大的方案。保证存在合法方案。

$n\leq 1000$

$2s,512MB$

Sol

记 $s_i$ 表示 $i,i+1,...,i+m-1$ 中的红色数量，相当于限制 $a\leq s_i\leq m-b$。

看成初始时全部选蓝色，则显然将一个位置改为红色相当于将一个区间的 $s_i$ 加一。

因此问题可以看成选一些区间，使得每个位置被覆盖的次数在一个区间之内，且选出区间的权值和最大。

考虑一个网络流模型，建 $n+1$ 个点编号为 $0,1,...,m$，从 $i$ 向 $i+1$ 连边，费用为0。对于一个区间 $[l,r]$ ，连有向边 $(l-1,r)$，流量为1，费用为权值。流这条边看成选了这个区间。以 $0$ 为原点， $1$ 为汇点，进行流量为 $m$ 的网络流。此时 $(i,i+1)$ 边的流量即为 $m$ 减去位置 $i$ 覆盖的次数。

因此问题可以看成所有 $(i,i+1)$ 的边有流量上下界，求这个图的最大费用流。直接求可以通过。

G. Game on Graph

Problem

两人在一个 $n$ 个点 $m$ 条边的有向图上进行游戏。有一个棋子，两人轮流移动，不能动的人输。

第一个人的策略是，优先进行能让游戏无限继续的操作，其次进行能让自己获胜的操作。

第二个人的策略是，优先进行能让自己获胜的操作，其次进行能让游戏结束的操作。

双方知道对方的策略且会执行最优操作。对于每个点，求出这个点上第一个人先手/后手时游戏的结果(先手赢/输/游戏无限进行)。

$n\leq 10^5,m\leq 2\times 10^5$

$2s,512MB$

Sol

将每个点分成两个点，分别代表此时第一个人/第二个人进行操作。问题变为求出每个点的胜负情况。

考虑首先求出每个点出发是否会导致无限进行，显然有：

1. 如果一个点没有出边，则不会导致无限进行。
2. 如果当前第一个人操作，且之后的所有状态不会导致无限进行，则不会导致无限进行。
3. 如果当前第二个人操作，且之后存在一个状态不会导致无限进行，则不会导致无限进行。
4. 否则从这个状态出发会导致无限进行。

初始时标记所有第一种情况的点，然后使用类似bfs的方式，维护所有当前标记了但没有更新它的入边的点，每次取一个这样的点，更新它的所有入边的点的状态，找到所有状态被改变的点。这样的复杂度为 $O(n+m)$

在剩余的点进行游戏时，显然不会导致无限进行，因此不会经过会导致无限进行的点。因此可以删去所有导致无限进行的点，且之后不用考虑无限进行的情况，此时双方的策略都是希望胜利。

然后考虑对于剩余的图求出每个点出发的胜负情况。如果图无环，则可以使用同样的bfs方式求出每个点的胜负。

但如果图有环，使用bfs的方式时，可能存在部分点的胜负情况无法求出。考虑这些点上的情况，一定满足在每个点上，如果当前操作的人向胜负情况被求出的点移动，则这个人会输。因此若双方都不想输，则会在这些点上无限走。但第二个人不希望无限进行，因此他会主动输。所以对于所有没有被确定的点，它们的状态都是第一个人获胜。

复杂度 $O(n+m)$

I. Indiana Jones and the Uniform Cave

Problem

交互题。

有一个 $n$ 个点的有向图，每个点有 $m$ 条出边。出边按照顺序排列成一个环。但不同点和边无法直接分辨。

在每个点上有一个石子，初始时石子在点的正中。在你到达一个点时，你可以将这个点上的石子放在一条出边上，且可以放到这条出边的左侧/右侧。在你进入一个点时，你可以从交互器中知道当前在正中还是在某条出边的左侧/右侧。此时从当前石子开始，按照顺时针将所有出边标号为 $0,1,2,...,m-1$ （在正中时随机选一个起始点）。在这个点上，你可以选择一个标号，将石子移到这个出边的左侧/右侧，再选择一个标号，沿着这条出边走。

你需要在走的边数不超过 $2\times 10^4$ 的情况下经过所有边。保证图强连通

$n,m\leq 20$

$2s,256MB$

Sol

将石子放在出边两侧可以看成给点一个0/1的标记。

考虑使用dfs的方式遍历每个点的所有出边。将当前在dfs栈中的点标记为 $1$ ，访问过但已经不在栈中的点标记为 $0$。对于每个点，每次走一条出边时将石子移动一位，并走现在石子所在的出边，记录走的次数即可。考虑从栈顶点走一条出边之后的情况：

1. 新到达的点没有被访问过(石子在正中)，则将这个点加入dfs栈顶，并将点标记为 $1$。
2. 新到达的点在dfs栈中(标记为 $1$)，此时从这个点开始，每一步都沿着石子所在的出边走，则会形成这个点到栈顶点的的一个环。因此将此时的点标记改为 $0$ 。因为环上只有这一个 $0$，走一次环即可知道环长。然后即可还原标记并定位到当前的栈顶。这里的移动次数不超过 $2n$。
3. 新到达的点不在dfs栈中(标记为 $0$)，考虑先找到一条路径，回到一个在dfs栈中的点，再使用上面的方式。如果能在不经过重复点的情况下回到dfs栈中的点，则移动次数也不会超过 $2n$。

考虑操作3如何进行。一个想法是在每个点上只走石子所在的出边。考虑记录从这个点出发，能走到的dfs栈中最靠前的点的深度（类似tarjan算法中的low），以及走到这个点这一步走的出边。因为图强连通，一直走low一定能回到dfs栈上。且只需要每一个点上都向low最小的出边移动。因此可以对于每个点找它low最小的出边。对于情况1，可以从子树的low转移。对于情况2,3，都可以通过循环部分的环长求出low。在一个点出边遍历结束后，将石子放到low最靠前的出边上，然后沿着石子的边走回去即可。

复杂度 $O(n^2m)$，移动次数不超过 $2n^2m$

K. Kids Designing Kids

Problem

给两个01矩阵，认为矩阵大小无限，且除去给出部分外都是 $0$ ，左上角坐标为 $(0,0)$。保证给出矩阵不为全0。

你需要将第二个矩阵平移，使得两个矩阵将对应位置异或后的结果平移后可以等于给出的第三个矩阵。输出平移的方案或输出无解。

设矩阵大小为 $n$，$n\leq 10^6$

$2s,256MB$

Sol

对于两个坐标 $(x_1,y_1),(x_2,y_2)$，定义 $(x_1,y_1)<(x_2,y_2)$ 当且仅当 $x_1<x_2$ 或者 $x_1=x_2,y_1<y_2$。可以发现，这样定义的为全序集，且两个点同时平移相同的向量大小关系不变。

考虑两个矩阵中的所有 $1$ 位置的坐标中最小的一个，对于这两个位置：

1. 如果这两个位置平移后重合，这种情况可以直接检查是否合法，复杂度 $O(n)$。
2. 如果两个位置平移后不重合，设这两个位置为 $s_1,s_2$ ，不妨设 $s_1<s_2$ ，对于一个在 $s_1$ 属于的矩阵中的 $1$ 的位置，它现在的位置 $s_3$ 一定满足 $s_3\geq s_1$ ，对于一个在 $s_2$ 属于的矩阵中的 $1$ 的位置，它现在的位置 $s_4$ 一定满足 $s_4\geq s_2>s_1$。因此平移并异或后所有可能为 $1$ 的位置 $s$ 都满足 $s\geq s_1$。因此 $s_1$ 一定与第三个矩阵的所有 $1$ 位置的坐标中最小的一个重合。

对于第二种情况，先枚举 $s_1$ 属于哪个矩阵，然后可以知道这个矩阵和第三个矩阵的位置关系。此时可以通过异或求出第二个矩阵，再判断是否可以平移到即可。

复杂度 $O(n)$

L. List of Primes

Problem

考虑所有元素均为质数的所有集合，将集合按照大小为第一关键字，字典序为第二关键字排序，并按照如下方式表示：

[2], [3], [2, 3], [5], [2, 5], [7], [3, 5], [2, 7], [2, 3, 5], [3, 7], [11], [2, 3, 7], [5, 7], [2, 11], [13], [2, 5, 7],

求出这个字符串的第 $l$ 个到第 $r$ 个字符。

$l\leq r\leq 10^{18},r-l\leq 10^5$

$2s,256MB$

Sol

显然取前 $60$ 个质数就可以构造 $2^{60}$ 个集合，因此 $10^{18}$ 内集合元素和的最大值不会太大。

考虑对于每个和 $s$ 求出和为 $s$ 的质数集合的数量，以及所有集合表示出来的长度和。这个可以直接dp求出。

此时可以发现只考虑和不超过 $2200$ 的集合。对于每个和分别考虑。可以发现相当于求出只考虑某个和的序列的某个区间。

设考虑的所有质数为 $p_1,...,p_k$ ，对于一个集合 $S$ ，可以将它映射到一个长为 $k$ 的 01 串 $l_S$ ，其中第 $i$ 位为 $1$ 当且仅当 $p_i\in S$ 。

这时可以发现，对于两个和相同的集合 $S_1,S_2$ ，$S_1$ 的字典序小于 $S_2$ 的字典序当且仅当 $l_{S_1}$ 大于 $l_{S_2}$。

证明：考虑两个串第一个不同的位置 $i$ ，此时 $l_{S_1}$ 这一位为 $1$， $l_{S_2}$ 这一位为 $0$，但此时因为两个集合和相同，所以两个集合在这一位之后不可能没有 $1$ 。因此 $l_{S_2}$ 后面还有至少一个 $1$ ，因此将 $S_1,S_2$ 表示成串时，前面的位相同，这一位上 $S_1$ 是 $p_i$ ，而 $S_2$ 这一位上一定大于 $p_i$ ，因此 $S_1$ 的字典序小于 $S_2$ 的字典序。

对于任意的 $s$ ，只考虑所有串的前 $s$ 位，可以将所有的集合对应的串分成若干子集，不同子集之间存在字典序顺序。这时在一个区间内的集合所在的段一定是一个字典序顺序的区间。对于每一个子集，可以记录子集对应的串的前 $s$ 位中所有 $1$ 的位置。

$s=0$ 时只有一个子集。考虑通过 $s=i$ 推出 $s=i+1$ 的所有与需要输出的区间有包含子集。

对于每一个子集，考虑这个子集对应的串的 $i+1$ 位的值，可以将这个子集分成两个子集，可以得到若干个按照对应的串的字典序排序的子集，考虑计算一个子集中所有元素的表示长度和。相当于求出所有满足某些数必须在集合中， $p_{i+1,...,k}$ 中的数可以出现也可以不出现，且集合和为某个数 $su$ 的集合的数量以及表示长度和。

考虑求出 $f_{i,j}$ 表示 $p_{i+1,...,k}$ 的子集中和为 $j$ 的数量， $g_{i,j}$ 表示 $p_{i+1,...,k}$ 的子集中和为 $j$ 的所有集合的表示长度和。设必须出现的数的和为 $s_1$ ，则需要求的集合可以和所有 $p_{i+1,...,k}$ 的子集中和为 $su-s_1$ 的集合一一对应，且将后者的每一个集合内加入必须出现的数则为前者。因此所有集合的表示长度和可以由 $f_{i,su-s_1},g_{i,su-s_1}$ 表示。求出 $f,g$ 的方式与dp相同。

因此此时可以求出每个子集元素的表示长度的和。此时可以删去两侧不会出现在输出区间中子集。通过这样的方式可以得到所有在输出区间内的质数集合。然后直接输出即可。

复杂度不超过 $O(k*(r-l+1))$ ，其中 $k$ 为需要的质数数量。当然也可以暴力找出需要输出的集合对应串的上下界然后dfs找

M. Mole Tunnels

Problem

给出 $n,m$ 。有一个 $n$ 个点的二叉树，且点 $i(i>1)$ 的父亲为 $\lfloor\frac i2\rfloor$ 。每个点有一个容量上限 $v_i$ 。

有 $m$ 个人，第 $i$ 个人的位置为 $p_i$ ，对于每一个 $i=1,2,...,m$ ，求出：

考虑前 $i$ 个人，现在每个人可以在树上沿着树边移动。需要满足移动后每个点上的人数不超过容量上限。移动方案的代价为每个点的移动距离和。你需要求出最小代价。

$n,m\leq 10^5$

$2s,256MB$

Sol

问题可以看成最小费用流问题。因此现在可以看成从每次操作原点向某个点加一条边，每次加边后求最小费用流。

根据费用流的性质，可以直接在上一次的残量网络上跑。考虑模拟费用流，对于每条边记录这条边的流量以及流量方向。根据费用流的方式，如果流量为 $0$ 则经过这条边的代价为 $1$ ，否则与流量方向相同的边代价为 $1$ ，反向边代价为 $-1$ 。

对于每个点 $i$ 求出 $f_i,g_i$ 表示 $i$ 子树内还有向汇点的流量的点到这个点的最短距离以及这个点的编号。每次加入一个人可以看成找一个到汇点有流量的点，使得这个人到这个点的距离最小。可以枚举两点LCA，通过 $f_i$ 求出最短路。然后更新每条边的流量。

因为这个树每个点深度都不超过 $\log n$ ，因此路径长度都不会超过 $\log n$ 。复杂度 $O(m\log n)$

2017-2018 ACM-ICPC Northern Eurasia (Northeastern European Regional) Contest

F. The Final Level

Problem

给定 $n,a,b$ ，一个 L 型积木的形状由方格 $(0,0),(0,1),...,(0,n-1),(1,0),(2,0),...,(n-1,0)$ 组成。积木可以 $90$ 度旋转（即选定 $x,y\in\{-1,1\}$ ，所有坐标变为 $(0,0),(0,x),...,(0,x*(n-1)),(y,0),(2y,0),...,(y*(n-1),0)$）。

你可以在网格图上放若干个这样的积木，满足积木不能重合，且只通过有积木的格子可以从格子 $(0,0)$ 移动到 $(a,b)$ 。输出一种放置积木数量最少的方案。

多组数据，一共有 $m$ 组数据。保证所有数据的最小积木数量的和不超过 $10^5$

$m\leq 100,n,a,b\leq 10^8$

$3s,512MB$

Sol

通过翻转坐标，可以只考虑 $a,b\geq 0$ 的情况。考虑问题答案的下界：

考虑横坐标的情况，这部分的下界为 $\lceil\frac an\rceil$，考虑纵坐标的情况，下界为 $\lceil\frac bn\rceil$。

考虑斜向的情况，下界为 $\lceil\frac {a+b}{2n-1}\rceil$。

此时可以发现答案即为这三个下界的 $\max$ ，考虑用如下构造归纳证明：

在答案为 $1$ 时，手玩可以发现一定可以构造出来，在答案大于 $1$ 时：

如果 $a,b\geq n$ ，则可以从 $(a,b)$ 向左下放一个L型到 $(a-n+1,b-n+1)$ 。这时只需要用剩下的积木从原点走到 $(a-n,b-n+1)$ 或 $(a-n+1,b-n)$ 即可。不妨设 $a\geq b$ ，则可以贪心选择 $(a-n,b-n+1)$ 。

如果 $a\geq n>b$ ，则可以从 $(a,b)$ 向左下放一个中心点在左上的L型，这时积木会经过 $(a-n+1,0)$ ，剩下的只需要从原点走到 $(a-n,0)$。

如果 $b\geq n>a$ ，则可以放一个中心点在右下的L型，类似可以发现此时接下来只需要走到 $(0,b-n)$ 。

可以发现这样归纳 $\max(\lceil\frac an\rceil,\lceil\frac bn\rceil,\lceil\frac {a+b}{2n-1}\rceil)$ 每次一定减一，因此这样的归纳可以达到最优解。又因为这样每次都是在 $(a,b)$ 的左下角区域放，因此可以发现不会重叠。

复杂度 $O(l)$，其中 $l$ 为答案大小。

G. The Great Wall

Problem

给三个长度为 $n$ 的序列 $a_i,b_i,c_i$ ，保证 $a_i<b_i<c_i$ 。

给定 $r$ ，你可以选两个 $[1,n]$ 内的长度为 $r$ 的区间 $[x,x+r-1],[y,y+r-1]$ ，满足两个区间不同。对于一种选取区间的方案，定义它的收益为每个位置的收益的和，每个位置的收益为：

如果这个位置没有被任意一个选择的区间包含，收益为 $a_i$ 。

如果这个位置被正好一个选择的区间包含，收益为 $b_i$ 。

如果这个位置被两个选择的区间包含，收益为 $c_i$ 。

求出所有 $\frac{(n-r+1)(n-r)}2$ 种方案的收益中，第 $k$ 大的收益。

$n\leq 3\times 10^4,1\leq k\leq \frac{(n-r+1)(n-r)}2$

$3s,512MB$

Sol

考虑二分答案，变为询问收益大于某个数的方案数量。

设方案中 $x<y$ ，从大到小枚举 $x$ ，设 $f_y$ 表示另外一个区间为 $[y,y+r-1]$ 时的收益。考虑 $x=t$ 时所有 $f_y$ 的值：

将 $b_i,c_i$ 分别减去 $a_i$ ，然后将 $a_i$ 看成 $0$ ，这样只需要将最后的答案加上 $a_i$ 的和。记 $sb,sc$ 为此时 $b,c$ 的前缀和，则：

如果两个区间相交 ( $x+r-1\geq y$ )，则 $f_y=sb_{y+r-1}-sb_{x+r-1}+sc_{x+r-1}-sc_{y-1}+sb_{y-1}-sb_{x}$

否则 ( $x_r-1<y$ ) ，$f_y=sb_{y+r-1}-sb_{y}+sb_{x+r-1}-sb_{x}$

可以发现两个都可以分成只与 $x$ 相关的部分和只与 $y$ 相关的部分，因此询问 $f_y$ 中大于某个数的数数量可以看成一个固定的序列，询问一个区间中某个值大于一个给定值的数的数量。

可以发现在 $x$ 从大到小的过程中，区间端点变化的距离和为 $O(n)$ ，因此可以看成插入删除数，询问大于某个数的数数量，可以splay/离散化BIT解决。也可以直接离线做二维偏序。

复杂度 $O(n\log^2 n)$

H. Hack

Problem

交互题

$p,d$ 固定， 考虑如下计算 $a^d\bmod p$ 的代码：

modPow(a, d, p) {
	r = 1;
	for (i = 0; i < 60; ++i) {
		if ((d & (1 << i)) != 0) {
		r = r * a % p;
		}
	a = a * a % p;
	}
}

定义一次 a*b%p 的操作的代价为 $f(a)*f(b)$ ，其中 $f(a)=\lceil\log_2(a+1)\rceil$ ，即 $a$ 二进制表示的位数，其余操作没有代价。

现在你知道 $p$ 但不知道 $d$ ，你可以向交互器询问一个 $a$ ，交互器会返回使用上面代码计算 $a^d\bmod p$ 的代价。你可以询问不超过 $3\times 10^4$ 次来求出 $p$ .

$p$ 的生成方式为随机两个 $[2^{29},2^{30})$ 之间的质数 $x,y$ ，令 $p=xy$ ，$d$ 为在 $[1,p)$ 中与 $p$ 互质的数中随机选择。

$10s,512MB$

Sol

对于一次询问，在不知道 $d$ 的情况下也可以求出 a*a%p 部分的代价以及每一个 $i$ 处的 $a$ 值。可以将交互器返回的代价减去这一部分的代价。

可以发现，若看成 $a$ 随机，则 $f(a)$ 和 $f(p)$ 的相差非常小，相差期望值为 $1$。

考虑随机 $a$ ，如果存在一个 $i$ 位置，使得到这个位置时 $f(a)$ 非常小，则如果 $d$ 在这一位上是 $1$ ，则这次询问的值很可能小于随机询问的期望值。

进行随机询问，求出代价的平均值。然后考虑每次询问，找到让 $f(a)$ 最小的 $i$ 以及剩余 $f(a)$ 的平均值。如果此时最小的 $f(a)$ 与剩余平均值的差较大且询问的代价与平均代价相差较大，则这一位很可能是 $1$ ，如果代价相差很小则这一位很可能是 $0$ 。

因此可以根据 $f$ 的差值和代价差值给这一位一个权值。然后对于每一位，它的权值较大意味着它是 $1$ 的概率较大。在调参优秀的情况下可以直接根据权值找出答案。

但在调参不那么优秀的情况下，可以根据权值随机若干个与权值预测的结果比较接近的(例如，如果通过权值认为这一位是 $1$ 的概率为 $p$ ，则随机这一位有 $\frac1{(1+e^{1-2p})^k}$ 的概率为 $1$ )，然后验证是否符合之前的结果。这样大概率可以通过。

I. Interactive Sort

Problem

交互题。

有一个长度为 $n$ 的排列，保证奇数位置上为奇数，偶数位置上为偶数。你可以向交互器给出一个奇数位置 $x$ 和一个偶数位置 $y$ ，交互器会返回这两个位置的大小关系。

在不超过 $3\times 10^5$ 次询问内求出整个排列。

保证排列随机生成。

$n\leq 10^4$

$10s,512MB$

Sol

如果只考虑奇数部分的前 $i$ 个数和偶数部分的所有数，则奇数部分的数会把偶数部分的数分成 $i+1$ 段。

考虑加入奇数部分下一个数时的操作，首先考虑找到这个数所在的段，考虑将这个数与某一段内的任意一个数比较。如果结果为小于，则这个数一定在这一段或者这一段之前，否则这个数在这一段或者这一段之后。因此可以二分找到相邻的两段，这个数一定在这两段中。

然后将这两段内的元素和这个数比较，即可划分出新的段。

考虑这样的复杂度。二分的复杂度为 $O(n\log n)$ ，考虑加入的元素所在的段的期望长度，即 $k$ 次之前每一段长度平方和的期望。在第 $k$ 次时，这可以近似看成 $2*\frac 1n\sum_{i=1}^n(n-i+1)(\frac{n-i+1}{n})^{k-1}=2\sum_{i=1}^n(\frac in)^k$ ，看成积分则期望为 $\frac {2n}{k+1}$ ，这部分求和为 $O(n\log n)$

考虑加入元素所在段的下一段的期望长度。可以发现这个期望与上一个类似，认为 $O(n\log n)$ 。

因此总操作次数 $O(n\log n)$ ，使用直接维护段或者Splay，复杂度 $O(n^2)$ 或 $O(n\log n)$

J. Journey from Petersburg to Moscow

Problem

给一个 $n$ 个点 $m$ 条边的带权无向图。你需要从 $1$ 到 $n$ 。

给定一个 $k$ ，对于你经过的路径，如果它的边数不超过 $k$ ，则你的费用为路径上所有的边的边权和。否则费用为路径上的所有经过边中边权最大的 $k$ 条边的的边权和。

求出最小费用。

$n,m,k\leq 3000$

$3s,512MB$

Sol

一定存在一个 $x$ ，满足支付的边权为经过的所有大于 $x$ 的和部分等于 $x$ 的。

定义一条路径在取 $x$ 时的费用为，将所有边权 $v$ 变为 $\max(v-x,0)$ 后，路径边权和加上 $kx$ 的值。可以发现，对于一条路径， 这条路径在取一些 $x$ 时得到的结果等于这条路径实际的费用，其余时刻得到的结果一定大于实际费用。且一定存在一个等于某个边权或者等于 $0$ 的 $x$ 让它取到等于。因此枚举 $x$ 时只用枚举所有的边权以及 $0$ 。

因此可以枚举 $x$ ，再枚举路径，计算这条路径在取 $x$ 时的费用，将所有费用取 $\min$ 。可以发现，对于一个 $x$ ，只有此时 $1$ 到 $n$ 的最短路可能计入答案。因此对于每个 $x$ 求出最短路即可。

复杂度 $O(nm\log m)$

K. Knapsack Cryptosystem

Problem

给定 $q=2^{64}$ ，有 $n$ 个正整数 $a_1,...,a_n$ ，满足 $a_i>\sum_{j=1}^{i-1}a_j,\sum_{i=1}^na_i<n$，以及一个 $r$ 满足 $r,q$ 互质。

令 $b_i=a_i*r\bmod q$，现在有一个长度为 $n$ 的 $01$ 串 $s$ ，定义 $su=(\sum_{i=1}^ns_i*b_i)\bmod q$

给出 $n,b,su$ ，你需要求出 $s$ 。

$n\leq 64$

$3s,512MB$

Sol

显然可以直接折半，这样的复杂度为 $O(2^{\frac n2})$

在 $n$ 较大时，可以发现 $a_1\leq\frac q{2^n}$，因此考虑枚举 $a_1$ 。设 $b_1=2^t*c$ ，其中 $c$ 为奇数，则因为 $r$ 为奇数，显然有 $2^t||a_1$ ，并且因为 $b_i=a_i*r\bmod q$ ，可以确定 $r$ 二进制的后 $64-t$ 位。

此时每一个 $a_i$ 可能的 $r$ 有 $2^t$ 个，可能的 $a_i$ 有 $\frac{q}{2^{n+t}}$ 个，因此考虑枚举所有的 $a_i$ 以及 $r$ 的前 $t$ 位，此时有 $\frac{q}{2^n}$ 种情况，对于每一种 $r$ 的情况，可以直接求出 $a$ 判断是否满足要求。复杂度 $O(\frac{nq}{2^n})$，但因为在随机 $r$ 的情况下，还原 $a$ 时出现 $a_i>a_{i+1}$ 的期望时间为 $O(1)$ ，因此复杂度期望为 $O(\frac{q}{2^n})$

复杂度 $O(q^{\frac 13})$

L. Laminar Family

Problem

给一棵 $n$ 个点的树，现在有 $m$ 个集合。对于每个集合，给出 $x_i,y_i$ ，表示这个集合为路径 $(x_i,y_i)$ 上的所有点构成的集合。

求出对于给定的这些集合，是否满足：

对于任意两个给出的集合 $A,B$ ，都满足 $A\subset B$ 或 $B\subset A$ 或 $A\cap B=\emptyset$

$n,m\leq 10^5$

$3s,512MB$

Sol

按照集合大小排序，则可以看成要求对于每一个集合，在它之后且与它相交的集合必须包含它。

考虑如下做法：

从后往前考虑每个集合，对每个元素维护一个标记。加入一个集合时，满足条件当且仅当这个集合中所有元素的标记相同。然后对于集合中的每个元素的标记中加入这个集合对应的编号。

显然满足条件当且仅当上面的过程会得到满足条件的结果。

标记显然不能直接维护，考虑，将每个标记看成一个数，给每个集合一个 $2^{60}$ 级别的数，然后给一个元素标记看成将这个标记异或集合对应的数。此时可以发现把不等判断成判断相等的概率为 $2^{-60}$ ，因为判断错误当且仅当每一次不等都被判断为相等，因此最后判断错误的概率不超过 $2^{-60}$ 。

因此问题变为链异或，求一条链点权是否全部相等。可以直接树剖解决。

复杂度 $O(n\log^2 n)$

2014 ACM-ICPC World Finals

A. Baggage

Problem

$2n$ 个物品排成一列，每个物品可能是 A,B 两种类型之一，初始时所有物品排成 BABABABA...BA的形状，物品左侧有 $n$ 个可用的空位，物品初始坐在的位置编号为 $1,...,2n$ ，空位编号为 $-2n+1,...,0$

你每次可以选择两个相邻且都有物品的位置，拿出这两个物品，在不改变它们顺序的情况下把它们放到任意两个连续且空的位置中。

你需要使用最少的操作，把物品变为 ...AAAA...ABBBB...B... ，对物品两侧的空位数不做要求。输出方案。

$n\leq 100$

$1s,1024MB$

Sol

手玩可以发现这样的方式：

__BABABA....BABABABA
ABBABABA....BABAB__A
ABBA__BA....BABABBAA
(中间部分递归操作)
ABBAAAAA....BB__BBAA
A__AAAAA....BBBBBBAA
AAAAAAAA....BBBBBBBB

此时可以通过 $4$ 步，把 $n$ 的问题变为 $n-4$ 的问题。

同样手玩可得，对于 $n=3$ 存在 $3$ 步方案，但不存在只使用左侧两空位的方案。对于 $n=4,5,6,7$ 都存在 $n$ 步只使用左侧两空位变为 AA..ABB..B__ 的方案。

此时通过递归即可得到 $n$ 步的做法。

考虑计算不考虑空位时相邻且不同的字符对数。可以发现初始这个值为 $2n-1$ ，结束时为 $1$ ，可以发现每次操作这个值最多 $-2$ 。

又因为显然第一次操作这个值最多 $-1$ ，因此操作步数至少为 $n$ 。因此直接这样构造即可。

复杂度 $O(n)$

B. Buffed Buffet

Problem

你想买质量为 $m$ 的物品，一共有 $n$ 种物品，每种物品数量无限。物品分为两类：

1. “离散的” 物品，这种物品只能取整数个，一个物品有质量 $w_i$ 以及 $t_i,\Delta t_i$ ，代表选这种物品 $s$ 个的收益为 $\sum_{j=1}^st_i-(j-1)\Delta t_i$
2. “连续的” 物品，这种物品可以取任意实数质量，一种物品有两个值 $t_i,\Delta t_i$ ，代表选质量为 $s$ 的这种物品的收益为 $\int_0^s(t_i-x\Delta t_i) dx$

求出买质量正好为 $m$ 的物品时的最大收益，或者判断无解。

$n\leq 250,m\leq 10^4$，所有数为非负整数。

$4s,1024MB$

Sol

首先考虑只有第一类的情况，考虑dp，设 $dp_{i,j}$ 表示考虑前 $i$ 种第一类的物品后重量和为 $j$ 的最大收益。

考虑加入一个物品时的转移，将dp按照 $j\bmod w_i$ 分类，对于每一类，dp为:

$dp_{i+1,j*w_i+v}=\max_{k\leq j}dp_{i,k*w_i+v}+t_i*(j-k)-\Delta t_i*\frac12*(j-k-1)*(j-k)\\ dp_{i+1,j*w_i+v}=(t_i*j-\Delta t_i*\frac12*(j^2-j)+\max_{k\leq j}dp_{i,k*w_i+v}-t_i*k-\Delta t_i*\frac12*(k*2+k)+\Delta t_i*j*k$

可以看出这是斜率优化的形式，直接做就行。

这部分复杂度为 $O(nm)$

考虑加入第二类，枚举第一类的重量，问题变为询问使用第二类物品和为 $k$ 的最大收益。

如果将一个物品选的数量和收益看成函数的关系，则可以发现得到的都是上凸函数。

此时可以发现，在最优解中，对于一个选择量大于 $0$ 的物品 $a$ 和一个物品 $b$ ，$a$ 的函数在选择量处的导数必须不小于 $b$ 的函数在选择量处的导数。否则调整减小 $a$ 增加 $b$ 可以更优。

因此在最优解中，所有选择量大于 $0$ 的物品 $a$ ，$a$ 的函数在选择量处的导数都相同，且选择量等于 $0$ 的函数在 $0$ 点的导数都小于等于这个导数。

因此可以二分导数，找到选的数量正好是 $k$ 的导数，也可以按照 $t_i$ 排序后扫过去。

复杂度 $O(nm\log v)$ 或者 $O(nm)$

C. Crane Balancing

Problem

有一个 $n$ 个点的多边形立在地平线 $x=0$ 上，多边形的质量均匀，且每 $1$ 单位面积的质量为 $1$。

称多边形平衡当且仅当它能在当前位置稳定，不向某个方向倾斜。

现在在某个点上有一个物品，物品的质量为 $x(x\geq 0)$。求出能使多边形平衡的 $x$ 的区间。

$n\leq 100$

$1s,1024MB$

Sol

考虑没有物品时多边形能不能平衡。考虑多边形与地面相交的区间，可以发现，如果多边形的重心横坐标在这个区间内，则向一侧端点旋转重心高度都会变大，因此此时是稳定的。

否则，沿着一侧端点那一侧旋转会使重心高度变小，此时一定不稳定。因此只需要使重心横坐标在这个区间中即可。

考虑求出多边形重心，可以将多边形划分成 $n$ 个有向三角形。对于每个三角形，它的重心坐标是三个顶点坐标的平均值。此时问题变为有 $n$ 个点，每个点有坐标和质量，求出重心。

可以发现，此时求这些点坐标的带权平均即可。

求出重心之后，加入物品相当于再加一个点，可以根据这个点横坐标，重心横坐标直接求出这个点合法的质量区间。

复杂度 $O(n)$

E. Maze Reduction

Problem

有一个 $n$ 个点，无自环无重边的无向图。点 $i$ 有 $c_i$ 条出边，出边按照给定顺序排成一个圆。

你会从某个点开始在图中游走。所有的点和边间不可区分。当你到达某个点时，你知道的信息只有这个点的出边数量以及你走到这个点时的这条边的位置。因为边不可区分，你能进行的操作只有选择一个 $d$，走从进入这个点的边开始，顺时针第 $d$ 条边。

定义两个点 $i,j$ 是等价的，当且仅当你从其中一个点开始走，不能分辨出自己的出发点是 $i$ 还是 $j$。

可以发现，可以将所有点划分成若干个集合，满足同一个集合中的两个点之间等价，不同集合中的两个点不等价。求出这样的集合划分。

$n\leq 100$

Sol

因为能在 $n$ 步之内走到一个点，因此如果两个点不等价，则走 $n$ 步之内一定可以找到不同。 因此两个点等价当且仅当 $n$ 步以内每一种走的方案(每一次选的 $d$ )得到的路径上每个点度数相同。

考虑hash，设 $f_{u,v,k}$ 表示当前从 $u$ 走到 $v$，之后再走 $k$ 步的所有路径的hash值。

考虑这一步的情况，设 $v$ 的出边为 $nt_{v,1},nt_{v,2},...,nt_{v,c_v}$，其中 $nt_{v,x}=j$，则根据这一次选的 $d$ 从小到大，接下来的状态为 $f_{nt_{v,x},v,k-1},f_{nt_{v,x+1},v,k-1},...,f_{nt_{v,x-1},v,k-1}$。将这个看成一个序列，求序列再加上当前点度数的hash值即可。

对于起始点的情况，因为没有入边，因此所有的状态会排成一个环。可以选择一个字典序最小的断环为链的方式，然后做hash。这样得到了每个点出发的所有路径的hash值。

可以发现，如果两个点等价，则它们的hash值相同。因此取 $10^9$ 级别的模数做hash即可使正确概率足够大。

复杂度 $O(n^4)$

F. Messenger

Problem

有两个人在一个二维平面上，两个人分别有一个由 $n,m$ 个点组成的路径。在初始时，每个人位于自己路径的起点，随后，每个人会从当前点开始，沿着最短路径走到自己路径的下一个点。两人的速度都是 $1$。

第一个人有一个物品，他要把这个物品给第二个人。第一个人可以在到达终点的那一刻以及之前将物品传递出。随后，物品会沿着某个方向，以 $1$ 的速度移动。如果在第二个人到达终点的那一刻或者之前他的位置与物品重叠，则他可以拿到物品。

两个人和物品都不能停下，求出在成功传递物品的情况下，物品从被传递出到被拿到中间移动的最小距离。输出最小距离或者无解。

$n,m\leq 5\times 10^4,0\leq x_i,y_i\leq 3\times 10^4$ ，两条路径长度不超过 $10^6$

$4s,1024MB$

Sol

假设固定了起点 $A$，考虑终点的位置 $B$，这个位置需要满足第一个人到 $A$ 的时间加上 $dis(A,B)$ 等于第二个人到 $B$ 的时间。

考虑将 $B$ 向第二个人到 $B$ 的距离更小的方向移动。假设移动的距离为 $l$，则根据三角形不等式 $dis'(a,b)\geq dis(a,b)-l$。因此向这个方向移动时，第二个人会比物品更先到达 $B$。如果向另一个方向移动，则物品会先到达。

可以发现如果 $B$ 取起点，则一定第二个人先到达。因此如果 $B$ 取第二个人终点时仍然 $B$ 先到则无解，否则可以二分这个位置。

可以发现固定 $B$ 的情况类似。因此在 $A$ 从第一个人起点开始向前移动时， $B$ 也在向前移动。

考虑将合法的 $A$ 取值划分成若干个区间，满足每个区间内 $A$ 在一条线段中，且对应的 $B$ 也在一条线段中。

对于每一个 $B$ 的路径顶点，二分出它对应的 $A$ 位置，按照这些位置加上 $A$ 的所有顶点划分，得到的这些区间就满足条件。

现在考虑一个区间，它满足 $A$ 在一条线段中，且对应的 $B$ 也在一条线段中。

此时可以发现，随着 $A$ 变化，答案会是一个单峰函数。因此在每一段上三分 $A$，再二分 $B$ 即可。

复杂度 $O(n\log^2 v)$

G. Metal Processing Plant

Problem

给一个 $n$ 个点的完全图，每条边有边权 $v_{i,j}$。

你需要将 $n$ 个点划分成两个集合 $S_1,S_2$。定义 $f(S)=\max_{i,j\in S}v_{i,j}$，你需要最小化 $f(S_1)+f(S_2)$

输出最小值。

$n\leq 200$

$4s,1024MB$

Sol

n^4/64是啥震撼东西

考虑钦定第一个集合的 $f$ 不超过 $a$，第二个集合的 $f$ 不超过 $b$。考虑判断这个是否合法。

可以发现这能够 2-SAT，大力建边即可。这样单次复杂度 $O(n^2)$。

考虑设 $a\geq b$，那么可以发现，所有边权大于 $a$ 的边，在 2-SAT 中相当于要求两个点状态不同。对于一个 $a$ ，显然可以二分求出最小的合法 $b$。这样单次 $O(n^2\log n)$

可以发现，在一个连通块中加入一条不带来奇环的这样的边和不加入是等价的。因此，在 $a$ 从大到小的过程中，只考虑边权大于 $a$ 的边，只有当新增加的一条这样的边连接了两个不同的连通块或者连出奇环(出现这种情况则更小的 $a$ 都无解)时，这部分边的效果会发生变化。这样的情况只有 $O(n)$ 次。

因此，只需要在每次连通块变化前的 $a$ 做二分，复杂度 $O(n^3\log n)$。

但注意到，上面条件成立的前提是 $a\geq b$ ，但可能出现在上一次变化时的结果是 $a\geq b$ ，但这一次变成了 $a<b$，此时需要在这一段中二分找到最后一个 $a\geq b$ 的位置。

复杂度 $O(n^3\log n)$

H. Pachinko

Problem

有一个 $n$ 行 $m$ 列的网格，有一些位置是障碍，一些位置是终点，第一行没有终点。

一个小球从第一行的随机一个非障碍位置开始移动。给出小球每一步向上/下/左/右的概率，小球每一步都会按照这个概率选一个方向移动，如果移动后的位置是障碍或者出界则不移动。

当小球到达某个终点时，小球停止。

求出小球停在每个终点的概率。

$n\leq 10^4,m\leq 20$

$6s,1024MB$

Sol

考虑设 $f_{x,y}$ 表示小球经过位置 $(x,y)$ 的次数。可以发现， $f_{x,y}$ 只和它四周的格子相关。

考虑对第一行进行消元，可以发现，消元后，一定可以将 $dp_{1,x}$ 用第二行的 $dp$ 表示出来，即表示成 $a+\sum_{i=1}^mv_idp_{2,i}$ 的形式。

使用同样的方式，可以依次对每一行消元，最后可以通过最后一行求出这一行的 $dp$ ，再反向推出所有 $dp$ 即可。

没写过不知道细节多不多

复杂度 $O(nm^3)$

I. Sensor Network

Problem

给二维平面上 $n$ 个点以及一个 $d$ ，两点之间有边当且仅当两点距离不超过 $d$。求出图的最大团。

$n\leq 100$

$2s,1024MB$

Sol

直接随机就能AC

考虑枚举最大团中距离最大的一对点 $A,B$ ，考虑剩余点的情况：

此时剩余点一定在 $A$ 为圆心，半径为 $AB$ 的圆和 $B$ 为圆心，半径为 $AB$ 的圆的交中，即图中 $ACBD$ 区域。

此时相当于在这个区域内选出若干个点，满足两点距离不超过 $AB$。可以发现，此时如果将区域沿着 $AB$ 分开，则上面区域中的任意两个点都满足条件，下面区域中的任意两个点都满足条件。

因此只有一个上面的点和一个下面的点可能不满足条件，因此这部分相当于在一个二分图中选最大独立集。直接网络流即可。

复杂度 $O(n^{4.5})$，跑不满

J. Skiing

不会

K. Surveillance

Problem

有一个长度 $n$ 的环，给出 $m$ 个区间，选出个数最少的区间，使得环上每个点都被某个选择的区间覆盖。

输出最小个数或输出无解。

$n,m\leq 10^6$

$4s,1024MB$

Sol

考虑链上的情况，设当前覆盖了长度为 $l$ 的前缀，则下一步一定是贪心找左端点小于等于 $l$ 的区间中右端点最大的 $x$ ，然后选这个区间，将当前覆盖的前缀长度设为 $x$ 即可。

对于环上的情况，考虑枚举选择的一段，如果一段被另外一段完全包含，则选这一段一定不优。因此选了这一段后将环分开，剩余的每个区间在链上还是一个区间，这样变成了链上的问题。

注意到链上每一步操作都是找包含 $l$ 的区间中右端点最大的区间，可以在环上预处理这个东西。这样可以得到每个 $l$ 下一步的 $x$。然后对这个东西倍增即可在 $O(\log n)$ 的复杂度内求出一个链上的问题。枚举一段直接做即可。

复杂度 $O(n\log n)$

L. Wire Crossing

Problem

在二维平面上有 $n$ 条线段，线段不会重叠但可以相交。

给定起点和终点，你需要找一条从起点到终点的路径满足：

1. 路径不经过已有线段的交点
2. 路径与线段相交的次数最小

求出最小相交次数。

$n\leq 100$

$2s,1024MB$

Sol

考虑建这 $n$ 条线段对应的平面图，先枚举每一对线段，找到所有的交点。对于每条线段，找到它依次经过的所有交点，将相邻交点连边。这样就得到了线段对应的平面图的所有边。

然后考虑建对偶图，对于每个点将它的出边极角排序。考虑从一条边的某一侧开始走，找到一个区域的边界。在到达一个点时，走到对应方向极角排序后下一个出边即可。走回初始位置时即找到了这个区域的边界。

这样可以对于一个平面图上的连通块找到这个连通块内所有区域的边界，以及连通块的外边界。考虑对于每个外边界找到这个外边界属于的平面区域。在外边界中选择一个点，判断这个点属于哪个平面区域即可。这里需要极其注意出现多边形内切以及内切共边的情况。

在得到了上面的东西后，即可对于平面图建对偶图，答案显然是对偶图上两点最短路。

复杂度 $O(n^4)$

2015 ACM-ICPC World Finals

B. Asteroids

不会

E. Evolution in Parallel

Problem

给出 $n$ 个字符串 $s_1,...,s_n$ 以及字符串 $t$，你需要将这 $n$ 个字符串划分成两个序列，满足：

1. 对于每个序列中相邻的两个字符串，前者是后者的非平凡子序列。
2. 每个序列中最后的字符串是 $t$ 的非平凡子序列。

定义 $a$ 是 $b$ 的非平凡子序列当且仅当 $a$ 是 $b$ 的子序列且 $a\neq b$

$n,|s_i|\leq 4000,|\sum|=3$

$2s,1024MB$

Sol

如果有一个字符串不是 $t$ 的子串显然无解，否则一定不需要考虑 $t$。

考虑将字符串按照长度排序，显然最后的序列一定是排序后的顺序子序列。

因此可以设 $dp_{i,j}$ 表示考虑前 $i$ 个串，当前第一个序列的结尾为第 $i$ 个串，第二个序列的结尾为第 $j$ 个串 ($i>j$)，这种情况是否合法。但因为转移复杂度为 $O(n)$，因此这样无法接受。

考虑找到最小的 $j$ ，满足 $[j,i]$ 这一段放在一个序列中合法。因为 $j-1$ 不能再放入，因此此时如果第一个序列的结尾为第 $i$ 个串，则第二个序列的结尾一定不会小于 $j-1$。

然后考虑第二个串结尾在 $[j,i-1]$ 内的所有状态。因为这部分内前一个都是后一个的子序列，因此显然第二个串结尾越靠前越优秀。因此这部分只需要记录最小的一个。

因此，对于每个 $i$ ，只需要记录最小的两个满足 $dp_{i,j}$ 合法的 $j$ 进行转移即可。这样转移次数只有 $O(n)$。

复杂度 $O(n^2)$

G. Pipe Stream

Problem

有一个长度为 $l$ 的管道，一个物品从管道一侧开始向另外一侧移动，它的速度 $v$ 位于 $[l,r]$ 之间。

你想知道这个物品的速度。你可以在某个时刻选择一个管道上的一个位置 $k$ ，你可以知道当前物品是否已经经过了 $k$。称这样的操作为观察操作。

观察操作的频率存在限制。你只能在物品开始运动 $s$ 秒后进行第一次观察操作，且两次观察操作间的间隔不少于 $s$ 秒。

你希望求出一个物品的速度 $v'$ ，满足 $|v'-v|\leq \frac t2$，其中 $t$ 给定。

你需要找到一个策略，使得你一定能找到满足条件的 $v'$ 且在最坏情况下，你观察的次数最小。

输出最坏情况下最小的观察次数或者输出无解。

多组数据

$T\leq 100,1\leq l,r,k,s,t\leq 10^9$ ，所有数都是整数

Sol

可以发现，在时刻 $t$ 观察位置 $k$ 相当于判断速度是否超过 $\frac kt$

因为可以观察任意位置，这相当于在 $[0,\frac lt]$ 中选一个值，判断速度是否超过这个值。

因此每次 $t$ 选的尽量小最好，所以每次操作的时刻一定是 $s,2s,3s,...$

考虑一种操作策略。显然操作策略可以被描述为一棵树的形式：

根节点对应区间 $[l,r]$，随后在这个区间内选择一点 $k$ ，判断当前的速度是否超过 $k$ ，随后若没有超过，则只需要判断 $[l,k]$，否则判断 $[k,r]$，因此可以将这两个区间看成两个儿子。

因为要求差不超过 $\frac t2$ ，因此如果当前需要判断的区间长度小于等于 $t$ ，则可以结束这个过程。称这样的区间为结束区间。

考虑每个点，设它的深度为 $d$ ，则到这个点时是第 $d$ 次操作，因此此时选的的 $k$ 不能超过 $\frac l{ds}$，且只要满足这个条件一定合法。

可以发现， $k$ 变小一定不会使得操作树不合法。因此如果存在除去第一个以外的一个结束区间长度不为 $t$，则将这个区间长度向左增加到 $t$，左侧所有端点相应左移。此时一定不会变差。因此存在一种最优方式，满足除去第一个区间外，每个结束区间长度都是 $t$。

此时可以发现，所有询问的位置即为 $r-t,r-2t,...,r-kt$。考虑求出对于每个位置，它只能在前多少次操作被选，记这个次数为 $c_i$。

考虑判断是否合法，可以看成如下问题：

有一个序列 $c_i$，你每次可以选择一个大于 $0$ 的位置，将其删去，剩余的每个数减一。

如果删完序列为空则你获胜，否则你获胜当且仅当对于分出的两部分你都能获胜。

求你能不能获胜。

直接做没有较优做法，但可以发现，因为 $c_i=\lfloor\frac{l}{s(r-it)}\rfloor$，可以发现序列不增。 此时可以发现如下性质：

序列单调时，序列 $c$ 有解当且仅当 $\sum \frac 1{2^{c_i}}<1$

考虑对序列长度归纳，序列长度为 $1$ 时显然有解当且仅当 $c_1>0$，即 $\frac 1{2^{c_i}}<1$。

设序列长度为 $m$，若 $\sum \frac 1{2^{c_i}}<1$，考虑从右向左，找到第一个位置 $x$ 满足 $\sum_{i=x}^m\frac 1{2^{c_i}}\geq\frac 12$。

此时，$\sum_{i=1}^{x-1}\frac 1{2^{c_i}}<\frac 12,\sum_{i=x+1}^m\frac 1{2^{c_i}}<\frac 12$。在从 $m$ 位置分开后，两侧和小于 $\frac 12$，全部减一后满足和小于 $1$ ，根据归纳有解。

如果 $\sum \frac 1{2^{c_i}}\geq 1$，同样考虑找到这样的 $x$。

此时因为 $\sum_{i=x+1}^m\frac 1{2^{c_i}}<\frac 12\leq \sum_{i=x}^m\frac 1{2^{c_i}}$，有 $\sum_{i=x+1}^m2^{c_x-c_i}<2^{c_x-1}\leq \sum_{i=x}^m2^{c_x-c_i}=1+\sum_{i=x+1}^m2^{c_x-c_i}$

因为 $c_i\geq c_{i+1}$，因此两侧都是整数，因此右侧等号成立，所以 $\frac 12=\sum_{i=x}^m\frac 1{2^{c_i}}$

可以发现，此时从 $(m-1,m)$中间分开，右侧和等于 $\frac 12$，左侧和大于等于 $\frac 12$，因此删一个位置后一定有一侧和大于等于 $\frac 12$，全部减一后和大于等于 $1$。

因此归纳成立。

此时即可判断是否有解，考虑计算最优解。

二分答案，考虑答案为 $a$ 是否合法。可以发现，如果存在一个解，则此时把所有大于 $a$ 的 $c_i$ 变成 $a$ 不影响这个解是否合法。

因此，考虑把序列每个元素 $c_i$ 变成 $\min(a,c_i)$，显然如果此时有解，则存在一个最差步数小于等于 $a$ 的解。因此可以用和之前一样的方式判断合法。

最后考虑求出 $c_i$。因为 $c_i=\lfloor\frac{l}{s(r-it)}\rfloor$，根据数论分块的结论，不同的 $c_i$ 只有 $O(\sqrt v)$ 个。使用类似数论分块的做法，即可求出每一种出现的 $c_i$ 以及每种 $c_i$ 出现的次数。

考虑计算 $\sum \frac 1{2^{c_i}}$，相当于有 $O(\sqrt v)$ 对 $a_i,b_i$ ，求 $\sum \frac{a_i}{2^{b_i}}$ 。只需要做类似二进制下的竖式加法即可。这样的复杂度为 $O(\sqrt v\log v)$

再加上二分答案即可，复杂度 $O(T\sqrt v\log^2 v)$。因为答案上界实际上很小，复杂度不满。

H. Qanat

Problem

给出 $w,h$，考虑一个直角三角形形状的山峰。三角形由 $(0,0),(w,0),(w,h)$ 三点构成。保证 $w>h$

给出 $n$ ，你需要选出 $n$ 个位置 $0<a_1<a_2<...<a_n<w$，然后：

你需要在山峰中挖掘从 $(0,0)$ 到 $(w,0)$ 的路径，从 $(w,0)$ 到 $(w,h)$ 的路径，以及对于每个 $i$ ，从 $(a_i,0)$ 到 $(a_i,a_i*\frac hw)$ 的路径。

挖掘一个点的代价 $f(x)$ 为只使用挖掘的路径，到达山峰表面（即 $(0,0),(a_i,a_i*\frac hw),(w,h)$ 这些点）的最短距离。挖掘的总代价即为 $\int f(x)dx$

你需要找到一个方案，使得总代价最小。输出最小代价以及方案。

$n\leq 1000,w\leq 10^4$

$2s,512MB$

Sol

考虑点 $(a_i,0)$ 的最短距离。显然走到 $(a_i,a_i*\frac hw)$ 需要 $a_i*\frac hw$ 的距离，走右侧的点显然不优。

考虑走左侧的点 $(a_j,a_j*\frac hw)$，此时距离为 $a_i-a_j+a_j*\frac hw=a_i*\frac hw+(a_i-a_j)*(1-\frac hw)$。因为 $h<w$，因此这也是不优的。

因此每个 $(a_i,0)$ 一定走到 $(a_i,a_i*\frac hw)$ 最优。可以发现，此时对于 $(a_i,x)$ 最近的点一定是 $(a_i,a_i*\frac hw)$ 。对于 $(a_{i-1},0)$ 到 $(a_i,0)$ 这一段最近的点一定是 $(a_i,a_i*\frac hw)$ 或者 $(a_{i-1},a_{i-1}*\frac hw)$。

考虑每一段挖掘的代价。对于竖直线段，因为它最近的一定是到正上面，因此这部分的代价为 $\sum_{i=0}^{n+1}\frac 12(a_i*\frac hw)^2(a_{0}=0,a_{n+1}=w)$

然后考虑横向 $(a_{i-1},0)$ 到 $(a_i,0)$ 的一段。考虑 $(a_{i-1},a_{i-1}*\frac hw),(a_{i-1},0),(a_i,0),(a_i,a_i*\frac hw)$ 的折线，可以发现只考虑这条折线内，每个点的 $f(x)$ 和整体的 $f(x)$ 相同。对于这条折线，最优解显然是从中间分开，向两侧移动。设折线长度为 $l$，则代价为 $\frac{l^2}4$。

因此这条折线的代价为 $\frac 14(a_i*\frac{h+w}w+a_{i-1}*\frac{h-w}w)^2$，因此总的代价为：

$\sum_{i=0}^n \frac 14(a_{i+1}*\frac{h+w}w+a_i*\frac{h-w}w)^2-\sum_{i=1}^n\frac 12(a_i*\frac hw)^2\\ =\frac 14(\sum_{i=1}^n2a_i^2+\sum_{i=1}^n2a_ia_{i+1}*\frac{h^2-w^2}{w^2}+a_{n+1}^2*\frac{(h+w)^2}{w^2})$

考虑一组最优解，显然在最优解中，对于每一个 $a_i$，只将 $a_i$ 看成变量，得到的函数在此点导数必定为 $0$。

因此此时有：

$4a_i+2(a_{i-1}+a_{i+1})\frac{h^2-w^2}{w^2}=0\\ a_i=\frac{w^2-h^2}{2w^2}(a_{i-1}+a_{i+1})$

考虑满足所有这些限制的 $a$，设 $a_1=x$，则可以用 $x$ 表示出所有 $a_i$，再通过 $a_{n+1}=w$ 即可求出 $x$。

因此可以发现满足这些限制的 $a$ 唯一，因此这即为最优解。

复杂度 $O(n)$

J. Tile Cutting

Problem

对于一个 $a\times b$ 的长方形，左下角坐标为 $(0,0)$，在长方形的每条边上选一个点，满足：

1. 每个点都是格点，且不能选长方形的顶点。
2. 这四个点构成一个平行四边形。

记 $f(x)$ 为使用这种方式，能构造出来的形状不同（旋转/翻转后相同算不同）的面积为 $x$ 的平行四边形个数。

$q$ 组询问，每次给 $l,r$ ，求出 $\max_{l\leq i\leq r}f(i)$ 以及取到最大的 $i$。

$q\leq 500,r\leq 5\times 10^5$

$15s,1024MB$

Sol

考虑把原点设在左侧选的点，设此时上侧选的点位置为 $(a,b)$，下侧选的点位置为 $(c,-d)$，显然 $a,b,c,d>0$

此时显然另外一个点位置为 $(a+c,b-d)$，且显然这样的平行四边形能被切出来。

可以发现，只要 $a,b,c,d$ 不同，得到的平行四边形形状一定不同。对于一组 $a,b,c,d$，计算叉积可以发现平行四边形的面积为 $ad+bc$。

因此 $f(i)$ 相当于满足 $ad+bc=i$ 的正整数 $a,b,c,d$ 对数。记 $d_i$ 表示满足 $ab=i$ 的正整数对数，可以发现 $f(i)=\sum_{j+k=i}d_jd_k$。

求 $d$ 可以线性筛，然后FFT求 $f$ 即可。

因为询问次数很少，询问可以直接暴力。

复杂度 $O(r\log r+qr)$

K. Tours

Problem

给一个 $n$ 个点 $m$ 条边的图，定义一个正整数 $k$ 是合法的，当且仅当：

存在一种给每条边染 $[1,k]$ 中颜色的方案，使得图中的每一个简单环上 $[1,k]$ 中每种颜色出现次数相同。

求出所有合法的 $k$。

$n,m\leq 2000$

$3s,1024MB$

Sol

之前的做法是假的，重新编了一个.jpg

所有的 $1$ 度点显然没用，可以删去，然后可以一直删直到没有 $1$ 度点。

此时考虑再把 $2$ 度点缩成一条链，考虑一条链的情况。

对于一条链 $(a,b)$ ，如果删去它后它的两个端点 $(a,b)$ 在同一个点双内，则相当于这两个端点在一个简单环内。

设简单环为 $(a,c,b,d)$，则考虑环 $(a,c,b),(a,d,b),(a,c,b,d)$，通过前两个环相加再减去第三个环，可以得到 $(a,b)$ 这条链上所有染色出现次数必须相同。

因此合法的 $k$ 一定是 $(a,b)$ 链长的约数。可以发现如果将这条链的端点合并后求出所有答案，答案加上这条链带来的限制一定是整体的答案。

因此只需要每次找到一条这样的链即可。显然可以做到线性。总复杂度 $O(nm)$

细节咕咕咕了。

L. Weather Report

Problem

给出 $n,p_0,p_1,p_2,p_3$。有一个长度是 $n$ 的字符串，其中每一位为 $0$ 的概率为 $p_0$，...，为 $3$ 的概率为 $p_3$。

你需要对 $4^n$ 种可能出现的字符串中的每一个进行编码。每个字符串对应一个 $01$ 串。这些编码需要满足不存在两个 $01$ 串满足一个是另外一个的前缀。

定义编码方式的代价为每种字符串出现概率乘上它对应的编码长度的和。求出所有方式中最小的代价。

$n\leq 20$

$2s,1024MB$

Sol

可以发现这是Huffman编码的形式，把概率看为权值即可。

显然，一个字符串出现的概率只和每种字符出现的次数有关。因此枚举每种字符出现的次数，可以得到 $O(n^4)$ 种概率，以及每种概率的字符串数。

考虑Huffman编码的正常做法，每次拿出两个权值最小的，将它们加起来，代价加上它们的和。对于多个相同的值，它们的操作显然可以一起做。

若干个相同的数在 $\log$ 轮合并后就会变成 $\log$ 个数，可以发现只会有 $O(n^4\log n)$ 次这样的操作。

显然合并出来的数权值递增。可以将原先的数排序后放在第一个队列，合并出来的数放在第二个队列，每次拿出两边较小的队首即可。

复杂度 $O(n^4\log n)$

M. Window Manager

Problem

给一个 $n\times m$ 的二维平面，支持 $q$ 次如下操作：

1. 向平面中加入一个矩形。矩形的边界平行于整体边界。如果加入矩形会导致矩形重合或出界，则不加入并输出错误信息。
2. 选择一个位置，删除包含这个位置的矩形，不存在输出错误信息。
3. 选择一个位置，改变包含这个位置的矩形的大小，如果不存在或者改变后导致矩形重合或出界则分别输出错误信息。
4. 选择一个矩形，将其向四个方向中的一个移动一个距离。矩形移动的过程中如果遇到其他矩形，则会推动这个矩形继续移动。不能移动则停止。如果移动的距离小于目标距离，则输出错误信息。

最后输出此时的所有矩形位置。

$n,m\leq 10^9,q\leq 256$

$2s,1024MB$

Sol

前三个操作暴力判断即可，考虑最后一个操作。

假设当前为向右推，记 $d_i$ 表示矩形 $i$ 最后的左边界位置。

则如果矩形 $i$ 在矩形 $j$ 的左侧且矩形 $i$ 向右能碰到矩形 $j$，则设矩形 $i$ 的宽度为 $w_i$，则无论怎么向右推都有 $d_j\geq d_i+w_i$。

对于推动的操作，先考虑无视边界的限制，则操作为将 $d_i$ 加 $k$，随后通过上面的不等式更新所有点的 $d$。可以发现这样得到的结果即为正确的结果。

可以发现上面的不等式相当于图上的单源最长路。可以 $O(q^2)$ 求出。

此时可以求出超过边界的距离，然后少推这么多距离即可。

复杂度 $O(q^3)$，注意细节。

2016 ACM-ICPC World Finals

A. Balanced Diet

Problem

有 $n$ 种物品，每一天，你可以选择拿任意一种物品中的一个。

设 $s_{i,j}$ 表示前 $i$ 天拿走的第 $j$ 种物品的数量，给出 $a_{1,2,...,n}$，定义 $f_i=\frac{a_i}{\sum a_i}$，你的方案需要满足：

$f_j*n-1<s_{n,j}<f_j*n+1$

现在给出前 $m$ 天你的选择，保证这部分合法，之后你可以任意选择，你可以在任一时刻停止。你希望你之后额外选择的次数最多。

输出你最多还能选多少次，如果可以无限选输出 forever。

$n,m,\sum a_i\leq 10^5$

$2s,1024MB$

Sol

如果只考虑下界，则相当于如下问题：

每种物品在 $\frac 1{f_i}$ 轮之前是合法的，每次选择它会让它的合法轮数加上 $\frac 1{f_i}$。

此时显然的贪心做法是每次选一个合法轮数最小的加。相当于每次选一个 $\frac{s_i}{f_i}$ 最小的加。

显然，在 $n-1$ 轮后，$n-1=\sum s_i<\sum f_i*n=n$，因此一定存在一个 $\frac {s_i}{f_i}<n$

此时选的数一定满足这个限制，此时再选一个这个，则 $s_i+1<f_i*n+1$，因此这样选一定满足上界。

同时 $n$ 轮后显然所有 $\frac {s_i}{f_i}$ 的差不超过 $1$，此时再做 $\sum a_i$ 轮一定循环。因此这么多轮之后如果还合法则表示一定可以无限进行下去。

复杂度 $O((n+\sum a_i)\log n)$

B. Branch Assignment

Problem

有一个 $N$ 个点 $M$ 条边的有权连通图，上面有 $n+1$ 个人，给出每个人的位置。

对于前 $n$ 个人，记人 $i$ 到人 $n+1$ 的距离为 $d_i$。

你需要将所有人划分成 $m$ 个集合，对于一个集合 $S$，它的代价为：

$\sum_{i,j\in S,i\neq j}d_i+d_j$

总的代价即为每个集合代价之和。求最小的总代价。

$n,m,N\leq 5000,M\leq 5\times 10^4$

$2s,1024MB$

Sol

考虑给代价加上 $2\sum d_i$，可以发现这时一个集合的代价变为 $2|S|\sum_{i\in S}d_i$。

假设确定了最后集合的大小，则显然是把 $d$ 小的往 $|S|$ 大的放。因此存在一种最优方式使得集合的划分方式等价于将所有 $d_i$ 排序，然后在序列上划分出若干段作为若干个集合。

此时可以设 $dp_{i,j}$ 表示前 $i$ 个元素划分 $j$ 段的最小代价，转移为：

$dp_{i,j}=\max_{k<i}dp_{k,j-1}+(i-k)\sum_{l=k+1}^id_l$

可以发现转移系数显然满足四边形不等式，因此每一层的转移有决策单调性，直接dp即可。

复杂度 $O(nm\log n+M\log M)$

D. Clock Breaking

Problem

有一个显示时间(小时/分钟)的电子表，电子表为一个 $7\times 21$ 的区域，其中有 $30$ 个部分显示时间。

但是这些部分可能存在问题，一些部分可能永远不会亮，另外一些部分可能永远都亮。

给出连续 $n$ 分钟中每一分钟它的显示情况，判断每个部分的状态（正常工作/常暗/常亮/无法确定）。如果无解输出 impossible

$n\leq 100$

$5s,1024MB$

Sol

考虑枚举一个开始时间，判断是否可能是这个开始时间，此时满足如下条件：

对于一个部分，它在这个区间中满足以下两者之一：

1. 这部分给出的显示情况和这部分正常情况下的显示情况匹配。
2. 这部分在给出的显示中常暗或常亮。

判断第二个非常容易，对于第一个，可以使用bitset优化判断。

如果得到一个开始时间合法，则显然可以求出此时每个位置可能的状态。枚举所有时间即可得到最后每条线段可能的状态集合，即可判断答案。

复杂度 $O(\frac{n*1440*30}{32})$ 好像没有必要bitset

F. Longest Rivers

Problem

有一个 $n$ 个叶子的树，满足每个点的儿子数量不为 $1$。每条边有长度。

从每个叶子开始都有一条河流出发。当多台条河流相遇时，一条河流继续延伸，其它一条河流在此停止。

定义一条河流的排名为长度大于它的长度的河流数量加一。对于每条河流，求出它对于所有延伸的情况，它的最小排名。

$n\leq 5\times 10^5$

$10s,1024MB$

Sol

考虑一条河流的答案，最优情况下然这条河流会延伸到根，此时相当于需要长度大于这条河流的河流最少。

从下往上考虑，对于每个点，如果子树内还没有长度大于给定值的，则显然希望让长度最小的向上延伸最优。

但如果长度最小的加上向上的边后大于给定值，则此时经过这个点向父亲边的河流长度一定大于 $k$。

考虑所有满足这个条件的边，经过这些边的河流长度都大于 $k$。可以发现，设 $d$ 为这些边中满足子树内没有这样的边的边数量，则显然至少需要 $d$ 条河流覆盖这些位置，且这 $d$ 条河流可以覆盖这些边到根的路径。因为询问点到根的距离为给定值，因此询问点到根路径上的边不会出现，因此 $d$ 即为答案。

可以发现一条边是否满足条件只与子树内叶子到它的最小距离是否大于给定值有关，按照给定值排序后相当于如下操作：

1. 加入一条边。
2. 询问当前有多少条边满足它的子树内没有被加入的边。

数据结构维护当前每个子树被哪条边覆盖，这样加边的时候就能找到变成不满足条件的边。

复杂度 $O(n\log n)$

H. Polygonal Puzzle

不会

I. Road Times

Problem

给一个 $n$ 个点 $m$ 条边的有向图，边有长度。

在每条边上还有一个 $[1,2]$ 之间的实数因子，经过这条边的时间为长度乘上这个因子的乘积。

给出 $k$ ，已知 $k$ 条如下信息：

一个人从 $s$ 出发到 $t$，他一定会选择长度和最短的方案。已知他经过这部分用了 $x$ 的时间。

有 $q$ 次询问，每次给出 $s,t$，表示：

一个人从 $s$ 出发到 $t$，他一定会选择长度和最短的方案。你需要求出他需要时间的上下界。

$n\leq 30,m,k,q\leq 100$，边权不超过 $1000$，保证给出的 $q+k$ 对点间最短路唯一。

$5s,1024MB$

Sol

记每条边的额外权值为一个 $[0,1]$ 间的实数变量 $v_i$，则可以看成如下约束:

1. $0\leq v_i\leq 1$
2. 对于一个给出的路径 $S$ ， $\sum_{i\in S}l_iv_i=time-\sum_{i\in S}l_i$
3. 对于询问的路径 $S$，最大/最小化 $\sum_{i\in S}l_iv_i$

那么可以对于每个询问跑单纯形即可，复杂度 $O(q*?)$。

可能需要用力卡常，一种有效的方式是先初始化再跑每组询问。

J. Spin Doctor

Problem

给出 $n$ 对数 $(a,b)$，其中有一些数对为关键的数对。

你需要选择实数对 $S,T$，随后将所有的数对按照 $aS+bT$ 排序，定义此时的权值为最坏情况下排序后关键数对间距离的最大值。

你希望权值最小，输出最小的可能权值。

$n\leq 2.5\times 10^5$

Sol

特判只有一个关键点的情况，此时答案一定为 $1$，否则选择 $S,T$ 后，设关键点的 $aS+bT$ 的最小值，最大值为 $mn,mx$，则最坏距离一定为 $\sum_i[a_iS+b_iT\in[mn,mx]]$。

将数对看成二维平面上的点，可以发现选择 $S,T$ 相当于选择一个斜率，用两条这个斜率的线去夹所有黑点。这些相当于夹所有关键点的凸包。

求出关键点的凸包，则相当于找到一对平行线夹这个凸包，使得平行线夹住的点数量最小。

考虑平行线角度旋转的过程。对于凸包内的点，它一定全程在平行线内。因为得到的都是凸包的切线，对于一个凸包外的点，考虑求出它到凸包的两条切线。可以发现，在旋转的过程中，这个点在平行线内的时间段一定是从碰到一条切线开始，到碰到另外一条切线结束。

只需要求出切线，即可求出这个点在平行线内的时间段。这样通过旋转即可求出所有情况的最小答案。

在凸包上选一个点，考虑这个点和凸包上点的连线，可以二分求出这条线和凸包另外一个点的交点。

然后只需要在两侧分别找到两个方向上最外侧的点，可以发现这个过程类似于凸包上二分，判断凸包上相邻两条边以及这个点的连线的角度关系即可。

复杂度 $O(n\log n)$

K. String Theory

Problem

称一个串为 $1$ 层嵌套串，当且仅当这个串的开头结尾为引号 '，且其他字符都不是引号。

称一个串为 $k$ 层嵌套串，当且仅当这个串的开头结尾都有 $k$ 个引号，且删去这 $k$ 对引号后，剩下的部分由若干个 $k-1$ 层嵌套串和若干非引号字符组成。

给出 $n$ 以及 $n$ 个正整数 $a_{1,2,...,n}$，一个串的组成方式为 $a_1$ 个引号加上若干个非引号，加上 $a_2$ 个引号加上若干个非引号，...，加上 $a_n$ 个引号。求出最大的 $k$ ，满足这个串是 $k$ 层嵌套串。

$n,a_i\leq 100$

$2s,512MB$

Sol

考虑判断一个串是不是 $k$ 层嵌套串。一个显然的条件为引号数量为偶数。

如果 $k=1$ ，则合法当且仅当原串只有两个引号。

如果 $k=2$，可以发现只要前两个引号连续且后两个引号连续，中间的引号可以全部看成 $1$ 层嵌套串。

对于 $k>1$ 的情况，显然开头结尾都必定顺序出现 $k,k-1,k-2,...,2$ 个连续引号。如果不能将开头结尾划分成这种形式则无解。

可以发现，此时可以把中间的引号全部看成 $1$ 层嵌套串，这样得到的一定为一种合法 $k$ 层嵌套串。因此满足上一个条件一定合法。直接判断即可。

复杂度 $O(n*a_i)$

M. What Really Happened on Mars?

Problem

模拟一个优先级上限协议

$2s,1024MB$

Sol

考虑直接模拟执行的过程，记录当前每个任务执行的情况以及当前每个资源被锁定的情况。唯一的问题在于每次计算当前优先级和阻塞关系。

每个资源的优先级上限已经确定，因为一个任务的当前优先级为所有被它阻塞的任务的优先级的最大值，考虑从高到低枚举优先级，判断哪些任务的优先级等于这个优先级。

考虑基准优先级等于当前枚举的优先级的任务，如果它的当前优先级已经确定(大于基准优先级)，则这种优先级一定在当前优先级中不会出现。

否则，因为剩下没有被确定的任务优先级一定小于等于它的优先级，因此这个任务的当前优先级等于它的基准优先级。

此时可以求出这个任务被哪些任务阻塞，如果阻塞这个任务的任务 $A$ 的当前优先级已经确定(大于它的当前优先级)，则这个任务的当前优先级不会改变。否则，任务 $A$ 的当前优先级会变的和这个任务的当前优先级一样。可以发现它的当前优先级也被固定了。可以使用类似bfs的方式实现这个过程。此时没有被确定的点当前优先级一定小于此时的优先级。

在上面的过程中每个点只会被确定一次，因此复杂度显然为 $O(n^2)$

注意到只要不出现新加入任务的情况，如果当前执行的任务执行到了若干个连续的 C，则显然之后的时刻所有优先级不变，直到这连续的 C 被执行完。因此总的模拟步数为 $O(na+s)$

复杂度 $O(n^2(na+s))$

2017 ACM-ICPC World Finals

A. Airport Construction

Problem

给一个 $n$ 个点的简单多边形，你需要在多边形内部画一条线段，求线段的最长长度。

$n\leq 200$

$2s,1024MB$

Sol

显然可以通过平移线段，使得线段至少覆盖一个顶点。

然后以这个点为原点旋转线段，考虑线段长度的变化，相当于以某个方向向双向连出射线，在第一个出界的位置停止。可以发现，一个端点在多边形的一条边上移动时，这一侧长度的变化为一个下凸函数。而凸函数改变的时刻即为碰到一个顶点时。

两个下凸函数相加还是下凸函数，可以发现对于下凸函数一定在端点处取值最优。因此最优解一定至少经过两个多边形顶点。

考虑枚举两个多边形顶点，考虑它们的连线，然后求出此时延伸的长度。枚举每条多边形的边判断相交即可。注意出现重合等特殊情况。

复杂度 $O(n^3)$

B. Get a Clue!

Problem

$4s,1024MB$

Sol

可以发现，每一种可能的信息(没有反驳，进行了反驳)相当于对一个人手上的牌进行了限制。

除去第一个人的牌后，剩余牌只有 $16$ 张，考虑枚举一个人手上的牌，判断是否合法。此时只需要满足如下条件：

对于一次提议，如果问到了这个人且这个人没有反驳，则这个人一定没有这三种牌。

如果这个人反驳了，则这个人一定至少有这三种牌中的一张，如果证据可见则一定他有这一张。

因此可以 $O(2^{16}*n)$ 求出每个人可能的牌集合。显然最后只需要知道所有人的牌的集合，考虑合并每个人的牌。

因为每个人的牌数量固定，因此可以直接看成一个与卷积。最后枚举判断即可。

复杂度 $O(16*2^{16}+2^{16}*n)$

D. Money for Nothing

Problem

给出 $n$ 对 $(a_i,b_i)$，$m$ 对 $(c_i,d_i)$，你需要在两侧各选一对，最大化：

$\max(c_j-a_i,0)*\max(d_j-b_i,0)$

$n,m\leq 5\times 10^5$

$5s,1024MB$

Sol

看成二维平面上的问题，则相当于有若干个黑白点，你需要选一个黑点作为左下角，一个白点作为右上角，最大化这样得到的矩形的大小。

可以发现如果一个黑点 $A$ 在另外一个黑点 $B$ 的右上方，则 $A$ 被 $B$ 替代一定更优。因此可以删掉没用的黑点。最后剩下的黑点 $(a_i,b_i)$ 按照 $a$ 排序后满足 $a_i<a_{i+1},b_i>b_{i+1}$。白点同理。

此时如果一个留下的白点在留下的黑点的左下方，可以发现这个白点一定没有意义，可以直接删去。

此时设 $f_{i,j}=(c_j-a_i)(d_j-b_i)$，则留下的点中计算这个值与计算原答案等价。问题变为求 $i,j$ 使得 $f_{i,j}$ 最大化。

可以发现这个满足 $f_{i-1,j}+f_{i,j-1}\leq f_{i,j}+f_{i-1,j-1}$，即满足决策单调性。因此可以直接分治。

复杂度 $O((n+m)\log (n+m))$

G. Replicate Replicate Rfplicbte

Problem

有一个无限大的01矩阵 $s$。有一个 $H\times W$ 的初始矩阵 $t$ 。在时刻 $0$ 时，矩阵 $s$ 中的一个 $H\times W$ 的区域的值等于 $t$，其余区域均为 $0$。

在每个时刻中， $s$ 的每个位置上的值都会发生变化。对于一个位置，这个位置的值为上一个时刻这个位置周围的 $9$ 个位置的和模 $2$ 的结果。

但在每一个时刻的变化后，可能会有一个位置上的值发生变化($0$ 变 $1$，$1$ 变 $0$)。

在若干个时刻后 $s$ 矩阵中所有的 $1$ 在一个 $n\times m$ 的区域中，给出这个区域中每个位置的值，你需要找到一个大小最小的初始矩阵 $t$，使得矩阵 $t$ 能通过上面的变化能变为 $s$。

$n,m\leq 300$

Sol

称当前矩阵的外边界为一个最小的包含矩阵所有 $1$ 的矩形。

可以发现，假设之前的外边界为 $a\times b$，则一次变化后外边界一定会扩展一圈，即变为 $(a+2)\times(b+2)$。并且显然这之后再改变一个位置的值不能改变外边界大小。

考虑倒推每次操作之前的情况，可以发现每倒推一次外边界必须缩小一圈。

如果没有翻转一个格子的值的操作，则每个位置现在的值是之前周围 $3\times 3$ 的值的异或和。在这一次之前，外边界上的位置应该全是 $0$。考虑从上往下依次确定每个位置之前的值，可以通过 $(x-1,y-1)$ 现在的值以及 $(x-1,y+t),(x,y+t),(x+1,y-1),(x+1,y)(t\in \{-1,0,1\})$ 之前的值推出 $(x,y)$ 之前的值。

但如果翻转了一个格子，会导致这样求出的结果在下右边界上不是全 $0$。考虑翻转 $(x,y)$，可以发现，这会改变所有满足 $x\leq x',y\leq y',3\not\equiv(x-x')(y-y') $ 的点 $(x',y')$ 的值。

因此考虑推出下右边界上两行的值，通过这两行上推出的值，可以找到唯一一个能让边界变为 $0$ 的 $x,y$。

因此这一步可能的改变一个位置的值操作唯一，直接倒推到不能继续即可。

复杂度 $O(nm\min(n,m))$

H. Scenery

不会

J. Son of Pipe Stream

Problem

有一个 $n$ 个点 $m$ 条边的网络，每条边有一个容量 $c_i$。

你需要运输两种液体 $A,B$，$A$ 的源点为 $1$，$B$ 的源点为 $2$，两种液体的汇点都为 $3$。

在管道中可以同向运输两种液体，但不能同时双向运输。两种液体的体积比为 $v$，你能在一条管道内运输质量为 $a$ 的 $A$ 液体和质量为 $b$ 的 $B$ 液体当且仅当 $a+bv\leq c_i$。

假设你最后运输了质量为 $x$ 的 $A$ 液体和质量为 $y$ 的 $B$ 液体，你的分数为 $x^ay^{1-a}$。

求出一种方案使得你的分数最大化。

$n\leq 300,m\leq \frac{n(n-1)}2$

$5s,1024MB$

Sol

显然可以给答案乘上 $\frac 1{v^{1-a}}$ 后变为 $v=1$ 的问题。

考虑 $x,y$ 的限制。设只考虑 $A$ 液体的最大流为 $s_1$，只考虑 $B$ 液体的最大流为 $s_2$，考虑两种液体的最大流为 $s_3$，则一定满足如下限制：

$x\leq s_1,y\leq s_2,x+y\leq s_3$

此时两种液体可以交换，因此可以不考虑双向流动的情况。

考虑先处理完 $A$ 液体的流，再考虑此时 $B$ 液体的最大流。考虑此时的割集：

如果割集包含 $1,2$，则在 $A$ 液体没有流时割边流量和大于等于 $s_3$，此时的流量和一定大于等于 $s_3-x$。

如果割集包含 $2$ 不包含 $1$，则在 $A$ 液体没有流时割边流量和大于等于 $s_2$，因为 $A$ 液体流入这部分的流量等于流出的流量，因此此时割集流量和大于等于 $s_2$。

因此最小割一定大于 $\min(s_3-x,s_2)$，这说明上面的结论成立。

此时最优解一定满足 $x+y=s_3$，可以三分求出最优解的位置。

最后考虑求方案。先将两种液体整体流一次，求出每条边的方向和流量。然后每条边只保留这么多流量，分别对两种液体求一次网络流即可。

复杂度 $O(能过)$

K. Tarot Sham Boast

Problem

有一个长度为 $n$ 的字符串， 每一位均为随机生成。

给出 $m$ 个串 $s_{1,2,...,m}$，它们的长度相同。

将它们按照它们在随机串中出现的概率排序。

$m\leq 10,n\leq 10^6,|s_i|\leq 10^5$，字符集大小为 $3$。

$2s,1024MB$

Sol

根据歌唱王国的结论，一个串出现的期望时间为 $\sum_{i=1}^l[s[1,i]=s[l-i+1,l]]3^i$。

因此可以直接感性理解，计算上面这个值并排序即可。计算这个值可以使用KMP。

唯一需要注意的是，上面的期望计算方式中，一个长度为 $i$ 的border参与计算当且仅当两个串重叠在一起，重叠长度为 $i$。因此长度小于 $2l-n$ 的border需要被忽略。

复杂度 $O(n|s|\log n)$

详细证明

L. Visual Python++

Problem

给出二维矩阵上 $n$ 个左上角和 $n$ 个右下角，左上角 $(x_1,y_1)$ 和右下角 $(x_2,y_2)(x_1\leq x_2,y_1\leq y_2)$ 构成了一个矩形，称矩形的边界为矩形内满足 x=x_1\or x=x_2\or y=y_1\or y=y_2 的点。

你需要将角之间两两配对形成 $n$ 个矩形，要求这 $n$ 个矩形之间两两要么不交要么包含，且边界不能相交。输出任意一个方案或输出无解。

$n\leq 10^5$

$5s,1024MB$

Sol

考虑 $x$ 最大的一个左下角（如有多个考虑 $y$ 最大的），设这个角为 $(x_1,y_1)$

考虑此时它能匹配的所有右下角，找到其中 $y$ 最小的一个 $(x_2,y_2)$。

如果 $(x_1,y_1)$ 不匹配 $(x_2,y_2)$，假设 $(x_1,y_1)$ 匹配了 $(x_3,y_3)$ 满足 $y_3\geq y_2$，此时假设 $(x_2,y_2)$ 匹配的左上角为 $(x_4,y_4)$，则此时 $x_4\leq x_1<x_3$，$y_4\leq y_2\leq y_3$，此时这两个矩形一定相交但不包含或者边界相交。

因此 $(x_1,y_1)$ 只能匹配它能匹配的中 $y$ 最小的。考虑从下往上扫依次考虑每个点的匹配。扫到一个右下角就加入集合，对于一个左上角，此时相当于在集合中 $y$ 大于等于它的中选一个 $y$ 最小的。set维护即可。

最后考虑判断合法，相当于有若干条线段判断是否相交，可以再做一次扫描线。

复杂度 $O(n\log n)$

2018 ACM-ICPC World Finals

C. Conquer the World

Problem

有一棵 $n$ 个点的树，边有边权。

点 $i$ 上初始有 $a_i$ 个人，你希望通过移动人的位置，让点 $i$ 上至少有 $b_i$ 个人。

最小化每个人移动的距离和，输出最小值。

$n\leq 2.5\times 10^5,\sum a_i\leq 10^6$

$8s,1024MB$

Sol

称人为流量，点 $i$ 上至少有 $b_i$ 个人为需求。

考虑一条链上的问题，显然这是一个费用流模型。

考虑在链上从从左往右扫，依次加入所有的流量。

如果不存在反悔操作，则直接使用set记录当前左侧没有使用的流量，每次加入一个需求时按照距离从小到大匹配即可。

但可能存在反悔操作，即费用流增广时流反向边的情况。

考虑一个匹配 $(a,b)(a<b)$：

如果 $a$ 反悔去匹配后面的一个 $c$，则相当于撤销这次匹配，因此代价为 $c-b$，这可以看成一个位置为 $b$ 的流量，匹配这个流量相当于撤销之前的匹配。（在链上点不带权的模型中，一定不会用这个匹配）

如果 $b$ 反悔去匹配后面的一个 $c$，则代价为 $c+a-2b$，可以看成一个位置为 $2b-a$ 的需求。

对于 $a>b$ 的情况同理。

一个代表撤销操作的点可以继续匹配，因此多次匹配后一个点可以代表若干次撤销，而匹配这个点代表撤销上一次匹配时的所有操作，可以发现这样的点参与上面的匹配时，反悔的代价仍然是这个。

考虑加入一个点，设它增广路的结尾为点 $x$，则 $x$ 的匹配一定反悔，这会导致导致包含 $x$ 的匹配点反悔。考虑看成匹配了这个匹配点，可以发现这样匹配的最短路一定等于增广路上的最短路（不然之前的匹配不是最优），因此每次加入点只需要和之前的一个点匹配。

考虑顺序扫过去，遇到一个流量时，如果它和一个需求匹配能减小费用则匹配，否则不动。遇到一个需求时，先看成它和位置 $-\infty$ 匹配，然后再做反悔。这也可以看成先将匹配点加入，然后取能让代价减小的匹配，一直取到不存在这样的匹配。

如果一个匹配的两侧都反悔去匹配后面的点，则此时两个匹配一定交叉，此时一定不优。因此每次加入的两个点最多有一个改变，因此操作次数为 $O(n)$，使用堆即可做到 $O(n\log n)$

考虑树上的情况，此时两点匹配代价变为 $dep_u+dep_v-2*dep_{lca(u,v)}$。

从下向上维护匹配，记录点的深度，在点 $u$ 处处理所有 $lca$ 在这个点的匹配，此时可以看成将它所有儿子的两种点分别合并，然后取能让代价减小的匹配。反悔时类似的处理代价即可。使用可并堆即可做到1log

可以将深度相同的点合并，这样的复杂度为 $O(n\log n)$。

D. Gem Island

Problem

有 $n$ 个人，初始每个人有一个 $v_i=1$

每一天随机选择一个人，以 $\frac{v_i}{\sum v_i}$ 的概率选中 $i$，然后将这个人的 $v_i$ 加一。

求出 $m$ 天后，$v_i$ 最大的 $k$ 个人的 $v_i$ 和，输出实数。

$n,m,k\leq 500$

$3s,1024MB$

Sol

输出实数导致容斥过不去

可以将这个概率乘上 $\frac{(n+m)!}{n!}$ 变为方案数，考虑一种最后 $v_{1,2,...,n}$ 出现的方案数。

考虑每一次加一给了谁，则这部分的方案数为 $\frac{m!}{\prod(v_i-1)!}$

再考虑每一个人每次加一的系数，这部分为 $\prod(v_i-1)!$，总的方案数即为上两个相乘。

因此可以发现每种可能的 $v$ 出现概率相等。

设 $f_{n,m}$ 表示此时的答案，$s_{n,m}$ 表示 $n$ 个非负整数和为 $m$ 的方案数。考虑枚举有多少个人最后 $v_i=1$，然后再让剩下的人每个人 $v_i$ 减一，则有：

$f_{n,m}=\min(n,k)*s_{n,m}+\sum_{i=1}^nC_n^if_{i,m-i}$

最后除以 $s_{n,m}$ 即可，显然 $s_{n,m}=C_{n+m-1}^m$。

复杂度 $O(n^2m)$

E. Getting a Jump on Crime

Problem

有一个 $n\times m$ 的网格，其中每个格子均为 $w\times w$ 的正方形。每个格子有一个高度 $h_{i,j}$。

你初始在某一个格子的中心，你可以通过跳跃到达其他格子的中心。

你跳跃的初速度 $v$ 给定，你可以选择跳跃的水平方向速度 $v_d$ 和竖直方向速度 $v_h$，满足 $v_d^2+v_h^2=v$，忽略空气阻力， $t$ 秒后你的速度向量可以看成 $(v_d,v_h-gt)$，其中 $g$ 为重力加速度，$g$ 给定。你必须正好降落在格子中心。在跳跃的过程中，你不能碰到其它格子，即在这些格子上时高度不能小于等于这个格子的高度。

对于每个格子，求出跳到这个格子需要的最少跳跃次数或输出不能到达。

$n,m\leq 20$

$2s,1024MB$

Sol

考虑一次跳跃，可以看成你从原点出发，必须经过 $(x,y)$，则需要满足：

$\int_{t=0}^\frac{x}{v_d}v_h-gt=y\\ \frac{xv_h}{v_d}-\frac{gx^2}{2v_d^2}-y=0\\ 2xv_dv_h=gx^2+2v_d^2y\\ 2x^2v_d^2(v^2-v_d^2)=(2yv_d^2+gx^2)^2$

这是一个关于 $v_d^2$ 的二次方程，可以得到两个可能的 $v_d$。

可以发现对于两个这样的抛物线， $v_d$ 更小 $v_h$ 更大的那个一定在更上方，因此可以选择合法的里面 $v_d$ 最小的。这样跳跃的曲线唯一。

然后考虑判断会不会碰到其它格子，因为曲线是上凸的，可以找出路线上每次经过横向或者纵向的边界的时刻，判断这些时刻即可。这样的时刻只有 $O(n+m)$ 个。

此时可以判断能否从一个点跳到另外一个点。然后bfs即可。

复杂度 $O(n^2m^2(n+m))$

G. Panda Preserve

Problem

给一个 $n$ 个点的简单多边形，你需要在多边形内找一个点，让这个点到多边形所有顶点的距离的最小值最大。输出最大距离。

$n\leq 2000$

$10s,1024MB$

Sol

对于每个顶点，考虑求出平面上满足与它的距离小于等于与其他顶点的距离的区域。即 $n$ 个顶点的 Voronoi diagram。

因为数据范围不大，考虑 Voronoi diagram 的暴力做法，对于每个点 $A$，考虑另外一个点 $B$ 和它的垂直平分线，可以发现与 $A$ 的距离小于等于与 $B$ 的距离的点即为垂直平分线一侧的点，因此对所有平分线求半平面交即可。复杂度 $O(n^2\log n)$。

考虑答案可能在的点，显然在多边形上距离一个点最远的点一定是一个顶点，因此对于点 $A$，答案只可能在如下两种点：

1. Voronoi diagram 上距离 $A$ 最近的点组成的多边形的顶点（如果在简单多边形内）。
2. Voronoi diagram 上距离 $A$ 最近的点组成的多边形与给出多边形的交点。

可以发现 Voronoi diagram 的总点数边数为 $O(n)$ 级别，因此对于第一部分，可以对于每个点暴力判断它是否在多边形内。对于第二部分，可以枚举 Voronoi diagram 的线段和多边形的线段求交点。

复杂度 $O(n^2\log n)$

H. Single Cut of Failure

Problem

给一个矩形的边框，有 $n$ 条线段，每条线段的端点都是边框上的点且不在角上，且两个端点不在同一条边框上。

你需要画若干条线段，每条线段端点都是边框上的点，使得给出的每一条线段至少与你画的一条线段相交。

找一种画的线段数量最小的方案，输出方案。

$n\leq 10^6$

$6s,1024MB$

Sol

因为不存在在同一个边框上的点，因此连接两条对角线一定满足要求，因此只需要判断是否能一条线段解决问题。

枚举第一个端点所在的位置，此时另外一个端点的位置限制之和第一个端点右侧区间中右端点的最小值以及左侧区间中左端点的最大值有关。二倍环长变成链后前后缀和即可。

复杂度 $O(n\log n)$

如果没有性质，注意到选 $n$ 条线段可以看成选 $2n$ 个分界点，可以使用类似 Surveillance 的倍增做法同样做到 $O(n\log n)$。

I. Triangles

Problem

给一个 $n\times m$ 的三角形点阵，其中相邻的边中有一些存在，有一些不存在。

求这个图中的三角形数量。

$n,m\leq 3000$

$6s,1024MB$

Sol

考虑先求出 $\Delta$ 形状的三角形数量，另外一个方向同理。

枚举底边所在的行，记 $rb_{i,j}$ 表示位置 $(i,j)$ 向右侧延伸的长度，$sr_{i,j}$ 表示位置 $(i,j)$ 向右上延伸的长度，$sl_{i,j}$ 表示位置 $(i,j)$ 向左上延伸的长度。

则 $(i,j),(i,k)(j<k)$ 合法当且仅当：

rb_{i,j}\geq k-j\and sr_{i,j}\geq k-j\and sl_{i,k}\geq k-j

对于一个 $k$ ，可以求出只考虑限制 $3$ 时合法的 $j$ 的后缀。对于 $j$ 也可以求出只考虑限制 $1,2$ 时合法 $k$ 的前缀。

此时相当于有序列 $l_{1,...,n},r_{1,...,n}$，求有多少对 $(i,j)(i<j)$ 满足 $l_i\geq j,r_j\leq i$，可以发现这类似于二维数点，扫过去树状数组维护即可。

复杂度 $O(nm\log n)$

J. Uncrossed Knight's Tour

不会

2019 ICPC World Finals

B. Beautiful Bridges

Problem

$n\leq 10^4$

$10s,1024MB$

Sol

考虑 $dp_{i}$ 表示上一个柱子在位置 $i$ ，前面的最小代价。只需要快速判断一个连边是否合法即可 $O(n^2)$ dp。

显然判断合法只需要判断中间的关键点是否都在圆弧的下方。设当前位置为 $x_2$，上一个位置为 $x_1$，则对于一个关键点 $(x,y)(x_1\leq x\leq x_2)$，需要满足：

y-h+\frac{x_2-x_1}2\leq\sqrt{(\frac{x_2-x_1}2)^2-(x-\frac{x_2+x_1}2)^2}\\ y-h+\frac{x_2-x_1}2\leq 0\or (y-h+\frac{x_2-x_1}2)^2\leq (\frac{x_2-x_1}2)^2-(x-\frac{x_2+x_1}2)^2

此时如果只把 $x_1$ 看成变量，则第一个限制相当于 $x_1\geq$ 一个值，第二个限制相当于 $ax_1^2+bx_1+c\leq 0(a\geq 0)$

因此一个关键点的限制形如 $x_1\in[a,b]$，因此考虑 $x_1$ 从大到小扫，依次加入限制并合并即可。

复杂度 $O(n^2)$

C. Checks Post Facto

不会

F. Directing Rainfall

Problem

二维平面上有 $n$ 条线段，满足如下条件：

1. 没有两条线段相交。
2. 不存在线段平行于坐标轴。

一个点从 $x$ 开始下落的方式如下：

初始这个点在 $(x,10^{18})$，随后这个点开始竖直向下移动。如果这个点碰到了一条线段，则它会沿着线段移动到端点再开始自由下落。下落到 $y=0$ 时停止。

你可以在线段上放洞。如果你在一条线段上放了一个洞，则点沿着线段运动的过程中碰到洞时会离开线段开始向下下落。

你需要放尽量少的洞，满足如下条件：

给定 $l,r$，存在 $x\in[l,r]$，使得一个点从 $x$ 开始下落，停止时横坐标在 $[l,r]$ 之间。

输出最小的洞数量。

$n\leq 5\times 10^5$

$10s,1024MB$

Sol

设 $dp_i$ 表示从横坐标 $i$ 出发时，至少需要放多少个洞。

在没有线段的时候，显然 $dp_{x}=0(x\in[l,r]),dp_{x}=+\infty(x\not\in[l,r])$

考虑加入一条线段，满足这条线段在之前所有线段的上方。设这条线段端点为 $(x_1,y_1),(x_2,y_2)$，考虑 $dp$ 的变化：

如果 $y_1<y_2$，则此时：

$dp_x=\min(\min_{i\in[x_1,x]}dp_i+1,dp_{x_1})(x\in[x_1,x_2])$

如果转移中只考虑第一部分，则相当于区间加一，然后区间做前缀max。考虑线段树维护 $dp$ 的差分。则前缀max可以看成对于差分后一个小于 $0$ 的位置，在它后面找一些差分大于 $0$ 的位置（或者到结尾），然后将这部分同时抵消。因此可以从后往前，每次找到最后一个差分为负的位置，然后从这个位置向后抵消，使用set/map维护即可。因为每次至少抵消一个位置，而插入次数为 $O(n)$，因此均摊复杂度 $O(n\log n)$

对于第二种转移，可以看成整体取min。注意到做完上面操作后 $dp$ 单调，因此这里一定是改变一段前缀。直接做即可。

因此只需要将所有线段排序，满足一条线段在它前面线段的上方，即可 $O(n\log n)$ 维护 $dp$。

这样的顺序显然存在。考虑按照 $x$ 扫描线，维护当前线段的顺序，因为不存在相交所以顺序不会改变，可以用set维护。在加入一条线段时，先找到它加入的位置，然后考虑从它上面的那个线段向它连有向边，它向它下面的线段连有向边，这里一条有向边 $f\to t$ 表示 $t$ 在 $f$ 下方，因此在最后的顺序中 $f$ 应该在更后面。

可以发现只要每次加入时都满足顺序，则这样的顺序即为合法的。因此对上面得到的图拓扑排序即可得到合法的顺序。

复杂度 $O(n\log n)$

G. First of Her Name

Problem

有 $n$ 个字符串，其中第 $i$ 个字符串为在第 $f_i$ 个字符串的开头加入字符 $c_i$ 得到的。

$q$ 次询问，每次给出一个字符串 $s$，询问 $n$ 个字符串中有多少个字符串包含 $s$ 作为前缀。

$n,q\leq 10^6,f_i<i,|\sum|=26,\sum |s|\leq 10^6$，给定字符串两两不同。

$10s,1024MB$

Sol

可以直接做树上后缀排序

考虑翻转所有串，则变为在后缀加入字符，询问多少个串包含后缀。此时给定串构成Trie的关系。

相当于给一个Trie，多次询问有多少个串包含一个后缀。这显然是 广义SAM AC自动机的经典应用。

建出AC自动机(广义SAM)后，每次询问先直接定位询问串，然后相当于数有多少个串能通过fail连接到达这个串。预处理即可。

复杂度 $O(n|\sum|)$

I. Karel the Robot

Problem

$10s,1024MB$

Sol

如果只有一个程序，则它可以看成一个顺序执行，包含条件跳转的结构。在if 的开头和 until 的开头结尾分别有条件跳转。顺序执行这个程序即可。

因为机器人的运动只和位置有关，可以设 $dp_{x,y,s,l}$ 表示当前机器人在 $(x,y)$，面向 $s$，当前执行到了第 $l$ 个位置，程序结束时机器人的位置。考虑记忆化搜索转移，可以发现如果转移发现了环，则环上的所有点开始都无法结束。可以同时记录每个 $dp_{x,y,s,l}$ 是否会结束，然后直接记忆化搜索即可。

考虑多个程序的情况，设 $dp_{x,y,s,a,l}$ 表示当前执行到了程序 $a$ 的第 $l$ 个位置，其它定义与上面相同，程序 $a$ 结束时机器人的位置。则遇到一个形如 B 的调用函数的语句时，这个语句结束时的状态一定为 $dp_{x,y,s,b,1}$。因此可以同样使用记忆化搜索，转移出现环则环上的状态都无法结束，记录每个状态的访问状态（是否访问过/是否在栈中）即可。

复杂度 $O(rc(d+e)l)$

可能空间是256mb，可能需要稍微注意一下空间

J. Miniature Golf

Problem

有 $n$ 个人，每个人有 $m$ 个正整数 $v_{i,1},...,v_{i,m}$

任意选择一个正整数 $k$ ，此时第 $i$ 个人的得分为 $\sum_{j=1}^m\min(v_{i,j},k)$，第 $i$ 个人的排名为分数小于等于他的人的数量。

对于每个人，求出 $k$ 任意时他可能的最小排名。

$n\leq 500,m\leq 50$

$6s,1024MB$

Sol

显然一个人的得分对于 $k$ 为一个 $m+1$ 段的分段线性函数，因此对于两个人，可以在 $O(m)$ 的时间内，求出使得第一个人分数大于等于第二个人分数的 $k$ 区间。这样的区间一定只有 $O(m)$ 段。注意细节

考虑对于一个人 $A$ 求出他的最小排名。依次考虑其他人，分别求出使得 $A$ 的分数大于等于这个人分数的 $k$ 区间。此时将这些区间合并，相当于找到一个位置使得这个位置被所有区间覆盖的次数最少。直接对区间排序扫过去即可。

复杂度 $O(n^2m\log nm)$

K. Traffic Blights

Problem

在直线上有 $n$ 个交通信号灯。第 $i$ 个灯在原点向右 $d_i$ 米，它显示红绿的规则为先显示 $r_i$ 秒红灯，再显示 $g_i$ 秒绿灯，然后循环。

在时刻 $0$ ，所有交通信号灯正好变为红灯。一辆车在 $[0,2019!]$ 中的随机一个时刻开始从原点出发，速度恒定为 $1m/s$，遇到第一个红灯时停止。

对于每个交通信号灯求出车停在这里的概率，并求出车不停止直接通过的概率。

$n\leq 500,d_i\leq 10^5,1\leq r_i+g_i\leq 100$，$d_i$ 两两不同，所有数都是非负整数。

$2s,1024MB$

Sol

灯循环的周期为 $lcm(1,2,...,100)$，显然 $2019!$ 被这个值整除，且所有灯的变化都出现在整数时刻，因此可以变为枚举周期中每个长度为 $1$ 的时间段 $[i,i+1]$，计算这个时间段内出发停止的位置。 停止一个位置的总次数除以 $lcm$ 即为答案。

但直接枚举显然不行，根据CRT，枚举 $i\bmod lcm(1,2,...,100)$ 可以改为枚举 $i\bmod 2^6,i\bmod 3^4,...,i\bmod 93,i\bmod 97$。对于这里面的大质数（比如 $97$ ），可以发现 $i\bmod 97$ 的值只影响所有循环节长度为 $97$ 的灯，且这些灯只被这个值影响，因此这些灯与其他灯独立。因此可以求出只考虑循环节为 $97$ 的灯，停在每个灯的概率。然后可以合并。

对于其他的循环节，它们之间不一定独立。考虑将这种情况转换为上一种情况，令 $s=2^5*3^3*3*7=30240$，这个值满足 $\frac 1slcm(1,2,...,100)=2*3*5*7*11*...*97$。枚举 $i\bmod s$，设 $i=j*s+(i\bmod s)$，考虑对于一种 $i\bmod s$ 其所有的 $j$ 算答案。

此时可以枚举 $j\bmod 2,j\bmod 3,...,j\bmod 97$，可以发现对于任意 $x\in[1,100],x\in \Z$，$\frac x{lcm(s,x)}$ 一定是一个质数 $p$，因此考虑 $j$ 增加时，它的循环节一定是一个质数。

此时考虑 $j$ 的变化，每个灯的循环节都是一个质数，每种循环节间独立。对于同一个循环节 $p$，可以求出考虑所有循环节为 $p$ 的灯，车停在每个路灯的概率。这可以通过预处理每个灯每个 $i\bmod(r_i+g_i)$ 时，一个循环节 $p$ 内的通行情况，然后bitset优化 $O(\frac{np}{w})$ 对应所有灯，求出只考虑自己这一类的灯时的答案。

最后车停在某个位置当且仅当这一类中车停在这里，且其它类中车停在后面，可以从后向前扫过去求出。

复杂度 $O(30240*\frac{np}w)$

可以发现，循环节为 $p,p^2,p^3,...$ 的所有路灯也是可以放在一起考虑的，设最大的循环节为 $p^k$，枚举 $i\bmod p^k$ 后显然前面的循环节也都可以计算。

因此可以选择更小的 $s$，只需要满足对于任意 $x\in[1,100],x\in \Z$，$\frac x{lcm(s,x)}$ 一定形如 $p^k$ 即可。此时可以发现取 $s=2^3*3^2*5*7$ 就能满足要求。复杂度降至 $O(2520*\frac{np}w)$