题目链接：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 }
std跑出来的时间大约是一百多ms
这种方式是1000+ms
只是提供一种思路，还是应该学学tarjan
如有不清楚，欢迎评论区留言，会更新的。