CF1307F Cow and Vacation

首先在边上建点，于是距离就从 $k$ 变成了 $2k$。

距离变成偶数后，对于两个位置，它们可达的条件就是从其中一个走 $k$ 另一个走 $k$ 能到的点有交。

首先考虑以每个点作为中转点可以到达的点。也就是只要某一步到达了这个点就一定可以通过转驿站来走到的点。做法是把所有驿站加入队列距离设置为 $0$ 进行一次 bfs 。考虑当我们从一个点到达另一个已经访问过的点，那么这两个点所对应的联通块可以直接合并，因为总是可以通过这两个点的初始驿站互相到达。如果当前点与最近的驿站的距离已经超过了 $k$ 就弹出。直接用并查集维护即可。

然后考虑两个点之间是否可达。相当于两个点作为了一个初始的驿站。根据一个很显然的贪心，我们可以通过向对方走 $k$ 步然后判断这两个点作为中转点是否可达即可。

Bubble Sort

题意：给你一个序列，问你进行一次交换后的最小逆序对数。

虽然没写，但是那天大致想了一下怎么做。

考虑交换两个数对逆序对造成的贡献，如果想要减小逆序，必须这两个数原本就是逆序的，贡献就是这两个位置之间的，大小在这两个数之间的数的个数。

本质上就是找两个点 $(i,A[i]) , (j,A[j])$ 选出它们的矩形内的点。不难发现一定有 $(i,A[i])$ 左上方一定没点，$(j,A[j])$ 右下方一定没点。

大概可以决策单调性，我们如果把能作为左上方的点拿出来，能作为右下角的点拿出来，考虑一下四边形不等式：

不难发现右边一定优于左边。我们把右上角的点的 $dp$ 值看作 $0$ ，这样就相当于只选一次做 $dp$ ，既然满足四边形不等式就一定满足决策单调性了，分治做即可。

还有扫描线做法，感觉有点麻烦就懒的写了。

P5902 [IOI2009]salesman

部分分很好做。如果任意两个展会都不在同一天举行，也就是对展会按照时间进行排序后，问题就可以转化成选择一个子序列，使得最后的权值尽量大。而且不难发现新加入一个点只和之前最后的一个点的权值有关，可以很简单地写出方程：

$$f[i] = \max\{f[j] - cost(j,i) + w_i\}$$

然后可以分成从上游来还是从下游来：

$$f[i] = \max\{f[j] - (L_j - L_i) U + w_i\} (L_j > L_i)\\ f[i] = \max\{f[j] - (L_i - L_j) D + w_i\} (L_j < L_i)$$

拿两个 BIT 维护前后缀最大值即可。

---

考虑有很多展会在同一天举行。

稍微更改一下 $dp$ 数组的定义，设 $f[i]$ 表示已经结束了 $i$ 展会这一天的所有操作，最后在 $i$ 这个位置结束，所得到的最优收益。

这一天内的展会最后会得到访问的必然是一段区间，显然不选择区间一定可以把左右端点内的所有点都选上更优。于是，一天的决策一定是这两种：

也就是要么一路扫过去，要么扫过去再折回来。

开始思路就卡在这里了，不太清楚怎么 $dp$ 这个。其实场后觉得也很自然。由于我们需要求出的是每个这一天内的点作为结束点的时候的最优收益，我们可以先用线段树把红箭头的情况解决，也就是用类似部分分的方程解决从上一天的状态转移到这一天的某个位置，并且只通过向上或者向下的方向之一走。然后再做一次层内的 $dp$ ，设 $dp[i]$ 表示层内结束点是 $i$ ，由 $i$ 上游某个点转移过来的最小代价，同理设 $pd[i]$ 表示从下游转移。这里就可以把折线的情况考虑到了，虽然会重复计算同一个方案，但是可以算出最优的结果。

复杂度是 BIT 查前后缀最大值 $O(n \log n)$。

HDU6212 Zuma

考虑一个区间 $dp$ ，设 $dp[l][r]$ 表示把区间 $[l,r]$ 全部削除的最小代价。不难发现，如果左右端点不同色，那么一定有一个中间的点，在这个点左边一起削完，右边也一起削完，直接从中间转移即可。

否则，如果左右端点同色，前面的转移依然适用。除此之外还需要考虑最后一次操作左右端点才被削掉的情况。我们考虑给颜色分段，每段颜色维护这段的长度（$1$ 或 $2$）。首先我们可以钦定把 $[l+1,r-1]$ 的东西先全部削除完，再来削除 $[l,r]$ ，因为如果在这个过程中，$[l,r]$ 已经有被削除的了，那么会在上一种转移中计算到，而且最后再削除 $[l,r]$ 不会优于之前的情况，因此，如果 $l,r$ 长度均为 $1$ 就再多进行一次操作即可。

但是还有一种情况，我们可以在中间枚举保留一个球，让它和左右相撞后一起削除。这种东西可以做到的前提是左右长度和不超过 $3$ ，也就是最多只有一边长度是 $2$ ，这样才可以让长度为 $1$ 的提前和这个球撞在一起，然后再把剩下的那个长度为 $2$ 的撞过来。

三种情况分别转移即可。详细 $dp$ 实现参考代码。

复杂度 $O(n^3)$ ，就是一个区间 $dp$ 的复杂度。跑不满，这题一般的 $O(n^3)$ 只要带常数基本就 GG 了。

UVA12212 Password Remembering

写的是非数位 $dp$ 做法，也挺细节的，可能不比数位 $dp$ 好写到哪里去。

首先，显然的容斥 $calc(B,B) - calc(A-1,B) - calc(B,A-1) + calc(A-1,A-1)$ ，然后我们只需要算 $cal(A,B)$ 也就是 $\le A$ 的数中倒过来 $\le B$ 的数的个数。

计算 $\le A$ 的数的基本套路就是枚举一段 $\text{LCP}$ ，考虑枚举 $\text{LCP}$ 的长度，然后再枚举一下 $\text{LCP}$ 的下一位放个啥，然后我们把第 $i$ 个数以及更高位组成的数存储下来，作为一个数 $t$ 。也就是我们现在确定了 $b$ 的低 $L+1$ 位。不难发现这个时候的方案数量就是 $\frac{B-t}{10^{L+1}} + 1$ 这个东西。

但是现在还有 $a$ 的位数不到 $A$ 的位数的情况。为了方便讨论，我们强制让 $B$ 的位数不超过 $A$ ，具体操作就是如果超过了把 $B$ 变成 $9999\dots 99$ 我们分两种，如果这个位数也不到 $B$ 的位数，很好处理，因为不管填个啥都不超过 $A,B$ 。然后还得考虑结尾填一些后缀 $0$ 上，但是不能补到和 $A$ 位数相同。最后就是 $b$ 和 $B$ 位数相同的情况，考虑方案数量，首先 $[0,10^{lB})$ 都被计算过了，我们考虑剩下的数，如果一个数有后缀 $0$ ，那么它就已经被之前算过了，去掉剩下的数中有后缀 $0$ 的即可，个数就是 $( b - \lfloor \frac b{10}\rfloor )(la - lb)$ 。

复杂度大概是 $O(T \times 19 \times 9)$ 这个东西。

T1 游戏

别人都是 $dp$ 做的，这里提供一个不用 $dp$ 的思路。

一次最多只能跨 $k$ 步，我们考虑把 $n$ 之内的所有质数先筛出来，然后考虑是否存在两个质数，它们的差减 $1$ 仍然严格大于 $k$ ，如果 $n$ 是质数，那么考虑 $n$ 和上一个质数的差是否严格大于 $k$ 。考虑如果出现了这种情况，那么可以断定后手必胜。我们考虑最后一次出现前面说的情况的两个质数 $p_i,p_{i+1}$ ，满足 $p_{i+1} - p_{i} - 1 > k \or ( p_{i+1}=n \and p_{i+1} - p_i > k )$ ，那么显然先手是不能一次跨过这两个质数的，那么某个时刻，先手一定会落在 $p_{i+1}$ ，后手这个时候只需要往前跳一步，先手就没救了。或者如果当前是 $n$ ，那么先手开头就直接没救。

现在我们考虑分别统计两种情况，最快结束和最晚结束。这个直接贪心跳即可。如果先手必胜，那每次就跳尽量远的素数，后手就没次都只跳 $1$ ，不难证明肯定是两个人的最优决策了，而且一定能获胜。如果先手必败，那么先手每次都跳最近的素数，然后后手每次就尽量跳 $k$ 即可。大概再判断一下后手能不能一次跳到之前找到位置的下一个位置即可。

复杂度 $O(n\log n)$ ，显然非常跑不满，场上比很多 $O(n)$ 都快。

T2 序列

憨憨题，为啥放在这里啊，数据范围还诈标 $500$ 。。

显然放开头结尾最优，直接拿栈整出最后的括号序的形状即可。

复杂度 $O(n)$。

T3 收益

题意：

给定一个长度为 $n$ 的序列，求区间 $[l,r]$ 内的最大 $a < b$ 满足 $\frac{\sum_{i=a}^b A_i}{b-a}$

也就是区间和除以区间长度减 $1$ 尽量小。

显然可以考虑前缀和，然后就是 $\frac{S_b - S_{a-1}}{b-a}$ 。我们考虑每个点维护两类点，一类 $A(a,S_a)$ 一类 $B(b,S_{b-1})$。

然后问题就转化成了区间内选择一个靠前的 $B$ 类点，一个靠后的 $A$ 类点，求这两个点的最大斜率。

首先考虑如果只有一次询问怎么做。这是一个经典的问题，有一种很仙的线形做法。首先，直接对这个点前面的 $B$ 点建凸包并在凸包上二分是可以的，但是复杂度会带一个 $\log$ （而且我场上这个东西还没写挂了）。但是，sjx 教了我一种很神仙的线形做法。考虑由于 $x$ 坐标单调递增，虽然 $y$ 坐标的变化无规律，但是我们仍然可以确定，在维护凸包的队首不优于第二个值的时候，队首就可以弹掉了。这样可能会导致局部的最优值挂掉，但是一定可以找到全局的最优解。因为这个东西挂掉的情况一定是两个最优线出现了一个交叉状的东西，但是后面的一定不优于前面的。（大概也可以画图感性理解一下）。

于是我们现在得到了一个 $O(nq)$ 的做法。可以通过前 $40\%$ 的数据。然后最开始数据太水被 $n^2$ 或者 $nq$ 水到了 $70$ 甚至 $100$ 。。后来加强数据只能 $40$ 了。

然后考虑，如果询问组数很多。首先可以分块，块内预处理出最优答案。然后：

设块大小是 $B$ 。

如果询问的两个位置在同一个块内，直接暴力，复杂度 $O(B)$ 。

考虑对于询问的两个位置不在同一个块内。

对于中间的整块，我们考虑对从每个块的左端点和右端点分别向右向左扫一遍处理出每个位置的最优解和前缀后缀 $\max$ ，于是整块对整块以及整块对散块的询问复杂度就是 $O(1)$ ，预处理复杂度是 $O(\frac{n^2}{B})$ 。

然后考虑两边零散的部分，不难发现它们关于整块的答案已经被解决了，于是现在的问题就只有零散块之间的部分。我们可以把它们拼在一起暴力做一遍，复杂度 $O(B)$

于是复杂度是 $O(qB + \frac{n^2}{B})$ ，如果设 $B = \sqrt n$ 大概复杂度就是 $O(n\sqrt n + q\sqrt n)$ 了。

空间复杂度是 $O(n\sqrt n)$ 左右，因为维护了两个数组很容易爆炸，块大小设得大一点就好了。（本身这题 $q$ 很小所以块设大一点也快一些）。

T4 蜡烛

写一个我场上写的做法，和出题人的做法不太一样。而且这个做法不是基环树的情况也可以做，也就是貌似控制一个灯的不一定得有一个开关是它自己。

我们把图给画出来，发现灯所在的一侧每个点度数都是 $2$ 。二分图上某一侧的点的度数都是 $2$ 是一个经典操作，可以考虑这两个出度之间的关系。

在这个题中，可以发现如果这个灯本身没亮，这两个出度点状态必须相同，否则这两个点状态必须不同。也就是说每个灯都可以看作是一个限制，限制的是两个开关的状态（要么相同，要么不同）。

如果这是个静态问题，那么这是一个可以用带权并查集维护的东西。我们考虑对每个并查集的每个点，维护出它向上的边权。如果是 $1$ ，就意味着这个点的子树内的点在整棵树中的限制要反色。然后我们还需要维护出整个树中限制为 $0$ 的点的个数和限制为 $1$ 的点的个数。然后查询答案的时候，可以发现我们一定会让限制为 $0$ 的点的个数和限制为 $1$ 的个数中较少的那一种作为亮灯，剩下的作为灭灯。然后合并的时候按秩合并，讨论一下加入的子树必须和另一个子树颜色相同或相反维护即可。

但是因为这题有 $A_i = i$ 的情况，这种限制就是钦定了一个开关的开关状态。于是我们还需要往并查集中加入一个这个并查集必须是 $0 / 1$ 的限制个数。如果一个并查集 $0/1$ 都必须限制，显然答案就是 $-1$。

然后如果这不是静态问题，显然每个灯的状态会持续的时间可以线段树分治，然后就没有删除操作了。然后线段树分治一下，只需要回滚操作，复杂度 $O(n\log^2 n)$ ，其中一个是按秩合并，实际上速度和 std 差不多，但是感觉可能没有 $\text{LCT / ETT}$ 之类的东西维护基环树写着爽。

CF743E Vladik and cards

值域 $8$ 就有很多奇妙做法了。

首先考虑出现次数最小的数字的出现次数，不难发现这个数是越大越好的，而且如果大的满足，小的一定满足。所以会想到二分一下次数最小数的出现次数。

然后判断我们可以直接 $O(8!)$ 枚举一下出现的顺序，然后直接贪心跳出现次数即可。

最后再 $O(2^8)$ 枚举一下哪些数出现次数多 $1$ ，判断还是暴力跳。

复杂度 $O(8 \times 8! \log n + 2^8 8!)$ 。

BZOJ3340 [CEOI2013] Tram

一个非常重要的观察：

$$\sqrt{1 + x^2} < \sqrt{(1+x)^2}$$

也就是，对于一个点，我们一定会找一个距离最近的有点的行最远的位置，如果有多个，就找是否存在一个位置最近的有点的行只有一边有点，且这里可以和这一行错开，这样可以让距离变大一些。所以，两个点实际上的距离可以变成以行号差做第一关键字，列号差做第二关键字的距离。虽然大致思路是这样，但是其实这个东西有很多细节，如果用 set 维护会显得非常难写，于是考虑线段树维护。

我们对每一个线段树的节点维护出这个节点所代表的区间内的位置，表示用这个位置到左右最近的有点的行的距离为第一个关键字，是否可以错开作为第二关键字的大小的最大的位置，同时维护这个距离。如果区间内一个点也没有或者只有一个点，那么就不维护这两个东西了，直接设 $0$ 。

然后还需要维护最左边和最右边有点的行是谁，以及这行内有一个点（包括位置）还是两个点。

然后 pushup 是一个非常码的东西。

首先最左边和最右边点的维护是很显然的。否则，我们可以先尝试继承一下左右的最大距离。

然后考虑跨中点的情况，这个东西很需要画图推一下。大致思路是先分类讨论一下两边都是两列都有点，还是只有一边两列的有点，还是都不是两列都有点，再讨论一下长度的奇偶就行了。大致情况长这样：

然后，还需要特殊讨论一下放在开头结尾的情况。就拿线段树中开头结尾的点出来判一下即可。

用来练习代码能力算是一个好题。然后我写这题 pushup 也是重构了一次的

Gym100543K The Imp

这也是一个有很多做法的题。

我们考虑如果你决策出了最优情况下的 $k$ 个物品，实际上的代价就是

$$\min\{v_1 -c_1 ,v_2-c_1-c_2 ,\dots ,v_k - \sum_{j=1}^k c_j\}$$

这是一个经典的贪心问题。我们可以贪心出最优的选择顺序，具体来说，直接按照 $v_i,c_i$ 来排序即可。证明的话，如果我们把 $c_i = -c_i , v_i = -v_i$ ，然后类似就变成了 $\max$ ，然后就可以套用这里的挑战一题的题解了。当然，也可以类似地推一下。这里就不再推了。

现在我们就确定了一个相对的顺序。然后的处理方式有很多。首先显然是不能背包的。

可以类似我当时写的做法，先二分你最后获得的钱，设 $dp[t]$ 表示选择了 $t$ 个物品最小需要的钱，必须满足选 $1\sim t$ 个物品时的收益都大于等于二分的值。然后考虑这个位置是否可以作为选择的第 $i$ 个物品，转移即可。复杂度 $O(nk\log n)$。

如果从后往前考虑发现可以不二分。就考虑到第 $i$ 个位置，当前选择了 $t$ 个物品可以获得的最优代价。倒着做有一个好处，就是每次新加入一个物品，没有必要去考虑之前的 $\sum c_i$ ，这个物品本身的贡献就正好是 $v_i - c_i$ ，而它后面的物品的贡献正好就是全部减去 $c_i$。转移就是

$$f[i][j] = \max\{f[i+1][j],\min\{f[i-1][j+1],v_i\}-c_i\}$$

很简洁，复杂度就是 $O(nk)$ 。

Gym100543L Outer space invaders

我们考虑按照时间作为 $x$ 轴，位置作 $y$ 轴，然后相当于给了 $n$ 条横着的线段，每次可以花费 $r$ 放一个底部在 $x$ 的长为 $r$ 的竖着的线段，并且消灭所有接触的线段。

我们先给坐标离散化一下，然后考虑区间 $dp$ 设 $dp[l][r]$ 表示消灭横坐标在 $l\sim r$ 的所有线段需要的最小花费。不难发现，因为最后所有线段都会被解决掉，我们每次直接拿区间内最高的线段区间来转移是可以的，这样计算每个位置的代价会很方便。

复杂度 $O(n^3)$。

T1 calxor

显然，由于答案是把所有东西 $xor$ 起来，所以可以直接把 $p_i$ 提前 $xor$ 起来。所以现在问题就变成了 $\oplus_{i} \oplus_j (i \bmod j)$ 。考虑枚举一下模数，不难发现相当于是算 $\oplus_{i < k} i$ 异或自己 $\lfloor \frac n k\rfloor$ 遍，在算 $\oplus_{i \le n \bmod k} i$ 。

所以预处理一下 $1 \dots n$ 的前缀异或就可以 $O(n)$ 算了。

大概长这样：

T2 perfume

开始看错题了就不会了。。后来发现是 $k^t$ 而不是 $t^k$ 就很显然了。

直接枚举一下 $k^t$ ，发现只需要枚举 $\log 10^{14}$ 次。 然后就是求区间和等于某个数的方案即可，这个东西用个 map ，或者 hash 一下都可以。复杂度也就是 $O(n\log n\log v)$ 或者 $O(n\log v)$。

记得特判 $\pm 1$。

T3 distrbute

神仙题。

场上都已经观察到 $2^k$ 的情况一定不需要钻石了，却没想到和 highbit 有联系。。感觉博弈论很薄弱。。

首先考虑 $s=0$ 的情况。

假装我们有两个钻石，手玩一下。如果有 $1$ 个人，显然是全部给自己。如果两个人，还是可以全部给自己，自己给自己投一票即可。

如果有三个人，我们可以给第一个人一个钻石，然后就可以收买第一个人，因为如果第三个人死了第二个人肯定不会分给第一个人钻石。

如果有四个人，那么我们可以给第二个人一个钻石，类似地可以收买他。如果有五个人，那么我们会给 $1,3$ 各一个，再自己给自己投一票。如果有六个人，那么会给 $2,4$ 各一个，再自己给自己一票。如果有七个人，那他就没救了。

也就是说，可以观察到的是，如果有 $k$ 个钻石，那么可以让前 $2k + 2$ 个人活下来。

那么 $2k + 2$ 之后就一定会死吗？我们继续手玩下去，$8$ 个人的情况，由于 $7$ 会死， $7$ 显然会投票，然后 $8$ 再在前面收买两个人，自己再投票，就活下来了！然后继续考虑，如果有 $9,10,11$ 个人，都会死，因为只能收买两个人，即使 $11$ 的时候 $9,10$ 都投他，自己再投票都不够。但是在 $12$ 的时候就可以活下来了，算一下会发现正好 $6$ 票。

我们把两个钻石的时候可以活下来的人数写出来，是 $1,2,3,4,5,6,8,12$ ，发现 $>4$ 的情况正好是 $4+1,4+2,4+4,4+8$ 。能否理性说明这个规律呢？我们考虑如果有 $k$ 个钻石，有 $2k + 2^t$ 个人，我们归纳一下，假设 $2k + 2^{t-1}$ 个人可以全部活下来，那么一定可以先用这 $k$ 个钻石去收买前 $2k$ 个人，然后剩下了 $2^t$ 个人前一半是可以稳活下来的，会把老大投出去，而后一半一定会被票，所以会给老大投。然后老大正好就可以活下来。然后除了 $2^t + 2k$ 这样的形式的人数，必然都会被前面的人票死。

所以我们现在就有了一个结论，获胜等价于人数等于 $2^t + 2k$ 。如果人数是偶数，显然直接除去 highbit 即可。否则，答案就是 $\lfloor \frac{n-1}{2} \rfloor$ ，也就是找一个 $k$ 使得 $2k+1 = n$ 。

然后 $s=1$ 的情况。

会发现，在人数超过 $2n$ 的时候，这个人能获胜的必要条件是他给自己零个。所以如果想要获胜，就必须找一个 $k$ 使得 $2k$ 大于等于人数，答案就是 $\lceil \frac n 2 \rceil$ 。

T4 editor

看到这些操作，看着就很平衡树。我们考虑维护一个 splay ：

• 插入，我们维护出当前光标的权值，然后直接插入即可，插入后继续维护光标位置。
• 删除，直接在 splay 删除。
• 左右移，移动光标位置即可。
• 询问，把 $[l,r]$ 放到一个子树上，然后维护个子树和即可。
• 修改，把这个数找到并且 splay 到根修改即可。

平衡树板子。

Circle Union

题面

首先考虑，如果所有圆的交是一个面积而不是一个点，那么一定不优。因为可以通过调整，把一些圆从交往外拖的方式，让交的面积进行很多次贡献，答案肯定变优。所以边界的交一定是一个点。

如图，我们现在相当于是在给每个圆分配一个角度（例如圆 $C$ 的 $\ang KNO$），使得角度的和是 $2\pi$ 同时面积的并尽量大。

对于同一个圆来说，如果半径和角度都确定，显然当 $ON,KN$ 相等的时候也就是对称的时候面积取到最值。这种情况下，也就是面积的上界是

$$\begin{aligned} S(\theta) &= \frac{2\theta r^2}{2} + 2\frac{r^2 \sin(\pi - \theta)}{2}\\ &= \theta r^2 + r^2\sin(\theta)\\ \end{aligned}$$

我们对这个东西求个导，发现是

$$S'(\theta) = r^2 + r^2\cos(\theta)$$

这个东西在 $0 < \theta < \pi$ 的时候是单减的。

考虑两个圆，如果对于一种分配角度的方式使得它们的导数不同，那么一定这样调整：

由于我们已经固定了角度的和，加入导数大的向右调整，导数小的向左调整，那么一定可以让答案变优，因为导数单减，变化率大的移动过程中带来的变化一定更多。

所以最优秀的方案一定是所有圆的函数的导数相等。

同时，我们可以说明如果所有圆的函数导数相等，那么取到的情况一定是上面说的对称的情况。

考虑之前那个图，用余弦定理算一下对称情况下公共弦的大小：

$$x = \sqrt{2r^2 - 2r^2\cos{(\pi - \theta)}} = \sqrt{2(r^2 + \cos(\theta))}$$

发现这个东西就是 $\sqrt{2S’(\theta)}$ ，所以导数相等的时候，安排角度后正好可以让所有弦相等，取到的是上界。

由于这个导函数有单调性，我们二分一下导数，然后看看角度和是否为 $2\pi$ 即可。

CF1425E

一开始不知道一个键可以被改变多次于是就被毒瘤到了。。

我们考虑如果有两次操作，第一次把全局费用最小的点 $u$ 连向开头，第二次把指向 $u$ 的指向 $u$ 的下一个，然后就可以得到获得 $A_1 \dots A_{n-1}$ 之一的情况下的全局的最优解。

然后如果超过了两次操作，除开最后两次之外我们可以随便把 $u$ 指向的位置变。然后一样可以得到全局最优解。

但是还有一种情况，如果之前所有激发的费用都比总收益大，我们也可能选择直接开 $n$ 这个位置。开始就是因为这个地方错了。

再多说一下，会发现如果不能重复操作，场上推了一下发现超过 $3$ 次一样是一定可以构造出来的，只有正好 $3$ 次操作会很毒瘤，这种情况最后感觉不太有救。

现在就只有一次操作的情况了，一次操作大概有这么些情况：

• 用了两个激发

  那么一定可以通过一次操作构造出权值的和减去最便宜的两个开关。

  构造方法就是，假装最便宜的两个开关是 $i,j$ 且满足 $i < j$ ，那么我们从 $j-1$ 向 $1$ 连边形成环，于是就可以通过 $D_i + D_j$ 获得所有的 $A_i$

• 只用一个激发

  • 抛弃 $A_n$

    不难发现最优决策一定是在前面找最便宜的开关，获得 $\sum_{i < n} A_i$ 。因为我们不可能通过 $D_n$ 来达成抛弃 $A_n$ ，所以这样花费和收益都最优化了。

  • 不抛弃 $A_n$

    只能连一次，所以肯定是选择一个段后缀，但是不一定可以拿到这段后缀。

    • 如果最后我们不是选择 $D_1$ ，那么一定可以拿完 $\sum_{i \ge k} A_i$ ，因为可以直接把 $E_1$ 连向 $3$ 。

    • 如果我们最后选择的是 $D_1$ ，那么必然是抛弃中间最小的 $A_k$ 。

于是所有情况就讨论完了，直接从中取最大值即可。

One Way Streets

考虑一个边双，一个结论是边双一定可以通过定向变成一个强连通。那么感性理解一下可以发现，给所有遍反向后仍然是一个强连通。所以在边双内的边答案肯定都是 $\text B$ 。

我们缩一下边双，现在就只有一个树了。

然后现在就是一个显然的树上差分了。因为保证有解，我们对每个点分别维护 up,dw 两个 tag 表示这个点的父边，是应该向上还是向下，对于一条路径 $u,v$ 就给 up[u],dw[v] 分别 $+1$ ，再给 LCA 的两个 tag 分别减少 $1$ 即可。复杂度是 LCA 的 $O(n\log n)$ ，最后做一次树上差分即可。

其实还有一种更加好写的做法。由于一定有解，我们可以定向一次后把路上的边都缩起来。用一个树上并查集找到第一个未被定向的祖先边，然后缩起来即可。跳的过程就类似树剖。复杂度就成了 $O(n\alpha(n))$ 。

Gym101620I Intrinsic Interval

刚刚看到这个题还以为是析合树之类的神仙操作（）

实际上没有必要。考虑一个性质，如果一个区间右边有两个位置 $i,j,i < j$ 使得从 $i,j$ 向左存在某一个连续段都可以包含当前询问的连续段，那么最优连续段的右端点一定不会在 $j$ 取到。因为假设右端点在 $j$ 取到，那么这个段一定可以和 $i$ 向左包含它的段取交。而连续段的交一定是连续段，所以可以得到一个更优的解。

我们考虑枚举一下前面说的 $i$ 这个位置。考虑当前仍然没有被解决掉的区间，我们把这些区间的 $l$ 放进一个优先队列里面。现在的问题就是以这个位置作为右端点，最靠左的点 $L$ 使得 $[L,i]$ 是一个连续段。

这个东西的维护基本上和 CF526F 等价。相当于是找到一个最靠左的 $L$ 使得 $R - L = \max - \min$ 。我们拿一个线段树去维护 $\max - \min - R + L$ 的值，然后用一个单调栈考虑右端点右移动时的 $\max , \min$ 的改变，具体来说，弹出单调栈相当于是给一段区间的 $\max / \min$ 增加或者减少一个值，对应到线段树上的区间加。然后 $R$ 还会加一，也是一个线段树上的区间加。不难发现当这个东西取到 $0$ 就是这个东西的下界了。所以当前要找最靠左的 $L$ 本质上就是找线段树上取到某个最小值的最靠左的位置。这个可以直接在线段树上二分解决。

现在我们可以对于右端点找到 $L$ 了，也就可以确定每个询问的答案的右端点是啥，但是怎么确定左端点？这个问题就是线段树上小于某个数的最大值。有一种很暴力做法是，把所有 $[1,l-1]$ 的数对应的线段树上的 $O(\log n)$ 段区间拿出来，然后找到最靠右的区间使得这个区间的最小值取到了下界，然后再在这个区间中二分出最靠右的下界位置。

虽然很暴力，但是复杂度还是 $O(n\log n)$ 。

Flights

代码还没写，这个题确实感觉非常难写。但是大概胡一下做法还是可以的。

首先显然的一点是，我们可以把询问拆成坐标区间内的极值点的最大值，以及 $l,r$ 上分别最大值。第一种可以看成是二维矩形内的最大值，为了好写可以 KD-Tree 解决。

对于第二种，我们建立一个线段树，维护出一个二次函数区间之内的所有二次函数在坐标上最上方的轮廓线，也就是维护出轮廓线的很多交点的位置以及是什么二次函数。

然后现在问题就是怎么合并。大概就是把两边的关键点都拖出来，然后用力扫过去。实现看起来有非常多的细节，如果以后要写可以参考一下 Claris 的代码。

链接

[APIO2013]道路费用

考虑如果只有一条路径可以收钱，那么我们一定会选择这个路径，并且把最小生成树上这个路径两端之间的最大值给丢掉让这个来做这个最大值。这样的构造显然最优。

否则，我们可以 $2^k$ 枚举一下哪些边我们钦定放进最小生成树中。如果不关心复杂度，我们可以把剩下的边依次加入，类似最小生成树来合并。如果加入的边的两端已经连通，那么就把这条路径上的所有可以收钱的边的花费和这个边取 $\min$ 。这样得到的树是就是钦定这些边在树里面的最小生成树的形态了。由于每个边的权值不同，所以这个树的形态是唯一的。在这个树上面 $\text{dfs}$ 即可。但是这样做复杂度是 $O(2^k n)$ ，无法接受。

但是考虑有很多点之间，在最后的树中一定可以通过非收钱边互相到达，如果我们可以把这种点缩起来，看起来点数就是 $O(k)$ 的了。所以我们在预处理的时候，钦定把 $k$ 条边全部加入，并且求出一个最小生成树，然后考虑把这 $k$ 条边断掉后的连通块看作一个点。

然后考虑枚举最小生成树外的边并且取 $\min$ 这个操作。显然是不能真枚举最小生成树外的所有边的。类似开始的想法，会发现真正可能有贡献的边也不多。具体来说，考虑之前钦定后求出的生成树断掉 $k$ 条边的情况下的森林。我们往这里面继续加非树边，每次加入后就一样连起来，直到加入 $O(k)$ 条边并且形成了整个联通块为止。会发现，最后可能产生贡献的也只能是这 $O(k)$ 条边。

最后，每条边产生贡献的时候，直接在这个 $k$ 个点的树上暴力跳并且打标记即可。也可以标记好后进行树上差分，再拿个 set 之类的东西维护一下这个差分，但是这个东西看着就还不如直接暴力，毕竟 $k$ 才 $20$。

于是复杂度就变成了 $O(m\log m + 2^k k^2)$ 。后面的 $k$ 显然是跑不满的。

[APIO2014]序列分割

非常经典斜优板子题，就不写题解了。这代码还是去年 $11$ 月写的。

ARC108F

早知道应该细想 F 的。。做过那个题本来很有可能想出来 F 的。

这个题类似于之前做过的 CF 题，一个结论是，最后，黑点间的直径还是白点间的直径都一定有一个端点在原树的直径上。

首先，如果两个直径端点的颜色都相同了，显然答案就是直径。直接给答案加上 $2^{n-1} len$ 即可。

我们下面之考虑直径两端颜色不同的情况，然后考虑统计答案 $\le x$ 的方案数。本质上就是距离直径两个端点距离 $\ge x$ 的点的颜色固定了，其他颜色随意放的方案数。当然，距离两个直径端点 $\ge x$ 的点有重叠，那么显然方案数量是 $0$ 。具体的维护方法就是考虑枚举一下这个上限 $x$ ，然后每次标记距离两个直径端点分别是 $x$ 的点，然后标记它们即可。

然后再给这么算出来的方案数量乘上 $2$ 即可，也就是直径端点交换颜色的情况。

复杂度 $O(n)$ 。

T1 反转了

写一种不太会证明的 zjk 做法。

考虑确定一个起点，把起点放入集合内部。我们时时刻刻保证集合内向集合外只有出边，只要这样集合本身就和外面不在一个强连通内。

然后考虑枚举一个个反转边。如果反转边在集合内，显然不会导致任何问题。如果反转边在集合外，那么也不会导致任何问题。

如果反转的边沟通了集合内外，那么我们就去扩张集合，把集合外的点加入集合并且把这个点连出去的向集合外的边都确定成当前朝外的。

如果可以一直这么做下去，到结束的时候集合没有扩展到 $n$ ，那么得到了一个解。否则我们换一个起点继续做。

场后一个牛逼老哥大概证明了一个上界是 $2n - 4$ 。所以就做完了。前面说的东西暴力维护即可，复杂度 $O(n^3)$ 。

T2 公共子段

考虑一个位置左右 $\gcd$ 改变的位置只有 $O(\log n)$ 个，所以我们可以暴力找出这左右的 $O(\log n)$ 个位置。可以用一个 ST表 预处理好，这样查询区间 $\gcd$ 是 $O(1)$ 的，找位置的时候倍增跳即可。这部分复杂度 $O(n\log^2 n)$。

然后考虑维护出每段前缀的答案和每段后缀的答案。因为往一个位置放东西是不影响 $pre[i-1],suf[i+1]$ 的。这个预处理可以用一个差分来解决，当 $i$ 作为左端点，设这个点作为右边最靠右的 $\gcd$ 不为 $1$ 的右端点为 $to_i$，显然会对所有 $[i,to_i]$ 的位置的前缀答案造成贡献，差分后算一下即可。

然后考虑把这个位置放进去之后跨过这个点的区间造成的贡献。我们考虑它一定会沟通一段左边的后缀和一段右边的前缀，让这些东西加上这个后得到的整个区间的 $\gcd$ 不为 $1$ 。这种东西的贡献是 $(R-i+1)(i-L+1)$，还需要考虑的是这个点本身和左边的一段后缀得到的区间，以及这个点本身和右边的一段前缀得到的区间，如果 $\gcd$ 不是 $1$ 也需要被算入。

我们考虑双指针扫这样的 $L,R$ 。因为如果 $L$ 固定的情况下，$R$ 向右移动的时候只会使得两边 $\gcd$ 的 $\text{lcm}$ 变小，所以只要满足 $\gcd [L,R] \neq 1$ 就一定会移动 $R$ 。

然后在放数的时候还需要判断一下，有可能你想要沟通 $[L,R]$ 的同时把这个数和前面的整个后缀，后面的整个前缀一起做 $\text{lcm}$ 超过了 $5 \times 10^5$ ，但是如果只去取前面的一段后缀和后面的一段前缀，就不会爆掉 $5 \times 10^5$ 了，这种情况需要特判一下。

还需要特判不进行任何沟通，只考虑这个东西和左边或者只考虑这个东西和右边的情况。

注意，在最开始的时候就需要把所有数变成 $\text{square free}$ 的，因为可能实际上放的并不是本身数的 $\text{lcm}$ 而是某些因子的 $\text{lcm}$ ，比如 $3^{10}\ x\ 2^{10}$。

然后我开始代码有两个情况都没判，但是跑过了所有 pretest，结果第二天被更新的构造数据叉了，才发现了这两种特殊情况。

T3 升升降降

感觉这个套路比较常见的，可惜场上没想到。

我们考虑对于一系列的操作，考虑一个函数 $f(x)$ 表示开始是 $x$ ，在进行玩这些操作后得到的数是啥。发现这个函数一定是前面一段是平的，中间一段斜率为 $1$ ，后面一段又是平的。

因为考虑 + 操作，本质上就是一个

$$f(x) = \begin{cases} x+1& x \le m-1\\m & x = m \end{cases}$$

发现对于一个函数，如果它满足之前的性质，复合上一个 $f$ 后，就是往上移动了一位，再把结尾某一段削平，所以仍然满足前面那个性质。

同理， - 操作一样。

然后考虑这个题本身，我们从大到小枚举一下阈值，显然有效的阈值只有 $O(n)$ 种，然后就是往线段树里面加入 + 或者 - 操作，同时考虑当前线段树的根节点的函数是否有值为 $v$ 的。这个很好判断。

最后再说下怎么 pushup 这个东西。现在我们知道左右两个函数的 $L,R,l$ 表示这个函数的值域以及最前面平的是 $[0,l]$ 。如果想要 $O(1)$ pushup 可以按照 zjk 说的分类讨论六种情况。但是一种好写的做法是直接二分这个平的的结束位置。因为最后的函数的下界是很好的到的（两边的函数都不减），所以可以 check 就直接查一下函数的值是否是下界。

复杂度 $O(n\log^2 n)$ ，可以通过分类讨论做到 $O(n\log n)$。

T4 数排列

我们把所有限制都拿来容斥。

考虑建 $2n$ 个点，$i$ 表示 $C_i = A_i$ 这个限制， $i+n$ 表示 $C_i = B_{i}$ 这个限制。我们在 $i,i+n$ 之间连一条边，表示 $C_i$ 不可能同时等于 $A_i,B_i$ 这两个数，再在 $posA[B_i]$ 和 $i+n$ 之间连一条边，表示不可能有两个 $C_i$ 同时等于 $B_i$ 。

那么现在，我们的到的是一个 $2n$ 个点 $2n$ 个边的图，同时每个点的度数必然是 $2$ ，我们要算钦定 $k$ 个点的，且点之间不能相邻的方案数量。容斥系数是 $(-1)^k$ 。还得乘上 $(n-k)!$ ，因为剩下的点随意分配。

一种简单的想法是考虑 $dp$ ，设 $dp[x][0/1][0/1]$ 表示当前位置已经钦定了 $x$ 个数，上一个数是否被钦定，以及当前环的开头是否被钦定。考虑每个环单独转移即可。复杂度 $O(n^2)$ 。

当然，有这么 一篇文章 中提到了这么个问题。链的情况是个广为人知的插板，而这里写到了连的情况也有式子：

$$\frac{n}{n-k} \binom{n-k}{k}$$

然后答案显然就是不同环分治 $\text{FFT}$ 一下。复杂度就优化到了 $O(n\log n)$ 。

Dissertation

我们考虑设 $dp[i]$ 表示在第二个串中考虑到当前位置，到现在 $\text{LCS}$ 长度是 $i$ ，第一个串中能取到的最小位置。

然后转移就是考虑把当前这个字符 $t_i$ 给加入进去，就是拿子序列自动机跳到 $nxt[dp[j]][t_i]$ 。所以就是：

$$dp[j + 1] = \min\{dp[j + 1] , nxt[dp[j]][c]\}$$

转移即可。复杂度是子序列自动机 + $dp$ ，也就是 $O(T(26n + m^2))$。

ABC160F

考虑式子是啥。考虑当前在点 $u$ ，我们先递归算好所有儿子的选点的方案，然后就每个儿子子树内的点就可以看作是同一个颜色了，然后就相当于做一个可重排列，也就是

$$dp[u] = \frac{(siz[u]-1)!}{\prod (siz[v])!} \prod dp_v$$

这个东西，因为根 $u$ 一定最先被选，所以不放进排列里面。

现在我们对确定的根算出了答案，对其他点作为根就是做一次换根 $dp$ 。因为只设计了 $siz$ ，这个换根很显然，推一波式子即可。

总复杂度 $O(n)$ 。

APIO 2018 New Home 新家

考虑按照年份枚举一下，相当于在 $l_i$ 加入 $i$ ，在 $r_i + 1$ 删除 $i$ 。然后询问就是二分一下答案，考虑 $[a-m,a+m]$ 是否存在所有类型的商店，也就是是否存在某个 $(a+m,\infin)$ 的数的 $pre$ 小于 $a-m$ ，是否存在某个 $(-\infin ,a-m)$ 的数的 $nxt$ 大于 $a+m$ 。

怎么维护呢？首先最显然的方式是直接上平衡树，虽然复杂度也是 $O(n\log^2 n)$ 但是 cjz 说这东西跑的还没我开始写的三个 $\log$ 快。

于是这个东西的维护可以考虑线段树。一个非常显然的维护方式是在每个位置开一个 set ，然后我们直接暴力修改，查询就是在 $\log$ 个 set 上找最小值。复杂度 $O(n\log^3 n)$，不太行。

一个很优秀的操作是，考虑在叶子结点开一个 set ，因为我们查询的只有区间最小值，所以线段树上的节点只需要维护最小值即可，没有必要都放一个 set 上去。

这个东西大概也可以通过线段树上二分做到一个 $\log$ ，但是感觉没有这个做法好写，直观。

CSacademy Light Count

考虑每 $64$ 个 01 串放到一个 ull 里面，这样直接开内存是 $6\text M$ 左右，然后块间用 BIT 维护，这样内存是 $3\text M$ ，因为每个位置只需要一个 int 。时间复杂度可以是 $O(q(64 + \log n))$ 或者通过__builtin_popcount 做到 $O(q\log n)$ 。

开始还以为题目中写最好空间不超过 $8\text M$ 被卡掉，后来发现直接就跑过去了，没有必要把块分大增加码量。

T1 节点

这是类似 AGC006F 的一个套路，可以考虑边的贡献，因为最后整个树点数就是边数加一，所以我们可以算所有情况下边数的和，再加上 $2^n - 1$ 即可算出整个树的点的数量。

我们考虑拆成每个边来算，每个边的贡献次数就是 $(2^{siz[u]} - 1)(2^{n-siz[u]}-1)$ 这个东西，因为除非两边任意一边一个点都不选择的情况都一定会选择这条边。

然后还需要减去树中的黑点的数量，也就是减去 $\sum_{i} \binom{n} i i$ ，表示对于任意选择 $i$ 个黑点的方案都需要除去 $i$ 个黑点。

答案就是

$$\sum_{u} (2^{s_u} - 1)(2^{n-s_u} - 1) + 2^n - 1 - \sum_{i=1}^n \binom n i i$$

复杂度 $O(n)$。

T2 繁殖

考虑一个细菌会分裂出的，也就是会从集合里丢掉的，一定是能够分裂出的最大的细菌。因为如果分裂出的细菌没不如最大的大，如果这回合不想分裂出最大的细菌，那么可以先分裂出最大的，下回合再用这个去分裂出次大的，或者由其他的在这回合去分裂最大的，但是如果其他的都可以分裂最大的，就一定可以分裂次大的了。所以每个细菌一定会贪心分裂自己能分裂的最大的。

其次，同一天内细菌分裂的顺序是无关的。因为大的先分裂还是小的先分裂，如果两个细菌都拥有能分裂的，画一下会发现无论顺序如何都会分裂好。

所以我们可以拿一个队列维护当前的细菌以及这些细菌是哪一天出生的，再拿一个 set 维护当前还身下的待分裂的细菌，我们每次拿队首在这些细菌中贪心分裂即可。

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

T3 异或

如果我们把 $a$ 复制一份放到后面，本质上就是一个比较奇特的匹配问题，就是问 $b$ 在 $xor$ 上一个值后在 $a$ 中匹配的位置。

可以发现，直接给 $a,b$ 分别做一次异或差分，再把第一个位置抛掉之后，就是一个直接的匹配问题了，因为可以在全局进行异或，所以第一个位置可以任意改变，可以认为是一定能匹配上的。

然后直接做一次 KMP 即可，复杂度 $O(n)$ 。

T4 涂色

考虑没有修改的时候答案是啥。不难发现这东西就是 NOIP2019 D1T1 。也就是先差分一下，然后操作就是一个位置减 $1$ 一个位置加 $1$ 。然后答案就是差分后正的差分的和。

如果可以修改呢？这题中修改本质上就是给 $d_i = d_i - x , d_{i+1} = d_{i+1} + x$ 。不难发现最优决策一定是通过这个操作把某一段的差分给均分，因为让一段变成全正或者全负一定优于一些正一些负。观察一下会发现这个操作需要的步骤一定正好是段长。

于是直接 $dp[i][j]$ 表示当前在 $i$ ，我们用了 $j$ 次操作。然后枚举一个操作次数，表示把 $[i-t,i]$ 全部均分，于是方程大概就是：

$$dp[i][j] = \min_t\{dp[i-t-1][j-t] + \max\{(A_i - A_{i-t-t}),0\}\}$$

复杂度 $O(n^3)$ 。

T5 划分

我们按位来考虑。如果有奇数个数在这个位有值，那么划分成两部分后一定是一部分在这位有 $1$ 一部分没有。所以最后两个集合的和这一位的贡献一定正好是 $1$ 。

所以现在我们可以直接把奇数 $1$ 的位全部删掉了，这些位对分配没有影响。于是剩下的位都有偶数个 $1$ ，所以总的异或和是 $0$ ，也就是说如果我们选择了一个集合，它们异或后是 $x$ ，那么剩下的集合异或也是 $x$ ，贡献一定是 $2x$ 。

于是问题就变成了，给你一个集合，从中选择一些数使得异或和尽量大。线形基即可，复杂度 $O(n \log v)$ 。

T6 纸牌

考虑如何 check 一个答案在 $k$ 的时候是否合法。我们给所有数和这个答案取最小值，然后判一下总和和最小值的 $k$ 倍的大小关系。如果总和大于等于 $k$ 倍答案，那么一定有解。证明大概可以考虑归纳，类似之前 AUOJ 的花束一题。

然后我们可以枚举一下 $k$ ，再维护一个答案。答案最大是 $n$ ，如果当前答案不合法，我们就直接给答案减 $1$ 并且继续判断。维护一个指针可以做到 $O(1)$ 判答案。因为最后答案肯定递减，所以这么做是对的。

总复杂度是排序的 $O(n\log n)$ ，用基数排序可以做到 $O(n)$ 。

ARC048D

从 $u$ 未经历关键点向上跳 $2^k$ 步，且在非 $u,u+2^k-1$ 的位置中经过一个关键点的最优代价 $G[u][k]$ ，从 $u+2^k$ 跳到 $u$ ，经过一个关键点代价设成 $G’$ ，那么：

$$G[u][k] = \min\{G[u][k-1] + 2^{k-1},2^{k} + G[g[u][k-1]][k-1]\}\\ G'[u][k] = \min\{G'[u][k-1] + 2^{k},2^{k-1} + G‘[g[u][k-1]][k-1]\}$$

算答案的时候，先考虑一个 $u$ 跳到深度相同的位置的贡献，维护出到现在为止 $u$ 没有经过关键点，经过了关键点分别的最优代价。然后分别向上跳，考虑每步是否经过关键点即可。

但是没有考虑如果跑到 LCA 外面去逛一圈怎么办，$dp$ 算出距离每个点最近的关键点即可。特判一下从 LCA 走到最近的关键点再走回 LCA 是否优。

还有一点点特殊情况，详细讨论参考代码。

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

ARC043C

可能和正解有点区别的构造方法。

考虑两个排列 $A,B$ 的距离，设 $pa[A[i]] = i,pb[B[i]] = i$ 可以写成

$$\sum_{i,j} [pa[i] < pa[j],pb[i] > pb[j]]$$

如果我们枚举一下 $pa[i]$ ，那么就是

$$\sum_{i<j} [pb[A[i]] > pb[A[j]]]$$

也就是 $S[i] = pb[A[i]]$ 这个序列的逆序对的个数。

所以我们考虑 $A,C$ 和 $B,C$ 的距离，就是 $pa[C[i]],pb[C[i]]$ 分别的逆序对数。

我们可以把 $C$ 拆成 $B^{-1} \cdot C’$ ，然后现在就变成了 $pa[pb[i]]$ 和 $\{1\dots n\}$ 两个东西复合上一个置换，使得两个序列逆序对个数相等，也就是转化成了给定一个排列 $A$ ，求一个排列 $C$ 使得 $C,A \cdot C$ 的逆序对个数相等。

我们考虑把数写成两行，分别是 $A$ 和 $1 \dots n$ ，然后每次我们同时交换上下的两个数到其他位置。当前下面逆序对个数是 $0$ ，上面是原本的逆序对个数。每次交换，我们要么使上下逆序对个数同时增加或减少 $1$ ，要么使上面减少 $1$ 下面增加 $1$ ，差距减少 $2$ 。

会发现，如果原本逆序对的数量是偶数，那么一定可以构造出上下逆序对数量相同。具体来说，我们每次把上面的 $1$ 向左移动，每次移动都会导致逆序对个数的差距减少 $2$ ，然后再移动 $2$ ，放到 $1$ 的右边，这样每次操作必然导致逆序对个数减少 $2$ ，一直操作下去一定可以取到一个让两边逆序对个数相同的状态。

ARC045D

考虑给 $x,y$ 分别建点。然后有一个结论：如果所有连通块内边数量是偶数，那么一定有解，且是充要的。

显然，如果有联通块内边数量是奇数，那么这个连通块肯定匹配不上，而联通块互相独立，所以必要性显然。

充分性证明大概可以分类讨论，考虑联通块的随意一个生成树，深度最深的点，深度相同就找度数最大的，

• 如果这个点连出两个非树边，不影响联通性。
• 如果这个点只连出了一个非树边，直接删掉这个边和他的父亲边，显然不会影响联通性。
• 如果这个点没连出非树边，那么考虑它父亲的另一个儿子，这个儿子显然不会连出去非树边，删掉这两个边即可。
• 如果这个点没连出非树边，并且他的父亲没有其他儿子，那么直接删掉这个点，这个点的父亲，以及这个点的父亲到父亲的父亲的边。因为随时边数都是偶数，所以显然找得到。

于是发现可以归纳下去就证完了。

做法的话，显然的做法是分治一下，类似删除一个物品的背包。

同时，也可以缩边双来做，然后删边讨论一下树边还是边双内的边即可。

最后关于某个神仙实现，考虑不缩边双了，把边转点放到图里面，然后直接靠 dfs 树来做。维护一个 $d$ 类似 tarjan 表示能够走到的最浅深度，然后通过这个判断每个边转出来的点是不是割点以及它子树内外是否有奇数个点的情况，然后大概就可以判了。

AGC020D Min Max Repetition

我们先考虑把最后的最大连续段长算出来，发现就是 $\lfloor \frac{\max(a,b)}{\min(a,b) + 1}\rfloor$ 。

手玩一下发现，最后最优的决策一定是前面一些 AAA...AAB 中间有一个 A...AB...B ，后面全是 ABBB... 这种样子的。如果我们能算出最后的形态，也就是算出前面有 $p$ 段 AAA...AAB ，中间有 $x$ 个 A 和 $y$ 个 B ，那么我们就能确定每个位置是什么字母。

现在问题就是如何计算字典序最小的情况下的 $p,x,y$ 。不难发现，肯定是会最大化 $p$ 。所以我们二分一下 $p$ ，在 $p$ 确定的情况下，由于 $y < k$ ，我们就可以确定出后面的段数肯定是 $\lfloor \frac{b-p}{k} \rfloor$ ，然后就可以算出一个 $x$ 。如果 $x > k$ 显然我们可以再放一些到前面去。于是就可以二分了。

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

URAL1552 Brainfuck

考虑直接 $dp$ ，设 $dp[i][a][b][c][d][t]$ 表示当前在原字符串的第 $i$ 个字符，当前四个位置分别是 $a,b,c,d$ ，当前在第 $t$ 个位置。转移显然。

但是发现空间会被卡，因为如果要输出方案不可以滚动数组。但是发现当前在的位置里面的字符必然是当前 $A_i$ ，所以可以删掉一维度状态，然后就只剩下三维，表示除开当前位置之外的位置的状态了。空间可以通过。

输出方案就再记录一个 $pre$ 即可。

可能也可以用其他的方法卡空间，比如之前学到的时间换空间，但是感觉肯定没直接卡好写。