AGC 011 题解
AB 水题= =
C
C 比 D 难诶 /kk
特——别好的题!二分图真香
C=V−E+F 学呆了,用不到就有点难受= = ?
原图中的独立点是最好搞的,设独立点个数为 p,则贡献为 np∗2−p2
考虑题目条件:(a,b) 到 (c,d) 有边当且仅当 a−>c,b−>d,等价于 a、b 同时移动了一步到达 c、d。因此推得状态 (a,b) 能到达状态 (c,d) ,显然当且仅当路径 a−>c 和 b−>d 的奇偶性相同。由此联想到二分图。
考虑“特征点”(x,y) 即无法在新图连通块内到达 (t,k) 使得 t<x 或到达 (x,z) 使得 z<y。可以理解为字典序最小。显然特征点个数就是连通块个数。
我们发现,特征点第一维 x 必须是原图连通块中最小的点。第二维 y 可以是最小的点。但如果 y 所在连通块是二分图,且和所在连通块里的最小点 z 不在同一边,就无法变成 z( (x,y)−>(x,z),x−>x 的奇偶性可以看作偶,那么 y−>z 的奇偶性如果是奇就不行)。
D
找规律发现滚一次球后串变为取反后左移一位,末尾补位A。大致原因就是
- A-> B 变成 A A->
- A-> A 变成 B A->
- 开头和结尾也符合规律
发现 2n 步(不是 n 步,因为串的奇偶性有影响)必然会把初始的串给替换掉(可以理解为一位一位溢出了,其中有至多 n 步是第一位为 A 的要弹回),串就变成了 ABABAB… 或者 BABABA… 的形式,讨论一下奇偶性就好了
E
咕咕
F
咕咕