思路

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

\texttt{Yes}

，否则输出

\texttt{No}

。

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

它的单位元为一个字符串为 $\texttt{A}$ 到 $\texttt{Z}$ 。
逆元是本身。
本题中的字母，置换后还是字母，满足封闭性。
没有交换律。
它的运算属于单目运算，和结合律没关系。

代码

CPP

#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;
}

题解：SP1843 LEONARDO - Leonardo Notebook

文章操作

思路

代码

相关推荐

评论

题解：SP1843 LEONARDO - Leonardo Notebook