Atcoder 试题乱做 Part 4

难度标签：$\mathtt{\text{[HARD]}}$，$\mathtt{\text{[NORMAL]}}$，$\mathtt{\text{[EASY]}}$。

[AGC004F] Namori

$\mathtt{\text{[HARD]}}$

首先，根据之前 LEGOndary Grandmaster 的提示，把深度为偶数的点的颜色翻转，于是就变成了每次交换一对相邻的 $01$（这个翻转颜色的操作实际上是将不合法操作转变为不优的操作）。

那么对于树的情况，记录每条边必须要被操作多少次（一条边划分的两棵子树中，颜色个数可能不对，就一定要跨过这条边），求和就是操作次数的下界。实际上是可以达到这个下界的，每次只要找一组恰好两个端点颜色都需要到另外一边的一条边，交换，就一定可以达到下界。当然，如果整棵树颜色总数不对，就直接无解。

对于基环树，“深度”的定义可能出现问题。如果是奇环，就会出现同色点之间有边的情况。注意到这种边相当于在进行颜色翻转之后，每次可以将两端两个同色点同时反色。他也就只有这个作用了，因此在这种情况下，只要颜色总数差距是偶数，就可以通过这条边来修好。剩下的就用树的做法即可。

如果是偶环，则可以通过这条边，加速一些点的移动。具体来说，记录环上其他边都需要怎么移动，然后将多出来的边上的移动设为 $x$，最后会得到一些带绝对值的项的和，可以取所有元素的中位数来取得最小值。

时间复杂度 $\mathcal{O}(n)$。

[AGC007E] Shik and Travel

$\mathtt{\text{[NORMAL]}}$

由于每条边只能走两次，所以每次一定是走完一棵子树，然后再去别的地方。

显然可以二分，所以先二分一个 $\text{mid}$，则所有叶子到叶子的路径长度都不能超过 $\text{mid}$。每次向上合并信息的时候，一定是先走进一棵子树，然后走出来，拼上走进另外一棵子树的路径长度，再走回来。所以，$x$ 子树中一条路径可以描述为 $(x,a,b)$ 的三元组：$a$ 表示走到第一个叶子的路径长度，$b$ 表示从最后一个叶子走回当前点的路径长度（当然是在一个固定的 $a$、中间路径都不超过 $\text{mid}$ 的情况下的最小 $b$）。

每次合并就是将左儿子一个方案的 $b$ 与右儿子一个方案的 $a$ 拼起来。注意到一组方案，如果 $a<a^{\prime }$ 且 $b<b^{\prime }$ 则 $(a^{\prime },b^{\prime })$ 完全没用，于是所有方案都是 $a<a^{\prime },b>b^{\prime }$ 的，匹配的时候可以指针移动。

事实证明，只需要每次暴力合并两个儿子（先左后右、先右后左），同时把不优的方案删掉，复杂度就是 $\mathcal{O}(n\log n)$。因为注意到每次一定是先到达一个儿子中的叶子，最后从另一个儿子中的叶子出来。最优方案只会有 $2min({\text{cnt}}_{\text{ls}},{\text{cnt}}_{\text{rs}})$ 个，其中 ${\text{cnt}}_x$ 是 $x$ 中的叶子个数。

这个可以用类似 $\text{dsu on tree}$ 的复杂度证明来分析：两边的 $min$ 其实可以看作“轻儿子大小”，轻儿子大小之和是 $\mathcal{O}(n\log n)$ 级别，所以是对的。

套上二分，最后时间复杂度是 $\mathcal{O}(n\log n\log v)$。

[AGC014D] Black and White Tree

$\mathtt{\text{[EASY]}}$

使用点减边容斥即可。或者欧拉定理，反正在这题条件下是一个东西。

[AGC015C] Nuske vs Phantom Thnook

$\mathtt{\text{[NORMAL]}}$

树上博弈问题。

先手输了当且仅当每个白点边上都有一个黑点。于是，如果这棵树有完美匹配，先手就必败了——因为后手每次可以选择先手选择的点的匹配点。

其他情况下，对于一个点 $x$，如果他有两个儿子都是叶子 $a,b$，先手抢占了 $x$，那么 $a,b$ 中至少有一个是后手染不到的。于是只要有一个节点存在两个是叶子的儿子，则先手必胜。否则，注意到每次删掉一个只有一个叶子作为儿子的点之后，不影响后面的答案。这和树上求完美匹配的过程恰好一样，所以我们就说明了 先手必胜 $⟺$ 树没有完美匹配。

[AGC015D] A or...or B Problem

$\mathtt{\text{[NORMAL]}}$

蚌埠住了，这题不会做。

首先，当 $A=B$，答案显然是 $1$。

接着，我们求出 $A,B$ 最高的不同的位 $k$，设 $T=2^k$，将区间划分为 $[A,T),[T,B]$。

$[A,T)$ 明显可以构造出 $A$ 到 $T-1$ 的所有元素（只选这个数字），当然也只能构造出这些。至于 $[T,B]$，找到 $B$ 在 $T$ 之后第一个 $1$ 的位置 $p$，容易说明 $[T,T+2^{p+1}-1]$ 都可以构造出来，因为对于任意 $q\le p$，$T+2^q$ 都存在。

如果 $[A,T)$ 和 $[T,B]$ 都有，则这个数字至少是 $T+A$ 了，同时不可能超过 $2T-1$。于是 $[T,B]$ 中唯一的作用就是贡献最高位的 $1$，剩下的 $[A,T)$ 都能搞定。所以这里能构造出 $[T+A,2T)$。三个区间求并就好了。

[AGC016C] +/- Rectangle

$\mathtt{\text{[EASY]}}$

乍一看以为俺不会做，给我整自闭了。

由于每一个 $h\times w$ 都要是负的，所以容易想到，当 $h|H,w|W$ 的时候，可以将矩阵划分为不交的 $h\times w$ 的小矩形，由于他们的和都要是负数，所以整个矩形不可能是非负的，直接输出 No。

否则，相当于在划分的时候，最后行、列都会留下一些边角料。一个简单的想法是：直接将一个 $h\times w$ 的“基础矩阵”循环放置，这样就可以使得每一个这么大的矩形都满足和 $<0$ 的条件。那最后的边角料部分，我们希望这些部分的和尽量大。

我们发现，这些边角料是不会包括“基础矩阵”的右下角的（否则就是整除的情况），所以把负的只放在最左下角即可。同时，我们希望边角料中能包括的正数尽量大，但一个完整的“基础矩阵”的和也尽量大。所以，可以将负数设置为 $-{10}^9$，将其他位置的正数和设为 ${10}^9-1$，这样和是 $-1$，且正数尽量大。

同样的，如果将 ${10}^9-1$ 分散在多个位置，边角料不一定会全部包括。不过如果把这个数字放在“基础矩阵”左上角，边角料就一定会包括了。其他地方放 $0$，检查一下是否合法即可。

[AGC016D] XOR Replace

$\mathtt{\text{[NORMAL]}}$

注意到做了一次操作之后，异或和就会变成被替换的数字。所以相当于有 $n+1$ 个数字，你手上有 $1$ 个，现在每次可以交换你手上的数字，和序列中一个位置的数字，要将序列变成另外一个。

首先，显然当 $n+1$ 个数字不覆盖目标的 $n$ 个数字时无解。

接着，明显在所有 $a_i=b_i$ 的位置，我们是不可能去动的。对于 $a_i\ne b_i$，连边 $b_i\to a_i$，这样会构成若干连通块。

考虑一开始序列的异或和 $x$。如果序列中没有这个数字，那他肯定最后会被剩下。于是所有连边都和 $x$ 无关，由于我们知道一定存在一种解，所以连边后的每一个连通块都肯定是一个环。于是每次我们需要首先把 $x$ 换成环中一个元素，绕环一圈，再把 $x$ 换回手里。

如果序列中存在 $x$，那么 $x$ 这个数字就可能出现在一个连通块中，操作这个连通块的时候就不用把 $x$ 换回手里了，因为做最后一步之前手上必然还是 $x$。

因此，设 $c$ 是 $a_i\ne b_i$ 的个数，$p$ 是 $>1$ 的连通块数，$t$ 是 $x$ 是否在一个 $>1$ 的连通块中，则答案是 $c+p-t$。并查集维护就足够了。

[AGC011E] Increasing Numbers

$\mathtt{\text{[NORMAL]}}$

一个递增的数可以表示为 $9$ 个 $111\cdots 111$ 的形式，即：

$$\sum _{i=1}^9{\displaystyle \frac{{10}^{p_i+1}-1}{9}}$$

若可以用 $k$ 个递增的数拼出数字 $x$，那么：

$$x=\sum _{i=1}^{9k}{\displaystyle \frac{{10}^{p_i+1}-1}{9}}$$

$$9x+9k=\sum _{i=1}^{9k}{10}^{p_i+1}$$

只需要判断 $9x+9k$ 的数位和是否 $\le 9k$ 即可判断 $k$ 是否合法。容易发现 $k\le {\log }_{10}n$，所以直接暴力从小到大枚举 $k$，高精度维护 $9x+9k$，均摊 $\mathcal{O}(\text{Ans})$。

[AGC016E] Poor Turkeys

$\mathtt{\text{[HARD]}}$

感觉有点难得转过弯。

先考虑简化问题，如果只需要判断 $i$ 是否可能存活怎么做。考虑倒推，因为正推不容易得知后面每一个人的命运，所以很难决定当前决策，而倒推就有可能根据后面每个人的命运来决定当前决策。

倒着考虑每次操作，我们称 $i$ 是“被保护的”，因为他在之前所有操作中都不能死，要死只能死另外一个人。对于一组 $(x,i)$，我们一定会选择杀掉 $x$，因为 $i$ 在后面还有用。这样，在更之前的操作中，$x$ 就不能死，因为他要在这里死。于是我们称 $x$ 也变为“被保护的”。

这样推回去，如果存在一个 $(x,y)$ 使得他们都是“被保护的”，则 $i$ 不可能活到最后。

再考虑两个人，注意到在上面一个人的情况下，有一些元素被我们钦定为“被保护的”，他们要么是要留下的元素本身，要么是为了这个元素赴死的元素。而一个元素至多为一个人赴死，所以当两个人的“被保护的”集合不交，则两个人能同时活。bitset 即可。

[AGC017D] Game on Tree

$\mathtt{\text{[HARD]}}$

虽然是经典问题，但是本身是困难的。况且我也没见过

首先考虑根挂下去的是若干条链的情况。注意到这和 $\text{nim}$ 游戏是等价的。

可以证明一棵树的 $\text{SG}$ 值是所有子树的 $\text{SG}$ 值 $+1$ 的异或和。考虑这样证明：

对于有 $k$ 个儿子的根，我们将其复制 $k$ 份，明显他们是独立的。则现在只需要考虑根只有一个儿子的情况了。我们可以证明整棵树的 $\text{SG}$ 值就是儿子的 $\text{SG}$ 值 $+1$。

具体来说，首先如果删掉儿子的子树，则 $\text{SG}=0$，否则可以证明当前局面能到达所有子树能到达的局面 $+1$（归纳）。