题解：SP1843 LEONARDO - Leonardo Notebook

zhangmuning1016 · 2024-12-18 18:58:41 · 题解

思路

判断是否有解：
寻找完所有的环，判断是否是偶环，如果都是偶环，且偶环的路径数成双成对地出现，或全是奇环，就输出 \texttt{Yes}，否则输出 \texttt{No}。

我们发现这里出现了置换群。为什么出现了置换群呢？

• 它的单位元为一个字符串为 \texttt{A} 到 \texttt{Z}。

• 逆元是本身。

• 本题中的字母，置换后还是字母，满足封闭性。

• 没有交换律。

• 它的运算属于单目运算，和结合律没关系。

代码

#include<bits/stdc++.h>
using namespace std;
int v[30],t[30],T;
char B[30];
int main() {
    cin>>T;
    while(T--) {
        cin>>x;
        memset(v,0,sizeof(v));//不要忘了初始化
        memset(t,0,sizeof(t));
        for(int i=0; i<=25; ++i) {
            if(!v[i]) {
                int j=i,n=0;
                do {
                    v[j]=1;
                    j=x[j]-'A';
                    n++;
                } while(j!=i);
                t[n]++;//枚举每个循环，用桶统计循环个数
            }
        }
        int flag=1;
        for(int i=2; i<=26; i+=2) {
            if(t[i]%2==1) {
                flag=0;//循环不是偶数，不能匹配
            }
        }
        if(flag) {
            cout<<"Yes\n";
        } else {
            cout<<"No\n";
        }
    }
    return 0;
}