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