前言
赛时没调出来,赛后调了一个上午,最后发现是有个地方没清零。
思路
首先对于位置 \(i\),我们必须要保证进行的操作中,最后一次出现 \(i\),\(i\) 的后面一定是 \(a_i\)。
那么我们考虑统计所有位置上的要求,用有向边链接,那么就会出现一个有环有向图(一定有环,因为点数等于边数)。
那么,自然想到缩点。
首先,如果有某个环的长度不为 \(k\)(不讨论长度为 \(1\) 的情况),那么一定无解,因为总会剩几个点没办法改,或者为了改最后几个点而导致把最开始的点改了,自己手玩一下应该很好理解。
那么还有不构成环的,也可以理解成长度为 \(1\) 的情况,我们可以先满足这些边的要求,这样可能会使得环内得答案不正确,但是我们可以最后再处理环,把之前错误的答案改正确。
所以做法就出来了,先建图,然后 tarjan 缩点,统计每个环的长度,长度要么为 \(k\),要么为 \(1\),如果存在不是 \(k\) 也不是 \(1\) 肯定无解,然后再统计长度为 \(k\) 的个数,如果没有也肯定无解,否则就是有解。
另外,还有 \(k=1\) 的特殊情况,这种情况,必须满足 \(a_i=i\),也就是它只能每次选一个值 \(l\),那必定是把 \(a_l\) 改成 \(l\),所以必须满足上述条件。
\(k\neq1\) 则必须满足 \(a_i\neq i\),因为 \(l\) 互不相同。
AC code
#include<bits/stdc++.h>
using namespace std;
int T,n,k,a[100005],e[100005],ne[100005],h[100005],num,idx=1,dcnt,siz[100005],dfn[100005],low[100005],z[100005],top,in_z[100005],ff,flag;
inline void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u)
{
dfn[u]=low[u]=++dcnt,in_z[u]=1,z[++top]=u;
for(int i=h[u];i;i=ne[i])
{
if(!dfn[e[i]]) dfs(e[i]),low[u]=min(low[u],low[e[i]]);
else if(in_z[e[i]]) low[u]=min(low[u],dfn[e[i]]);
}
if(dfn[u]==low[u])
{
++num;
while(z[top+1]!=u) in_z[z[top--]]=0,++siz[num];//因为这个写法,可能和上一次的进栈的元素相同,导致错误,所以要初始化z数组。
}
}
inline bool sol()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n+1;++i) z[i]=siz[i]=h[i]=dfn[i]=0;//因为判断是z[top+1],所以要多预处理一位
//奇怪的是,我在洛谷这么写都没错,难道是洛谷没卡这种情况?
idx=1,num=flag=dcnt=top=0;
if(k==1)
{
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) if(i!=a[i]) return 0;
return 1;
}
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) if(i==a[i]) return 0;else add(i,a[i]);
for(int i=1;i<=n;++i) if(!dfn[i]) dfs(i);
for(int i=1;i<=num;++i)
{
if(siz[i]!=1&&siz[i]!=k) return 0;
if(siz[i]==k) flag=1;
}
return flag;
}
int main()
{
scanf("%d",&T);
while(T--)
if(sol()) puts("YES");
else puts("NO");
return 0;
}
标签:CF1867D,Operations,Cyclic,int,top,100005,++,dfn,low
From: https://www.cnblogs.com/One-JuRuo/p/17695827.html