Processing math: 100%


AGC 011 题解

AB 水题= =

C


C 比 D 难诶 /kk

看了题解

特——别好的题!二分图真香

C=VE+F 学呆了,用不到就有点难受= = ?

原图中的独立点是最好搞的,设独立点个数为 p,则贡献为 np2p2

考虑题目条件:(a,b)(c,d) 有边当且仅当 a>cb>d,等价于 ab 同时移动了一步到达 cd。因此推得状态 (a,b) 能到达状态 (c,d) ,显然当且仅当路径 a>cb>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


咕咕