Codeforces Round 500 (Div 2) Solution

2021-09-16 14:51:11

Problem A Piles With Stones

题目大意

　　有若干堆石子排成一排。第一天科研人员记录了它们每一堆的数量。第二天科研人员又记录了这些石子的数量。晚上可能有非常多的游客来过。每个游客有三种可选操作：

  1. 不对石子做什么。
  2. 拿走一个石子
  3. 将一个石子移动到另一堆中。

　　给定两天记录的数据问是否可能。

　　直接判断第二天的数量是否小于等于第一天。

Code

 /**

  * Codeforces

  * Problem#1013A

  * Accepted

  * Time: 31ms

  * Memory: 0k

  */

 #include <iostream>

 #include <cstdlib>

 #include <cstdio>

 using namespace std;

 typedef bool boolean;

 int n;

 int s1 = ;

 inline void init() {

     scanf("%d", &n);

     for (int i = , x; i <= n; i++)

         scanf("%d", &x), s1 += x;

     for (int i = , x; i <= n; i++)

         scanf("%d", &x), s1 -= x;

     if (s1 < )

         puts("No");

     else

         puts("Yes");

 }

 int main() {

     init();

     return ;

 }

Problem A

Problem B And

题目大意

　　给定$n$个数和$x$，将一个数按位与$x$算作一次操作，要求序列中至少有两个相同的数，问最少的操作数。无解输出-1.

　　显然答案只可能是-1,0,1,2。

　　第一种是无解。第二种不需要操作。第三种是一个数按位与x后与另一个数相同。最后一种是两个数与x后相同。

　　每个数与x，然后用stl判一判。

Code

 /**

  * Codeforces

  * Problem#1013B

  * Accepted

  * Time: 124ms

  * Memory: 4200k

  */

 #include <bits/stdc++.h>

 using namespace std;

 typedef bool boolean;

 const int N = 1e5 + ;

 int n, x;

 int ar[N];

 map<int, int> sa;

 set<int> sb;

 inline void init() {

     scanf("%d%d", &n, &x);

     for (int i = , a; i <= n; i++) {

         scanf("%d", &a);

         ar[i] = a;

         if (sa.count(a)) {

             puts("");

             exit();

         }

         sa[a] = i;

     }

 }

 int res = ;

 inline void solve() {

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

         int b = ar[i] & x;

         if (sb.count(b))

             res = min(res, );

         sb.insert(b);

         if (sa.count(b) && sa[b] != i)

             res = ;

     }

     if (res == )

         puts("-1");

     else

         printf("%d", res);

 }

 int main() {

     init();

     solve();

     return ;

 }

Problem B

Problem C Photo of The Sky

题目大意

　　有$2n$个数，要求分成元素个数相等的两组$X$和$Y$，且$\left(max(X) - min(X)\right)\left(max(Y) - min(Y)\right)$最小。问这个最小值。其中$min(X),max(X)$分别表示$X$中最小、最大的数。

　　考虑两种情况：

  • 如果最大值和最小值在同一个集合内，那么设下的数一定是排序后连续的一段，否则我取这中间最小的和排它后面的$(n - 1)$可以更优。这一部分可以$O(n)$处理掉。
  • 如果最大值和最小值在不同集合内，那么我们要使最小值在的集合的最大值尽量小，最大值在的集合的最小值尽量大。显然取前$n$小作为$X$，剩下的作为$Y$最优。

Code

 /**

  * Codeforces

  * Problem#1013C

  * Accepted

  * Time: 93ms

  * Memory: 800k

  */

 #include <bits/stdc++.h>

 using namespace std;

 typedef bool boolean;

 const int N = 2e5 + ;

 int n;

 int ar[N];

 inline void init() {

     scanf("%d", &n);

     n <<= ;

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

         scanf("%d", ar + i);

 }

 inline void solve() {

     sort(ar + , ar + n + );

     n >>= ;

     long long res = (ar[n] - ar[]) * 1ll * (ar[n << ] - ar[n + ]);

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

         res = min((ar[i + n - ] - ar[i]) * 1ll * (ar[n << ] - ar[]), res);

     cout << res << endl;

 }

 int main() {

     init();

     solve();

     return ;

 }

Problem C

Problem D Chemical table

题目大意

　　有一个$n\times m$的网格图，如果三个有原料的格子恰好在恰好围住它们的最小矩形的三个"顶点"上，那么剩下的一个"顶点"能自动填上原料。现在有$q$个位置填上了原料。你可以在某个格子上放置原料，问如果要整张图都填满原料，至少还要放置多少原料。

　　一个比较经典的模型？

　　每行每列分别建一个点，$(i, j)$ 有原料那么第 $i$ 行向第 $j$ 列连一条边。

　　然后算算连通块数就能算答案了。

Code

 /**

  * Codeforces

  * Problem#1013D

  * Accepted

  * Time: 109ms

  * Memory: 6500k

  */

 #include <bits/stdc++.h>

 using namespace std;

 typedef bool boolean;

 const int N = 2e5 + ;

 int n, m, q;

 boolean v1[N], v2[N];

 int uf[N << ];

 int find(int x) {

     return (uf[x] == x) ? (x) : (uf[x] = find(uf[x]));

 } 

 inline void init() {

     scanf("%d%d%d", &n, &m, &q);

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

         uf[i] = i;

     for (int i = , x, y; i <= q; i++) {

         scanf("%d%d", &x, &y);

         uf[find(x)] = find(y + n);

     }

 }

 int res = -;

 inline void solve() {

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

         if (find(i) == i)

             res++;

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

 }

 int main() {

     init();

     solve();

     return ;

 }

Problem D

Problem E Hills

题目大意

　　有一条连绵起伏的山脉，第$i$个山峰的高度是$h_{i}$。有一个工程队，每小时能将任意一座山的高度减少1。一个山峰能建立房子当且仅当它两边的山峰高度严格小于它。要求输出当建立$1. \cdots, \left \lceil \frac{n}{2} \right \rceil$个房子的时候至少需要工程队施工的时间。

　　显然用$f[i][j][0 / 1]$表示考虑到第$i$座山峰，已经建立了$j$个房子，当期山峰是否建立房子的最少施工时间。

　　首先如果一个地方要建立房子，那么会贪心地使周围两座山的高度尽量高（因为这样花的时间少），因此如果知道一座山两边有没有盖房子，这座山在最优的情况下的高度是确定的。

　　转移也比较显然。如果当前山峰没有建立房子，那么从$i - 1$转移。

　　如果当前山峰建立了房子，那么前一座山一定不能建房子。考虑$i - 2$座山上有没有建房子，如果建立了，那么补上第$i - 1$座山的高度差，以及减少第$i + 1$座山的高度的耗时。如果没有建房子，直接计算耗时转移。

Code

 /**

  * Codeforces

  * Problem#1013E

  * Accepted

  * Time: 124ms

  * Memory: 98100k

  */

 #include <bits/stdc++.h>

 #ifndef WIN32

 #define Auto "%lld"

 #else

 #define Auto "%I64d"

 #endif

 using namespace std;

 typedef bool boolean;

 #define ll long long

 const int N = 5e3 + ;

 int n, hn;

 int ar[N];

 int f[N][N >> ][];

 inline void init() {

     scanf("%d", &n);

     hn = (n + ) >> ;

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

         scanf("%d", ar + i);

 }

 int calc(int p) {

     if (p < )    return ;

     return ((ar[p - ] < ar[p]) ? () : (ar[p - ] - ar[p] + )) + ((ar[p + ] < ar[p]) ? () : (ar[p + ] - ar[p] + ));

 }

 int calc2(int a) {

     if (a < )    return calc(a + );

     int res = ((ar[a - ] < ar[a]) ? () : (ar[a - ] - ar[a] + ));

     res += (ar[a + ] < min(ar[a], ar[a + ])) ? () : (ar[a + ] - min(ar[a], ar[a + ]) + );

     res += (ar[a + ] < ar[a + ]) ? () :(ar[a + ] - ar[a + ] + );

     return res;

 }

 int res[N];

 inline void solve() {

     memset(f, 0x7f, sizeof(f));

     ar[] = -1e5 + , ar[n + ] = -1e5;

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

         f[i][][] = ;

     f[][][] = calc(), f[][][] = ;

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

         for (int j = ; j <= hn && j <= ((i + ) >> ); j++) {

             if (!j)

                 f[i][j][] = f[i - ][j][];

             else {

                 f[i][j][] = min(f[i - ][j][], f[i - ][j][]);

                 f[i][j][] = min(f[i - ][j - ][] + calc(i), f[i - ][j - ][] - calc(i - ) + calc2(i - ));

 //                cerr << i << " " << calc(i) << " " << calc2(i - 2) << " " << calc(i - 2) << " " << f[i - 2][j][0] << endl;

             }

         }

     memset(res, 0x7f, sizeof(res));

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

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

             res[j] = min(res[j], f[i][j][]), res[j] = min(res[j], f[i][j][]);

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

         printf("%d ", res[i]);

 }

 int main() {

     init();

     solve();

     return ;

 }

Problem E

Problem F AB-Strings

题目大意

　　有两个只含字符'a'、'b'的字符串。一次操作是指交换这两个字符串的可空前缀。问使得每个串内只包含一种字符最少的操作数。要求输出方案。保证至少有一个'a'和'b'。

　　显然把已经连续的相同字符断开不优，因此把连续的相同缩在一起。

　　然后有用的状态就只有两个串的串长，以及开头的字符是否相同。

　　因此我们可以暴力动态规划。

　　但是感觉这玩意决策不会太多，因为每次至多只会消掉两个字符。

　　于是我们可以对小数据进行动态规划，并打表。

　　然后发现第一列、第二列、第一行、第二行除去前几项决策4个一循环。

　　剩下的决策与它们的长度差模4的余数有关。

　　然后再写个链表模拟一下。交上去就过了。

　　如果哪位佬会证明，麻烦在评论区内写一写。

Code

 #include <bits/stdc++.h>

 using namespace std;

 typedef bool boolean;

 const int N = ;

 boolean vis[N][N][];

 int f[N][N][], p1[N][N][], p2[N][N][];

 int s1[N], s2[N];

 void update(int &f, int& p1, int& p2, int val, int sl, int sr) {

     if (val < f || (val == f && (sl + sr < p1 + p2)) || (sl + sr == p1 + p2 && sl < p1))

         f = val, p1 = sl, p2 = sr;

 }

 int dp(int l, int r, int dif) {

     if (!l || !r)

         return 0x7f7f7f7f;

     if (l ==  && r == )

         return (dif == ) ? () : (0x7f7f7f7f);

     if (vis[l][r][dif])

         return f[l][r][dif];

     vis[l][r][dif] = true;

     for (int sl = ; sl <= l; sl++)

         for (int sr = ; sr <= r; sr++) {

             if (!sl && !sr)

                 continue;

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

                 s1[i] = (dif + i) & ;

             s1[sr] = sl & ;

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

                 s2[i] = i & ;

             s2[sl] = (dif + sr) & ;

             int red1 = , red2 = ;

             for (int i = ; i <= sr && i < l - sl + sr; i++)

                 red1 += (s1[i] == s1[i - ]);

             for (int i = ; i <= sl && i < r + sl - sr; i++)

                 red2 += (s2[i] == s2[i - ]);

             if (!red1 && !red2)

                 continue;

 //            cerr << l << " " << r << " " << dif << " " << sl << " " << sr << " -> " << l + sr - sl - red1 << " " << r + sl - sr - red2 << " " << (s1[0] != s2[0]) << endl;

             update(f[l][r][dif], p1[l][r][dif], p2[l][r][dif], dp(l + sr - sl - red1, r + sl - sr - red2, s1[] != s2[]) + , sl, sr);

         }

     return f[l][r][dif];

 }

 int n, m, d;

 int main() {

 //    cin >> n >> m >> d;

     cin >> d;

     memset(vis, false, sizeof(vis));

     memset(f, 0x7f, sizeof(f));

 //    cout << dp(n, m, d) << endl;

     freopen("list.txt", "w", stdout);

     for (int i = ; i <= ; i++, cout << endl)

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

             dp(i, j, d);

             cout << "(" << p1[i][j][d] << ", " << p2[i][j][d] << ") ";

 //            assert(p1[i][j][d] == p1[min(i, 10)][min(j, 10)][d]);

 //            assert(p2[i][j][d] == p2[min(i, 10)][min(j, 10)][d]);

         }

     return ;

 }

Table Maker

 /**

  * Codeforces

  * Problem#1013F

  * Accepted

  * Time: 109ms

  * Memory: 8000k

  */

 #include <bits/stdc++.h>

 using namespace std;

 typedef bool boolean;

 const int N = ;

 boolean vis[N][N][];

 int f[N][N][], p1[N][N][], p2[N][N][];

 int s1[N], s2[N];

 void update(int &f, int& p1, int& p2, int val, int sl, int sr) {

     if (val < f || (val == f && (sl + sr < p1 + p2)))

         f = val, p1 = sl, p2 = sr;

 }

 int dp(int l, int r, int dif) {

     if (!l || !r)

         return 0x7f7f7f7f;

     if (l ==  && r == )

         return (dif == ) ? () : (0x7f7f7f7f);

     if (vis[l][r][dif])

         return f[l][r][dif];

     vis[l][r][dif] = true;

     for (int sl = ; sl <= l; sl++)

         for (int sr = ; sr <= r; sr++) {

             if (!sl && !sr)

                 continue;

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

                 s1[i] = (dif + i) & ;

             s1[sr] = sl & ;

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

                 s2[i] = i & ;

             s2[sl] = (dif + sr) & ;

             int red1 = , red2 = ;

             for (int i = ; i <= sr && i < l - sl + sr; i++)

                 red1 += (s1[i] == s1[i - ]);

             for (int i = ; i <= sl && i < r + sl - sr; i++)

                 red2 += (s2[i] == s2[i - ]);

             if (!red1 && !red2)

                 continue;

 //            cerr << l << " " << r << " " << dif << " " << sl << " " << sr << " -> " << l + sr - sl - red1 << " " << r + sl - sr - red2 << " " << (s1[0] != s2[0]) << endl;

             update(f[l][r][dif], p1[l][r][dif], p2[l][r][dif], dp(l + sr - sl - red1, r + sl - sr - red2, s1[] != s2[]) + , sl, sr);

         }

     return f[l][r][dif];

 }

 typedef class Node {

     public:

         Node* suf;

         int col, s;

         Node() {    }

         Node(Node* suf, int col, int s):suf(suf), col(col), s(s) {    }

 }Node;

 int d;

 int l = , r = ;

 Node *stl, *str;

 Node nl[], nr[];

 char buf[];

 inline void init() {

     int c1, c2;

     scanf("%s", buf);

     c1 = buf[];

     nl[] = Node(nl + , -, -);

     nl[] = Node(nl + , c1, );

     for (int i = ; buf[i]; i++)

         if (buf[i] == buf[i - ])

             nl[l].s++;

         else

             l += , nl[l] = Node(nl + l + , buf[i], );

     nl[l + ].s = -;

     scanf("%s", buf);

     c2 = buf[];

     nr[] = Node(nr + , -, -);

     nr[] = Node(nr + , c2, );

     for (int i = ; buf[i]; i++)

         if (buf[i] == buf[i - ])

             nr[r].s++;

         else

             r += , nr[r] = Node(nr + r + , buf[i], );

     nr[r + ].s = -;

     d = (c1 != c2);

     stl = nl, str = nr;

 }

 pair<int, int> swapS(int sl, int sr, int& l, int& r) {

     Node *pl = stl, *psl, *pr = str, *psr;

     int rl = , rr = ;

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

         pl = pl->suf, rl += pl->s;

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

         pr = pr->suf, rr += pr->s;

     psl = pl->suf, psr = pr->suf;

     swap(stl, str);

     pl->suf = psr;

     pr->suf = psl;

     if (pl->s >  && psr->s >  && pl->col == psr->col) {

         pl->s += psr->s;

         pl->suf = psr->suf;

         r--;

     }

     if (pr->s >  && psl->s >  && pr->col == psl->col) {

         pr->s += psl->s;

         pr->suf = psl->suf;

         l--;

     }

     return pair<int, int> (rl, rr);

 }

 pair<int, int> st1[] = {pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, )};

 pair<int, int> st2[] = {pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, )};

 pair<int, int> st3[] = {pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, )};

 pair<int, int> st4[] = {pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, )};

 pair<int, int> st5[] = {pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, )};

 pair<int, int> st6[] = {pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, ), pair<int, int>(, )};

 pair<int, int> g(int x, int y, int d) {

     if (x <=  && y <= ) {

         dp(x, y, d);

         return pair<int, int>(p1[x][y][d], p2[x][y][d]);

     }

     if (!d) {

         if (y == )

             return st1[x % ];

         if (y == )

             return st2[x % ];

         if (x == )

             return st3[y % ];

         if (x == )

             return (y %  == ) ? (pair<int, int>(, )) : (pair<int, int>(, ));

         return ((((x - y) %  + ) % ) == ) ? (pair<int, int>(, )) : (pair<int, int>(, ));

     } else {

         if (y == )

             return st4[x % ];

         if (y == )

             return st5[x % ];

         if (x == )

             return (y %  == ) ? (pair<int, int>(, )) : (pair<int, int>(, ));

         if (x == )

             return st6[y % ];

         return ((((x - y) %  + ) % ) == ) ? (pair<int, int>(, )) : (pair<int, int>(, ));

     }

 }

 vector< pair<int, int> > opt;

 inline void solve() {

     memset(vis, false, sizeof(vis));

     memset(f, 0x7f, sizeof(f));

     while (l >  || r > ) {

         pair<int, int> s = g(l, r, d);

         int sl = s.first, sr = s.second;

         l = l - sl + sr, r = r + sl - sr;

         opt.push_back(swapS(sl, sr, l, r));

         d = (stl->suf->col != str->suf->col);

     }

     printf("%d\n", (signed) opt.size());

     for (int i = ; i < (signed) opt.size(); i++)

         printf("%d %d\n", opt[i].first, opt[i].second);

 }

 int main() {

     init();

     solve();

     return ;

 }

Problem F

上一篇：POI使用：用poi接口不区分xls/xlsx格式解析Excel文档(41种日期格式解析方法，5种公式结果类型解析方法，3种常用数值类型精度控制办法)


下一篇：接口测试之HTTP协议详解