382
技术社区[云栖]
cf 153.div2 D. Playing with Permutations
比赛的时候一直没看懂题，后来看了下，其实很简单，就是给你一个变换序列q ，有两种变换1和2，1就是令Pi=Pqi，2则相反，互为逆变换，所以只要单独求出每种变换要多少少次，即可判断出来能否成功变换。
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#define INF 1E9
using namespace std;
int q[100];
string aim="";
char p[105];
int i,n;
string c1(string s)
{
for(i=0;i<n;i++)
p[i]=s[q[i]];
return p;
}
string c2(string s)
{
for(i=0;i<n;i++)
p[q[i]]=s[i];
return p;
}
string now="",nn;
int k1,k2;
int main()
{
int k,t,lvl;
scanf("%d%d",&n,&k);
for(i=0;i<n;i++)
{
scanf("%d",&q[i]);
q[i]--;
}
for(i=0;i<n;i++)
{
scanf("%d",&t);
aim.push_back(t);
now.push_back(i+1);
}
nn=now;
for(k1=0;k1<=k&&now!=aim;now=c1(now),k1++);
for(k2=0;k2<=k&&nn!=aim;nn=c2(nn),k2++);
if((k-k2)%2&&(k-k1)%2||(k>1&&k1==1&&k2==1)||!k1)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
最后更新：2017-04-02 00:06:51