题目 | Cyclic Operations
Codeforces Round 897 (Div. 2)
D. Cyclic Operations
https://codeforces.com/contest/1867/problem/D
1 second / 256 megabytes
standard input / standard output
Problem
Egor has an array
Since Egor doesn't take easy paths, only the following operation can be used (possibly zero or several times):
- choose an array
of length ( , all are distinct) and change each element to ( ).
He became interested in whether it is possible to get the array
The operation
Input
The first line of the input contains an integer
Each test case consists of two lines. The first line contains two integers
The second line contains the array
It is guaranteed that the sum of
Output
For each test case, output "YES" (without quotes) if there is a way to get the array
Example
Input
6
5 3
2 3 5 3 4
4 2
2 4 3 1
1 1
1
3 1
1 2 3
5 3
5 4 3 2 1
6 1
1 2 3 1 5 6
Output
YES
NO
YES
YES
NO
NO
Note
Let's consider the first example:
- Apply the operation with
= . Now = . - Apply the operation with
= . Now = = .
We see that it is possible to get the array
题解
首先,要注意到对于一个完整的置换环,是没有任何方法增加或减少它的长度的,因此所有环长必须
例如对于
因此,首先需要找到 No
.
对于不在环中的元素,它一定在某个环的支链上,将上面的例子可视化即为:
可以看到
由于不同操作可以互相覆盖,那么不管链有多长,一定能找到一种构造方式将链构造出来。
例如对于上面的例子,如果
将链构造完后,环上数字不一定满足条件,不过只要再构造一遍环,环上的数字就会被覆盖成正确的了。
例如对于
如上图可见支链很长,已经比
将链构造完后,环上数字不一定满足条件,不过只要再构造一遍环,环上的数字就会被覆盖成正确的了。
易错点
如果到这里你没有发现一些纰漏,那么就会掉到一个坑里了,好在本题样例里面有这个坑,很容易检查出来。
这个问题就是,对于
因此,需要特判 No
.
代码
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> nxt(n + 10);
for (int i = 1; i <= n; i++)
cin >> nxt[i];
if (k == 1)
{
for (int i = 1; i <= n; i++)
{
if (nxt[i] != i)
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
return;
}
vector<int> idx(n + 10), cir(n + 10);
for (int i = 1; i <= n; i++)
{
if (idx[i])
continue;
int now = i;
idx[now] = 1;
cir[now] = i;
while (!idx[nxt[now]])
{
idx[nxt[now]] = idx[now] + 1;
cir[nxt[now]] = i;
now = nxt[now];
}
int cnt = idx[now] - idx[nxt[now]] + 1;
if (cir[nxt[now]] == i && cnt != k)
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
本文采用 CC BY-SA 4.0 许可,本文 Markdown 源码:Haotian-BiJi