WF 2014

Baggage

设 $(BA)$ 表示 $BABA\cdots BA$，$(AB)$ 表示 $AAA\cdots ABBB\cdots B$。

首先爆搜一下 $n=3,4,5,6,7$，可以发现最短的构造长度为 $n$，同时从 $\_\_(BA)$ 变成了 $(AB)\_\_$。

考虑 $n\geq 8$ 的情况。我们可以做如下操作：
$$
\begin{matrix}
\_\_BABA(BA)BABA\\
ABBABA(BA)B\_\_A\\
ABBA\_\_(BA)BBAA
\end{matrix}
$$
中间那个 $\_\_(BA)$ 可以直接递归处理，处理完后再做如下操作：
$$
\begin{matrix}
ABBA(AB)\_\_BBAA\\
A\_\_A(AB)BBBBAA\\
AAAA(AB)BBBB\_\_
\end{matrix}
$$
这样子整个序列就变成了 $(AB)$，长度为 $n$。可以证明这是最短的。

Maze Reduction

这种题看着就是要对每个点求一个哈希值，所以关键在于如何设计哈希函数。

设 $h_{i,j,k}$ 表示从 $j$ 的第 $k$ 扇门进去走 $i$ 步的哈希值。假设从 $j$ 的第 $k$ 扇门走进去是 $v$，那么可以从 $j$ 开始绕着 $v$ 走一圈，把所有的 $h_{i-1,v,x}$ 哈希起来表示 $h_{i,j,k}$。特别的，当 $i=0$ 时可以用 $j$ 的度数表示。

然后对每个房间 $i$ 求 $h_{n,i,j}$ 的最小表示，即可当做其哈希值。因为数据范围很小所以可以暴力求，时间复杂度 $\mathcal{O}(n^4)$。

Metal Processing Plant

不妨设 $D(A) \leq D(B)$。

从小到大枚举 $D(A)$，双指针从大到小枚举 $D(B)$，那么只需要考虑如何判断是否合法。

因为每个点要么在 $A$ 中要么 $B$ 中，因此考虑 2-SAT。对于边权在 $(D(A), D(B)]$ 中的边，其两端点需要满足不同时在 $A$ 中；对于边权 $>D(B)$ 的边，其两端点需要满足不同时在一个集合中。

使用压位 Kosaraju 算法找出强连通分量判断即可，时间复杂度 $\mathcal{O}(\frac{n^4}{\omega})$。

Pachinko

设 $f_{i, j}$ 为能够到达 $(i, j)$ 的概率，可以列出一个 $n\times m$ 元方程组。然而直接解时空都无法承受。

不妨把所有格子按照从上到下、从左往右的顺序编号，这样子矩阵是一个长度为 $m$ 的带状矩阵。

因从我们只需要对每行保存 $2m$ 个值，消元时也只需要往下消 $m$ 行再回代就可以了。

Sensor Network

直接随机贪心求最大团是可以过的。具体就是用 bitset 维护已经加入的点，然后随机一个加点排列，能加就加即可。

正解是枚举两个点 $A,B$，则其它点必定在分别以 $A,B$ 为圆心、半径为 $D$ 的两个圆的交内，我们要求最大团。转化成补图的最大独立集，可以发现补图中所有边的端点都在 $AB$ 的两侧，因此补图为二分图，从而很好求最大独立集。

Surveillance

把所有区间按左端点排序，则选了每个区间后下一个必选的区间可以直接双指针预处理出来。

然后预处理倍增数组，枚举起点，然后直接倍增跳一圈即可。

WF 2015

Evolution in Parallel

设 $A\subseteq B$ 表示 $A$ 是 $B$ 的子序列。

首先至少要有 $s_i\subseteq U$，判掉后 $U$ 就没用了。

考虑一条链上的串长度显然是不降的，于是我们把所有串按长度从小到大排序后依次加入，并维护两条链。我们称一个串 $S$ 能接在一条链的末端当且仅当链尾串 $T$ 满足 $T\subseteq S$。

• 如果当前串不能接在任意一条链的末端，则无解；
• 如果当前串只能接在一条链的末端，就接上去；
• 如果当前串可以接在两条链的末端，发现不好处理。我们再维护一条待选链，那么
  • 如果当前串可以接在待选链末端，那么就接上去；
  • 否则一定是这个串和待选链分别接在两条链的末端，随便选择一种接法即可。

这样子总共只需要询问 $\mathcal{O}(n)$ 次 $A\subseteq B$ 是否成立，复杂度 $\mathcal{O}(n^2)$。

Qanat

可以证明，竖井一定会垂直往上运，底部一定会走左右两个竖井中近的那个往上运。

考虑确定最右边的竖井的位置，这样子加上最右边竖井右边部分的代价后即可转化为一个子问题，而这个子问题对应的三角形与原三角形是相似的，所以我们可以只求出原三角形中放 $n-1$ 个竖井的代价，乘上比例系数的平方就可以还原回去。

设最右边竖井到母井的距离为 $L$，我们要计算右边一个 L 状物的代价，即一个 U 状物的代价减去最右边竖井的代价。设 U 状物总长为 $a$，其代价为 $\frac{a^2}{4}$。设原三角形中放 $i$ 个竖井的代价为 $C_i$，于是有
$$
C_n=C_{n-1}\left(1-\frac{L}{w}\right)^2+\frac{\left(h+L+(1-\frac{L}{w})h\right)^2}{4}-\frac{\left[\left(1-\frac{L}{w}\right)h\right]^2}{2}
$$
大力化简得到
$$
C_n=\frac{1-\frac{h^2}{w^2}-\frac{2h}{w}+\frac{4C_{n-1}}{w^2}}{4}L^2+\left(h-\frac{2C_{n-1}}{w}\right)L+\left(C_{n-1}+\frac{h^2}{2}\right)
$$
是二次函数的形式，令 $L=-\frac{2a}{b}$ 即可求出最值。最后再倒推一遍把每条线段放到相似的三角形里去即可。

Weather Report

显然就是要我们求 $4^n$ 个串的 Huffman 编码，直接求复杂度是 $\mathcal{O}(n4^n)$ 的，无法承受。

但是注意到不同的概率只有 ${n+3\choose 3}$ 种，于是我们可以把概率相同的放在一起，每次批量合并即可。

Tile Cutting

设长、宽分别为 $w,h$，长、宽上切点到一个端点的长度为 $a,b$，则面积为 $wh-a(h-b)-b(w-a)$。

令 $c=w-a,d=h-b$，则面积为 $(a+c)(b+d)-ad-bc=ab+cd$。

设面积为 $x$ 的方案数的 OGF 为 $F$，约数个数的 OGF 为 $G$，那么有 $F=G^2$。

线性筛 $d$，NTT 后预处理 ST 表回答询问即可。

WF 2016

Balanced Diet

设 $s=\sum a_i$。当 $s|n$ 时，只有一种取值，否则有两种取值。

如果一个长度为 $s$ 的前缀合法，那么只需要不断重复它就可以构造出无穷长的合法序列，因此我们只需要判断能否到 $s$ 即可。

先只考虑下界限制，也就是要有 $c_i>nf_i-1$，即 $n<\lceil\frac{c_i+1}{f_i}\rceil$。也就是说，对于每个 $i$，我们都需要把它在这个时间之前加上 $1$。我们把这个时间叫做截止时间。

于是可以贪心，每次找一个截止时间最小的出来加 $1$ 即可。可以证明这样并不会超过上界限制。

Branch Assignment

先跑两遍最短路求出 $dis(i,b+1)$ 和 $dis(b+1,i)$。

设 $w_i=dis(i,b+1)+dis(b+1,i)$，可以求出一个集合的权值为 $W(S)=(|S|-1)\sum_{i\in S} w_i$。为了方便我们将 $|S|-1$ 看成 $|S|$，最后再减去 $\sum w_i$ 即可。

将 $w_{1..b}$ 从小到大排序，那么放在一个集合内的一定是连续的一段，从而可以考虑 DP。

设 $dp_{i,j}$ 表示前 $j$ 个数分成了 $i$ 段的最小权值和，转移为
$$
dp_{i,j}=\min_{0\leq k\leq j}\{dp_{i-1,k}+(j-k)(s_j-s_k)\}
$$
这里的 $s$ 是 $w$ 的前缀和。

可以发现这个 DP 对于两维都具有决策单调性。具体的，设 $p_{i,j}$ 表示 $dp_{i,j}$ 是从哪个 $k$ 转移而来的，那么有 $p_{i-1,j}\leq p_{i,j}\leq p_{i,j+1}$。我们从小到大枚举 $i$、从大到小枚举 $j$，在 $[p_{i-1,j},p_{i,j+1}]$ 内枚举转移点，即可做到 $\mathcal{O}(n^2)$。

Clock Breaking

如果一个灯管一直都是 X 或者一直都是 .，那它就有可能恒亮或恒灭。

枚举起始时间，那么如果一个不可能恒亮或恒灭的灯管没有正常发光，那么这个起始时间就不合法。

如果对于某个起始时间，某个灯管都正常发光，那它就有可能是正常工作的。

如果一个灯管的可能性超过 $2$ 种，那么就输出 ?，否则输出对应的东西即可。

Longest Rivers

不妨先考虑只有一个询问 $u$ 时怎么做。显然 $u$ 到根应该都划给 $u$，设这一段长度为 $L$，那么我们希望 $>L$ 的河流数量尽量少。

这个可以直接在树上贪心。如果子树中有一个 $>L$ 的，那么就接它，否则接一个最短的。

后面那一部分和 $L$ 是没有关系的，所以我们考虑让每个节点都接上儿子中最短的，得到一组方案。设 $d_u$ 为这组方案中 $u$ 往下延伸的长度，则有
$$
d_u=\min\left\{d_v\right\}+w_{fa_u,u}
$$
如果只统计 $d_u>L$ 的 $u$ 的数量，显然是会算多的。规定一个节点算了后它的祖先就都不能算了，这样子相当于满足了“如果自述中有一个 $>L$ 的就接它”，算出来的就是对的了。

进一步，如果我们把所有 $d_u\leq L$ 的节点删掉，答案就是叶节点个数 $+1$。

现在已经很好扩展到多组询问了。我们把所有叶节点按到根的距离从小到大排序，这样子 $L$ 是不降的，用堆维护所有叶节点即可。

String Theory

首先如果 $\sum a_i$ 是奇数则一定无解。

显然一个 $k$ 阶串左边一定是 $k-1$ 个引号、$k-2$ 个引号、……、$1$ 个引号，右边一定是 $1$ 个引号、$2$ 个引号、……、$k-1$ 个引号。

那么中间还剩下偶数个引号，我们可以直接把它们整成 $1$ 阶串。

于是可以直接枚举答案，然后从左往右、从右往左各扫一遍判断是否满足条件即可。

What Really Happened on Mars?

直接按照题意模拟即可，主要的问题在 Step 2，也就是如何算当前优先级。

这个东西实际上和最长路很类似，可以直接跑一遍 SPFA 求出。

WF 2017

Airport Construction

显然答案所在直线一定经过多边形的两个顶点。于是可以枚举这两个顶点，然后算长度。

算长度的话，先把所有被直线切开的边拿出来按照交点位置排序，然后扫一遍把所有合法段求个 $\max$ 即可。

Get a Clue!

可以直接爆搜，但是有更加高妙的做法。

我们先预处理出每种手牌集合是否可能是每个玩家持有的手牌。这个可以简单地通过输入数据判断。

注意到每种集合对每个人是独立的，因此可以直接做子集卷积，求出每种集合是否有可能是玩家的手牌。注意到后面我们只需要算缺三张牌的集合，只有三个人的集合两两无交时它们的并才可能恰好缺三张牌，因此可以直接做集合并卷积。

然后对所有可能缺三张牌的集合，判断它缺的三张牌是否每种类型都有一张，如果是说明这三张牌有可能是答案。

最后对每种类型扫一遍，如果答案唯一直接输出，否则输出 ?。

Money for Nothing

可以发现我们要求的就是
$$
\max_{d_i<e_j}\left\{(e_j-d_i)(q_j-p_i)\right\}
$$
可以猜测它有决策单调性，但是我们来尝试证一下。我们把所有东西按时间排好序，设 $i<j\leq k<l$，则应有
$$
(e_k-d_i)(q_k-p_i)+(e_l-d_j)(q_l-p_j)\geq(e_l-d_i)(q_l-p_i)+(e_k-d_j)(q_k-p_j)
$$
大力拆开化简得到
$$
d_iq_k+e_kp_i+d_jq_l+e_lp_j\leq d_iq_l+e_lp_i+d_jq_k+e_kp_j
$$
然而这个东西并不恒成立……

从头再分析一下。如果 $d_i<d_j,p_i<p_j$，那么我们一定不会买 $j$ 的零件。同理，如果 $e_i<e_j,q_i<q_j$，则我们一定不会卖零件给 $i$。我们可以直接把这些不满足条件的去掉。

那么现在有 $p_i>p_j,q_i>q_j$，根据排序不等式有
$$
\begin{cases}
d_iq_k+d_jq_l\leq d_iq_l+d_jq_k\\
e_kp_i+e_lp_j\leq e_lp_i+e_kp_j
\end{cases}
$$
这样子上面那个东西就成立了，也就是有决策单调性了，直接分治即可。分治时有一些小细节需要注意。

Replicate Replicate Rfplicbte

注意到每次复制一定会向四周扩展一圈，也就是至多扩展了 $\max\left\{\frac{n}{2},\frac{m}{2}\right\}$ 次。

如果没有发生错误，我们可以直接递推出上一次的状态：
$$
b_{i,j}=a_{i-1,j-1}\oplus b_{i,j-1}\oplus b_{i,j-2}\oplus b_{i-1,j}\oplus b_{i-1,j-1}\oplus b_{i-1,j-2}\oplus b_{i-2,j}\oplus b_{i-2,j-1}\oplus b_{i-2,j-2}
$$
问题是有错误。注意到一个错误 $(x,y)$ 会对 $(x+1,y+1),(x+1,y+2)$、$(x+1,y+4),(x+1,y+5)$、……造成影响，那么如果 $b_{i+1,m+1}+b_{i+1,m+2}>0$ 说明第 $i$ 行一定有错误，我们再按列推一遍就可以找到错误位置，然后改掉后再递推就好了。

如果错误数 $\geq 1$ 或者 $n=1$ 或者 $m=1$ 就是答案了。

Tarot Sham Boast

结论：把每个串满足 $2l-i\leq n$（$l$ 是串长，$i$ 是 border 长度）的 border 求出来从大到小排序，字典序小的出现概率大。

官方证明

简化后的感性理解：

• 长度为 $l$ 的串 $s$ 出现概率为（假设随机串是 $R$）
  $$
  \sum_{S\subseteq\{1,2,\cdots,n-l+1\}}(-1)^{|S|+1}\prod_{i\in S}P(R_{i..i+l-1}=s)
  $$

• 不妨设
  $$
  F(x)=\sum_{S\subseteq\{1,2,\cdots,n-l+1\},|S|=x}(-1)^{x+1}\prod_{i\in S}P(R_{i..i+l-1}=s)
  $$

• 可以发现 $F(1)$ 恒等于 $3^{-l}$，且 $F(i+1)\ll F(i)$，所以我们可以只比较 $F(2)$ 的值。

• 假设 $S=\{x,y\}$，那么
  $$
  F(2)=\begin{cases}-3^{-2l},&i+l-1\leq j\\-3^{-2l+(i+l-j)},&\mathrm{otherwise}\end{cases}
  $$

• 后面那种情况会出现当且仅当 $s$ 有一个长度为 $i+l-j$ 的 border，而且 border 越长贡献越大。又因为前面的系数是 $-1$，所以要按字典序从小到大排序。

• 需要注意的是 $2l-i>n$ 的 border 是没有贡献的，所以并不能把它们算进去。

Visual Python++

假设有解，先考虑如何找到这组解。

从左往右扫描线，并用一个 set 维护纵坐标，那么对于一个右上角，拿 set 中纵坐标最大的左下角和它匹配即可。

问题是可能无解，所以上面求出的解不一定是合法的。我们再从左往右扫描线，那么每次加入或删除一个矩形时上下边中间不能有任何其它边界，同样可以用 set 维护。

因为边界重叠也不合法，所以还有许多细节要考虑。

WF 2018

Conquer the World

考虑反着看整个过程，那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞，所有老鼠都必须进洞。

$u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$，每次把儿子的堆合并，然后取堆顶匹配，再把反悔操作加入堆中即可。

然而这样并不能保证所有老鼠都进洞，所以我们把老鼠的 $dep$ 减去 $+\infty$，最后再把答案加上 $+\infty\times\sum y_i$ 即可。

这样子当匹配的老鼠和洞来自同一棵子树答案可能会不对，但是这样子一定不会是最优解，所以不会有问题。

因为一对匹配的老鼠和洞不会同时反悔，所以只会操作 $X=\sum x_i$ 次，所以时间复杂度 $\mathcal{O}(X\log X)$。可以记一个 pair 表示代价和出现次数从而做到 $\mathcal{O}(n\log n)$。

Gem Island

可以证明，每种最终局面出现的概率是相等的。

于是可以考虑 DP。设 $f_{i,j}$ 表示 $j$ 枚宝石分给 $i$ 个人的方案数，$g_{i,j}$ 表示 $j$ 枚宝石分给 $i$ 个人的所有方案中前 $r$ 多的和。枚举 $k$ 个人，给他们每人一棵宝石，其他人都不再拿宝石，可以得到转移
$$
\begin{aligned}
f_{i,j}&=\sum_{k=0}^{\min\left\{i,j\right\}}{i\choose k}f_{k,j-k}\\
g_{i,j}&=\sum_{k=0}^{\min\left\{i,j\right\}}{i\choose k}(g_{k,j-k}+\min\left\{k,r\right\}f_{k,j-k})
\end{aligned}
$$
答案即为 $\frac{g_{n,d}}{f_{n,d}}+r$。

Getting a Jump on Crime

如果我们能够求出从 $u$ 能否到达 $v$，那么就变成一个简单的最短路了，直接 BFS 即可。

考虑这个东西怎么求。设距离为 $d$，高度差为 $h$，根据物理必修一相关知识，可以列出方程
$$
\begin{cases}
v_x\!^2+v_y\!^2=v^2\\
d=v_xt\\
v_yt-\frac{1}{2}gt^2=h
\end{cases}
$$
化简得到
$$
\frac{1}{4}g^2t^4+(gh-v^2)t^2+h^2+d^2=0
$$
我们肯定想让 $v_y$ 尽量大（这样就更不容易撞到楼上），所以我们只需要求出 $t$ 的最大值，从而求出 $v_x,v_y$。

然后我们枚举每个边界，如果和路线有交的话就算出跳到这个位置时的高度，然后比较一下即可知道是否会撞上。

Single Cut of Failure

切两条对角线一定能够切断所有电线，所以我们只需要判断答案是否为 $1$ 即可。

把所有端点排序，那么需要判断是否有一个连续的长度为 $n$ 的区间包含恰好 $n$ 条电线，直接开个桶扫一下即可。

由于题目要求，需要把坐标微平移一下。

WF 2019

Beautiful Bridges

容易想到一个 DP，即设 $dp_i$ 表示前 $i$ 个点的最小代价，转移枚举从哪个点修过来。

然而判断转移点是否合法是 $\mathcal{O}(n)$ 的，显然会 T。

考虑对于每个转移点 $j$ 计算不撞上 $j$ 时的半径范围。可以列出式子
$$
r^2\geq (x_j-x_i+r)^2+(y_j-h+r)^2
$$
于是可以解出合法的 $r$ 的范围。然而有可能一定撞不上 $j$，即 $x_i-x_j\leq 2(y_j-h)$，此时解出来的 $r$ 的范围要特判一下。

对于每个 $j$，只需要看 $x_j$ 是否同时满足 $[j,i]$ 的半径限制即可判断它是否合法。

Directing Rainfall

从上往下扫描线，并维护每个横坐标要有雨最少需要打多少个孔。

那么对于一个雨棚，如果其斜率为正则相当于做一个后缀 $\min$ 再把非左端点加上 $1$，斜率为负则相当于做一个前缀 $\min$ 再把非右端点加上 $1$。

考虑维护其差分数组，并用两个 set 维护差分值为正、为负的位置。前缀 $\min$ 就相当于把正的位置改成 $0$，后缀 $\min$ 就相当于把负的位置改成 $0$，在 set 中找到对应的位置改掉即可。可以发现每次操作会付出 $\mathcal{O}(c)$ 的代价减少差分数组中的 $c$ 个非 $0$ 值，而非 $0$ 值的增加次数是 $\mathcal{O}(n)$ 的，所以这部分复杂度为 $\mathcal{O}(n \log n)$。

我们还需要确定雨棚的加入顺序。我们需要保证一个雨棚加入前其上方所有雨棚都已加入，所以直接按 $y$ 排序是错误的。可以从左往右扫描线来得出雨棚之间的先后关系，然后拓扑排序即可求出一个合法的顺序。

注意到我们不仅需要维护所有整数坐标的答案，还需要维护 $k+0.5$ 这样的坐标的答案，因为有从中间下去更优的情况。

First of Her Name

为了方便，将所有串都反过来，问题变为询问有多少个串以某个串为后缀。

将询问的所有串建 AC 自动机，把名字拿到自动机上匹配并把最终位置 $+1$，在 fail 树上统计子树和即可。

Miniature Golf

显然一个人的分数关于阈值的函数是一个斜率单减的分段函数。

假设我们在求 $x$ 的最好排名。我们枚举一个其它的人 $y$，然后找到它们的交点，则 $x$ 的排名会在交点处改变（$+1$ 或 $-1$）。我们把所有交点拿出来排一遍序，然后扫一遍就可以求出最好排名了。

这个交点比较好求。我们把两个人的所有拐点拿出来归并排序，然后从右往左扫，当 $y$ 的大小关系发生变化时直接算一下即可。

因为题目要求是整数，所以有一些奇奇怪怪的取整的问题。

Traffic Blights

不晓得这东西怎么讲，所以直接蒯 smy 的了

因为 $r_i+g_i\leq 100$，所以经过 $T=\operatorname{lcm}(1,2,\cdots,100)$ 秒红绿灯一定会回到一开始的状态，而 $T|2019!$，所以我们可以看成在 $[0,T)$ 内的随机时刻开始。

考虑求出到达第 $i$ 个红绿灯的概率 $f_i$，这样子差分一下就可以得到答案了。

朴素地想法是列出若干个 $k+x_i\geq r_i\pmod{r_i+g_i}$ 的同余方程，然后求出解集大小，再除掉 $\operatorname{lcm}(r_i+g_i)$。

考虑一些特殊的同余方程组：

• $\begin{cases}x\in S_1\pmod{p}\\x\in S_2\pmod{q}\end{cases}$，且 $\gcd(p,q)=1$，则解集大小为 $|S_1|\times|S_2|$。
• $\begin{cases}x\in S_1\pmod{p}\\x\in S_2\pmod{q}\end{cases}$，且 $p|q$，则可以 $\mathcal{O}(q)$ 求出解集。

如果所有 $p_i$ 都只有一个质因数，那么就可以直接对每个质因数维护一个 $\bmod p^{\lfloor\log_p 100\rfloor}$ 的同余方程，最后合并起来。

我们再设一个 $X$，然后枚举 $a\in[0,X)$，并算所有开始时刻是 $kX+a(k\in N)$ 的贡献。可以发现，$X,a$ 已知时 $kX+a+x_i\geq r_i\pmod{r_i+g_i}$ 可以改写为一个形式为 $k\in S\pmod{\frac{r_i+g_i}{\gcd(r_i+g_i,X)}}$ 的同余方程。

令 $X$ 等于 $\sqrt{100}$ 内所有数的 $\operatorname{lcm}$（即 $2520$），则 $\forall i\in[1,100]$，$\frac{i}{\gcd(i,X)}$ 都只有一个质因数，这样子就可以套用上面的做法了。

NEERC 2017

The Great Wall

把 $b_i,c_i$ 都减去 $a_i$，那么只需要考虑被一个区间覆盖或两个区间覆盖的情况，最后加上 $\sum a_i$ 即可。

考虑二分答案，则我们需要计算 $\leq mid$ 的方案数。

先考虑两个区间无交的情况。设 $b_i$ 的前缀和为 $sb_i$，$c_i$ 的前缀和为 $sc_i$，则和为
$$
sb_{i+r}-sb_i+sb_{j+r}-sb_j
$$
设 $f_i=sb_{i+r}-sb_i$，相当于 $f_i+f_j\leq mid,i+r\leq j$，是一个二维数点问题。

再考虑两个区间有交的情况，和为
$$
sb_j-sb_i+sc_{i+r}-sc_j+sb_{j+r}-sb_{i+r}
$$
设 $g_i=sc_{i+r}-sb_i-sb_{i+r}$，$h_i=sb_i-sc_i+sb_{i+r}$，相当于 $g_i+h_j\leq mid,i+r>j$，同样是一个二维数点问题。

Journey from Petersburg to Moscow

考虑枚举经过第 $k$ 大的边，然后把所有边边权减去这条边的边权后对 $0$ 取 $\max$，那么对应的最短路就是 $dis_n+kw$。

可能没有经过 $k$ 条边，所以还要对原图的最短路取个 $\min$。

通过一些感性理解可以知道这样子包含了所有情况。

Knapsack Cryptosystem

一个做法是直接 meet in the middle，复杂度 $\mathcal{O}(2^{n/2})$，并不能过 $n\leq 64$。

但是题目中还有一个奇妙的性质 $a_i>\sum_{j=1}^{i-1} a_j$，套用得到 $a_1<2^{65-n}$。

发现随着 $n$ 增大 $a_i$ 的取值范围逐渐减小，这启发我们在 $n$ 大时去枚举 $a_1$。

枚举 $a_1$ 后考虑解出 $r^{-1}$，这样子就可以直接求出 $a_{1..n}$，然后倒着贪心一下就可以求出 $s_{1..n}$ 了。

可以列出同余方程
$$
a_1\equiv b_1r^{-1}\pmod{q}
$$
设 $z=v_2(b_1)$，$b'=\frac{b_1}{2^z}$，那么
$$
a_1\equiv2^zb'r^{-1}\pmod{q}
$$
因为 $r$ 是奇数，所以 $v_2(a_1)=z$，设 $a'=\frac{a_1}{2^z}$，那么
$$
a'\equiv b'r^{-1}\pmod{2^{64-z}}
$$
这样子可以解出 $r'=r^{-1}\bmod 2^{64-z}$，$r^{-1}$ 实际取值可能为 $r'+k2^{64-z}(0\leq k<2^z)$。于是我们再枚举 $k$，然后检查得到的 $a_{1..n}$ 是否合法即可。

这样子 $a_1$ 的总枚举量是 $2^{64-n-z}$，$k$ 的总枚举量是 $2^z$，所以总的枚举量是 $2^{64-n}$ 的。

于是我们把两个做法缝合一下，当 $n\leq B$ 时用做法一，否则用做法二，即可做到 $\mathcal{O}(q^{\frac{1}{3}})$。

Laminar Family

考虑把所有路径按照长度从大到小排序，则只有可能是前面的包含后面的。

我们依次加入所有路径，如果当前加入的路径上和两条或者更多条之前的路径有交，那么显然就 GG 了。

我们可以把加入一条路径看成染一种颜色，那么我们只需要支持

• 链修改颜色；
• 询问一条链上所有点颜色是否相同。

可以给每种颜色一个编号，然后维护最小值和最大值来解决询问，这样子直接树剖+线段树维护就好了。

NEERC 2016

Binary Code

每个 ? 可以填 $0$ 或 $1$，而且有一些限制，自然想到 2-SAT。然而朴素连边是 $\mathcal{O}(n^2)$ 的，需要优化。

把所有可能的串插入到一棵 Trie 中，那么相当于选出的点互相不能为祖先。

考虑利用 Trie 树优化连边。对于一条 $u\to \neg v$ 的限制，从 $u$ 向对应的节点连边，然后一路往上连到某个节点，再向 $\neg v$ 连边。因为是 2-SAT 所以还有反边，连边方式同理。

但是这并不能处理相同的串。我们想要相同的串只能选一个，朴素连边同样是 $\mathcal{O}(n^2)$ 的，前缀优化连边即可。这样子在 Trie 树上连边时需要拿自己最前面的点去连父节点最后的点。

Cactus Construction

不妨先考虑树的构造。不难得到一种需要 $3$ 种颜色的方案：先把 $u$ 的子树全部建成根是 $1$、其他节点是 $2$，再把 $u$ 改成 $3$，然后把 $u$ 与子节点合并后连 $(1,3)$，再把 $3$ 改成 $1$ 即可。这个构造是递归的。

扩展到仙人掌上时只需要考虑环的处理。我们先把环上的点连出去的子树都接好，然后把环上某个点染成 $4$，然后按照上面的方法连出一条链，最后连 $(1,4)$ 并把 $1$ 改成 $2$、$4$ 改成 $1$ 即可。

操作次数大概是 $4m$，完全能过。

Delight for a Cat

考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划
$$
\begin{matrix}
\mathrm{maximize } \sum_{i=1}^n x_i(e_i-s_i)+\sum_{i=1}^n s_i\\
\mathrm{s.t. }\begin{cases}x_1+x_2+\cdots+x_k\geq m_e\\x_1+x_2+\cdots+x_k\leq k-m_s\\\cdots\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n\geq m_e\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n\leq k-m_s\\0\leq x_1,x_2,\cdots,x_n\leq 1\end{cases}
\end{matrix}
$$
发现是全幺模矩阵，所以一定有整数解，可以考虑费用流。

按照惯例添加辅助变量
$$
\begin{cases}x_1+x_2+\cdots+x_k-y_1=m_e\\x_1+x_2+\cdots+x_k+z_1=k-m_s\\\cdots\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n-y_{n-k+1}=m_e\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n+z_{n-k+1}=k-m_s\end{cases}
$$
然后差分一下
$$
\begin{cases}x_1+x_2+\cdots+x_k-y_1=m_e\\z_1+y_1=k-m_s-m_e\\\cdots\\z_{n-k+1}+y_{n-k+1}=k-m_s-m_e\\-x_{n-k+1}-x_{n-k+2}-\cdots-x_n-z_{n-k+1}=m_s-k\end{cases}
$$
用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。

Mole Tunnels

可以想到一个费用流做法：

• 对于每只鼹鼠，从原点向 $p_i$ 连容量为 $1$、费用为 $0$ 的边；
• 对于相连的两个点，连容量为 $+\infty$、费用为 $1$ 的边；
• 对于每个点，向汇点连容量为 $c_i$、费用为 $0$ 的边。

注意到树高是 $\log$ 级别的，所以我们可以暴力枚举当前点与流向的点的 LCA。具体的，我们预处理每个点子树中到它费用最小的点，然后每次暴跳祖先找到流向的点，再连上反边并更新即可。

NEERC 2015

Binary vs Decimal

可以发现如果 $x$ 是合法的，那么 $x$ 的后缀也是合法的。

于是可以从 $0$ 和 $1$ 开始 BFS，每次加上 $10^k$ 判断是否合法即可。

注意到 $10^k$ 在二进制下末尾一定有 $k$ 个 $0$，所以我们只需要判断 $x$ 在十进制下的最高位一直到 $k$ 是否都为 $0$ 即可。

实现时只需要记录二进制和十进制最高位即可。

Cactus Jubilee

移动一条边等价于先删掉一条边再加入一条位置不同的边。不妨去掉位置不同的限制，最后将答案减去边数即可。

那么我们相当于要对每个断掉一条边后求出有多少种加边的方案，满足加边后是仙人掌。

分两种情况讨论：

• 如果断掉的边是桥，那么剩下的两部分之间任意连都可以，方案数为两部分点数之积。
• 如果断掉的边不是桥，根据 ZJOI2017 仙人掌 的结论，需要保证连边的两点路径上的边全为桥边。因此可以只保留桥边得到一个图，答案为 $\sum {sz_i-1\choose 2}$。

桥的情况可以一遍 DFS 求出，而非桥的情况似乎不好快速计算。注意到同一个环上的边断掉后保留桥边得到的连通分量相同，因此可以每次对一个环计算。这个环断掉一条边后相当于若干个连通块合并成了一个，只要找到环上的所有点，减去原来的贡献，再加上合并后的贡献即可。

Distance on Triangulation

对于这种图上多次询问最短路的题，显然考虑分治。

我们找到一条边，这样子就可以把图拆分成两部分，按照 ZJOI2016 旅行者 一题的方法更新询问的答案即可。因为边权全为 $1$ 所以只需要 BFS。

考虑复杂度。整个过程相当于在对偶图上做边分治，而三角剖分图的对偶图的最大度数为 $3$，所以每次分治大的一部分至多有 $\frac{2}{3}m$ 条边，因此复杂度是正确的。

Jump

我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。

规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。

假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。

考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus\{u,v\}|=\frac{n}{2}+2(1-|A\cap\{u,v\}|)$。那么每次可以确定一个二元组与 $A$ 的交是否 $=1$。

不妨令 $u=1$，那么可以得到其它的数是否可以同时和 $1$ 在 $A$ 内，这样子有两种可能的情况，都问一遍即可。

这里最坏会询问 $n+1$ 次，于是我们需要思考如何在 $499$ 次内找到一个 $I$。

考虑随机，那么一次问到一个 $\frac{n}{2}$ 的概率是 $\frac{{n\choose n/2}}{2^n}$，在 $n=1000$ 时约等于 $2.52\%$。于是随机 $499$ 次有很大的概率出解。

King’s Inspection

注意到出度为 $1$ 的点接下来该往哪走是确定的，我们只需要爆搜出度不为 $1$ 的点往哪走即可。

注意不要漏判无解的情况。

Landscape Improved

我们钦定一个横坐标最后是最高的，然后二分它的高度。

check 时只需要找出左右第一个不需要补的位置，然后算出区间内要填的数量，判断它是否 $\leq n$ 就好了。

然而直接暴力找显然不太行。考虑二分，把式子写出来移项后发现要求 $h_i-i$ 和 $h_i+i$ 的 $\max$，ST 表即可。

NEERC 2014

Epic Win!

如果初始状态确定，那么很容易造出一个 $n$ 个点、每个点只有一个转移的自动机来 $100\%$ 打败对手：每个节点的输出正好能战胜对方这个节点的输出，然后根据对方这个节点的输出转移到对应的节点即可。

如果直接拿这个自动机去打，那么可能某时刻没有转移边，这说明我们没有赢。于是我们只要根据对手的输出，转移到对手的节点对应的自己的节点去即可。

这样子会有一些问题，原因在于我们新加的转移边是会成环的，导致会重复到达某个没赢的状态。所以我们每次没赢时新复制一个自动机，然后转移到新自动机去即可。这样子新加的转移是一个外向树的结构，就不会有问题。

根据上面的分析可以知道，这样子至少可以赢 $10^9-n$ 次，可以通过本题。

Gomoku

人类智慧题。

simulator

Hidden Maze

从小到大枚举所有边，将已经枚举到的（包括当前的）边的边权设为 $1$、仍未枚举到的边的边权设为 $-1$，则此时所有经过这条边的边权和为 $1$ 的路径的中位数就是这条边。

设 $s_{i, j}$ 表示以 $i$ 为根的子树中有多少个点到 $i$ 的边权和为 $j$。于是统计时只需要枚举 $u$ 的祖先作为路径两个端点的 LCA，然后很容易算出方案数（注意路径的两个端点不能在同一棵子树中，需要类似点分治的减掉），修改时直接暴力修改祖先即可。

因为树随机生成，所以期望树高是 $\mathcal{O}(\sqrt{n})$ 级别的，因此时间复杂度为期望 $\mathcal{O}(n \sqrt{n})$。

Improvements

经过一些手玩或者打表可以发现，合法当且仅当 $\forall i\in[1,n]$，$p_i$ 是一个后缀最小值或者后缀最大值。

必要性证明可以考虑找到 $p_i=n$ 的位置，则前面必然是 $p_1=1,p_2=2,\cdots,p_{i-1}=i-1,p_i=n$，后面是一个子问题，可以递归证明；充分性证明略。

这个结论等价于 $p^{-1}$ 是一个单峰的排列，因为 $p_n$ 前面比它小的数单增、比它大的数单减。

修改一个数和直接删掉没有区别。于是只要正反求两遍 LIS，然后枚举最高点即可。

NEERC 2013

Hack Protection

枚举右端点，那么往左的过程中 and 和只会变化 $\log$ 次。

求出前缀异或和，那么我们只需要对 $\log$ 个区间统计其中某个值的出现次数，可持久化 01 Trie 即可（好像可以直接二分）。

这 $\log$ 个区间可以记一下上一个某一位是 $0$ 的数来找出。

Interactive Interception

设速度为 $k$、起始点为 $b$，那么 $t$ 时刻的坐标 $f(t)=kt+b$。

考虑二分，把 $(k,b)$ 看成一组值，每次尽量划分出一半的值出来。

然而 $(k,b)$ 多达 $10^{10}$ 组，直接存下是不可能的。但是注意到任意时刻对于某个 $k$，可能的 $b$ 都是一个区间，因此我们可以对每个 $k$ 记下这个区间。

现在考虑如何划分。我们把所有可能的 $(k,b)$ 都拿出来并计算它们在 $t$ 处的取值，那么我们只需要询问 $[0,M]$（$M$ 是这些取值的中位数）就可以尽量划分成一半了。求中位数可以二分实现。

Kabaleo Lite

假设自己已经操作完了，考虑能否必胜。

这样考虑：其他人为了阻止自己胜利，一定会尽量把 $h$ 变成别的，并尽量多地造另一种。于是我们考虑求出最少会剩下多少个 $h$（记做 $A$），以及不是 $h$ 的出现次数最多的数出现多少次（记做 $B$）。 那么如果 $A>B$ 的话，则必胜。

先考虑如何求 $A$。设 $x$ 为 $b_{1..n}$ 中 $h$ 的数量，$y$ 为 $l_{2..p}$ 中不为 $h$ 的数量，那么有 $A=\max\{x-y,[l_p=h]\}$。

再考虑如何求 $B$。设 $x_i$ 为 $i$ 在 $b_{1..n}$ 中的出现次数，$y_i$ 为 $i$ 在 $l_{2..n}$ 中的出现次数，那么有 $B=\max_{i\neq h}\{x_i+y_i\}$。

直接做的话是 $\mathcal{O}(n^2)$ 的，考虑优化修改后算 $A,B$ 的过程。一次修改相当于把 $b_i$ 的出现次数减 $1$、$l_1$ 的出现次数加 $1$。

首先 $A$ 是很好维护的，可以发现只有可能 $x$ 变化，只要维护 $b_{1..n}$ 中 $h$ 的数量即可。

$B$ 就有些复杂。可以发现，修改后的最大值只有可能是原来的最大值、次大值和 $l_1$ 中的一个，三个取个 $\max$ 即可。注意不能和 $=h$ 的取 $\max$。

这样子就做完了。注意要特判 $n=1,l_p=h$ 的情况。

CERC 2017

Buffalo Barricades

我们首先求出每个栅栏实际包含的牛的数量（也就是不算被后面的栅栏包含的）。

从上往下扫描线，并用 set 维护所有往下的栅栏的横坐标。

• 如果当前点是牛，我们找到一个最小的 $x\geq$ 它的横坐标的栅栏，则最终这个栅栏包含这头牛；
• 如果当前点是栅栏，我们把它加入 set 中，然后模拟一遍往左延伸的过程，把编号比它大的连续的一段删掉。

接着求出每个栅栏加入时包含的牛的数量。可以发现，如果 A 包含 B，且 A 加入时间比 B 早，那么 B 的答案要加到 A 中去。可以发现这个东西实际构成一个树形关系，我们只需要从前往后扫，然后把父边断掉，这样子扫到每个点时它的 $size$ 就是答案了。可以直接 LCT 维护。

当然也可以不 LCT，直接倒过来变成加边，就很好用并查集维护了。

Cumulative Code

不妨先写出 $k=5$ 时的 Prufer 序列
$$
p^{(5)}=[8,8,4,9,9,4,2,10,10,5,11,11,5,2,1,{\color{red}{3}},12,12,6,13,13,6,3,{\color{red}{7}},14,14,7,{\color{red}{15}},15]
$$
红色的数与其它数不同——这些位置删除的节点是根。但是这些数只有 $k-2$ 个，我们可以单独考虑。下面我们只考虑黑色数的连续段中的情况。

可以发现这样的连续段等于左子树的后序遍历中每个数除以 $2$。

不妨把每个数写成关于根的父亲编号的一次函数的形式，如当 $k=4$ 时有
$$
p^{(4)}(x)=[8x,8x,4x,8x+1,8x+1,4x,2x,8x+2,8x+2,4x+1,8x+3,8x+3,4x+1,2x,x]
$$
考虑 $p^{(k)}(x)$ 与 $p^{(k-1)}(x)$ 的关系。可以发现，$[x]p^{(k)}(x)$ 等于 $\Big[2[x]p^{(k-1)}(x),2[x]p^{(k-1)}(x),1\Big]$，$[x^0]p^{(k)}(x)$ 等于 $\Big[[x^0]p^{(k)}(x),\frac{1}{2}[x]p^{(k)}(x)+[x^0]p^{(k)}(x),0\Big]$。

这样子我们就可以将求 $p^{(k)}$ 中若干等差数列项的和转为两个求 $p^{(k-1)}$ 中若干等差数列项的和的问题，可以直接递归计算。

然而如果递归到底的话是 $\mathcal{O}(2^k)$ 的。我们只需要在没有元素时及时返回，再加上记忆化即可。为了记忆化我们把询问拆成前缀相减，并记录深度与末项的位置。

这样子时间复杂度变为 $\mathcal{O}(2^{k/2})$。实际上我们只需要对前 $\frac{k}{2}$ 层记忆化即可，不影响复杂度。

Donut Drone

考虑先暴力走到第一列，然后倍增跳 $k/m$ 圈，再暴力走完剩下的。

那么我们要维护 $(i,1)$ 走 $2^km$ 步后会到哪里。考虑用线段树维护，每个区间维护从 $l$ 走到 $r+1$ 的哪一行，这样子根节点就是 $(i,1)$ 走 $2^0m$ 步后到的行，再倍增即可。

修改直接把前一列在线段树上修改一下即可。

复杂度大概是 $\mathcal{O}(Qn\log k)$，似乎挺能过的。

Intrinsic Interval

析合树模板题。

如果两个点在析合树上的 LCA 是析点，那么答案就是这个析点对应的段；否则还要找到两个点所在的两棵子树，LCA 的儿子序列中这两个子树间的子序列才是答案。

Kitchen Knobs

显然每个按钮要么最终位置唯一（因为 $7$ 是奇数），要么最后在哪都可以（这种情况当且仅当 $7$ 个数都相等）。后面那种我们可以直接去掉。

我们把每个按钮需要旋转的次数算出来，然后再差分一下（注意这里是在模 $7$ 意义下），问题变为每次可以给一个数加 $x$ 一个数减 $x$，求把所有数变成 $0$ 的最小次数。

$0$ 我们可以直接不管；对于剩下的数，显然我们会先把 $1,6$、$2,5$、$3,4$ 两两相消，这样子最后会剩下至多 $3$ 种数。

可以发现，如果剩下的 $3$ 种数和为 $7$ 的倍数，那么我们一定可以用数量减 $1$ 次操作把它们都消成 $0$。于是我们预处理所有这 $3$ 种数的和为 $7$ 的倍数的情况，然后直接 DP 即可。

Lunar Landscape

注意到值域很小，又和覆盖有关，所以猜测和差分有关。

A 类正方形很好差分处理；B 类正方形是斜着的，感觉不太好处理。

我们做坐标变换 $\begin{cases}x\leftarrow x+y\\y\leftarrow x-y\end{cases}$，那么 B 类正方形就变成正的了，同样可以差分处理。

算答案时，我们算出每个面积为 $0.25$ 的小三角形是否被覆盖，然后加起来即可。

CERC 2016

Bipartite Blanket

可以发现，左右两边点集的可行性是无关的，于是我们可以先预处理出两边的每个点集是否可能被一组匹配覆盖。

考虑这个东西怎么预处理。设 $f_S$ 表示左边点集 $S$ 能否被一组匹配覆盖。那么根据 Hall 定理，我们需要枚举 $S$ 的每个子集 $T$，然后判断 $|T|\leq |N(T)|$ 是否成立。然而这样显然无法通过。

但是仔细思考一下可以发现，$|T|\leq |S|-1$ 的 $T$ 是否都成立我们已经知道了（根据 $f_{S-\{i\}}$），我们只要判断 $|S|\leq |N(S)|$ 是否成立就好了。这样就可以在 $\mathcal{O}(n2^n)$ 的时间内求出 $f$。同理我们在 $\mathcal{O}(m2^m)$ 的时间内求出 $g$ 表示右边点集 $S$ 能否被一组匹配覆盖。

那么问题变为求有多少个 $(S,T)$ 满足 $f_S=1,g_T=1,s_S+s_T\geq t$，可以用 meet in the middle 的思想，把所有 $g_T=1$ 的 $T$ 按 $s_T$ 排序，然后枚举 $f_S=1$ 二分出满足条件的 $T$ 的个数即可。

Dancing Disks

设 $f_{i,j}$ 表示 $(i,j)$ 最多能让多少个数有序。显然 $(i,j)$ 可以多路归并左上方的所有柱子上的数，那么有
$$
f_{i,j}=\sum_{1\leq x\leq i,1\leq y\leq j,(x,y)\neq (i,j)}f_{x,y}
$$
显然 $f_{1,1}=f_{1,2}=f_{2,1}=1$，于是可以推出 $f_{6,6}=26928$，感觉不太行。

冷静分析一下发现，对于 $(1,2)$ 和 $(2,1)$，我们可以看 $(1,1)$ 最上面两个的大小关系，从而实现 $f_{1,2}=f_{2,1}=2$，这样 $f_{6,6}=42960$，非常好。

于是我们递归做这个过程，每次用堆维护多路归并即可。注意每个柱子实际上是一个栈，所以如果当前柱子需要从小到大排，则前面的柱子需要从大到小排，所以我们还要记一下排序方式。

Easy Equation

考虑一组解 $(x_0,y_0,z_0)$，把 $x$ 看成主元，有
$$
x^2-k(y_0+z_0)x+(y_0\!^2+z_0\!^2-ky_0z_0-1)=0
$$
由韦达定理可知，$x$ 的另外一根为 $k(y_0+z_0)-x_0$。

显然原方程有一组解 $(0,0,1)$，我们只要从这个解出发，按照上面的方法扩展出两个更大的解，直到找到 $n$ 个解即可。

Jazz Journey

显然我们可以对所有 $u\to v$ 和 $v\to u$ 的路线单独拿出来算。

首先我们算出 $u\to v$ 的最小花费、$v\to u$ 的最小花费、$u\to v\to u$ 的最小花费、$v\to u\to v$ 的最小花费。需要注意的是前两种可以买双程票，后两种可以买两张单程票。

那么现在一定在不浪费的前提下尽量多买双程票更优，于是我们先做两遍类似括号匹配的过程，先尽量多买更便宜的那种双程票，再尽量多买另一种，剩下的就买单程票即可。

Lost Logic

如果一个变量取值全为 $0$，我们加一个 $x\to \neg x$，限制它只能为 $0$；同理，如果一个变量取值全为 $1$，我们加一个 $\neg x\to x$，限制它只能为 $1$。

然后一个自然的想法是枚举 $i,j$，如果 $i$ 为 $x$ 的时候 $j$ 全为 $y$，就加一个 $ix\to jy$。但是这个约束数是 $\mathcal{O}(n^2)$ 的，并不太行。

那么可以先把那些相同的或者互补的缩起来。具体的，如果 $i,j$ 相同就加 $i\to j$ 和 $\neg i\to \neg j$，如果 $i,j$ 互补就加 $i\to \neg j$ 和 $\neg i\to j$。

这样子只会剩下至多 $3$ 种（$0,0,1$、$0,1,0$ 和 $1,0,0$）。冷静分析一下发现：如果 $3$ 种都有，则不能构造出合法方案；如果只有 $1$ 种，则我们不需要再连边；如果只有 $2$ 种，我们直接枚举两种的取值（共 $4$ 种情况），然后判断是否需要连边即可。

CERC 2015

Export Estimate

考虑按边权从大到小加边。

先考虑算点数。观察一下这个过程，似乎所有度数是 $0$ 或 $2$ 的点都会被删掉？其实并不是，因为一个度数全是 $2$ 的点构成的环最后会留下一个点。所以点数实际上是 $n-cnt_0-cnt_2+cnt_{loop}$。

边数同理，所有度数为 $2$ 的点都会删去两条边再加上一条边，但一个度数全是 $2$ 的环最后会留下 $2$ 条边。所以边数是 $e-cnt_2+cnt_{loop}$，这里的 $e$ 是已经加入的边数。

那么唯一的问题就是如何维护 $cnt_{loop}$ 了。因为只有加边，所以可以用并查集很方便的维护（只需要维护每个连通块是否是度数全为 $2$ 的环即可）。

Frightful Formula

先考虑 $c=0$ 的情况。我们计算每个 $l_i$ 和 $t_i$ 对 $(n,n)$ 的贡献。

只考虑 $l_i$，那么相当于从 $(i,1)$ 走到 $(n,n)$，第一步必须往右，往右走一步乘 $a$，往下走一步乘 $b$，求所有路径的权值和。这个东西显然等于
$$
{2n-i-2\choose n-2}a^{n-1}b^{n-i}
$$
再考虑 $c$ 的贡献。同理可以知道，$(x,y)$ 对 $(n,n)$ 的贡献是
$$
c{2n-x-y\choose n-x}a^{n-y}b^{n-x}
$$
那么总贡献是
$$
\begin{aligned}
&c\sum_{i=2}^n\sum_{j=2}^n{2n-i-j\choose n-i}a^{n-j}b^{n-i}\\
=&c\sum_{i=2}^n\sum_{j=2}^n(2n-i-j)!\frac{a^{n-j}}{(n-j)!}\frac{b^{n-i}}{(n-i)!}\\
=&c\sum_{d=4}^{2n}(2n-d)!\sum_{i+j=d}\frac{a^{n-j}}{(n-j)!}\frac{b^{n-i}}{(n-i)!}
\end{aligned}
$$
后面是卷积的形式，于是直接 MTT 即可。

有的小青年就发问了，我不喜欢卷积，我不喜欢 MTT，我永远只爱组合意义，你这种推式子，我很不满意！

很好！很有精神！那我们就来分析一下。

我们打个表看一下每一项对 $(n,n)$ 的贡献
$$
\begin{matrix}
ca^0b^0{0+0\choose 0} & ca^1b^0{1+0\choose 1} & ca^2b^0{2+0\choose 2} & \cdots \\
ca^0b^1{0+1\choose 0} & ca^1b^1{1+1\choose 1} & ca^2b^1{2+1\choose 2} & \cdots \\
ca^0b^2{0+2\choose 0} & ca^1b^2{1+2\choose 1} & ca^2b^2{2+2\choose 2} & \cdots \\
\vdots & \vdots & \vdots & \ddots
\end{matrix}
$$
可以发现，当 $i+j\leq n-2$ 时，贡献就是 $c(a+b)^{i+j}$；当 $i+j>n-2$ 时，可以把上一 / 的贡献乘上 $a+b$，然后再减去边上两项，就可以得到贡献了。

Greenhouse Growth

如果一段向日葵高度相同，那么它们在之后任意时刻高度都相同，因此可以缩成一段。

用链表维护这些连续段，每段维护如下信息：

• $l,r$：左右端点；
• $t,h$：在第 $t$ 天时高度为 $h$；
• $fl,fr$：光在左边 / 右边时是否会长高。

第 $i$ 天时的高度可以通过前 $i$ 天光在左边和右边的天数来求出。

我们逐天处理，每天把能合并的合并即可。对于两个相邻的连续段，我们可以根据它们的高度差求出它们会在什么时间合并。于是只要当发生改变时重新计算一下合并时间即可。

具体实现细节比较多，要注意各种奇奇怪怪的情况（比如之前要合并的现在不要合并了）。

Ice Igloos

注意到值域和 $r$ 都很小，所以我们可以只枚举那些圆心到直线距离 $<1$ 的圆。

具体地，我们需要找到所有满足
$$
\frac{\lvert Ax+By+C\rvert}{\sqrt{A^2+B^2}}<1
$$
的圆。

因为值域很小，所以可以直接枚举 $x$，然后把 $y$ 的范围算出来就好了。注意端点需要特判。

Juice Junctions

看到这题的第一反应就是最小割树，然而这个 $n\leq 3000$ 的数据范围一看就很不能过。

注意到题目中有一个奇妙的度数 $\leq 3$ 的限制，这说明最大流 $\leq 3$，我们可以讨论一下：

• 如果两点不连通，最大流为 $0$；
• 如果两点不在同一个边双中，最大流为 $1$；
• 如果两点在同一个边三连通分量中，最大流为 $3$；
• 否则最大流为 $2$。

问题是这个“边三连通分量”怎么求。思考一下发现，如果断掉任意一条边后两点都在一个边双中，则它们在同一个边三中。我们可以枚举断掉的边，然后相当于判断两点所在边双是否一一相等，可以直接哈希判断。

实际上有线性求边三连通分量的算法，但是这题 $\mathcal{O}(m^2)$ 可以过所以就懒得去看了。

CERC 2014

Can't stop playing

可以发现游戏中的序列一定是一个 ^ 的形状。

对于一个单增或单减的只由 $2^k$ 构成的序列，我们只要知道它们的和即可还原出整个序列。

设 $f_{i,j}$ 表示前 $i$ 个数、最高点右边的和为 $j$ 是否可行。因为前 $i$ 个数的和已知所以可以求出左边的和。

转移时只需要看一下当前数是不是小于等于最左边 / 最右边的数即可。注意放在右边时可能会产生新的最大值使得右边的和变成 $0$。

在转移过程中记录一下转移点，倒推即可求出方案。

Pork barrel

把所有边从大到小排序，然后依次加入，并维护 MST。假设询问 $[l,r]$，则加入了所有 $\geq l$ 的边后 MST 上 $\leq r$ 的边权之和即为答案。

LCT 维护生成树、主席树维护每种边权的出现次数即可。

The Imp

实际上双方都知道对方的最优策略。

那么对于我方的某个策略 $(s_1,s_2,\cdots)$，显然有 $v_{s_i}<v_{s_{i+1}}$，否则一定更劣。

于是我们先把所有物品按 $v$ 从大到小排序，然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品，对方去掉了 $j$ 个的最大收益，转移为
$$
dp_{i,j}=\max\left\{dp_{i-1,j},\min\left\{w_i-v_i,dp_{i-1,j-1}-v_i\right\}\right\}
$$
答案即为 $dp_{n,k}$。

Outer space invaders

考虑 $d$ 最大的那个外星人，我们选一个时刻把它打了，那么剩下左右两端只剩下了被完全包含的外星人。

于是可以区间 DP。设 $dp_{i,j}$ 表示 $[i,j]$ 完全包含的外星人被打掉的最小代价，转移是
$$
dp_{i,j}=\max_{k=i}^j\left\{dp_{i,k-1}+x+dp_{k+1,j}\right\}
$$
这里的 $x$ 时被 $[i,j]$ 完全包含的外星人中最大的 $d$。

CERC 2013

Subway

似乎是 JSOI2015 地铁线路 的原题。当然那题把输入改简单了。

第一问考虑最短路。对于每条线路建一个点，线路上的站向线路连边权为 $1$ 的边，线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。

第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。

假设一条线路的 $dis$ 为 $d$，则我们可能在 $dis$ 为 $d-1$ 的站上车，在 $dis$ 为 $d$ 的站下车，所以我们要用 $dis$ 为 $d-1$ 的站更新 $dis$ 为 $d$ 的站。

把所有线路按 $dis$ 从小到大排序，然后对于每条线路转移：$dp_j\leftarrow dp_i+dis(i,j)\;(dis_i=d-1,dis_j=d)$。记一下前后缀最大值即可 $\mathcal{O}(L)$ 转移。

Chain & Co.

考虑按照平行的平面分成三类，那么每一类内部肯定只能在一个集合内。

于是我们枚举哪一类是单独的，然后暴力 check 一下就好了。

Captain Obvious and the Rabbit-Man

可以发现 $p_i$ 是 $k$ 阶常系数齐次线性递推数列，其特征多项式为 $p=(X-1)(X-2)\cdots (X-F_k)$。

设 $p=X^k+a_{k-1}X^{k-1}+\cdots+a_0$，则有
$$
p_{k+1}+a_{k-1}p_k+\cdots+a_0p_1=0
$$
只需要 $\mathcal{O}(k^2)$ 求出 $p$ 的系数即可。

NEERC NSub 2017

Consonant Fencity

暴力是枚举每种字符是大写还是小写，然后扫一遍算答案，复杂度 $\mathcal{O}(2^{|\Sigma|}n)$。

实际上我们只需要知道每个字符对的出现次数，预处理后即可做到 $\mathcal{O}(2^{|\Sigma|}|\Sigma|^2)$。

然而 $|\Sigma|=26$。但是实际上元音字母的大小写是无关紧要的，我们只需要知道辅音字母的大小写即可。这样子就有 $|\Sigma|=19$，可以通过此题。

Equal Numbers

显然只有两种情况：要么是一个数全部变成了它的某个倍数，要么是一些数变成了它们的 LCM。

两种情况肯定都是先选个数少的，排序后扫一遍即可。

Fygon 2.0

对于一个 for i in range(a, b):，可以看成 $i$ 在 $[1,n]$ 内循环，但是只有 $a\leq i\leq b$ 时才算贡献。

我们从 $a$ 向 $i$、$i$ 向 $b$ 连边，则一个强连通分量内的变量取值必须相同，即 $k$ 即为强连通分量数。

然后 $C$ 感性理解一下就是缩点后的大小关系数除以点数的阶乘，而前面那个东西就等于 DAG 的拓扑序数，状压 DP 即可。具体证明可以看这里。

Grand Test

似乎和 CF521E Cycling City 一模一样。

首先 DFS 一遍求出一棵生成树，那么只会有一些返祖边。答案存在当且仅当有一条树边被至少两条非树边覆盖。

假设这两条非树边是 $(a,b)$ 和 $(c,d)$，$t$ 是 $a,c$ 的 LCA，如下图

那么 $3$ 条路径即为 $t\to b$、$t\to a\to b$、$t\to c\to d\to b$。

实现时可以直接暴力覆盖、暴力求 LCA，时间复杂度 $\mathcal{O}(n)$。

Hidden Supervisors

可以证明，包含根的最大匹配只会比不包含根的最大匹配大 $0$ 或 $1$。

于是我们对每棵树都求一个最大匹配（可以直接 DFS 求出），然后分成两类：根在匹配中的和根不在匹配中的。特别的，$1$ 并不能连父边，所以要强制看成第一类。

那么我们相当于要把第二类的根拿去匹配前面某个未匹配的点。第一类树中的未匹配点是可以匹配的，而第二类按照未匹配点的数量从大到小排序后加入一定是最优的。如果前面没有未匹配的点，那么可以连到 $1$ 上保证形成一棵树。

NEERC NSub 2016

Digital Addition

每一位的状态只有 $200$ 种，可以直接预处理出来。

考虑数位 DP。设 $f_{i,S,0/1}$ 表示 $[i,w]$ 位、第 $i$ 位左边黑色部分为 $S$、是否进位是否可行，转移直接枚举下一位的状态即可。

因为要输出方案，所以要记录一下每个状态是从哪里转移过来的。

Easy Reading

首先不是 u,d,l,r 的字符是没用的，可以直接去掉。

两个图案相同至少要黑格子数量相同，于是可以双指针求出所有黑格子数满足条件的区间。

在双指针的过程中可以维护出黑格子，但是我们并不能 $\mathcal{O}(nm)$ 的判断图案是否相同。

考虑哈希。设 $H_{x,y}=A^xB^y\pmod{p}$，那么我们只需要比较两个图案的哈希值即可。注意图像是可以平移的，所以我们还需要求出当前图案的黑格子中最小的 $x$ 和 $y$，然后乘上 $A^{-x}B^{-y}$ 平移到原点比较。

然而卡自然溢出，所以最好在哈希值相同时暴力比较一遍。

Gangsters in Central City

显然至少要断掉的边数就是 $1$ 的有强盗的子树数量，因为我们可以直接断掉与 $1$ 相连的边。

于是我们可以把 $1$ 的每棵子树分开考虑（下面的强盗只指 $1$ 的某棵子树中的）。为了满足第二个条件，断掉的边一定是最深的强盗全在其中的点的父边。这个点实际上就是强盗的 LCA。

可以考虑一个经典套路：对于每个强盗，把它到根的路径加上 $1$，那么这个点就是所有点权最大的点中最深的那个。

这样子就可以直接树剖+线段树维护了。删点后子树中没有强盗了的情况可能需要注意一下。

Integral Polygons

如果总面积不是整数则答案为 $0$，否则只要一侧面积为整数即满足条件。

那么也就是（$\times$ 是叉积）
$$
\vec{p_i}\times\vec{p_{i+1}}+\vec{p_{i+1}}\times\vec{p_{i+2}}+\cdots+\vec{p_{j-1}}\times\vec{p_j}+\vec{p_j}\times\vec{p_i}\equiv 0\pmod{2}
$$
设
$$
s_n=\sum_{i=2}^n\vec{p_{i-1}}\times\vec{p_i}
$$
上面的条件即
$$
s_j-s_i+\vec{p_j}\times\vec{p_i}\equiv 0\pmod{2}
$$
把叉积也拆开，变成
$$
s_j-s_i+x_jy_i-y_jx_i\equiv 0\pmod{2}
$$
枚举 $j$，那么 $s_j,x_j,y_j$ 的奇偶性已知，我们只需要知道 $s_i,x_i,y_i$ 的奇偶性即可判断是否合法。这只有 $8$ 种情况，开一个桶记一下即可。

注意去掉 $i=j+1$ 和 $i=1,j=n$ 的情况，因为这样的情况面积一定是整数，所以只需要最后减 $n$ 即可。

Java2016

我们可以先对很多个 ? 取 max 来得到 $255$，然后把两个 $255$ 相除得到 $1$。因为代码长度限制需要套几层宏定义。

然后可以求出 $2,4,8,16,32,64,128$，直接把 $c$ 拆位即可。

$0$ 需要特判（直接把样例蒯下来即可）。

NEERC NSub 2015

Distribution in Metagonia

不是很晓得怎么想出来的，直接给算法了：

• 首先找到最大的 $2^x|n$；
• 然后找到最大的 $2^x3^y\leq n$；
• 把 $2^x3^y$ 作为一个答案，然后递归分解 $n-2^x3^y$。

可以发现 $n-2^x3^y$ 中 $2$ 的次数一定 $>x$（因为 $n$ 除掉 $2^x$ 后是奇数，再减掉奇数后是偶数，也就是 $(n-2^x3^y)/(2^x)$ 是偶数），而 $3$ 的次数一定 $<y$（因为数变小了 $2^x$ 还变大了），所以满足条件。

Fygon

易知答案是 $\leq 6$ 次的多项式，于是只要暴力模拟出 $n=0,1,\cdots,6$ 时的执行次数，然后拉格朗日插值即可。

Insider’s Information

考虑每次确定两边的一个元素。那么一个三元组 $(a,b,c)$ 相当于要求 $b$ 不是最早被确定的元素。

考虑先求出一个排列 $p$，满足对于每个三元组 $(a,b,c)$，$a,c$ 中都有一个在 $b$ 的前面。这个可以拓扑排序求出。

然后我们按照这个排列的顺序插入。一个三元组在排列中的顺序只有两种情况：$b$ 在第二个或者第三个。

假设第一个在左边。如果 $b$ 在第二个，那它应该插入到左边才能满足；如果 $b$ 在第三个，那它应该插入到右边才能满足。

这样子会有一些三元组要求当前元素插到左边、一些三元组要求当前元素插到右边，哪一种多就插到那边即可，这样子满足的三元组数一定不会少于不满足的。

NEERC NSub 2014

Fragmentation

如果 $i$ 与 $i+1$ 在同一段中，则连边 $(i,i+1)$，则我们相当于要最大化边数。

可以发现，如果 $a_i=a_{i+1}$，则两者在同一段内更优。下面设 $a_i\neq a_{i+1}$。

考虑怎样 $i$ 和 $i+1$ 才能连边：

• 首先显然要有 $a_i<a_{i+1}$。
• 如果存在一个 $j$ 使得 $a_i<a_j<a_{i+1}$，则不合法。为了方便可以先离散化，则应有 $a_i+1=a_{i+1}$。
• 如果 $a_{i-1}+1=a_i=a_{i+1}-1$，且 $a_i$ 出现次数大于 $1$，则不能同时连 $(i-1,i)$ 和 $(i,i+1)$。
• 对于一个 $c$，最多只能有一条边 $(i,i+1)$ 满足 $a_i=c,a_{i+1}=c+1$。

考虑 DP。设 $dp_i$ 表示只考虑权值 $\leq a_i$ 的边，且连了边 $(i-1,i)$ 时边数的最大值。

转移从 $a_j<a_i$ 的 $j$ 转移过来；如果 $a_i$ 出现超过一次，则还不能从 $a_i-1$ 转移。因此只需要维护一个最大值和次大值即可。

输出方案的时候不要忘记把之前去重去掉的加回来。

Kebeb House

设 $dp_{i,j}$ 表示前 $i$ 秒、做当前串时已经做了 $j$ 次梦的方案数。转移有两种：

• 如果这一秒不做梦，从 $dp_{i-1,j}$ 转移。
• 如果这一秒做梦，设 $p=i-t-1$，那么
  • 如果 $p$ 时刻做的串不是当前串，那么那一串做几次梦都是可以的，所以从 $\sum dp_{p,k}$ 转移到 $dp_{i,1}$（这时一定有 $j=1$，因为 $i$ 是当前串第一个做梦的时刻）。
  • 如果 $p$ 时刻做的串是当前串，从 $dp_{p,j-1}$ 转移。

NEERC NSub 2013

Heavy Chain Clusterization

把每种前后缀拿出来，对于每个串把它的前后缀连边，问题转化为求二分图最小点覆盖。