Codeforces Round #532 (Div. 2) Solution

A. Roman and Browser

签到.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n, k, a[110];
 5 
 6 int get(int b)
 7 {
 8     int vis[110];
 9     memset(vis, 0, sizeof vis);
10     int c = b; 
11     while (c <= n)
12     {
13         vis[c] = 1;
14         c += k;
15     }
16     c = b - k;
17     while (c >= 1)
18     {
19         vis[c] = 1;
20         c -= k;
21     }
22     int l = 0, r = 0;
23     for (int i = 1; i <= n; ++i) if (!vis[i])
24     {
25         if (a[i] == 1) ++l;
26         else ++r;
27     }
28     return abs(l - r);
29 }
30 
31 int main()
32 {
33     while (scanf("%d%d", &n, &k) != EOF)
34     {
35         for (int i = 1; i <= n; ++i) scanf("%d", a + i);
36         int res = 0;
37         for (int i = 1; i <= n; ++i) res = max(res, get(i));
38         printf("%d
", res);
39     }
40     return 0;
41 }

View Code

B. Build a Contest

签到.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 int n, m, a[N];
 6 int cnt[N]; 
 7 
 8 int main()
 9 {
10     while (scanf("%d%d", &n, &m) != EOF)
11     {
12         for (int i = 1; i <= m; ++i) scanf("%d", a + i);
13         int need = n;
14         memset(cnt, 0, sizeof cnt);
15         for (int i = 1; i <= m; ++i)
16         {
17             if (cnt[a[i]] == 0)
18                 --need;
19             ++cnt[a[i]];
20             if (need) putchar('0');
21             else
22             {
23                 putchar('1');
24                 for (int j = 1; j <= n; ++j) 
25                 {
26                     --cnt[j];
27                     if (!cnt[j])
28                         ++need;
29                 }
30             }
31         }
32         puts("");
33     }
34     return 0;
35 }

View Code

C. NN and the Optical Illusion

签到.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const double eps = 1e-8;
 5 const double PI = acos(-1.0);
 6 
 7 int main()
 8 {
 9     int n; double r;
10     while (scanf("%d%lf", &n, &r) != EOF)
11     {
12         double ang1 = 2.0 * PI / n;
13         double ang2 = (PI - ang1) / 2;
14         double R = (r * sin(ang1) * 1.0) / (2 * sin(ang2) - sin(ang1));
15         printf("%.10f
", R);
16     }
17     return 0;
18 }

View Code

D. Dasha and Chess

Upsolved.

题意：

你有一个白王，对方有$666$个黑王

你每次可以八个方向走一步，对方可以任意移动一个黑王的位置

在$2000步以内如果你和某个黑王同行同列，你就赢了$

$给出你必胜的方案$

思路：

先走到中间，再考虑黑王个数最少的那个角落，向它的反方向走就可以了

考虑最差的情况，四个角很平均都有$166个左右$

那么也就是说另外三个角的个数加起来至少是$500个，而从中间走到某一角落只需要499步$

所以一定可以包围一个

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 #define pii pair <int, int>
 6 #define x first
 7 #define y second
 8 int G[N][N], x, y, cnt[4];
 9 pii cor[N];
10 
11 void Move(int edx, int edy)
12 {
13     while (x != edx || y != edy)
14     {
15         if (x < edx && G[x + 1][y] == 0) ++x;
16         else if (x > edx && G[x - 1][y] == 0) --x;
17         if (y < edy && G[x][y + 1] == 0) ++y;
18         else if (y > edy && G[x][y - 1] == 0) --y;
19         printf("%d %d
", x, y);
20         fflush(stdout);
21         int k, a, b;
22         scanf("%d%d%d", &k, &a, &b);
23         if (k == -1) exit(0);
24         G[cor[k].x][cor[k].y] = 0;
25         cor[k].x = a, cor[k].y = b;
26         G[cor[k].x][cor[k].y] = 1;
27     }
28 }
29 
30 int main()
31 {
32     while (scanf("%d%d", &x, &y) != EOF)
33     {
34         memset(G, 0, sizeof G);
35         for (int i = 1; i <= 666; ++i)
36         {
37             scanf("%d%d", &cor[i].x, &cor[i].y);
38             G[cor[i].x][cor[i].y] = 1;
39         }
40         Move(500, 500);
41         memset(cnt, 0, sizeof cnt);
42         for (int i = 1; i <= 999; ++i)
43             for (int j = 1; j <= 999; ++j)
44                 if (G[i][j])
45                 {
46                     if (i < x && j < y) ++cnt[0];
47                     else if (i < x && j > y) ++cnt[1];
48                     else if (i > x && j < y) ++cnt[2];
49                     else ++cnt[3];
50                 }
51         if (cnt[0] <= 166) Move(999, 999);
52         else if (cnt[1] <= 166) Move(999, 1);
53         else if (cnt[2] <= 166) Move(1, 999);
54         else Move(1, 1);
55     }
56     return 0;
57 }

View Code

E. Andrew and Taxi

Upsolved.

题意：

给出一张有向图，求改变一些边使得它没有环

改变一条边的花费是它的边权，要使得最大花费最小

输出最大花费和需要改变的边数

再输出相应的边

思路：

先二分答案，每次check的时候检查一下边权大于limit的边组成的图是否有环

如果有环，那么一定不行，如果没有环，那么一定可以

对于剩下的边，方向自定，拓扑序小的连向拓扑序大的

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 int n, m;
 6 struct Graph
 7 {
 8     struct node
 9     {
10         int to, nx, w, id;
11         node() {}
12         node (int to, int nx, int w, int id) : to(to), nx(nx), w(w), id(id) {}
13     }a[N << 1];
14     int head[N], pos;
15     void init()
16     {
17         memset(head, 0, sizeof head);
18         pos = 0;
19     }
20     void add(int u, int v, int w, int id) 
21     {
22         a[++pos] = node(v, head[u], w, id); head[u] = pos;
23     }
24 }G;
25 #define erp(u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w, id = G.a[it].id; it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w, id = G.a[it].id)
26 
27 int degree[N], ord[N];
28 bool check(int x)
29 {
30     memset(degree, 0, sizeof degree);
31     for (int i = 1; i <= n; ++i) erp(i) if (w > x)
32         ++degree[v];
33     int cnt = 0;
34     queue <int> q;
35     for (int i = 1; i <= n; ++i) if (!degree[i])
36         q.push(i);
37     while (!q.empty())
38     {
39         ++cnt;
40         int u = q.front(); q.pop();
41         ord[u] = cnt;
42         erp(u) if (w > x && --degree[v] == 0)
43             q.push(v);
44     }
45     return cnt >= n;
46 }
47 
48 int main()
49 {
50     while (scanf("%d%d", &n, &m) != EOF)
51     {
52         G.init();
53         for (int i = 1, u, v, w; i <= m; ++i)
54         {
55             scanf("%d%d%d", &u, &v, &w);
56             G.add(u, v, w, i);
57         }
58         int l = 0, r = (int)1e9, res = -1;
59         while (r - l >= 0)
60         {
61             int mid = (l + r) >> 1;
62             if (check(mid))
63             {
64                 res = mid;
65                 r = mid - 1;
66             }            
67             else
68                 l = mid + 1;
69         }
70         vector <int> vec;
71         check(res);
72         for (int i = 1; i <= n; ++i) erp(i) if (w <= res && ord[i] > ord[v]) vec.push_back(id);
73         printf("%d %d
", res, (int)vec.size());
74         for (int i = 0, len = vec.size(); i < len; ++i) printf("%d%c", vec[i], " 
"[i == len - 1]);
75     }
76     return 0;
77 }

View Code

F. Ivan and Burgers

Upsolved.

题意：

询问区间任意数异或最大值

思路：

维护前缀线性基，但是要注意将$位置id大的数更换基底$

$因为这样这些基底被用户更新答案的概率就更高$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 500010
 5 int n, q, c[N];
 6 int pos[N][25], p[N][25];
 7 
 8 void work(int x)
 9 {
10     for (int i = 0; i <= 20; ++i) 
11     {
12         pos[x][i] = pos[x - 1][i];
13         p[x][i] = p[x - 1][i];
14     }
15     int tmp = c[x];
16     int id = x;
17     for (int i = 20; i >= 0; --i)
18     {
19         if ((tmp >> i) & 1)
20         {
21             if (!p[x][i])
22             {
23                 p[x][i] = tmp;
24                 pos[x][i] = id;
25                 return; 
26             }
27             if (pos[x][i] < id)  
28             {
29                 swap(tmp, p[x][i]);
30                 swap(id, pos[x][i]); 
31             }
32             tmp ^= p[x][i];
33         }
34     }
35 }
36 
37 int ask(int l, int r)
38 {
39     int res = 0;
40     for (int i = 20; i >= 0; --i) if (pos[r][i] >= l && (res ^ p[r][i]) > res)
41         res ^= p[r][i];
42     return res;
43 }
44 
45 int main()
46 {
47     while (scanf("%d", &n) != EOF)
48     {
49         for (int i = 1; i <= n; ++i) scanf("%d", c + i);
50         for (int i = 0; i < 25; ++i) pos[0][i] = p[0][i] = 0;
51         for (int i = 1; i <= n; ++i) work(i);
52         scanf("%d", &q);
53         for (int qq = 1, l, r; qq <= q; ++qq)
54         {
55             scanf("%d%d", &l, &r);
56             printf("%d
", ask(l, r));
57         }
58 
59     }
60     return 0;
61 }

View Code