自己的互测还tm出锅了555
自闭了。。。
题解：
朱德の战争 (war)
画一画图可以发现，最后的关系一定是两两互为合作伙伴。这样才有可能保证任意两个不同的城市合作伙伴不同。否则由于原图没有环，到后面必定会撞上。然后直接 dfs 一遍就能得到匹配关系或者判断无解。合作伙伴都确定了就很简单了。对于每个点 \(i\)，它的合作伙伴 \(u\) 的危险度肯定比它连接的其他点 \(v_i\) 的危险度小，就可以从 \(u\) 向 \(v_i\) 连边。因为有危险度的限制，我们可以直接根据限制从叶节点开始遍历，因为叶节点的合作伙伴必须是它的父节点。可以用堆维护当前入度为 \(0\) 的点中编号最小的来保证字典序最小。
时间复杂度 \(O(n\log n)\)。
朱德の串儿 (string)
个人认为这是个线性 DP 好题。
设 \(f[i][j]\) 表示当前字符匹配到了第 \(i\) 位，Jude 匹配到了第 \(j\) 位时候的最小代价。
状态转移方程如下：
\[f[i][j] =\begin{cases} f[i-1][j] & \mbox{if s[i]}\neq s[j-1] \\\min(f[i-1][j-1],f[i-1][j])+a[i] & \mbox{if }s[i]=s[j-1]\end{cases}\]
最后要求的就是 \(\min(f[n][1\sim 4])\)。
时间复杂度 \(O(n)\)。
朱德の序列 (sequence)
我们可以枚举 \(l\)，看 \(r\) 在哪里可以取到。
如何处理最大公约数呢？我们可以把 \(a_{l\dots r}\) 按 \(\gcd\) 前缀和分组，相同的分为一组，这样我们在每组内只需要找到满足 \(\text{xor}_{i=l}^r a_i=\frac{k}{\gcd}\) 即可。
所以可以将程序分为以下几个步骤：
对 \(i≥l\)，找到最大的 \(j≥i\), 使得 \(\gcd(a_{l\dots i})=\gcd(a_{l\dots i+1})=\dots =\gcd(a_{l\dots r})\)。
直接倍增预处理区间 \(\gcd\)，找的时候按倍增的方法往后跳就行了。
区间异或：预处理异或前缀和即可。
在区间内找异或相等：用 \(\text{map}\) 即可实现。
时间复杂度 \(O(n \log^2 n)\)，它的常数可能有点大。