题目链接:https://nanti.jisuanke.com/t/40259
(自己做的时候当作思维题做了,昨晚才发现是tarjan缩点。。。在这里分享一下思维题的思路)
题意:
每个人有3种模式能力值,两人比赛,能力值大的人获胜。询问Q个人,假设可以自己选择进行模式进行比赛,询问的这些人是否有可能夺冠?
注:是一场一场比,不是一次性分成两部分比,开始想错了想了好久。
思路:
首先,如果有个人的某种模式下能力值第一,那么这个人一定有可能夺冠。只需要无脑选择这种模式。
因此,我们设3种模式的能力排行榜为rk1,rk2,rk3。既 rk1[1] rk2[1] rk3[1]这三人一定可能夺冠。(当然,这不一定是三个人,但不影响结论)
接下来,这三人也一定有其他两项能力值。
设该人为甲, rk1 为 1 , rk2 为 a , rk3 为b。
如果存在乙,rk2 或 rk3 比 甲高,那么乙也一定能获胜。只需要让甲胜过其他所有人,乙再用比甲高的那个模式战胜甲,那么乙夺冠。
那么就从甲的rk2和rk3排行榜向上遍历,所有人都可获胜,所以全压入队列,进行下一次判断。
同理,战胜乙的也一定能夺冠,如此反复判断下去,标记人,没人只判断一次。大致时间复杂度是O(3n*多少)的复杂度,,不太高。
询问时如果被标记了就说明有一条A->B->C->```->第一名 的战胜链。没标记的话就说明无法战胜。
整体复杂度大致是三次排序3nlogn+倒排名3×n+判断3n×多少.
具体实现见代码
1 #include<iostream> 2 #include<algorithm> 3 #include<queue> 4 #include<cstdio> 5 using namespace std; 6 const int maxn = 1e5+50; 7 int rk1[maxn],rk2[maxn],rk3[maxn];//表示三个排行榜,rk[排名]=人序号 8 bool check[maxn];//检测是否曾经到过这个人 9 struct qq 10 { 11 int rk1,rk2,rk3;//三个能力的排名 12 int ne1,ne2,ne3;//能力 13 }; 14 15 qq info[maxn];//信息 16 17 bool cmp1(int a,int b){ 18 return info[a].ne1>info[b].ne1; 19 } 20 bool cmp2(int a,int b){ 21 return info[a].ne2>info[b].ne2; 22 } 23 bool cmp3(int a,int b){ 24 return info[a].ne3>info[b].ne3; 25 }//用来排名的自定义排序比较函数 26 27 int main(){ 28 int n,Q; 29 while(~scanf("%d%d",&n,&Q)){ 30 for(int i=0;i<=n;i++){ 31 rk1[i]=rk2[i]=rk3[i]=i; 32 } 33 for(int i=1;i<=n;i++){ 34 scanf("%d",&info[i].ne1); 35 } 36 for(int i=1;i<=n;i++){ 37 scanf("%d",&info[i].ne2); 38 } 39 for(int i=1;i<=n;i++){ 40 scanf("%d",&info[i].ne3); 41 } 42 43 sort(rk1+1,rk1+1+n,cmp1);//求排名 44 sort(rk2+1,rk2+n+1,cmp2); 45 sort(rk3+1,rk3+1+n,cmp3); 46 47 for(int i=1;i<=n;i++){ //倒排名,能够知道人立即求出他的排名 48 info[rk1[i]].rk1=i; 49 info[rk2[i]].rk2=i; 50 info[rk3[i]].rk3=i; 51 } 52 53 int low1=0,low2=0,low3=0;//边界,曾经处理过的最低的排名 54 queue <int> q; 55 q.push(rk1[1]);q.push(rk2[1]);q.push(rk3[1]); 56 check[rk1[1]]=1;check[rk2[1]]=1;check[rk3[1]]=1;//初始3人排名为1,压入队列 57 while(!q.empty()){ 58 int now = q.front();q.pop(); 59 int pos1,pos2,pos3;//排名:pos now:号码 用来剪枝的 60 pos1=info[now].rk1;pos2=info[now].rk2;pos3=info[now].rk3; 61 if(pos1>low1){ //如果当前人pos1比rk1历史处理最低排名还低 62 for(int i=low1+1;i<=pos1;i++){ //将没处理过的pos1~rk1的人数压入队列 63 if(check[rk1[i]]==0){ 64 q.push(rk1[i]); 65 check[rk1[i]]=1; 66 } 67 } 68 low1=pos1; //更新pos 69 } 70 if(pos2>low2){ 71 for(int i=low2+1;i<=pos2;i++){ 72 if(check[rk2[i]]==0){ 73 q.push(rk2[i]); 74 check[rk2[i]]=1; 75 } 76 } 77 low2=pos2; 78 } 79 if(pos3>low3){ 80 for(int i=low3+1;i<=pos3;i++){ 81 if(check[rk3[i]]==0){ 82 q.push(rk3[i]); 83 check[rk3[i]]=1; 84 } 85 } 86 low3=pos3; 87 } 88 } 89 int qqq; 90 for(int i=0;i<Q;i++){ //如果遍历到过,那就有战胜路径,否则没有。 91 cin>>qqq; 92 if(check[qqq])puts("YES"); 93 else puts("NO"); 94 } 95 } 96 return 0; 97 }
如有不清楚,欢迎评论区留言,会更新的。