VP 2023 ICPC 网络赛 第一场

The 2022 ICPC Asia Regionals Online Contest (I)
Date 2025.08.28
Solved 6 / 12

A	B	C	D	E	F	G	H	I	J	K	L
O		O	O			O	O				O

L - LCS-like Problem

预处理下字符串是否可以匹配转移，然后 dp

void solve() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    s = " " + s, t = " " + t;

    vector ban(26, vector(26, 0));
    vector<int> vis(26);

    for (int i = m; i >= 1; i--) {
        int ch = t[i] - 'a';
        for (int j = 0; j < 26; j++) {
            if (vis[j]) ban[ch][j] = 1;
        }
        vis[ch] = 1;
    }

    vector<int> dp(26);
    for (int i = 1; i <= n; i++) {
        auto ndp = dp;
        int ch = s[i] - 'a';

        for (int j = 0; j < 26; j++) {
            if (!vis[ch]) {
                ndp[j]++;
            } else if (!ban[j][ch]) {
                ndp[ch] = max(ndp[ch], dp[j] + 1);
            }
        }

        dp = move(ndp);
    }

    int ans = 0;
    for (int i = 0; i < 26; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
}

G - Read the Documentation

直接 dp

int x[5], s[105];
int dp[6][52][35][27][22];

void solve() {
    int n = read(), T = read();

    for (int i = 1; i <= 4; i++) {
        x[i] = x[i - 1] + read();
    }
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + read();
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int a = 0; a <= n / 2 + 1; a++) {
            for (int b = 0; b <= n / 3 + 1; b++) {
                for (int c = 0; c <= n / 4 + 1; c++) {
                    for (int d = 0; d <= n / 5 + 1; d++) {
                        if (a * x[1] + b * x[2] + c * x[3] + d * x[4] > T) break;

                        int res = dp[(i + 5) % 6][a][b][c][d];
                        if (a >= 1 and i >= 1) res = max(res, dp[(i + 4) % 6][a - 1][b][c][d] + s[i] - s[i - 1]);
                        if (b >= 1 and i >= 2) res = max(res, dp[(i + 3) % 6][a][b - 1][c][d] + s[i] - s[i - 2]);
                        if (c >= 1 and i >= 3) res = max(res, dp[(i + 2) % 6][a][b][c - 1][d] + s[i] - s[i - 3]);
                        if (d >= 1 and i >= 4) res = max(res, dp[(i + 1) % 6][a][b][c][d - 1] + s[i] - s[i - 4]);

                        dp[i % 6][a][b][c][d] = res;
                        ans = max(ans, res);
                    }
                }
            }
        }
    }

    cout << ans << '\n';
}

A - 01 Sequence

考虑最多可以进行多少次删除操作。
对于连续 $k$ 个 1 ，可以进行 $\left\lceil\frac{k}{2}\right\rceil$ 次操作。
优先进行不会导致 1 的连续段合并的操作。
如果所有删除都会导致 1 的连续段合并，则说明序列中没有相邻的 0 ，显然能够删完。
而每次修改可以增加 1 次操作次数。
因此答案为 $\max \lbrace 0, \frac{r-l+1}{3}-\Sigma\lceil \frac{k_i}{2}\rceil \rbrace$ 。
预处理左右连续段长度和前缀和，即可 $O(1)$ 回答询问。

void solve() {
    int n = read(), q = read();
    string s; cin >> s;
    s = " " + s;

    int las = -1;
    vector<int> sum(n + 5), pre(n + 5), suf(n + 5);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1];
        if (s[i] == '1' and las != i - 1) {
            sum[i]++, las = i;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') {
            suf[i] = suf[i - 1] + 1;
        } else {
            suf[i] = 0;
        }
    }
    for (int i = n; i >= 1; i--) {
        if (s[i] == '1') {
            pre[i] = pre[i + 1] + 1;
        } else {
            pre[i] = 0;
        }
    }

    while (q--) {
        int l = read(), r = read();
        auto calc = [&]() -> int {
            int ll = l + pre[l], rr = r - suf[r];
            if (ll >= rr) return (r - l + 1 + 1) / 2;
            return sum[rr] - sum[ll - 1] + (pre[l] + suf[r] + 1) / 2;
        };
        int res = max(0LL, (r - l + 1) / 3 - calc());
        cout << res << '\n';
    }
}

H - Step Debugging

写一个 parser 模拟即可

Z go() {
    Z res = 0;
    while (1) {
        string s; cin >> s;
        if (s == "for") {
            break;
        } else if (s == "library") {
            res += 1;
        } else if (s == "repeat") {
            res += go();
        }
    }
    int coef; cin >> coef;
    return coef * res;
}

void solve() {
    Z ans = 0;
    while (1) {
        string s; cin >> s;
        if (s == "fin") {
            break;
        } else if (s == "library") {
            ans += 1;
        } else if (s == "repeat") {
            ans += go();
        }
    }

    cout << ans << '\n';
}

C - Delete the Tree

把整棵树删完等价于整张图 0 / 1 度点总数量为 0

void solve() {
    int n = read();

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u = read();
        int v = read();
        g[u].eb(v);
        g[v].eb(u);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i].size() <= 1) ans++;
    }
    cout << ans << '\n';
}

D - Find the Number

可以类似于数位 dp 那样，也可以直接预处理，发现合法的数最多 5e5 个。

int a[500], num = 0;
vector<int> ans;

void dfs(int p) {   
    // debug(p);
    if (p > 30) {
        if (num) return;

        int res = 0;
        for (int i = 1, bas = 1; i <= 30; i++, bas *= 2) {
            if (a[i]) res += bas;
        }
        ans.eb(res);
        return;
    }

    if (num) {
        num--;
        a[p] = 1, dfs(p + 1);
        num++;
    }

    a[p] = 0, dfs(p + 1);
}

void solve() {
    int L = read();
    int R = read();

    int x = ranges::lower_bound(ans, L) - ans.begin();

    if (x >= ans.size() or ans[x] > R) {
        cout << "-1\n";
        return;
    }

    cout << ans[x] << '\n';
}

signed main() {
    for (int i = 1; i <= 16; i++) {
        for (int j = 1; j <= i; j++) a[j] = 0;
        a[i + 1] = 1; num = i - 1;
        dfs(i + 2);
    }

    ranges::sort(ans);
    ans.erase(unique(ans.begin(), ans.end()), ans.end());

    // debug(ans.size());

    for (int T = read(); T--; solve());
    // solve();
    return 0;
}