比赛链接：Here

1530A. Binary Decimal

现在规定一种只由0和1组成的数字,我们称这种数字为二进制数字,例如10,1010111,给定一个数n,求该数字最少由多少个二进制数字组成.

水题，

每取一个二进制数字,可以使得原数字n上各位都减小1或者0,为了使次数尽可能地小,那么当原数字n上各位不为0的时候都应该-1,那么最小的次数就是各位上最大的数字

  1. int main() {
  2.     cin.tie(nullptr)->sync_with_stdio(false);
  3.     int _; for (cin >> _; _--;) {
  4.         string s; cin >> s;
  5.         int cnt = s[0] - '0';
  6.         for (int i = 1; i < s.size(); ++i)cnt = max(s[i] - '0', cnt);
  7.         cout << cnt << "\n";
  8.     }
  9. }

1530B. Putting Plates

给定一个高为h,宽为w的网格,你可以在网格的四个边缘处,放置一个盘子,每个盘子的四周都不能有别的盘子(四周指的是最近的8个格子),请输出一个种安排方式.

构造模拟题,首先为了使个数尽可能多,那么一定是从第一个开始放置,然后检测后面是否合法,如果合法就放下盘子,如果不合法就跳过.

  1. int main() {
  2.     cin.tie(nullptr)->sync_with_stdio(false);
  3.     int _; for (cin >> _; _--;) {
  4.         int n, m;
  5.         cin >> n >> m;
  6.         vector<std::string> s(n, string(m, '0'));
  7.         for (int i = 0; i < m; i += 2) {
  8.             s[0][i] = '1';
  9.         }
  10.         for (int i = 1; i < n; i++) {
  11.             if (s[i - 1][m - 1] != '1' && s[i - 1][m - 2] != '1') {
  12.                 s[i][m - 1] = '1';
  13.             }
  14.         }
  15.         for (int i = m - 2; i >= 0; i--) {
  16.             if (s[n - 1][i + 1] != '1' && s[n - 2][i + 1] != '1') {
  17.                 s[n - 1][i] = '1';
  18.             }
  19.         }
  20.         for (int i = n - 2; i > 1; i--) {
  21.             if (s[i + 1][0] != '1' && s[i + 1][1] != '1') {
  22.                 s[i][0] = '1';
  23.             }
  24.         }
  26.         for (int i = 0; i < n; i++) {
  27.             cout << s[i] << "\n";
  28.         }
  29.     }
  30. }

1530C. Pursuit

二分，

给t组样例
每组样例给n个数
a[1] , a[2] , a[3] …… a[n]
b[1] , b[2] , b[3] …… b[n]
数据保证(0 <= a[i] , b[i] <= 100 , t组样例n的总和小于1e5)
a[i]表示第一个人在i这个阶段的分数
b[i]表示第二个人在i这个阶段的分数

现在只给了n个阶段每个人的分数
后面若干个阶段的分数值0到100之间都有可能

现在定义一个人在i这个阶段的得分为
从i个分数中取出 i - i / 4 个最大的分数相加即为
在i阶段的分数

问在n这个阶段是否第一个人的得分大于第二个人的得分
如果可以输出0
如果不行输出最少加几个阶段
使得第一个人的得分大于等于第二个人的得分

  1. const int N = 1e6 + 10;
  2. int a[N], b[N];
  3. int main() {
  4.     cin.tie(nullptr)->sync_with_stdio(false);
  5.     int _; for (cin >> _; _--;) {
  6.         int n;
  7.         cin >> n;
  8.         for (int i = 1; i <= n; ++i)cin >> a[i];
  9.         for (int i = 1; i <= n; ++i)cin >> b[i];
  10.         sort(a + 1, a + 1 + n);
  11.         sort(b + 1, b + 1 + n);
  13.         auto check = [&](int k) {
  14.             int m = n + k, rm = m - m / 4;
  15.             int A = 0, B = 0;
  16.             for (int i = 1; i <= k; ++i) a[n + i] = 100;
  17.             for (int i = m; i > m - rm; --i)A += a[i];
  18.             for (int i = n; i > max(0, n - rm); --i)B += b[i];
  19.             return A >= B;
  20.         };
  22.         if (check(0))cout << "0\n";
  23.         else {
  24.             int l = 0, r = n;
  25.             while (r - l > 1) {
  26.                 ll mid = (l + r) >> 1;
  27.                 if (check(mid))r = mid;
  28.                 else l = mid;
  29.             }
  30.             cout << r  << "\n";
  31.         }
  32.     }
  33. }

当然既然要让a的分数要大于等于b的分数

那么a[n+1] , a[n+2] , a[n+3] ……都应该是100

b[n+1] , b[n+2] , b[n+3] ……. 都应该是0

所以从大到小排序之后 用前缀和优化到 Codeforces Round #733 (Div. 1 Div. 2, based on VK Cup 2021 - Elimination (Engine)) - 图1#card=math&code=%5Cmathcal%7BO%7D%28n%29) 也是可以做的

1530D. Secret Santa

图论，

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  5. // jiangly TQL
  6. int main() {
  7.     cin.tie(nullptr)->sync_with_stdio(false);
  8.     int _; for (cin >> _; _--;) {
  9.         int n;
  10.         cin >> n;
  12.         int ans = 0;
  13.         vector<int> a(n), b(n, -1), c(n, -1);
  14.         for (int i = 0; i < n; i++) {
  15.             cin >> a[i];
  16.             a[i]--;
  17.             if (c[a[i]] < 0) {
  18.                 b[i] = a[i];
  19.                 c[a[i]] = i;
  20.                 ans++;
  21.             }
  22.         }
  24.         vector<int> u, v;
  25.         for (int i = 0; i < n; i++) {
  26.             if (c[i] >= 0)  continue;
  27.             int j = i;
  28.             while (b[j] >= 0)  j = b[j];
  29.             u.push_back(i);
  30.             v.push_back(j);
  31.         }
  33.         if (!u.empty()) {
  34.             if (u.size() > 1 || u[0] != v[0]) {
  35.                 for (int i = 0; i < int(u.size()); i++)
  36.                     b[v[i]] = u[(i + 1) % u.size()];
  37.             } else {
  38.                 int x = u[0];
  39.                 int y = a[x];
  40.                 b[x] = y;
  41.                 b[c[y]] = x;
  42.             }
  43.         }
  45.         cout << ans << "\n";
  46.         for (int i = 0; i < n; i++)
  47.             cout << b[i] + 1 << " \n"[i == n - 1];
  48.     }
  49. }