2023 ICPC 合肥｜Apr.5 CUC2024区域赛重现#6

CUC2024区域赛重现#6

The 2023 ICPC Asia Hefei Regional Contest (The 2nd Universal Cup. Stage 12: Hefei)

ID	Difficulty	Topic	Status
A
B	⭐⭐⭐⭐	DP (LIS, Dilworth’s Theorem)	(Upsolved)
C	⭐⭐⭐	Strings (Palindrome Automaton)
D	⭐⭐⭐	Binary Search, Strings (Hashing)	(Upsolved)
E	⭐⭐	Math, Implementation	1:14:16 (+2)
F	⭐	Implementation	0:06:16
G	⭐⭐⭐⭐	Binary Search, DP	(Upsolved)
H
I
J	⭐⭐⭐	Graphs (Kruskal, MST), DFS, Implementation, Greedy	(Upsolved)
K
L

B. Queue Sorting

• 题意 给定一个单调不降的序列$S$，其中有$a_i$ 个$i$，将其按任意顺序 插入(push) 两个 队列 (std::queue) ，再按任意顺序 出队(pop) ，求可能的所得序列$T$ 的数量。

• 思路$T$ 能拆分为两个单调不降的子序列，于是它的最大下降子序列的长度$\leqslant2$。（止步于此）

  设$f_{i,j}$ 表示将所有$\leqslant i$ 插入，且所有长为$2$ 的下降子序列的首元素的最靠后的一个（最后一个长度为$2$ 的下降子序列的第一个数字）为$j$ 的方案数。

  我们引入了$j$，这是由于插入$i+1$ 时，只能插入到$>j$ 的位置，否则会形成长为$3$ 的下降子序列。

  考虑新的$j'$ 的位置，即插入后，所有长为$2$ 的下降子序列的首元素的最靠后的一个为$j'$。$i+1$ 要么插入到$\left(j,j'\right)$ 之间，要么插入到最后。设有$x$ 个$i+1$ 加到最后，又由于有$1$ 个$i+1$ 恰好在第$j'$ 位，还剩下$a _ {i+1} -x-1$ 个$i+1$ 放在$\left(j,j'\right)$ 之间，这区间内共有$j'-j-1$ 个数，选择$a _ {i+1}-x-1$ 个的方法数为$C_{j'-j-1}^{a_{i+1}-x-1}$，得到状转方程：

  $$f_{i+1,j'} =\begin{cases} \displaystyle \sum_{0 \leqslant j < s_i} \sum_{ \scriptsize \begin{array}{c} x \geqslant 0 \\ k+1+x \leqslant s_{i+1} \\ 0 \leqslant a_{i+1}-x-1 \leqslant j'-j-1 \end{array} } f_{i,j}~C_{j'-j-1}^{a_{i+1}-x-1} , & j < j' \leqslant s_{i+1} \\ f_{i,j}, & j'=j \end{cases}$$

  答案是$\sum f_{n,*}$ 。时间复杂度$\Theta(n^4)$。

  优化：注意到状转方程中有一大串连续组合数的和，预处理组合数前缀和，将时间复杂度优化到$\Theta(n^3)$ （实际也没快多少） 。

• void eachT() {
      int n = read();
      for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + (a[i] = read());
  
      for (int i = 0; i <= sum[n]; ++i) {
          sumC[i][0] = C[i][0] = 1;
          for (int j = 1; j <= i; ++j) {
              C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
              sumC[i][j] = sumC[i][j - 1] + C[i][j];
          }
      }
  
      dp[0][0] = 1;
      for (int i = 0; i < n; ++i) {
          for (int j = 0; j <= sum[i]; ++j) {
              dp[i + 1][j] += dp[i][j];
              for (int k = j + 1; k <= sum[i + 1]; ++k) {
                  int llt = a[i + 1] - min(a[i + 1] - 1, sum[i + 1] - k - 1) - 1;
                  int rrt = a[i + 1] - max(0, a[i + 1] - (k - j)) - 1;
                  dp[i + 1][k] += 1ll * dp[i][j] * (sumC[k - j - 1][rrt] - sumC[k - j - 1][llt - 1]);
              }
          }
      }
      
      mint ans = 0;
      for (int i = 0; i <= sum[n]; ++i) ans += dp[n][i];
      printf("%lld\n", ans);
  }

C. Cyclic Substrings

D. Balanced Array

• 题意 对每一个$i$，判断是否存在$k ~(1\leqslant k\leqslant \frac {i-1} 2)$，满足对任意的$j~(1 \leqslant j \leqslant i-2k)$，有$a_j+a_{j+2k}=2a_{j+k}$。

• 思路 上述条件等价于$\operatorname{hash}(1,i-2k)+\operatorname{hash}(2k+1,i)=2\operatorname{hash}(k+1,i-k)$，又注意到$k$ 是单调不降的，在遍历$i$ 的时候逐步扩大$k$，判断是否满足要求。

• void eachT() {
      int n = read();
      vector<ll> s(n + 1);
      for (int i = 1; i <= n; ++i) {
          ll ans = 0;
          for (char c = getchar(); c != ' '; c = getchar()) {
              if (c >= '0' && c <= '9') ans = ans * 62 + c - '0';
              else if (c >= 'a' && c <= 'z') ans = ans * 62 + c - 'a' + 10;
              else if (c >= 'A' && c <= 'Z') ans = ans * 62 + c - 'A' + 36;
              else break;
          }
          s[i] = ans + 1;
      }
  
      vector<ull> pow(n + 1), ha(n + 1);
      const int H = 13331;
      pow[0] = 1;
      for (int j = 1; j <= n; j++) {
          pow[j] = pow[j - 1] * H, ha[j] = (ha[j - 1] * H + s[j]);
      } // init
      auto get = [&](int i, int j) {
          return ha[j] - ha[i - 1] * pow[j - i + 1];
      }; // get
  
      string ans;
      for (int i = 1, k = 1; i <= n; ++i) {
          bool flag = 0;
          for (; k <= (i - 1) / 2; ++k) {
              if (get(1, i - 2 * k) + get(2 * k + 1, i) == 2 * get(k + 1, i - k)) {
                  ans += '1'; flag = 1; break;
              }
          }
          if (!flag) ans += '0';
      }
      cout << ans << endl;
  }

E. Matrix Distances

• 题意 求矩阵中所有同色点的 曼哈顿距离(Manhattan distance) 之和。

• 思路 按横坐标和纵坐标分别计算。$m+n$ 次排序的方法会超时（代码一），需优化为只排两次（代码二），时间复杂度$\Theta(mn\log mn)$。

• 代码一

  void eachT() {
      int n = read(), m = read();
      map<int, vector<int> > mp[2];
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= m; j++) {
              int c = read();
              mp[0][c].push_back(i);
              mp[1][c].push_back(j);
          }
      }
      ll ans = 0;
      for (int op = 0; op <= 1; ++op)
          for (auto v : mp[op]) {
              sort(v.s.begin(), v.s.end());
              for (int i = 1; i < v.s.size(); ++i) {
                  ans += i * (v.s.size() - i) * (v.s[i] - v.s[i - 1]);
              }
          }
      printf("%lld\n", ans << 1);
  }

• 代码二

  void eachT() {
      int n = read(), m = read();
      vector<pair<int, int> > mp[2];
      map<int, int> sum;
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= m; j++) {
              int c = read();
              mp[0].push_back({ c,i }); mp[1].push_back({ c,j });
              sum[c]++;
          }
      }
      ll ans = 0;
      for (int op = 0; op <= 1; ++op) {
          sort(mp[op].begin(), mp[op].end());
          ll num = 0;
          for (int i = 1; i < mp[op].size(); ++i) {
              if (mp[op][i - 1].f == mp[op][i].f)
                  ++num, ans += num * (sum[mp[op][i].f] - num) * (mp[op][i].s - mp[op][i - 1].s);
              else num = 0;
          }
      }
      printf("%lld\n", ans << 1);
  }

F. Colorful Balloons

• 题意 找出出现频率 greater than 50% 的字符串。

• void eachT() {
      int n = read();
      map<string, int> mp;
      for (int i = 1; i <= n; i++) mp[readstr()]++;
      for (auto [s, i] : mp) {
          if (i > n / 2) return void(cout << s);
      }
      cout << "uh-oh";
  }

G. Streak Manipulation

• 题意 给定的 01 串，最多把$m$ 个$0$ 变$1$，最大化第$k\ (1\le k\le 5)$ 长的连续$1$ 段的长度。

• 思路 二分答案为$x$，判断是否能得到至少$k$ 个长度$\geqslant x$ 的段。 （止步于此）

  令$f_{i,j,0/1}$ 表示前$i$ 位，得到$j$ 个长度$\geqslant x$ 的段，且当前字符在修改后是否位于第$j$ 段末尾，最少需要修改的次数。

  注意第三维$0/1$ 的含义：不是当前字符是否为$0/1$，$1$ 表示修改后是否位于第$j$ 段连续$1$ 段末尾，$0$ 表示不在。

  初始有$f_{0,0,*} = 1$，其余赋最大值。

  更新$i$：

  • $s_i=1$：
    • 如果原来第$i$ 位位于第$j$ 段末尾，补上$1$ 之后，这一段延长$1$ 个字符，第$i+1$ 位仍位于第$j$ 段末尾，即$f_{i,j,1} \leftarrow f_{i-1,j,1}$；
    • 如果原来第$i$ 位不在第$j$ 段末尾，补上$1$ 之后，仍不在，即$f_{i,j,0} \leftarrow f_{i-1,j,0}$。
  • $s_i=0$：
    • 如果原来第$i$ 位位于第$j$ 段末尾，补上$0$ 之后，可以选择花费一次操作将$0$ 变成$1$，这样仍在第$j$ 段末尾了，也可以选择不操作，这样就不在了，即$f_{i,j,1} \leftarrow f_{i-1,j,1}+1,~f_{i,j,0} \leftarrow f_{i-1,j,1}$；
    • 如果原来第$i$ 位不在第$j$ 段末尾，补上$0$ 之后，仍然不在，即$f_{i,j,0} \leftarrow f_{i-1,j,0}$。

  更新$j$：

  • 新增一长度$\geqslant x$ 的段，最优解是长度恰好为$x$，需要让$[i-x+1, i]$ 位都是$1$，第$i-x$ 位是$0$，因此需要利用$f_{i-x,j-1,0}$ 这个状态，操作的花费是$[i-x+1, i]$ 这段区间中$0$ 的个数，即$f_{i,j,1}=f_{i-x,j-1,0}+\sum_{u} (s_u=0)$，注意需要$i\geqslant x \land j\geqslant 1$。

  总的方程为：

  $$\begin{cases} f_{i,j,0}=f_{i-1,j,0}, & f_{i,j,1}=f_{i-1,j,1}, & \text{if}\quad s_i=1 \\\\ f_{i,j,0}=\min\left(f_{i-1,j,0},f_{i-1,j,1}\right), &f_{i,j,1}=f_{i-1,j,1}+1, & \text{if}\quad s_i=0 \\\\ f_{i,j,1}=f_{i-x,j-1,0}+\sum\limits_{u\in [i-x+1, i] } (s_u=0), & \text{if}\quad i\geqslant x \land j\geqslant 1 \end{cases}$$

  答案是$\min\left(f_{*,k,*}\right)$。复杂度$O(nk\log n)$。

void eachT() {
    int n = read(), m = read(), k = read();
    string s; cin >> s; s = ' ' + s;

    vector<int> cnt0(n + 1);
    for (int i = 1; i <= n; ++i) cnt0[i] = cnt0[i-1] + (s[i] == '0');

    vector f(n + 1, vector(k + 1, vector<int>(2)));
    auto half = [&](int x) {
        f[0][0][0] = f[0][0][1] = 0;
        for (int j = 1; j <= k; ++j) f[0][j][0] = f[0][j][1] = INTINF;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                if (s[i] == '1') {
                    f[i][j][0] = f[i - 1][j][0];
                    f[i][j][1] = f[i - 1][j][1];
                }
                if (s[i] == '0') {
                    f[i][j][0] = min(f[i-1][j][0], f[i-1][j][1]);
                    f[i][j][1] = f[i-1][j][1] + 1;
                }
                if (i >= x && j >= 1) {
                    f[i][j][1] = min(f[i][j][1], f[i-x][j-1][0] + (cnt0[i] - cnt0[i-x]));
                }
            }
        }
        return min(f[n][k][0], f[n][k][1]) <= m;
    };

    int l = 0, r = n, mid = -1, ans = -1;
    while (l <= r) { mid = l + r >> 1; half(mid) ? ans = mid, l = mid + 1 : r = mid - 1; }
    printf("%d\n", ans == 0 ? -1 : ans);
}

• 评注 回看以上过程，我们不需要抉择是「把两个段连起来」或是「在某个段前后操作」，只需选定状态，按某个步骤扫描，找到每个状态的最优化结果，便可知答案。

  有时需在状态中引入新的维度，借助这个维度进行转移。

  其实转移的过程是很贪心的，只需看「需要得到什么」「需要用到哪些状态」，用之前的状态更新当前状态。

• 更多方法

  // https://www.cnblogs.com/PHarr/p/17880645.html
  vector f(n + 1, vector<int>(k + 1));
  auto half = [&](int x) {
      f[0][0] = 0;
      for (int j = 1; j <= k; ++j) f[0][j] = INTINF;
      for (int i = 1; i <= n; i++) {
          f[i] = f[i - 1];
          if (i >= x && s[i - x] != '1') {
              for (int j = 1; j <= k; j++)
                  f[i][j] = min(f[i][j], f[max(0, i - x - 1)][j - 1] + cnt0[i] - cnt0[i - x]);
          }
      }
      return f[n][k] <= m;
  };

  // https://blog.gyx.me/official/icpc/48/hefei/#g.-streak-manipulation
  vector<int> cnt0(n + 1), lst0(n + 1);
  int lst = 0;
  for (int i = 1; i <= n; ++i) {
      cnt0[i] = cnt0[i - 1];
      lst0[i] = lst;
      if (s[i] == '0') lst = i, ++cnt0[i];
  }
  
  vector f(n + 1, vector<int>(k + 1)), mn(n + 1, vector<int>(k + 1));
  auto half = [&](int x) {
      for (int i = 0; i <= n; ++i)
          for (int j = 1; j <= k; ++j) f[i][j] = 1e9;
      for (int j = 1; j <= k; ++j) mn[0][j] = f[0][j];
      for (int i = 1; i <= n; ++i) {
          if (i >= x && (i == n || s[i + 1] == '0')) {
              for (int j = 1; j <= k; ++j)
                  f[i][j] = min(f[i][j], mn[max(0, lst0[i - x + 1] - 1)][j - 1] + cnt0[i] - cnt0[i - x]);
              if (f[i][k] <= m) return 1;
          }
          for (int j = 1; j <= k; ++j) {
              mn[i][j] = min(mn[i - 1][j], f[i][j]);
          }
      }
      return 0;
  };

J. Takeout Delivering

• 题意 有边权无向图，从$1$ 指向$n$ 的路径中，最大边权和次大边权之和的最小值。

• 思路 枚举最大边$e_{uv}$ （主机 想到但被 小明 否认了） ，剩余的路径是$1\to u$ 和$v\to n$，在这上面找出次大边，即找出$1\to u$ 路径上最大边权的最小值和$v\to n$ 路径上最大边权的最小值中较大的那一个。而最大边权的最小值在最小生成树上，只需求出$1\to u$ 和$v\to n$ 最小生成树的最大边。实现时，先分别预处理$1$ 和$n$ 到每个点的路径上的最大边权的最小值，然后枚举边，计算求解。时间复杂度$\Theta(n\log n)$。

• const int maxN = 1e6 + 8;
  int fa[maxN], d[2][maxN];
  vector<pair<int, int> > adj[maxN];
  vector<tuple<int, int, int> > E;
  
  int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
  
  void dfs(int u, int fa, int x) {
      for (auto [v, w] : adj[u]) {
          if (v != fa) {
              d[x][v] = max(d[x][u], w);
              dfs(v, u, x);
          }
      }
  }
  
  void eachT() {
      int n = read(), m = read();
      for (int i = 1; i <= m; ++i) {
          int u = read(), v = read(), w = read();
          E.emplace_back(w, u, v);
      }
      
      // Kruskal
      for (int i = 1; i <= n; ++i) fa[i] = i;
      sort(E.begin(), E.end());
      for (auto [w, u, v] : E) {
          if (find(u) != find(v)) {
              fa[find(u)] = find(v);
              adj[u].emplace_back(v, w);
              adj[v].emplace_back(u, w);
          }
      }
      
      // DFS
      dfs(1, 1, 1);
      dfs(n, n, 0);
      
      // Implementation
      ll ans = INF;
      for (auto [w, u, v] : E) {
          if (d[0][u] <= w && d[1][v] <= w) ans = min(ans, w + max(d[0][u], d[1][v]));
          if (d[1][u] <= w && d[0][v] <= w) ans = min(ans, w + max(d[1][u], d[0][v]));
          // if (u == 1 && v == n || u == n && v == 1) ans = min(ans, w); // 无需特判
      }
      printf("%lld", ans);
  }