首页 > 代码库 > Codeforces Gym 101142C：CodeCoder vs TopForces（搜索）

Codeforces Gym 101142C：CodeCoder vs TopForces（搜索）

2024-08-18 19:51:56   224人阅读

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 }

 

Codeforces Gym 101142C：CodeCoder vs TopForces（搜索）


联系
我们