Codeforces Round #532 (Div. 2) Solution

A. Roman and Browser

签到.

 #include <bits/stdc++.h>

 using namespace std;

 int n, k, a[];

 int get(int b)

 {

     int vis[];

     memset(vis, , sizeof vis);

     int c = b;

     while (c <= n)

     {

         vis[c] = ;

         c += k;

     }

     c = b - k;

     while (c >= )

     {

         vis[c] = ;

         c -= k;

     }

     int l = , r = ;

     for (int i = ; i <= n; ++i) if (!vis[i])

     {

         if (a[i] == ) ++l;

         else ++r;

     }

     return abs(l - r);

 }

 int main()

 {

     while (scanf("%d%d", &n, &k) != EOF)

     {

         for (int i = ; i <= n; ++i) scanf("%d", a + i);

         int res = ;

         for (int i = ; i <= n; ++i) res = max(res, get(i));

         printf("%d\n", res);

     }

     return ;

 }

B. Build a Contest

签到.

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 int n, m, a[N];

 int cnt[N]; 

 int main()

 {

     while (scanf("%d%d", &n, &m) != EOF)

     {

         for (int i = ; i <= m; ++i) scanf("%d", a + i);

         int need = n;

         memset(cnt, , sizeof cnt);

         for (int i = ; i <= m; ++i)

         {

             if (cnt[a[i]] == )

                 --need;

             ++cnt[a[i]];

             if (need) putchar('');

             else

             {

                 putchar('');

                 for (int j = ; j <= n; ++j)

                 {

                     --cnt[j];

                     if (!cnt[j])

                         ++need;

                 }

             }

         }

         puts("");

     }

     return ;

 }

C. NN and the Optical Illusion

签到.

 #include <bits/stdc++.h>

 using namespace std;

 const double eps = 1e-;

 const double PI = acos(-1.0);

 int main()

 {

     int n; double r;

     while (scanf("%d%lf", &n, &r) != EOF)

     {

         double ang1 = 2.0 * PI / n;

         double ang2 = (PI - ang1) / ;

         double R = (r * sin(ang1) * 1.0) / ( * sin(ang2) - sin(ang1));

         printf("%.10f\n", R);

     }

     return ;

 }

D. Dasha and Chess

Upsolved.

题意：

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

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

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

$给出你必胜的方案$

思路：

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

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

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

所以一定可以包围一个

 #include <bits/stdc++.h>

 using namespace std;

 #define N 1010

 #define pii pair <int, int>

 #define x first

 #define y second

 int G[N][N], x, y, cnt[];

 pii cor[N];

 void Move(int edx, int edy)

 {

     while (x != edx || y != edy)

     {

         if (x < edx && G[x + ][y] == ) ++x;

         else if (x > edx && G[x - ][y] == ) --x;

         if (y < edy && G[x][y + ] == ) ++y;

         else if (y > edy && G[x][y - ] == ) --y;

         printf("%d %d\n", x, y);

         fflush(stdout);

         int k, a, b;

         scanf("%d%d%d", &k, &a, &b);

         if (k == -) exit();

         G[cor[k].x][cor[k].y] = ;

         cor[k].x = a, cor[k].y = b;

         G[cor[k].x][cor[k].y] = ;

     }

 }

 int main()

 {

     while (scanf("%d%d", &x, &y) != EOF)

     {

         memset(G, , sizeof G);

         for (int i = ; i <= ; ++i)

         {

             scanf("%d%d", &cor[i].x, &cor[i].y);

             G[cor[i].x][cor[i].y] = ;

         }

         Move(, );

         memset(cnt, , sizeof cnt);

         for (int i = ; i <= ; ++i)

             for (int j = ; j <= ; ++j)

                 if (G[i][j])

                 {

                     if (i < x && j < y) ++cnt[];

                     else if (i < x && j > y) ++cnt[];

                     else if (i > x && j < y) ++cnt[];

                     else ++cnt[];

                 }

         if (cnt[] <= ) Move(, );

         else if (cnt[] <= ) Move(, );

         else if (cnt[] <= ) Move(, );

         else Move(, );

     }

     return ;

 }

E. Andrew and Taxi

Upsolved.

题意：

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

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

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

再输出相应的边

思路：

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

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

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

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 int n, m;

 struct Graph

 {

     struct node

     {

         int to, nx, w, id;

         node() {}

         node (int to, int nx, int w, int id) : to(to), nx(nx), w(w), id(id) {}

     }a[N << ];

     int head[N], pos;

     void init()

     {

         memset(head, , sizeof head);

         pos = ;

     }

     void add(int u, int v, int w, int id)

     {

         a[++pos] = node(v, head[u], w, id); head[u] = pos;

     }

 }G;

 #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)

 int degree[N], ord[N];

 bool check(int x)

 {

     memset(degree, , sizeof degree);

     for (int i = ; i <= n; ++i) erp(i) if (w > x)

         ++degree[v];

     int cnt = ;

     queue <int> q;

     for (int i = ; i <= n; ++i) if (!degree[i])

         q.push(i);

     while (!q.empty())

     {

         ++cnt;

         int u = q.front(); q.pop();

         ord[u] = cnt;

         erp(u) if (w > x && --degree[v] == )

             q.push(v);

     }

     return cnt >= n;

 }

 int main()

 {

     while (scanf("%d%d", &n, &m) != EOF)

     {

         G.init();

         for (int i = , u, v, w; i <= m; ++i)

         {

             scanf("%d%d%d", &u, &v, &w);

             G.add(u, v, w, i);

         }

         int l = , r = (int)1e9, res = -;

         while (r - l >= )

         {

             int mid = (l + r) >> ;

             if (check(mid))

             {

                 res = mid;

                 r = mid - ;

             }

             else

                 l = mid + ;

         }

         vector <int> vec;

         check(res);

         for (int i = ; i <= n; ++i) erp(i) if (w <= res && ord[i] > ord[v]) vec.push_back(id);

         printf("%d %d\n", res, (int)vec.size());

         for (int i = , len = vec.size(); i < len; ++i) printf("%d%c", vec[i], " \n"[i == len - ]);

     }

     return ;

 }

F. Ivan and Burgers

Upsolved.

题意：

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

思路：

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

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

 #include <bits/stdc++.h>

 using namespace std;

 #define N 500010

 int n, q, c[N];

 int pos[N][], p[N][];

 void work(int x)

 {

     for (int i = ; i <= ; ++i)

     {

         pos[x][i] = pos[x - ][i];

         p[x][i] = p[x - ][i];

     }

     int tmp = c[x];

     int id = x;

     for (int i = ; i >= ; --i)

     {

         if ((tmp >> i) & )

         {

             if (!p[x][i])

             {

                 p[x][i] = tmp;

                 pos[x][i] = id;

                 return;

             }

             if (pos[x][i] < id)

             {

                 swap(tmp, p[x][i]);

                 swap(id, pos[x][i]);

             }

             tmp ^= p[x][i];

         }

     }

 }

 int ask(int l, int r)

 {

     int res = ;

     for (int i = ; i >= ; --i) if (pos[r][i] >= l && (res ^ p[r][i]) > res)

         res ^= p[r][i];

     return res;

 }

 int main()

 {

     while (scanf("%d", &n) != EOF)

     {

         for (int i = ; i <= n; ++i) scanf("%d", c + i);

         for (int i = ; i < ; ++i) pos[][i] = p[][i] = ;

         for (int i = ; i <= n; ++i) work(i);

         scanf("%d", &q);

         for (int qq = , l, r; qq <= q; ++qq)

         {

             scanf("%d%d", &l, &r);

             printf("%d\n", ask(l, r));

         }

     }

     return ;

 }

巴特西

Codeforces Round #532 (Div. 2) Solution

最新文章

热门文章