跳转至

260120 模拟赛

T1

给定两个字符串 \(S,T\)，对于 \(S\) 中的每种字符，你可以选择一段区间并保留这个区间内的所有这个字符。你需要让最后剩下来的子序列等于 \(T\)。

\(S\) 的每个下标有一个权值，最大化剩余下标的权值和。

\(1\le |T|\le |S|\le 2\times 10^5\)

我们可以看成是向 \(T\) 的空隙中插入字符，最终得到 \(S\)。注意到 \(T\) 的每个空隙中都有一些不能插入的字符，然后又注意到“不能插入的字符”形成的连续段只有 \(O(\Sigma)\) 段，因此考虑对这个连续段 dp。对于每一个段，我们删去 \(S\) 中那些可以出现在段中的字符，因为它们不用被考虑；然后剩下的字符要和 \(T\) 匹配，可以用哈希实现，时间复杂度 \(O(n|\Sigma|)\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000021;

int n, m;
string s, t;

int mn[26], mx[26];
bool valid[60][26];
string seg[60]; int nn;

int pw[N], h2[N], pos[N], len[N];
ll f[N], g[N], w[N], sum[N];

inline int get_hash(string s) {
    int res = 0;
    for(int i = 1; i < s.size(); i++) res = ((ll)res * 29 + s[i] - 'a' + 1) % MOD;
    return res;
}
inline int get_hash(int l, int r) {
    if(l == r) return s[l] - 'a' + 1;
    return (h2[r] - (ll)h2[l - 1] * pw[len[r] - len[l - 1]] % MOD + MOD) % MOD;
}

int main() {

    pw[0] = 1;
    for(int i = 1; i < N; i++) pw[i] = (ll)pw[i - 1] * 29 % MOD;

    cin >> s >> t;
    n = s.size(), m = t.size();
    s = " " + s; t = " " + t;

    for(int i = 1; i <= n; i++) cin >> w[i];

    for(int i = 0; i < 26; i++) mn[i] = N;
    for(int i = 1; i <= m; i++) {
        mn[t[i] - 'a'] = min(mn[t[i] - 'a'], i);
        mx[t[i] - 'a'] = max(mx[t[i] - 'a'], i);
    }

    for(int j = 0; j < 26; j++) valid[0][j] = 1;
    for(int i = 1; i <= m; i++) {
        if(mn[t[i] - 'a'] == i || mx[t[i] - 'a'] == i) {
            ++nn;
            for(int j = 0; j < 26; j++) valid[nn][j] = valid[nn - 1][j];
            if(mn[t[i] - 'a'] == i) valid[nn][t[i] - 'a'] = 0;
            if(mx[t[i] - 'a'] == i) valid[nn][t[i] - 'a'] = 1;
        }
        seg[nn].push_back(t[i]);
    }

    for(int i = 1; i <= nn; i++) {
        for(int j = 0; j <= n; j++) g[j] = -INF;
        for(int j = 1; j <= n; j++) {
            if(!valid[i][s[j] - 'a']) {
                len[j] = len[j - 1] + 1;
                h2[j] = ((ll)h2[j - 1] * 29 + s[j] - 'a' + 1) % MOD;
                pos[len[j]] = j;
                sum[j] = sum[j - 1] + w[j];
            } else {
                len[j] = len[j - 1];
                h2[j] = h2[j - 1];
                sum[j] = sum[j - 1];
            }
        }
        int tmp = get_hash(seg[i]);
        for(int j = 1; j <= n; j++) {
            // 我们将字符划在它后面的空隙段上
            // 如果某个字符是最后一次出现，那么它在段内会被直接删掉，因此哈希需要扣掉段内的第一个字符
            if(s[j] == seg[i].front() && f[j - 1] >= 0 && len[j] + seg[i].size() - 1 <= len[n])
            if(tmp == get_hash(j + 1, max(j, pos[len[j] + seg[i].size() - 1]))) {
                int t = max(j, pos[len[j] + seg[i].size() - 1]);
                g[t] = max(g[t], f[j - 1] + sum[t] - sum[j] + w[j]);
            }
        }
        for(int j = 1; j <= n; j++) {
            if(valid[i][s[j] - 'a']) {
                g[j] = max(g[j], g[j - 1]);
            }
        }
        for(int j = 0; j <= n; j++) f[j] = g[j];
    }

    ll ans = f[n];
    if(ans < 0) cout << -1 << '\n';
    else {
        ans = -ans;
        for(int i = 1; i <= n; i++) ans += w[i];
        cout << ans << '\n';
    }

    return 0;
}

T2

给定一棵树的两种黑白染色方案 \(T_1,T_2\)。每次你可以选择 \(T_1\) 上的两个点，如果它们颜色相同则同时 flip，否则不变。问将 \(T_1\) 变成 \(T_2\) 的最小步数。若不能则为 \(0\)。

\(T_1\) 和 \(T_2\) 中有一些 ?，你需要对于所有将 ? 填成 01 的方案求出最小步数之和。

\(n\le 5\times 10^5\)

先把奇数层的颜色全都 flip，这是二分图经典 trick，这样操作就转化为交换两个点的颜色。然后我们可以通过归纳法证明，每条边的交换次数为子树内 0 的数量之差的绝对值（1 同理）。

然后考虑对所有方案求答案之和，考虑把贡献拆到每条边上，对于一条边 \(u,v\)，其贡献为：

\[ \sum_{k}|k+z|\Biggl(\sum_{i}\binom{a}{i}\binom{b}{i+k}\Bigg)\Biggl(\sum_{i}\binom{A-a}{i}\binom{B-b}{i-k-d}\Bigg) \]

其中 \(a,b\) 表示两种染色方案中子树内 ? 的数量，\(A,B\) 表示原树中 ? 的数量，\(z\) 表示子树内初始时 0 数量之差，\(d\) 表示原树中初始的 0 数量之差。

注意到后面四个组合数形如两个范德蒙德卷积，因此式子等于：

\[ \sum_{k}\binom{a+b}{b-k}\binom{A+B-a-b}{B-b+k+d}|k+z| \]

此时我们获得了一个 \(O(n^2)\) 的做法。正解考虑令 \(k\gets b-k\)

\[ \sum_{k}\binom{a+b}{k}\binom{A+B-a-b}{B-k+d}|b-k+z| \]

令 \(A\gets A+B,~B\gets B+d\)，记

\[ F(x,y)=\sum_{k}\binom{x}{k}\binom{A-x}{B-k}|k-y| \]

然后考虑某种莫队（dsu on tree），尝试 \(O(1)\) 从 \(F(x,y)\) 递推到 \(F(x+1,y),F(x,y+1),F(x,y-1)\)，然后先遍历重儿子，再加入轻儿子的贡献，就可以实现 \(O(n\log n)\) 的复杂度。

考虑如何加减 \(1\)。将式子拆成

\[ F(x,y)=\sum_{k}\binom{x}{k}\binom{A-x}{B-k}(k-y)+2\sum_{k\le y}\binom{x}{k}\binom{A-x}{B-k}(y-k) \]

对于第一项，使用 \(\binom{x}{k}k=\binom{x-1}{k-1}x\) 即可化为范德蒙德卷积。对于第二项，考虑 x++ 操作，如果 \(x<y\) 那么 \(k\) 的实际上界为 \(x\)，后面可以写成范德蒙德卷积；如果 \(x\ge k\) 那么可以通过组合意义（前半部分）和一些推导（后半部分）得到增量为

\[ (-2y)\binom{x}{y}\binom{A-x-1}{B-y-1}+2(x+1)\binom{x-1}{y-1}\binom{A-x-1}{B-y-1}-2\sum_{k\le y}\binom{x-1}{k-1}\binom{A-x}{B-k} \]

第三项可以额外用一个变量 \(c\) 记录 \(\sum_{k\le y}\binom{x-1}{k-1}\binom{A-x}{B-k}\)，其增量也可以用组合意义导出，为 \(\binom{x-1}{y-1}\binom{A-x-1}{B-y-1}\)（边界 \(\binom{A-1}{B-1}\text{ for }1=x<y\)）。这里说的组合意义就是，考虑范德蒙德卷积的组合意义，然后发现一种方案变成不合法当且仅当它前面选了 \(k\) 个，并且第 \(x+1\) 个也被选了。

考虑 y++ 操作，稍作推导可得增量为

\[ \sum_{k\le y}\binom{x}{k}\binom{A-x}{B-k} \]

这玩意用另一个变量 \(d\) 记录，在 x++ 时需要同步更新 \(d\)（用组合意义可得增量为 \(\binom{x}{y}\binom{A-x-1}{B-y-1},x>y\)，\(d\) 的初值为 \(\binom{A}{B}\)），y++ 时也需要同步更新 \(c\)。y-- 和 y++ 基本一致。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// 代码中 c,d 和上文是反的，但不影响阅读
#include<iostream>
typedef long long ll;
using namespace std;
const int N = 5e5 + 10;
const int MOD = 1e9 + 7;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }
inline int mod(int x) { return (x >= MOD) ? x - MOD : x; }

struct Edge {
    int v, next;
} pool[2 * N]; int ne, head[N];
inline void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]}; head[u] = ne;
}

int n, ans;
int dep[N], sz[N], son[N];
int a[N], b[N], sa[N][2], sb[N][2];
int A, B, x, y, c, d, sum;

int fac[2 * N], ifac[2 * N], inv[2 * N];
inline ll C(int a, int b) { if(b < 0 || b > a) return 0; return (ll)fac[a] * ifac[a - b] % MOD * ifac[b] % MOD; }

inline void clear() {
    x = y = c = d = sum = 0;
    c = C(A, B);
}
inline void x_inc() {
    if(x < y) {
        add(sum, MOD - 2ll * C(A - 1, B - 1) % MOD);
        if(x == 0) add(d, C(A - 1, B - 1));
        return;
    }
    add(sum, MOD - 2ll * y % MOD * C(x, y) % MOD * C(A - x - 1, B - y - 1) % MOD);
    add(sum, MOD - 2ll * d % MOD);
    add(sum, 2ll * (x + 1) * C(x - 1, y - 1) % MOD * C(A - x - 1, B - y - 1) % MOD);
    add(c, MOD - C(x, y) * C(A - x - 1, B - y - 1) % MOD);
    add(d, MOD - C(x - 1, y - 1) * C(A - x - 1, B - y - 1) % MOD);
}
inline void y_inc() {
    add(sum, mod(2 * c));
    add(c, C(x, y + 1) * C(A - x, B - y - 1) % MOD);
    add(d, C(x - 1, y) * C(A - x, B - y - 1) % MOD);
}
inline void y_dec() {
    add(d, MOD - C(x - 1, y - 1) * C(A - x, B - y) % MOD);
    add(c, MOD - C(x, y) * C(A - x, B - y) % MOD);
    add(sum, MOD - mod(2 * c));
}
inline void ins(int p) {
    if(a[p] == 2) x_inc(), x++;
    else if(a[p] == 0) y_dec(), y--;
    if(b[p] == 2) x_inc(), x++, y_inc(), y++;
    else if(b[p] == 0) y_inc(), y++;
}
inline int query() {
    return (x * C(A - 1, B - 1) - y * C(A, B) % MOD + MOD + sum) % MOD;
}

void dfs1(int u, int fa) {
    dep[u] = dep[fa] + 1;
    sz[u] = 1;
    if(dep[u] & 1) {
        if(a[u] <= 1) a[u] ^= 1;
        if(b[u] <= 1) b[u] ^= 1;
    }
    if(a[u] == 0) sa[u][0]++;
    else if(a[u] == 2) sa[u][1]++;
    if(b[u] == 0) sb[u][0]++;
    else if(b[u] == 2) sb[u][1]++;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs1(v, u);
        if(sz[v] > sz[son[u]]) son[u] = v;
        sz[u] += sz[v];
        sa[u][0] += sa[v][0];
        sa[u][1] += sa[v][1];
        sb[u][0] += sb[v][0];
        sb[u][1] += sb[v][1];
    }
}

void dfs3(int u, int fa) {
    ins(u);
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs3(v, u);
    }
}

void dfs2(int u, int fa) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa || v == son[u]) continue;
        dfs2(v, u);
        clear();
    }
    if(son[u]) dfs2(son[u], u);
    ins(u);
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa || v == son[u]) continue;
        dfs3(v, u);
    }
    add(ans, query());
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    inv[1] = fac[0] = ifac[0] = 1;
    for(int i = 2; i < 2 * N; i++) inv[i] = MOD - (ll)inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < 2 * N; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
    for(int i = 1; i < 2 * N; i++) ifac[i] = (ll)ifac[i - 1] * inv[i] % MOD;

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }
    for(int i = 1; i <= n; i++) {
        char c; cin >> c;
        if(c <= '1') a[i] = c - '0';
        else a[i] = 2;
    }
    for(int i = 1; i <= n; i++) {
        char c; cin >> c;
        if(c <= '1') b[i] = c - '0';
        else b[i] = 2;
    }

    dfs1(1, 0);

    A = sa[1][1] + sb[1][1];
    B = sb[1][1] + (sb[1][0] - sa[1][0]);
    clear();

    dfs2(1, 0);
    cout << ans << endl;

    return 0;
}