【11.3】【VP】Codeforces Round #726 (Div. 2)

ALL：7
AC：7
Rank：111

记念第一次 AK div.2 ，这一场后几道题做起来比较顺手，而且是比较擅长的题。

---

D. Deleting Divisors

题意：

Alice 和 Bob 正在玩游戏，他们都绝顶聪明。

开始时有一个整数 $n(1\le n\le 10^9)$，二者轮流行动，每次行动可以在当前的 $n$ 上减去其一个非 $1$ 非 $n$ 的因子。

若 Alice 先手，某一方无法进行操作则判输，谁会赢呢？

思路：赛时打表找的规律，不会证明。证明看 这里 。

AC代码：https://codeforces.com/contest/1537/submission/179029276

---

E2. Erase and Extend (Hard Version)

题意：

你有一个字符串 $s$，你可以进行两种操作。

• 删去字符串的最后一个字符。
• 将 $s$ 变为 $s+s$，$+$ 表示字符串连接，也就是复制一次字符串。

你可以随意的进行操作，也可以不进行操作。

你需要找到 $s$ 进行操作后获得的所有长度为 $k$ 的字符串中字典序最小的字符串。

$1\le n,k\le 5\cdot 10^5$

思路：策略就是，找到最长的一个后缀，去掉或者不去掉这个后缀之后，剩下的部分重复复制即可。

看题解是在前缀字典序上求解，我是在后缀字典序上求解。一个有瑕疵的思路是，先后缀排序一下，找到最长的后缀 $s[i,n]$ ，使得 $s[1,n]>s[i,n]$ ，删掉剩下 $s[1,i-1]$ 。

但是按照我们的策略，必须还要保证 $s^{\infty }[1,i-1]$ 是最小的，如果复制一份，第二份就会又影响到字典序，因此要复制一份之后跑后缀排序。

AC代码：https://codeforces.com/contest/1537/submission/179034582

---

F. Figure Fixing

题意：

你有一张 $n(2\le n\le 2\cdot 10^5)$ 点 $mn(n-1\le m\le \min (2\cdot 10^5,\frac{n\cdot (n-1)}{2}))$ 边的无向连通图，第 $i$ 个点上有点权 $v_i$ 和目标值 $t_i$。

在一次操作中，你可以选择一条边 $(i,j)$，并同时给 $v_i$ 和 $v_j$ 增加一个任意整数值，可以为负。

你需要判断，这张图是否可以在有限步操作中，使得每个节点满足 $v_i=t_i$。

思路：每个点的变化量为 $d{t}_i=t_i-v_i$ ，有解的必要条件为 $\sum dt=0$ 。

如果无奇数环，而且染色之后左部图右部图的 $\sum dt$ 相等，那么一定是有解的。否则无解。

如果有奇数环，那么一定有解，求解的策略为：在奇数环上顺次跑一边，一定可以使得某个点 $dt=dt\pm 2$ ，然后可以把这个 $-2,-1,1,2$ 其中之一转移到其他的点上。

AC代码：https://codeforces.com/contest/1537/submission/179036842