http://codeforces.com/gym/101142/attachments

題意：每個人在TC和CF上分別有兩個排名，如果有一個人在任意一個網站上大于另一個人的排名，那么這個人可以打敗另外一個人。還有就是如果 B 能打敗 A， C 能打敗 B，但是 C 直接從排名上看 C 并不能打敗 A，但是因為 B -> A 并且 C -> B，所以 C -> B -> A， 即 C 也能（通過打敗 B 來）打敗 A。

如這個樣例： A ：5, 5 ,

　　　　　　 B ：1, 6，

　　　　　　?C：2, 2。

因為 B 的 第二個數大于 A 的第二個數，所以 B 能打敗 A， C 的第一個分數 大于 B 的第一個分數，所以 C 能打敗 B，所以就算 C 的分數都小于 A，也能打敗 A。

思路：因為這樣的關系，所以開兩個數組分別對第一個分數和第二個分數進行排序，如果 Ai-1 < Ai，那么表示 i 一定能打敗 i-1， 就對 i -> i-1 連一條有向邊，代表 i 能打敗的人有 i - 1，然后通過這條邊去找所有能打敗的人數，就可以了。從分數小的開始DFS，如果找不到比它小的就進行下一個DFS，因為分數小的可以打敗 sum 個人，那么分數大的肯定也能打敗大于等于?sum 個人。所以用一個標記記錄不要找重，每個人只需要找一次，復雜度是O（n）。

1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 using namespace std; 6 #define N 100010 7 struct node 8 { 9 int a, b, id; 10 }x[N], y[N]; 11 int xid[N], yid[N], sum, ans[N]; 12 bool vis[N]; 13 14 bool cmp1(const node &a, const node &b) 15 { 16 if(a.a == b.a) return a.b < b.b; 17 return a.a < b.a; 18 } 19 20 bool cmp2(const node &a, const node &b) 21 { 22 if(a.b == b.b) return a.a < b.a; 23 return a.b < b.b; 24 } 25 26 void dfs(int x) 27 { 28 vis[x] = true; 29 sum++; 30 int idx = xid[x], idy = yid[x]; 31 if(!vis[idx] && xid[idx] != 0) dfs(idx); 32 if(!vis[idy] && yid[idy] != 0) dfs(idy); 33 } 34 35 int main() 36 { 37 freopen("codecoder.in", "r", stdin); 38 freopen("codecoder.out", "w", stdout); 39 int n; 40 scanf("%d", &n); 41 for(int i = 1; i <= n; i++) { 42 scanf("%d%d", &x[i].a, &x[i].b); 43 x[i].id = i; 44 y[i] = x[i]; 45 } 46 memset(xid, 0, sizeof(xid)); 47 memset(yid, 0, sizeof(yid)); 48 memset(vis, 0, sizeof(vis)); 49 sum = 0; 50 sort(x + 1, x + 1 + n, cmp1); 51 sort(y + 1, y + 1 + n, cmp2); 52 for(int i = 2; i <= n; i++) { 53 if(x[i].a > x[i-1].a) xid[x[i].id] = x[i-1].id; 54 if(y[i].b > y[i-1].b) yid[y[i].id] = y[i-1].id; 55 } 56 for(int i = 1; i <= n; i++) { 57 if(!vis[x[i].id]) dfs(x[i].id); 58 if(!vis[y[i].id]) dfs(y[i].id); 59 ans[x[i].id] = sum - 1; 60 } 61 for(int i = 1; i <= n; i++) printf("%d\n", ans[i]); 62 return 0; 63 }

?

轉載于:https://www.cnblogs.com/fightfordream/p/6028964.html

總結

以上是生活随笔為你收集整理的Codeforces Gym 101142C：CodeCoder vs TopForces（搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。