CodeForces 520D 又见贪心

戳这里：520D

//贪心的做法比较明显：取出方格中的数从左往右排列形成一个 m 进制的数，前者想要数最大,则每次取符合条件的最大的数，后者想要数最小，则每次取符合条件的最小的数。

//做法也比较暴力：在整个剩余的数形成的集合中两人每次贪心取数，那么就相当于是对剩余的数形成的集合进行搜索，考虑到极端情况：集合里面有很多数，但是只有一个可以取，这时通过加强集合元素的条件（是剩余的数 && （之前能被取出 || 现在能被取出））来缩小集合的大小，但是在数被取出之后需要对集合进行维护（添加元素）

//之前感觉写起来挺麻烦，就一直没动手去写，没想到今天写完交上去就过了......

 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "utility"
 6 #include "set"
 7 #include "map"
 8 using namespace std;
 9 const int mod = 1e9 + 9;
10 int m;
11 int x[100010], y[100010];
12 set<int> s;
13 map<pair<int, int>, int> mp;
14 bool available(int index)
15 {
16     int X = x[index], Y = y[index];
17     pair<int, int> point = make_pair(X, Y), pre, next;
18     bool no;
19     int i, j;
20     for(i = 1, pre = make_pair(X - 1, Y + 1); i <= 3; ++i, ++pre.first) {
21         if(!mp[pre])
22             continue;
23         no = 1;
24         for(j = 1, next = make_pair(pre.first - 1, pre.second - 1); j <= 3; ++j, ++next.first) {
25             if(mp[next] && next != point) {
26                 no = 0;
27                 break;
28             }
29         }
30         if(no)
31             return 0;
32     }
33     return 1;
34 }
35 
36 void res_add(__int64 &res, int v)
37 {
38     res = (res * m) % mod;
39     res = (res + v) % mod;
40 }
41 
42 void cube_add(int index)
43 {
44     int i;
45     pair<int, int> next;
46     int tmp;
47     for(i = 1, next = make_pair(x[index] - 1, y[index] - 1); i <= 3; ++i, ++next.first) {
48         tmp = mp[next];
49         if(!tmp)
50             continue;
51         --tmp;
52         if(available(tmp)) {
53 //            printf("add_cube index == %d  next == %d
", index, tmp);
54 //            printf("%d %d
", next.first, next.second);
55             s.insert(tmp);
56         }
57 
58     }
59 }
60 
61 int main()
62 {
63     int i;
64     scanf("%d", &m);
65     for(i = 0; i <= m - 1; ++i) {
66         scanf("%d%d", &x[i], &y[i]);
67         mp[make_pair(x[i], y[i])] = i + 1;
68     }
69     for(i = 0; i <= m - 1; ++i) {
70         if(available(i)) {
71             s.insert(i);
72 //            printf("ava == %d
", i);
73         }
74     }
75     int tmp;
76     __int64 res = 0;
77     for(i = 1; i <= m; ++i) {
78         while(!s.empty()) {
79             if(i & 1)
80                 tmp = *s.rbegin();
81             else
82                 tmp = *s.begin();
83 //            printf("chi == %d
", tmp);
84             s.erase(tmp);
85             if(available(tmp)) {
86                 res_add(res, tmp);
87                 mp.erase(make_pair(x[tmp], y[tmp]));
88                 cube_add(tmp);
89                 break;
90             }
91         }
92     }
93     printf("%I64d
", res);
94 }