首页 题解

贪心 + 模拟，计数，AC自动机 + 状压dp，神秘题

# A. 魔法（magic）

考场上理解错题意了，几乎爆零。不过似乎大家也都因为被输出卡没了（雾

那么实际上就是一道拿栈模拟的题。

令 R=1R = 1，B=−1B = -1，依次考虑每一个球。

  • 如果当前栈顶的 kk 个元素的和符合条件，那么把栈顶 kk 个元素直接删掉。

  • 把当前球入栈。

感性理解一下发现这东西非常正确。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
int n, R, B;
char s[N];
int stk[N], sum[N], top, cnt;
vector <int> ans[N];

signed main(){
    ios :: sync_with_stdio(false);
    cin >> n >> R >> B >> (s + 1);
    if((!B && !R) || n % (R + B)) return cout << "NO\n", 0;
    int s0 = 0, s1 = 0;
    for(int i = 1; i <= n; ++i)
        s0 += (s[i] == 'R'), s1 += (s[i] == 'B'); 
    if(!B || !R){
        if((!B && s1) || (!R && s0)) return cout << "NO\n", 0;
        if(!B){
            cout << "YES\n" << n / R << '\n';
            for(int i = 1; i <= n / R; ++i){
                for(int j = (i - 1) * R + 1; j <= i * R; ++j) cout << j << ' ';
                cout << '\n';
            }
        }else{
            cout << "YES\n" << n / B << '\n';
            for(int i = 1; i <= n / B; ++i){
                for(int j = (i - 1) * B + 1; j <= i * B; ++j) cout << j << ' ';
                cout << '\n';            
            }
        }
        return 0;
    }
    if(n % (R + B) || s0 % R || s1 % B || s0 / R != s1 / B) return cout << "NO\n", 0;

    for(int i = 1; i <= n; ++i){
        stk[++top] = i, sum[top] = sum[top - 1] + (s[i] == 'R' ? 1 : -1);
        if(top >= R + B && (sum[top] - sum[top - R - B]) == R - B){
            cnt++;
            for(int j = top - R - B + 1; j <= top; ++j) ans[cnt].pb(stk[j]), sum[j] = 0;
            top -= (R + B);
        }
    }
    if(top) return puts("NO"), 0;
    reverse(ans + 1, ans + 1 + cnt);
    cout << "YES\n" << cnt << '\n';
    for(int i = 1; i <= cnt; ++i){
        for(auto x : ans[i]) cout << x << " ";
        cout << '\n';
    }
    return 0;
}

# B. 连通性（floyd）

挺复杂的计数题。

50 分应该还是比较好拿的，n=mn = m 的情况就是贝尔数第 nn 项，也即第二类斯特林数前缀和。

下面说正解。

观察 Floyd\text{Floyd} 运行机制，我们设前 n−mn - m 个点为黑点，后 mm 个点为白点。

那么合法的图一定是下面两种情况之一：

  • 黑白点都有的连通块，对于任意点对 (u,v)(u, v) 都能找到一条路径满足除端点以外都是黑点的路径。

  • 都是白点的连通块，一定是完全图。

也就是说如果一个连通块里有黑点，那么黑点的导出子图必须连通，且每个白点至少与一个黑点相连。

然后就可以 dp\text{dp} 了。

先设 gng_n 表示 nn 个点的简单无向连通图个数。

转移是经典容斥：总的 - 不连通的个数。枚举 1 所在连通块大小：

gn=2n(n−1)2−∑i=1n−1gi×2(n−i)(n−i−1)2×(n−1i−1)g_n = 2^{\frac {n(n-1)}{2}} - \sum_{i = 1}^{n - 1}g_i\times2^{\frac {(n - i)(n - i - 1)}{2}} \times \dbinom{n - 1}{i - 1}

不解释了。

然后设 fn,mf_{n, m} 表示黑点有 nn 个，白点 mm 个时的答案，那么有转移：

  • 全是白点，枚举最后一个连通块内有几个点：

f0,m=∑i=1mf0,m−i(m−1i−1)f_{0, m} = \sum_{i = 1}^mf_{0, m - i}\dbinom{m - 1}{i - 1}

  • 有黑点，枚举 1 的连通块内几黑几白：

fn,m=∑i=1n∑j=0mfn−i,m−j(n−1i−1)(mj)hi,jf_{n, m} = \sum_{i = 1}^n\sum_{j = 0}^mf_{n - i, m - j}\dbinom{n - 1}{i - 1}\dbinom{m}{j}h_{i, j}

这个 hi,jh_{i, j} 表示 ii 个黑点和 jj 个白点连通的方案数，有：

hi,j=gi×(2i−1)j×2j(j−1)2h_{i, j} = g_i \times (2^i - 1)^j \times 2^{\frac {j(j - 1)}{2}}

就是 ii 个黑点组成连通图的方案数 gig_i，每个白点至少和一个黑点相连且有 jj 个白点 (2i−1)j(2^i - 1)^j，白点内任意连边 2j(j−1)22^{\frac{j(j - 1)}{2}}。

fn,mf_{n, m} 通过 O(n4)O(n^4) 复杂度预处理出来即可。

然后就没了。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 110;
const int mod = 1e9 + 7;
int T, n, m;
int g[N], pw[N * N], h[N][N];
int C[N][N], f[N][N];

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}

inline void init(int n){
    for(int i = 0; i <= n; ++i) C[i][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j) C[i][j] = add(C[i - 1][j - 1] + C[i - 1][j]);
    pw[0] = 1;
    for(int i = 1; i <= n * n; ++i) pw[i] = add(pw[i - 1] + pw[i - 1]);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j < i; ++j) g[i] = add(g[i] + mul(g[j], mul(pw[(i - j) * (i - j - 1) / 2], C[i - 1][j - 1])));
        g[i] = sub(pw[i * (i - 1) / 2] - g[i]);
    }

    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
            h[i][j] = mul(g[i], mul(qpow(pw[i] - 1, j), pw[j * (j - 1) / 2]));

    f[0][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            f[0][i] = add(f[0][i] + mul(C[i - 1][j - 1], f[0][i - j]));
    for(int a = 1; a <= n; ++a)
        for(int b = 0; b <= n - a; ++b)
            for(int i = 1; i <= a; ++i)
                for(int j = 0; j <= b; ++j){
                    f[a][b] = add(f[a][b] + mul(mul(f[a - i][b - j], C[a - 1][i - 1]), mul(C[b][j], h[i][j])));
                }
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    init(N - 10);
    cin >> T;
    while(T--){
        int n, m; cin >> n >> m;
        cout << f[n - m][m] << '\n';
    }
    return 0;
}

# C. 文本串的价值（value）

把 AC 自动机建出来。

先说暴力 dp\text{dp}，设 fi,j,Sf_{i, j, S} 表示匹配到文本串 ss 的第 ii 个字符，在 trie\text{trie} 图上的 jj 号点，当前填了状态为 SS 的字符。

转移时判断 ss 的下一位是不是问号，是的话枚举字符，不是的话直接跳。

注意：你要记录模式串的贡献时要在 trie 图上做链和（根到当前点的链和）。

不是子树和！！！不是子树和！！！不是子树和！！！

然后你就能拿到 30 分的好成绩。

观察到如果 si+1s_{i + 1} 不是问号，转移是固定的，我们还要枚举实在是浪费。

并且最多只有 14 个问号。

所以我们预处理出来 dpi,jdp_{i, j} 表示在第 ii 个问号且当前在 trie 图上 jj 号点，依次跳每个字符到 i+1i + 1 个问号之前会到达哪个点，且中间会得到多少收益。

这样一来，我们转移的时候可以先枚举状态 SS，计算出当前是在哪两个问号之间跳，然后枚举转移字符 cc，当前位置 jj 就可以转移了。

时间复杂度 O(214∣T∣)O(2^{14}|T|)，有个字符集的常熟。

感觉正解比暴力好写。

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
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;

const int N = 4e5 + 10;
int k, n;
char s[N], t[N];

int ch[N][15], tot, num[N];

inline void insert(char *s, int x){
    int len = strlen(s), u = 0;
    for(int i = 0; i < len; ++i){
        int c = s[i] - 'a';
        if(!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    num[u] += x;
}

int fail[N];

inline void build(){
    queue <int> q;
    for(int i = 0; i < 14; ++i)
        if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(int i = 0; i < 14; ++i){
            if(ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
            else ch[x][i] = ch[fail[x]][i];
        }
    }
}

typedef pair<int, int> P;
int f[1010][(1 << 14) + 5], g[1010][(1 << 14) + 5];
P dp[1010][1010];
int p[N], cnt;

inline void Max(int &x, int y) {x = x > y ? x : y;}

vector <int> G[N];

inline void dfs(int x){
    for(auto y : G[x]) num[y] += num[x], dfs(y);
}

signed main(){
// #ifndef ONLINE_JUDGE
//     freopen("test.in", "r", stdin);
//     freopen("test.out", "w", stdout);
// #endif
    cin >> k;
    for(int i = 1, x; i <= k; ++i)
        cin >> t >> x, insert(t, x);
    build();
    for(int i = 1; i <= tot; ++i) G[fail[i]].pb(i);
    dfs(0);

    cin >> (s + 1), n = strlen(s + 1);
    for(int i = 1; i <= n; ++i)
        if(s[i] == '?') p[++cnt] = i;
    p[cnt + 1] = n + 1;
    for(int i = 0; i <= cnt; ++i)
        for(int j = 0; j <= tot; ++j){
            int x = j, v = 0;
            for(int l = p[i] + 1; l < p[i + 1]; ++l) x = ch[x][s[l] - 'a'], v += num[x];
            dp[i][j] = {x, v};
        }

    // f([i])[j][s]: s 第 i 个字符，树上 j 点，状态 S 
    memset(f, -0x3f, sizeof(f));
    f[dp[0][0].fi][0] = dp[0][0].se;
    int ans = -1e9;
    for(int S = 0; S < (1 << 14); ++S){
        int c1 = __builtin_popcount(S);
        if(c1 == cnt) for(int i = 0; i <= tot; ++i) Max(ans, f[i][S]);
        if(c1 >= cnt) continue;
        for(int c = 0; c < 14; ++c){
            if(S & (1 << c)) continue;
            for(int i = 0; i <= tot; ++i)
                Max(f[dp[c1 + 1][ch[i][c]].fi][S | (1 << c)], f[i][S] + dp[c1 + 1][ch[i][c]].se + num[ch[i][c]]);
        }
    }
    cout << ans << '\n';


    // 暴力
    // for(int i = 0; i < n; ++i){
    //     for(int j = 0; j <= tot; ++j){
    //         memcpy(g[j], f[j], sizeof(f[j]));
    //         memset(f[j], -0x3f, sizeof(f[j]));
    //     }
    //     for(int j = 0; j <= tot; ++j){
    //         if(s[i + 1] != '?'){
    //             int k = ch[j][s[i + 1] - 'a'];
    //             for(int S = 0; S < (1 << 14); ++S){
    //                 if(g[j][S] >= -1e9) Max(f[k][S], g[j][S] + num[k]);
    //             }
    //         }else{
    //             for(int c = 0; c < 14; ++c){
    //                 for(int S = 0; S < (1 << 14); ++S){
    //                     if(g[j][S] >= -1e9 && !((S >> c) & 1)){
    //                         int k = ch[j][c];
    //                         Max(f[k][S | (1 << c)], g[j][S] + num[k]);
    //                     }
    //                 }
    //             }
    //         }
    //     }
    // }
    // for(int j = 0; j <= tot; ++j)
    //     for(int S = 0; S < (1 << 14); ++S)
    //         ans = max(ans, f[j][S]);
    // cout << ans << '\n';
    return 0;
}

# D. 排列（permutation）

没看，不会（

自己看题解吧。

更新于 阅读次数 次