题解 P6264 【[COCI2014/2015#3]DOM】

sukimo

2020-04-08 09:25:44

Solution

这道题是一个基础的模拟题。一旦理解题目,代码就呼之欲出了。 首先,让我们仔细品味这句话:“如果有多个老人讨厌现在的频道,他们中最年轻的会站起来,把频道换成他最喜欢的,其余的人都会坐着。”这句话揭示了一个十分重要的性质:如果在所有讨厌老人$i$讨厌的频道的老人中,老人$i$不是最年轻的,那么就可以忽略老人$i$不管(听起来好没责任感的样子)。因为就算出现他不喜欢的频道,也轮不到他来换台,而是由更年轻的老人来做。 那么,我们定义两个数组$hate$和$like$(它们的意义可不相同)。$hate[i]$表示讨厌$i$频道的最年轻老人编号,而$like[i]$表示老人$i$喜欢的频道。这样就好像构成了一条链,我们由当前的频道$fir$,如何判断切换的下一个频道呢(如果要换)?那么就是$like[hate[fir]]$。这应该比较好理解。如果没有人讨厌当前这个频道,那么$hate[i]$就是$0$。如果要判断会不会一直换台,只用一个标记数组记录一下换过的频道就好了。一旦重复就说明会一直换下去。接下来的代码应该是十分清晰好懂的: ``` #include<bits/stdc++.h> using namespace std; const int MX=100005;int vis[MX],hate[MX],like[MX]; int main(){ int n,m,fir,cnt=0;scanf("%d%d%d",&n,&m,&fir); for(int i=1;i<=n;i++){int q;scanf("%d%d",&like[i],&q);if(!hate[q])hate[q]=i;} while(hate[fir]){ if(vis[hate[fir]]){cnt=-1;break;}cnt++;vis[hate[fir]]=1;fir=like[hate[fir]]; } printf("%d",cnt); return 0; } ``` 那么这篇题解就到这里,谢谢观赏!!