CodeForces 1327D - Infinite Path
Problem
排列的$k$次幂代表一次移动变为移动$k$次。
然后就是可怕的卡时间了,先找出排列中所有的环和长度,然后对每个环进行遍历的时候只考虑步长$k$整除环的长度的情况,还需要先计算出来走$k$步到达的位置。
Solution
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int n = 0, cnt = 0, len = 0;
int p[200005] = {};
int c[200005] = {};
int idx[200005] = {};
int off[200005] = {};
int nex[200005] = {};
bool vis[200005] = {};
vector<int> g[200005];
void dfs(int pos) {
if (vis[pos]) return;
vis[pos] = true;
idx[pos] = cnt;
off[pos] = len++;
g[cnt].emplace_back(pos);
dfs(p[pos]);
}
int main() {
int T = 0;
scanf("%d", &T);
while (T--) {
cnt = 0;
memset(vis, 0, sizeof(vis));
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &p[i]);
p[i] = p[i] - 1;
}
for (int i = 0; i < n; ++i) {
scanf("%d", &c[i]);
}
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
len = 0;
g[cnt].clear();
dfs(i);
++cnt;
}
}
int ans = n;
for (int i = 0; i < cnt; ++i) {
len = g[i].size();
for (int j = 1; j <= len; ++j) {
if (len % j == 0) {
for (int k = 0; k < len; ++k) {
vis[g[i][k]] = false;
nex[g[i][k]] = g[i][(k + j) % len];
}
for (int k = 0; k < len; ++k) {
if (!vis[g[i][k]]) {
bool flag = true;
int pos = nex[g[i][k]];
while (pos != g[i][k]) {
vis[pos] = true;
if (c[pos] != c[g[i][k]]) {
flag = false;
break;
}
pos = nex[pos];
}
if (flag) {
ans = min(ans, j);
break;
}
}
}
}
}
}
printf("%d\n", ans);
}
return 0;
}
<EOF>