2019 icpc南昌邀请赛 G Winner (思维)

题目链接: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

        

如有不清楚,欢迎评论区留言,会更新的。

 

2019 icpc南昌邀请赛 G Winner (思维)

上一篇:Python学习笔记<二>:列表、元组、字典


下一篇:Saltstack系列3:Saltstack常用模块及API