VP 2022 ICPC 沈阳

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

这个题解怎么和 Claris 一个 slides 板子，给我看 ptsd 了（

Problems	AC
A. Absolute Difference	待补
B. Binary Substrings
C. Clamped Sequence	○
D. DRX vs. T1	○
E. Graph Completing	⊕
F. Half Mixed	⊕
G. Meet in the Middle	待补
H. P-P-Palindrome	待补
I. Quartz Collection	⊕
J. Referee Without Red
K. Security at Museums
L. Tavern Chess	○
M. Vulpecula

D 签到

void solve() {
    string s;
    cin >> s;
 
    int x = 0;
    int y = 0;
 
    for (auto ch : s) {
        if (ch == 'D') {
            x++;
        }
        if (ch == 'T') {
            y++;
        }
 
        if (x > 2 or y > 2) {
            break;
        }
    }
 
    if (x > 2) {
        puts("DRX");
    } else {
        puts("T1");
    }
}

C

赛时秒出思路但是吃了发罚时，队友提醒了下发现 a[i] 作为上下界都可以，但是忘了枚举其中一种情况。

void solve() {
    int n = read(), d = read();
    int ans = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
 
    for (int i = 1; i <= n; i++) {
        int L = a[i], R = a[i] + d;
 
        int res = 0;
        for (int j = 1; j < n; j++) {
            int x = a[j];
            int y = a[j + 1];
            x = max(x, L);
            x = min(x, R);
            y = max(y, L);
            y = min(y, R);
            res += abs(x - y);
        }
 
        ans = max(ans, res);
    }
 
    for (int i = 1; i <= n; i++) {
        int L = a[i] - d, R = a[i];
 
        int res = 0;
        for (int j = 1; j < n; j++) {
            int x = a[j];
            int y = a[j + 1];
            x = max(x, L);
            x = min(x, R);
            y = max(y, L);
            y = min(y, R);
            res += abs(x - y);
        }
 
        ans = max(ans, res);
    }
    
    cout << ans << '\n';
}

L

炉管题，队友做了。

F 贪心，构造

太神必了这题。

子矩形数量是 $\frac{n(n + 1)}{2} \times \frac{m(m + 1)}{2}$，如果这个数量是奇数则显然无解。
否则 $\frac{n(n + 1)}{2}$ 和 $\frac{m(m + 1)}{2}$ 至少有一个是偶数。不妨设后者是偶数。

赛时打表发现可以将问题转化到一维上去，然后堆叠起来。也就是解决 $1 \times m$ 的问题然后堆叠 $n$ 行。

对于一个 $1 \times m$ 的矩形，子矩形数量是 $\frac{m(m + 1)}{2}$，设每一个同色区间的长度是 $a_i$。那么纯色子区间数量就是 $\sum_{i = 1}^k{\frac{a_i(a_i + 1)}{2}}$，则问题转化为解下列方程组：

• $\sum_{i = 1}^{k} a_i = m$
• $\sum_{i = 1}^k{\frac{a_i(a_i + 1)}{2}} = \frac{m(m + 1)}{4}$

不难证明一定存在一组解，构造时贪心让每个 $a_i$ 尽可能大即可。

void solve() {
    int n, m;
    cin >> n >> m;
 
    vector<int> a(n, 1);
    int h = 0, t = n - 1;
    int tar = n * (n - 1) / 2;
    int val = n;
 
    while (h < t and val < tar) {
 
        int nval = val - a[h] * a[h] + (a[h] + 1) * (a[h] + 1) - 1; 
 
        if (val < nval and nval <= tar) {
            val = nval;
            a[h] += 1;
            t--;
        } else {
            h++;
        }
    }
 
    if (val == tar) {
        puts("Yes");
 
        for (int i = 0, k = 0; i <= t; i++, k ^= 1) {
            for (int rj = 1; rj <= a[i]; rj++) {
                for (int j = 1; j <= m; j++) {
                    cout << k << " \n"[j == m];
                }
            }
        }
        return;
    }
 
    std::swap(n, m);
 
    a.assign(n, 1);
    h = 0, t = n - 1;
    tar = n * (n - 1) / 2;
    val = n;
 
    while (h <= t and val < tar) {
 
        int nval = val - a[h] * a[h] + (a[h] + 1) * (a[h] + 1) - 1; 
        if (val < nval and nval <= tar) {
            val = nval;
            a[h]++;
            t--;
        } else {
            h++;
        }
    }
 
    std::swap(n, m);
 
    if (val == tar) {
        puts("Yes");
 
        for (int i = 1; i <= n; i++) {
            for (int j = 0, k = 0; j <= t; j++, k ^= 1) {
                for (int rj = 1; rj <= a[j]; rj++) {
                    cout << k << " \n"[j == t and rj == a[j]];
                }
            }
        }
        return;
    }
    puts("No");
}

I 贪心、线段树

总的和是固定的，可以将游戏看作每块石头价值 $b_i$，但是先选的话就有 $a_i - b_i$ 的收益，后选的话收益为 $0$。

因此实际上双方就是按照 $a_i - b_i$ 从小到大分别选。A 拿第 0 个，B 拿第 1, 2 个，A 拿第 3, 4 个，以此类推，A 会拿 rank % 4 = 0 或 3 的。

因此维护一个权值线段树，下标是 $a_i - b_i$，维护区间内排名 % 4 相同的数的和即可。

struct SGT {
    int cnt[N << 2];
    int sum[N << 2][4];
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define mid (l + r >> 1)
    void pushup(int p) {
        cnt[p] = cnt[ls] + cnt[rs];
        sum[p][0] = sum[p][1] = sum[p][2] = sum[p][3] = 0;
        for (int i = 0; i < 4; i++) {
            sum[p][i] += sum[ls][i];
            sum[p][(cnt[ls] + i) % 4] += sum[rs][i];
        }
    }

    void upd(int p, int l, int r, int pos, int val) {
        if (l == r) {
            if (val > 0) sum[p][cnt[p] % 4] += pos;
            else sum[p][(cnt[p] - 1) % 4] -= pos;

            cnt[p] += val;
            return;
        }

        if (pos <= mid) upd(ls, l, mid, pos, val);
        else upd(rs, mid + 1, r, pos, val);
        pushup(p);
    }
    void upd(int pos, int val) {
        upd(1, -1e5, 1e5, pos, val);
    }
    int qry(int p = 1) {
        int res = sum[ls][0] + sum[ls][3];

        if (cnt[ls] * 2 % 4 == 0) {
            res += sum[rs][0] + sum[rs][2];
        } else {
            res += sum[rs][1] + sum[rs][3];
        }

        return res;
    }

} seg;

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

    int sumb = 0;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read(), b[i] = read();

        seg.upd(a[i] - b[i], 1);
        sumb += b[i];
    }

    cout << sumb + seg.qry() << '\n';
    for (int i = 1; i <= m; i++) {
        int t = read(), x = read(), y = read();

        sumb -= b[t], sumb += y;
        seg.upd(a[t] - b[t], -1);
        a[t] = x, b[t] = y;
        seg.upd(a[t] - b[t], 1);
        cout << sumb + seg.qry() << '\n';
    }
}

E 边双、容斥、TreeDP

给定一个 $n$ 个点 $m$ 条边的简单无向图，可以加入任意多条（包括 $0$ 条）边，使得这张图边双联通，求加边的方案数。

边双联通的定义：任意不同的两点存在至少两条没有重复边的简单路径。

对原图进行边双缩点，由于原图是连通的，缩点之后会得到一棵树。此时每加一条边 $(u, v)$ 就会对树上 $u$ 到 $v$ 的树上路径进行覆盖，当所有树边都被覆盖时就得到了一个边双连通图。

现在问题转化为：加若干条边，使得这棵树的每条树边都被新加的非树边覆盖至少一次。求方案数。

这个方案数不好求，考虑容斥：设至少有 $k$ 条边没被覆盖的方案数为 $g_k$，则答案为 $\sum_{k}(-1)^{k}g_k$。

把这个容斥扔到树上做 TreeDP。如果一些边被钦定了没被覆盖，那么这些边会把原树划分成若干连通块，连通块内任意连边。

设 $dp_{u, i}$ 表示以 $u$ 为根的子树的连通块大小为 $i$ 时子树内的方案数。转移时考虑一个子树 $v$ 是否连上来（即边 $(u, v)$ 是否被覆盖）。如果连上来的话就是乘上一个 $2^{siz_u + siz_v - 1}$ 的系数（减去的 1 是那条已经有的树边，除此之外的边都可以覆盖这条边），没连上来的话就是容斥系数 $-1$。

注意每个子树根节点的初值应设为 $dp_{u, siz_u} = 2^{\frac{siz_u(siz_u - 1)}{2} - cnte_u}$，其中 $cnte_u$ 表示边双连通分量中的边数。

注意要写个光速幂，这样转移的时候可以少个快速幂的 log。

另，用的是哥哥的 EBCC 板子，发现那个板子算 cnte 好像是有问题的，debug 了半天。。。。而且看了眼哥哥的代码，写的有点过于神秘了，看不懂。。。。。。

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
using std::cerr;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

using pii = std::pair<int, int>;
struct EBCC {
    int n, cur, cnt;
    vector<vector<int>> adj;
    vector<int> stk, dfn, low, bel;
    EBCC() {}
    EBCC(int n) { init(n); }
    void init(int n) {
        this->n = n;
        adj.assign(n, {}), dfn.assign(n, -1);
        low.resize(n), bel.assign(n, -1);
        stk.clear(), cur = cnt = 0;
    }
    void addEdge(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); }
    void dfs(int x, int p) {
        dfn[x] = low[x] = cur++, stk.push_back(x);
        for (auto y : adj[x]) {
            if (y == p) continue;
            if (dfn[y] == -1)
                dfs(y, x), low[x] = std::min(low[x], low[y]);
            else if (bel[y] == -1)
                low[x] = std::min(low[x], dfn[y]);
        }
        if (dfn[x] == low[x]) {
            int y;
            do { y = stk.back(), bel[y] = cnt, stk.pop_back(); } while (y != x);
            cnt++;
        }
    }
    std::vector<int> work() { return dfs(0, -1), bel; }
    struct Graph {
        int n;
        vector<pii> edges;
        vector<int> siz, cnte;
    };
    Graph compress() {
        Graph g; g.n = cnt;
        g.siz.resize(cnt), g.cnte.resize(cnt);
        for (int i = 0; i < n; i++) {
            g.siz[bel[i]]++;
            for (auto j : adj[i]) {
                if (bel[i] < bel[j]) g.edges.emplace_back(bel[i], bel[j]);
                else if (i < j and bel[i] == bel[j]) g.cnte[bel[i]]++;
            }
        }
        return g;
    }
};

template <class T>
constexpr T power(T a, i64 b) { T res {1}; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - (i64)(1.L * a * b / p) * p; res %= p; if (res < 0) res += p; return res; }
template <i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    static i64 Mod;
    constexpr static i64 getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
    constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
    constexpr i64 val() const { return x; }
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    constexpr MInt inv() const { return power(*this, getMod() - 2); }
    constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(x, rhs.x, getMod()); return *this; }
    constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; }
    constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
    friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;

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

    EBCC g(n);
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        u--, v--;
        g.addEdge(u, v);
    }
    g.work();
    auto G = g.compress();

    vector<Z> pw(n + 1), comp(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * 2;
    }
    comp[0] = 1;
    for (int i = 1; i <= n; i++) {
        comp[i] = comp[i - 1] * pw[n];
    }

    int N = n;
    n = G.n;

    auto pow2 = [&](int b) {
        return pw[b % N] * comp[b / N];
    };

    vector<vector<int>> adj(n);
    for (auto [x, y] : G.edges) {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vector dp(n, vector<Z>(N + 1));
    vector<int> siz(n);
    std::function<void(int, int)> dfs = [&](int u, int fa) {
        siz[u] = G.siz[u];
        dp[u][siz[u]] = pow2(siz[u] * (siz[u] - 1) / 2 - G.cnte[u]);

        for (auto v : adj[u]) {
            if (v == fa) continue;
            dfs(v, u);

            vector<Z> ndp(N + 1);
            for (int i = 1; i <= siz[u]; i++) {
                for (int j = 1; j <= siz[v]; j++) {
                    ndp[i + j] += dp[u][i] * dp[v][j] * pow2(i * j - 1);
                    ndp[i] -= dp[u][i] * dp[v][j];
                }
            }

            dp[u] = std::move(ndp);
            siz[u] += siz[v];
        }
    };
    dfs(0, -1);

    Z ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += dp[0][i];
    }

    cout << ans << "\n";
}

signed main() {
    solve();
    return 0;
}