ABC296E Transition Game

ABC296E Transition Game

题目大意

有一个序列$A=(a_1,a_2,\dots ,a_n)$，$a_i(1\le i\le n)$满足$1\le a_i\le n$

小A和小T玩$n$轮游戏，第$i$轮游戏如下：

• 小A写下一个数字$k_i$
• 小T知道$k_i$的值之后，选择一个在$1$到$n$之间的数$s_i$，然后将其写在黑板上
• 重复下面操作$k_i$次
  • 用$a_x$来代替黑板上的数字$x$

如果第$i$轮经过上述操作后留在黑板上的数字为$i$，则在小T在这一轮获胜；否则小A在这一轮获胜。

假设双方都用最优策略，求小T能赢的次数。

题解

我们把每个$a_i$看作一条从$i$到$a_i$的有向边，那么这就是一个$n$个点$n$条边的有向图。小T的任务就是选择一个$s_i$，使得点$s_i$走$k_i$步之后走到点$i$的位置。

对于每个$i$，如果点$i$在环上，那么小T一定可以通过$k$的大小来选定一个$s_i$，使得从点$s_i$走$k_i$步后能走到点$i$的位置，那么小T必然获胜。但如果点$i$不在环上，那么点$i$一定在一条通往一个环的链上，而$s_i$只能在能到达点$i$的点中选，那么小A可以将$k_i$定得很大，使得没有$s_i$能在走$k_i$步的情况下到达$i$，那么小A必然获胜。

综上所述，如果$i$在环上，则第$i$轮小T获胜；否则小A获胜。

这个可以用拓扑排序来解决。将所有没有入度的放进队列，然后做拓扑排序，最后入过队列的为链上的点，否则为环上的点。

时间复杂度为$O(n)$。

code

#include<bits/stdc++.h>
using namespace std;
int n,tot=0,ans=0,a[200005],cnt[200005],to[200005];
queue<int>q;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		++cnt[a[i]];
	}
	for(int i=1;i<=n;i++){
		if(!cnt[i]){
			to[i]=1;
			q.push(i);
		}
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		--cnt[a[u]];
		to[a[u]]=max(to[a[u]],to[u]+1);
		if(!cnt[a[u]]) q.push(a[u]);
	}
	for(int i=1;i<=n;i++){
		if(cnt[i]) ++ans;
	}
	printf("%d",ans);
	return 0;
}