最近做到的一些有意思题

### [PA 2015 Final] Edycja

首先完全图上每条边（包括自环）都会有一个权值，然后你现在要给每个字符安排一条出边。

考虑什么样的出边集合是可行的。每个连通块，如果环是自环显然可行；如果是一个基环树，可以把一个环点先拉到下面子树上去，也不要额外代价；如果是一个纯环，必须借助外面的点，多花费一个 c 的代价。如果全部是环，就爆了。

直接 dp 复杂度升天了。但是我们有一个非常规的高超手法。

我们先让每个点选择自己代价最小的边。进行一些调整。此时我们获得了一个很优秀的性质是，调整不会产生新的环，否则把它调回代价最小的那条边，不仅破了一个环，还让代价更小。因此只用状压把哪些原有的环击杀了即可（否则必定不会贡献进 dp 数组内）。

所以我们直接一手 dp。由于不需要考虑自环，复杂度 $O(2^{26/2} \cdot 26)$。

需要注意，如果调整前的图全是环，那你至少进行一次调整。但是实际上你也没必要记录 0/1（我不懂题解都怎么想的），因为在纯环情况下只要进行了一次操作就必定会破掉一个环，直接判就好了。

### [省选联考 2021 A 卷] 矩阵游戏

一直听说这一道题，终于做掉了。它比较迷惑性的一点在于那个 $[0,1e6]$ 的固定限制容易让人以为是人类智慧构造。只要你跨过这个坎，就比较简单了。

首先显然不能是消元，我们考虑把左上那两条自由元先设成 0，其它递推出来。然后想一下能对整个矩阵做哪些调整。

发现实际上是选定一行或一列，让它加上一个 1 -1 交替的东西。

所以每个格子的约束实际都只和两个调整相关。但是你会发现一部分的约束是 $x_i + y_j \in [L,R]$ 的形式，这不能差分约束，很不好。这里用一个简单 trick，把行调整($x$)的奇数列取反，列调整偶数列取反，就都是 $x_i - y_j \in [L,R]$ 形式了，直接跑 SPFA。

### P7952 [✗✓OI R1] 天动万象

诶，我是不是整出来个新做法。

这个 加儿子很牛逼啊，看着不太会做。

所以考虑下特殊情况，一条链。一条链是直接平移，没错。

那么一般树呢？考虑一个链剖分。对一个子树做时，包含那个点的“主链”可以直接平移，剩下来的非空（用并查集维护）链则暴力做。

如果我们用长链剖分，暴力做的总势能是 $O(n)$ 的，这不是对完了吗！

确实对完了。但是还要注意一点是，非主链每次做完可以 pop 最后一个，但主链不行，不然会出现对着一个主链删删删，再删它父亲发现主链没了副链反而存在的情况，就爆了。

### P10360 [PA 2024] Desant 3

这是人想的吗我请问了。

直接正着爆搜，但是你不维护具体的串，而是允许有一些位置为“还未确定”。

如果一个操作两个位置全都是确定的，直接做。

如果有一个位置是确定的，可以根据这个位置唯一得知是否需要 swap，直接做。

如果两个位置都不确定，发现有两种情况这一次操作后会直接得到相同结果，mod 2 下就没意义了。所以确定这两个位置并分两种情况做。

复杂度显然是 $O(2^{n/2} \cdot m)$。

### [POI 2021/2022 R2] kon

苦战 2h 终于战胜。还拿了个最优解。

肯定要尝试梳理这个结构。我们建出两棵树，一个是操作 1 的森林（下记 T1)，一个是操作 2 的森林（下记 T2)。

有一个性质是，一个点在两个森林内至少有一个是根。

现在考虑查询时查的是什么。

发现答案由两部分组成，一个是这个点出现时就和它有连接的点，它直到查询时在 T2 上的子树大小，另一个是这个点出现后才挂上去的它的 T1 上的儿子在 T2 上的子树大小。

那这个点出现时就有连接的点是哪些呢？发现其实是 它在 T2 上的祖先 在 T1 上的邻居 在 T2 上的子树并。这个很绕，需要理解一下。

这个还不完全对，你还需要要求这个 T1 上的祖先 的 编号比在路径上出现的下一个点小，不然这个是不会继承下去的。

邻居看上去不好维护，但是我们有刚才所说的那个性质，所以几乎所有的“邻居”都可以被改成“儿子”，除了查询点在 T2 上的根在 T1 上的父亲在 T2 上的子树大小（如果有）。

然后你维护，就是你每次加点，找到它在 T2 上的根，如果存在 T1 上的父亲，就作为儿子贡献进去，找到这个父亲在 T2 上第一个编号 > 它的儿子，那么后面的儿子的子树都可以贡献到。

别忘了那个特殊情况（T2 的根 T1 上的父亲）也是有约束的，但是这个约束是反过来的，需要手玩一下。

两个 BIT 解决，复杂度 1log。