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)$，有 $aj+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$。
总的方程为：
答案是 $\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);
}