题解 P6264 【[COCI2014/2015#3]DOM】
sukimo
2020-04-08 09:25:44
这道题是一个基础的模拟题。一旦理解题目,代码就呼之欲出了。
首先,让我们仔细品味这句话:“如果有多个老人讨厌现在的频道,他们中最年轻的会站起来,把频道换成他最喜欢的,其余的人都会坐着。”这句话揭示了一个十分重要的性质:如果在所有讨厌老人$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;
}
```
那么这篇题解就到这里,谢谢观赏!!