首页 > 代码库 > POJ 3128 Leonardo's Notebook [置换群]
POJ 3128 Leonardo's Notebook [置换群]
传送门
题意：26个大写字母的置换$B$，是否存在置换$A$满足$A^2=B$
$A^2$，就是在循环中一下子走两步
容易发现，长度$n$为奇数的循环走两步还是$n$次回到原点
$n$为偶数的话是$\frac{n}{2}$次，也就是说分裂成了两个循环
综上$B$中长度为偶数的循环有奇数个就是不存在啦
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=30;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}char s[N];int a[N],cnt[N],vis[N];int main(){ freopen("in","r",stdin); int T=read(); while(T--){ scanf("%s",s+1); for(int i=1;i<=26;i++) a[i]=s[i]-‘A‘+1,vis[i]=cnt[i]=0; for(int i=1;i<=26;i++) if(!vis[i]){ int u=a[i],len=1; while(u!=i) vis[u]=1,len++,u=a[u]; cnt[len]++; } int flag=1; for(int i=2;i<=26;i+=2) if(cnt[i]&1) {flag=0;break;} if(flag) puts("Yes"); else puts("No"); }}
POJ 3128 Leonardo's Notebook [置换群]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。