2024WHCPC｜May.11 CUC2024区域赛重现#13

2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site

ID	Difficulty	Topic	Status
A
B	⭐⭐⭐	Greedy, Math, Bitmasks	0:50:02 (-3)
C
D
E	⭐⭐⭐⭐	Tree(Diameter), Implementation	(Upsolved)
F	⭐⭐⭐	Interactive, Implementation, Binary Search	3:58:48 (-5)
G
H
I	⭐	Brute Force, Implementation	0:07:42
J
K	⭐⭐	Games, Math, Bitmasks	0:27:43
L
M	⭐⭐⭐	Greedy, Implementation	(Upsolved)

B. Countless Me

• 题意 给定序列，可执行至多$n$ 次操作使$a_i\leftarrow a_i+x$ and$a_j \leftarrow a_j-x$，最小化操作后${\Large|}_{i=1}^{n}a_i$。

• 思路$n$ 次操作后可将序列变为任意和不变的新序列。首先，答案不是平均值向上取整，亦不是平均值的上下取整作按位与，这些都是错误地贪心（赛时已找出 Hack 数据）。 正确的做法是，从二进制最高位开始，贪心地填。

• void eachT() {
      ll n = read(), ans = 0, sum = 0;
      for (int i = 1; i <= n; ++i) sum += read();
      for (int i = 30; i >= 0; --i) {
          if (((1ll << i) - 1) * n >= sum) continue;
          ll num = min(n, sum / (1ll << i));
          if (num == 0) continue;
          sum -= num * (1ll << i);
          ans |= 1ll << i;
      }
      printf("%lld", ans);
  }

  赛时代码

  void eachT() {
      ll n = read(), ans = 0, sum = 0;
      for (int i = 1; i <= n; ++i) sum += read();
      while (sum) {
          for (ll i = 0; ; ++i) {
              if (sum / ((1ll << (i + 1)) - 1) <= n) {
                  ll num = min(n, sum / (1ll << i));
                  sum -= num * (1ll << i);
                  ans += 1ll << i;
                  break;
              }
          }
      }
      printf("%lld", ans);
  }

*E. Boomerang

• 题意 有根树。$t$ 时刻的两棵子树是$V(r,t)=\{v \mid \mathrm{dis}(r,v)\le t\}$，$V'(r',t)=\{v \mid \mathrm{dis}(r',v)\le k(t-t_0)\}$。对于每一个$k$，分别任选$r'$，求最小的$t$ 使$V(r,t)\subseteq V'(r',t)$。
• 思路 选取树的中心为$r'$，答案具有单调性，使用双指针维护。

• struct Diameter {
      int len, u, v;
      bool operator<(const Diameter& other) const {
          return len < other.len;
      }
  };
  int ans[N]; // ans[i] i-1时刻的直径长度
  
  int dist(int u, int v) {
      return dep[u] + dep[v] - 2 * dep[getlca(u, v)];
  }
  
  void eachT() {
      int n = read();
      for (int i = 1; i < n; ++i) {
          int u = read(), v = read();
          E[u].push_back(v);
          E[v].push_back(u);
      }
      int rt = read(), t0 = read();
      initlca(rt);
  
      Diameter D = { 1, rt, rt };
      for (int i = 1; i <= n; ++i) {
          ans[i] = ans[i - 1];
          for (auto u : tdep[i]) {
              D = max(D, { dist(u, D.u) + 1, u, D.u });
              D = max(D, { dist(u, D.v) + 1, u, D.v });
              ans[i] = max(ans[i], D.len);
          }
      }
  
      int j = n + t0;
      for (int k = 1; k <= n; ++k) {
          while ((ans[min(n, j + 1)]) / 2 <= (j - t0) * k) j--;
          printf("%d ", j + 1);
      }
  }

F. Custom-Made Clothes

• 题意 交互。方阵自左向右不减，自上向下不减，求第$k$ 大数。询问$a_{ij}\leqslant x$ 并返回其值。

• 思路 二分答案。$a_{ij}\leqslant x$ 构成的矩阵中，$1$ 和$0$ 的分割线是阶梯型，计算阶梯一侧的$1$ 的个数，以判断返回值。此时二分的结果即是「最小的$n^2 - k + 1$ 个数中最大数」，也即第$k$ 大数。所需的操作次数$2n\log n$ 在$n\leqslant 1000$ 的范围内满足$\leqslant50000$（不需要对搜索结果记忆化）。（不需要对二分出的阶梯进一步查找，二分出的即是答案，前者的操作次数为$4n\log n$，记忆化也无法通过）。

• int query(int i, int j, int k) { cout << "? " << i << " " << j << " " << k << endl; cout.flush(); int x; cin >> x; return x; }
  void print(int x) { cout << "! " << x; cout.flush(); }
  
  int n, k;
  bool half(int x) {
      int cnt = 0, i = n, j = 1;
      while (j <= n && i >= 1) {
          if (query(i, j, x)) ++j;
          else --i, cnt += n - j + 1;
      }
      return cnt >= k;
  }
  void eachT() {
      cin >> n >> k;
      int l = 1, r = n * n, mid = -1;
      while (l <= r) mid = l + r >> 1, half(mid) ? l = mid + 1 : r = mid - 1;
      print(l);
  }

I. Cyclic Apple Strings

• 题意 给定 01 串，每次操作选择一个子串和一个正整数$k$，将子串向左循环移动$k$ 位。求出将给定字符串变为有序的最小操作次数。

• void eachT() {
      string s; cin >> s;
      s = '#' + s;
      int cnt = 0;
      for (int i = 1; i < s.size(); ++i) {
          cnt += s[i - 1] == '1' && s[i] == '0';
      }
      printf("%d", cnt);
  }

K. Party Games

• 题意 序列$a_i=i$，每次操作可去除最小数或最大数，至少操作几次使剩下的序列${\Large\oplus}_{i=l}^{r}a_i = 0$。

• 思路 注意到至多四次，暴力枚举。更优的解法：注意到

  $${\Large\oplus}_{i=1}^{n}a_i = \begin{cases} n, & n \equiv 0 \\ 1, & n \equiv 1 \\ n+1, & n \equiv 2 \\ 0, & n \equiv 3 \\ \end{cases} \pmod 4$$

• void eachT() {
      int n = read();
      bool flag = 0;
      if (a[n] == 0) flag = 1;
      else if ((a[n] ^ 1) == 0 || (a[n] ^ n) == 0) flag = 0;
      else if ((a[n] ^ 1 ^ 2) == 0 || (a[n] ^ n ^ (n - 1)) == 0 || (a[n] ^ n ^ 1) == 0) flag = 1;
      else if ((a[n] ^ 1 ^ 2 ^ 3) == 0 || (a[n] ^ n ^ 1 ^ 2) == 0 || (a[n] ^ n ^ (n - 1) ^ 1) == 0 || (a[n] ^ n ^ (n - 1) ^ (n - 2)) == 0) flag = 0;
      printf("%s\n", flag ? "Pinkie Pie" : "Fluttershy");
  }

  void eachT() {
      int n = read();
      bool flag = n % 4 > 1;
      printf("%s\n", flag ? "Pinkie Pie" : "Fluttershy");
  }

*M. Merge

• 题意 可若干次将序列两个数合并，最大化操作后将序列降序排列的字典序。

• 思路 只有奇偶性不同的数才能合并，合并的结果一定是奇数，两个合并后的数不能再次合并，因此，对于某一组数的合并操作是 独立 的。
  因为需要结果尽可能大，贪心地构造最大数，从结果 反推 选数过程。对于序列中的最大偶数$x$，判断是否可以合并为$2x\pm1$，并将这些数$^{\dagger}$ 从序列中删除$^{\dagger\dagger}$ 。重复操作，直至合并完毕。

  $\dagger:$ 这些数都是奇数，且根据下述的合并方式，这些数的选择方法是 惟一（所以贪心）的。

  $\dagger\dagger:$ 合并方法：对于某个奇数$2x+1$，如果有现成的，就直接使用，否则查找是否有$x,x+1$。对于某个偶数，只能找现成的。

• map<ll, ll> mp;
  vector<ll> dels, ans;
  
  void mp_del(ll x) { if (--mp[x] == 0) mp.erase(x); } // 删干净
  
  // 找能不能拼成x
  bool search(ll x) {
      if (mp.count(x)) { mp_del(x); dels.push_back(x); return 1; }  // 有就直接用
      else if (x & 1 && x > 1) return search(x - x / 2) && search(x / 2);  // 没有就找
      else return 0;  // 找不到就寄
  }
  
  bool solve(ll x) {
      dels.clear();
      if (search(x)) { ans.push_back(x); return 1; }   // 有解 加入答案
      else { for (auto x : dels) ++mp[x]; return 0; }  // 无解 刚才删的加回去
  }
  
  void eachT() {
      for (ll n = read(); n--; ) mp[read()]++;
      while (mp.size()) {
          ll x = (*mp.rbegin()).first;  // 剩余序列中最大数
          if (x & 1) {
              if (!mp.count(x - 1)) {
                  ans.push_back(x); mp_del(x);
                  continue;
              }  // 这个奇数是孤立的 直接加入答案并从序列中删除
              x = (*(++mp.rbegin())).first;  // 有一个与奇数相邻的偶数 搜这个偶数
          }
          if (solve(2 * x + 1)) continue;
          if (solve(2 * x - 1)) continue;
          ans.push_back(x); mp_del(x);  // 这个偶数不能合并 直接加入答案并从序列中删除
      }
      printf("%lld\n", ans.size());
      for (auto i : ans) printf("%lld ", i);
  }