2022SYCPC｜Apr.29 CUC2024区域赛重现#9

The 2022 ICPC Asia Shenyang Regional Contest (The 1st Universal Cup, Stage 1: Shenyang)

ID	Difficulty	Topic	Status
A
B
C	⭐⭐	Greedy, Implementation	0:34:09 (+1)
D	⭐	Brute Force	0:06:36
E			(Upsolved)
F	⭐⭐⭐⭐	Constructive algorithms, Math	3:21:40
G
H
I
J
K
L	⭐⭐⭐	Math, Implementation, Brute Force	4:16:23 (+2)
M

C. Clamped Sequence

• 题意 选择一个区间$[l,r]$，且$r-l\leqslant d$，使序列$b_i := \min(\max(a_i,l),r)$ 的$S=\sum|b_i-b_{i+1}|$ 最大，其中$n\leqslant5000$。

• 思路 一方面，选择区间后$S$ 会减小，希望$r-l = d$；另一方面，固定$l$，希望$r$ 尽可能大，固定$r$，希望$l$ 尽可能小。综合看，只能取$l=a_i$ 或$r=a_i$。遍历这$2n$ 中取法，计算$S$ 的最大值，时间复杂度$\Theta(n^2)$。

• 注意 仅仅取$l=a_i$ 判断是不行的，如 Hack 数据 a = { 2,6,7,6 }, d = 2。

• void eachT() {
      int n = read();
      ll d = read();
  
      vector<ll> a(n + 1);
      for (int i = 1; i <= n; ++i) a[i] = read();
  
      ll ans = 0;
  
      auto solve = [&](ll l, ll r) {
          ll sum = 0;
          for (int i = 2; i <= n; ++i) 
              sum += abs(min(max(a[i], l), r) - min(max(a[i-1], l), r));
          ans = max(sum, ans);
      };
  
      for (int i = 1; i <= n; ++i) {
          solve(a[i], a[i] + d);
          solve(a[i] - d, a[i]);
      }
  
      printf("%lld\n", ans);
  }

D. DRX vs. T1

• 题意 五局三胜，判断胜利者。

• 思路 出现次数多者胜。

• void eachT() {
      string s; cin >> s;
      int t = 0, d = 0;
      for (auto c : s) {
          t += c == 'T';
          d += c == 'D';
      }
      cout << (t > d) ? "T1" : "DRX";
  }

F. Half Mixed

• 题意

• 思路

• ll a[maxN];
  
  void eachT() {
      for (int i = 1; i < maxN; i++) {
          a[i] = 1ll * i * (i - 1) / 2;
      }
  
      int n = read(), m = read();
      if (n * (n + 1) * m * (m + 1) % 8 != 0) return void(printf("No\n"));
  
      printf("Yes\n");
  
      vector<int> v;
  
      int x = n, y = m;
      bool flag = 1;
      if (n * (n + 1) % 4 == 0) {
          swap(x, y);
          flag = 0;
      }
  
  
      ll sum = y * (y + 1) / 4 - y;
      int tot = 0;
      while (sum != 0) {
          int p = upper_bound(a + 1, a + maxN, sum) - a;
          p--;
          sum -= a[p];
          tot += p;
          v.push_back(p);
      }
      while (tot < y) {
          tot += 1;
          v.push_back(1);
      }
  
      if (flag) {
          string ans;
          bool op = 0;
          for (int i = 0; i < v.size(); i++) {
              for (int j = 0; j < v[i]; ++j) {
                  ans += (char)(op + '0');
                  ans += ' ';
              }
              op ^= 1;
          }
          while (n--) cout << ans << endl;
      } else {
          bool op = 0;
          for (int i = 0; i < v.size(); i++) {
              string ans;
              for (int j = 0; j < m; j++) {
                  ans += (char)(op + '0');
                  ans += ' ';
              }
              while (v[i]--) cout << ans << endl;
              op ^= 1;
          }
      }
  }

L. Tavern Chess

• 题意 模拟《炉石传说》，求双方获胜概率。

• 思路 模拟。注意概率需要「加权」，即在第一轮有一种情形获胜的概率与在第二轮有一种情形获胜的概率是不同的，后者需要将本轮的概率乘上上一轮为判别胜负的概率。

•   int n, m;
  
  struct PROBABILITY {
      double a, b, t;
  };
  
  struct MINION {
      int a, h, w, die = 0;
      int dies;
  };
  
  PROBABILITY dfs(bool op, vector<MINION> a, vector<MINION> b, int ta = 0, int tb = 0) {
      PROBABILITY ans = { 0,0,0 };
  
      if (op) {
          int anum = ta;
          while (a[anum].die == 1) {
              anum = (anum + 1) % n;
          }
      
          for (int bnum = 0; bnum < b.size(); ++bnum) {
              if (b[bnum].die == 1) continue;
      
              vector<MINION> atmp = a, btmp = b;
              atmp[anum].h -= btmp[bnum].a;
              atmp[anum].w += 1;
              btmp[bnum].h -= atmp[anum].a;
      
              if (atmp[anum].h <= 0) {
                  atmp[anum].die = 1;
                  atmp[0].dies += 1;
              }
              if (btmp[bnum].h <= 0) {
                  btmp[bnum].die = 1;
                  btmp[0].dies += 1;
              }
      
              if (atmp[0].dies == n && btmp[0].dies == m) {
                  ans.t += 1.0;
              } else if (atmp[0].dies == n) {
                  ans.b += 1.0;
              } else if (btmp[0].dies == m) {
                  ans.a += 1.0;
              } else {
                  PROBABILITY tmp = dfs(op ^ 1, atmp, btmp, (anum + 1) % n, tb);
                  ans.a += tmp.a / (tmp.a + tmp.b + tmp.t);
                  ans.b += tmp.b / (tmp.a + tmp.b + tmp.t);
                  ans.t += tmp.t / (tmp.a + tmp.b + tmp.t);
              }
          }
  
  
  
      } else {
          int bnum = tb;
          while (b[bnum].die == 1) {
              bnum = (bnum + 1) % m;
          }
          for (int anum = 0; anum < a.size(); ++anum) {
              if (a[anum].die == 1) continue;
      
              vector<MINION> atmp = a, btmp = b;
              btmp[bnum].h -= atmp[anum].a;
              btmp[bnum].w += 1;
              atmp[anum].h -= btmp[bnum].a;
      
              if (atmp[anum].h <= 0) {
                  atmp[anum].die = 1;
                  atmp[0].dies += 1;
              }
              if (btmp[bnum].h <= 0) {
                  btmp[bnum].die = 1;
                  btmp[0].dies += 1;
              }
      
              if (atmp[0].dies == n && btmp[0].dies == m) {
                  ans.t += 1.0;
              } else if (atmp[0].dies == n) {
                  ans.b += 1.0;
              } else if (btmp[0].dies == m) {
                  ans.a += 1.0;
              } else {
                  PROBABILITY tmp = dfs(op ^ 1, atmp, btmp, ta, (bnum + 1) % m);
                  ans.a += tmp.a / (tmp.a + tmp.b + tmp.t);
                  ans.b += tmp.b / (tmp.a + tmp.b + tmp.t);
                  ans.t += tmp.t / (tmp.a + tmp.b + tmp.t);
              }
          }
      }
      
      return ans;
  }
  
  void eachT() {
      n = read(), m = read();
  
      vector<MINION> a(n), b(m);
      for (auto& i : a) i.a = i.h = read(), i.w = 0;
      for (auto& i : b) i.a = i.h = read(), i.w = 0;
      
      PROBABILITY ans;
      if (a.size() < b.size()) {
          ans = dfs(0, a, b);
      } else if (a.size() > b.size()) {
          ans = dfs(1, a, b);
      } else {
          ans = dfs(0, a, b);
          PROBABILITY tmp2 = dfs(1, a, b);
          ans.a += tmp2.a;
          ans.b += tmp2.b;
          ans.t += tmp2.t;
      }
      printf("%.12lf ", ans.a / (ans.a + ans.b + ans.t));
      printf("%.12lf ", ans.b / (ans.a + ans.b + ans.t));
      printf("%.12lf ", ans.t / (ans.a + ans.b + ans.t));
  }

• 变式 模拟《Super Auto Pets》，求在随机选择排队方式中，双方获胜概率。

• int a_atk[maxN], a_hp[maxN], b_atk[maxN], b_hp[maxN];
  void eachT() {
      int n = read(), m = read();
      for (int i = 0; i < n; ++i) a_hp[i] = a_atk[i] = read();
      for (int j = 0; j < m; ++j) b_hp[j] = b_atk[j] = read();
    
      int alice = 0, bob = 0, tie = 0;
    
      std::sort(a_atk, a_atk + n);
      do {
          for (int bnum = 0; bnum < n; ++bnum) a_hp[bnum] = a_atk[bnum];
    
          std::sort(b_atk, b_atk + m);
          do {
              for (int j = 0; j < m; ++j) b_hp[j] = b_atk[j];
    
              int bnum = 0, j = 0;
              while (iLoveCUC) {
                  a_hp[bnum] -= b_atk[j];
                  b_hp[bnum] -= a_atk[j];
                  if (a_hp[bnum] <= 0) ++bnum;
                  if (b_hp[j] <= 0) ++j;
                  if (bnum == n && j == m) {
                      tie++;
                      break;
                  }
                  if (bnum == n) {
                      bob++;
                      break;
                  }
                  if (j == m) {
                      alice++;
                      break;
                  }
              }
    
          } while (std::next_permutation(b_atk, b_atk + m));
      } while (std::next_permutation(a_atk, a_atk + n));
    
      printf("%.12lf ", alice / (alice + bob + tie));
      printf("%.12lf ", bob / (alice + bob + tie));
      printf("%.12lf ", tie / (alice + bob + tie));
  }