Codeforces 1481D AB Graph 三元环结论,构造_完全图中三元环

题意

一张完全图的每一条有向边上写着$a$或者$b$,问能否构造一条边数为$m$的不间断路线使该路线为回文串.

推论

随便找两个点,我们发现边数为奇数的回文串是必定能够构造出来的.
随便找一个三元环,假设三个点为$x,y,z$.我们发现其中必定有一个点$y$满足$x->y$和$y->z$是同一个字母,如果不是$y$就调整为$x$或者$z$,肯定有.枚举所有情况可证.
那么对于边数为偶数的回文串,必有$z,x,z,x,y,z,x,z,x(前面和后面一起加)$这条路线可以构造出任意长度边数为偶数的回文串.
唯一一种不存在答案的情况就是边数为偶数,点数为$2$的情况.
所以代码如下.

const int aoi=2038;
char c[aoi][aoi];
vector<int> zw;
 
int main() {
  for (int t=read();t--;) {
    int n,m,i,j;
    read(n),read(m);
    for (i=1;i<=n;++i) scanf("%s",c[i]+1);
    if (m&1) {
      puts("YES");
      for (i=0;i<=m;++i) printf("%d ",i%2+1);pl;
    } else {
      if (n==2) {
        puts(c[1][2]==c[2][1]?"YES":"NO");
        if (c[1][2]==c[2][1]) {
          for (i=0;i<=m;++i) printf("%d ",i%2+1);pl;
        }
      } else {
        puts("YES");
        int f=c[1][2]==c[2][3]?2:c[2][3]==c[3][1]?3:1;
        for (i=0;i<=m;++i) printf("%d ",(f+i+m-1)%3+1);pl;
      }
    }
  }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26