Cyclic Operations 题解

前言

看这道题有好多巨佬都是用 Tarjan 来做的，在这里讲一个自认为比较简单的做法，(不到 \(30\) 行)。

题意

题意比较难讲，建议自己去看一下翻译，在这里不多赘述。

思路

首先看到题目中间给的一个每一次操作的式子：\(a_{l_{i}}=l_{(i\mod k)+1}\)。仔细观察这个式子后会发现，其实每一次操作的目的其实就是将 \(a_{i}\) 变为 \((i+1)\mod k\)。再看样例的数组从 \(1,2,3\) 变成了 \(2,3,1\)，于是我们就联想到了环。所以我们可以从 \(i\) 向 \(a_{i}\) 连一条边，这样就构成了一张图，且图中有若干个环。而每一个环其实就对应着每一次操作，不在环上的点不用考虑，因为随便选一些不在环上的点和一些在环上的点一共凑齐 \(k\) 个点之后按要求进行操作就可以达到目标了。

接下来只需要考虑每一个环是否符合要求就行了。因为题目上说了每一次操作选的数的数量必须刚好是 \(k\) 个，而每一个环上的点又必须一起选，所以我们只需要判断每一个环上的点数是否刚刚好等于 \(k\) 就行了。

注意当 \(k=1\) 的情况时需要特判一下。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair <int,int> pii;
const int MAXN = 2e5 + 10;
int T,n,k,a[MAXN],num[MAXN],vis[MAXN];
bool flag;
signed main()
{
	cin >> T;
	while(T--)
	{
		flag = true;
		cin >> n >> k;
		for(int i = 1;i <= n;i++) cin >> a[i],flag &= (!(k == 1 && a[i] != i));
		for(int i = 1;i <= n;i++)
		{
			if(vis[i] == true) continue;
			int u = i,cnt = 0;
			while(vis[u] == false) vis[u] = i,num[u] = ++cnt,u = a[u];
			if(vis[u] != i) continue;
			if(cnt - num[u] + 1 != k) flag = false;
		}
		if(flag == false) puts("No");
		else puts("Yes");
		for(int i = 1;i <= n;i++) num[i] = vis[i] = 0;
	}
	return 0;
}