Codeforces Round 537 (Div. 2) 题解

发表于 | 分类于 |
字数统计: 2,798 字

这次比赛难度适中，有一些题目的idea比较巧妙。

A

题目大意：给定两个字符串，定义一次转换为将某一个元音（或者辅音）字母转换为另一个元音（或者辅音）字母。判断第一个字符串能否经过有限次数的转换得到第二个字符串。

只要判断两个字符串对应位置的字母种类是否相同即可。

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
char s[1005], t[1005];
void init(){
    scanf("%s%s", s, t);
}
bool isv(char ss){
    return ss == 'a' || ss == 'e' || ss == 'i' || ss == 'o' || ss == 'u';
}
void solve(){
    int len = strlen(s);
    if(strlen(t) != len){
        printf("No\n");
        return ;
    }
    for(int i = 0; i < len; ++i){
        if(isv(s[i]) ^ isv(t[i])){
            printf("No\n");
            return ;
        }
    }
    printf("Yes\n");
}
int main(){
    init();
    solve();
    return 0;
}

B

题目大意：给定长度为$n$的数列。定义一次操作为：将数列中一个数移除，或者将其中一个数加1。总共可以做$m$次操作，对一个数最多做$k$次操作。求操作后数列（非空）均值的最大值。

枚举删除序列的长度。长度一定时，删去数列中最小的那些数，给剩下的数进行自增是最优操作。因此对原序列排序，构造前缀和，然后枚举长度，计算并更新答案即可。

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k, m, a[100005];
ll sum[100005];
void init(){
    n = read(), k = read(), m = read();
    sum[0] = 0;
    for(int i = 1; i <= n; ++i)
        a[i] = read();
}
void solve(){
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + 1ll * a[i];
    if(n == 1) {
        printf("%d\n", a[1] + min(k, m));
    }else{
        double ans = 0;
        
        for(int i = 0; i <= min(n - 1, m); ++i){
            ll tt = sum[n] - sum[i] + min(1ll * k * (n - i), 1ll * (m - i));
            ans = max(ans, (double)tt / (n - i));
        }
        printf("%.15lf\n", ans);
    }
}
int main(){
    init();
    solve();
    return 0;
}

C

题目链接

分治，先对每个敌人所在位置排序，然后设$solve(l, r, l’, r’)$返回的是长度区间是$[l’, r’]$，敌人下标为$l$到$r$，且敌人的坐标全部在区间内的代价。然后分类讨论：

  1. 区间内没有敌人，直接返回$A$。
  2. 区间内有敌人，设$mid’=\frac{l’+r’}{2}$，二分出$mid$使得下标从$l$到$mid$的敌人全部在$[l’, mid’]$上，下标从$mid+1$到$r$的敌人全部在$[mid’+1, r’]$上，然后返回$\min\lbrace B(r-l+1)(r’-l’+1),solve(l, mid, l’, mid’)+solve(mid+1, r, mid’+1, r’) \rbrace$。前者表示直接消灭这一段的代价，后者表示分两半消灭的代价。

这个算法的时间复杂度感觉是比$O(nk\log k)$小？

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k, A, B;
int pos[100005];
ll solve1(int hd, int tl, int st, int ed, int rk){
    if(tl < hd) return A;
    if(ed == st)
        return 1ll * B * (tl - hd + 1);
    ll res = 1ll * B * (tl - hd + 1) * (ed - st + 1);
    int mid = (st + ed) >> 1, cur;
    cur = upper_bound(pos + hd, pos + tl + 1, mid) - pos;
    res = min(res, solve1(hd, cur - 1, st, mid, rk - 1) + solve1(cur, tl, mid + 1, ed, rk - 1));
    return res;
}
void init(){
    n = read(), k = read(), A = read(), B = read();
    for(int i = 1; i <= k; ++i)
        pos[i] = read();
    sort(pos + 1, pos + 1 + k);
}
void solve(){
    printf("%I64d\n", solve1(1, k, 1, 1 << n, n));
}
int main(){
    init();
    solve();
    return 0;
}

D

题目大意：给定一个偶数长度的字符串，可以将字符串中的任意两个字符交换位置。定义一个串是合法的，当且仅当该串中某一种类的字符全部出现在串的前半部分或者后半部分。有$q$次询问，每次询问求下标为$x$和$y$的字符在同一个半部分时，不同的合法的串数目。

只有52种字符，而询问高达1e5次，显然要预处理出所有答案。
合法串数目的计算可以归约为背包问题和组合问题，前者把一种字符的数目抽象为物品的体积，串长的一半抽象为背包的容纳量，后者考虑字符分配完之后排列的种数。根据公式答案为，其中$n$为串长，为每一种字符的数目。
现在考虑删去两个物品之后的背包问题如何从原问题得到。因为背包问题中，物品的顺序不影响最终答案，因此可以假定这两个物品是最后考虑的。之前的遍历方式是体积从大到小加，现在要减就从小到大减，即：

1
2
for(int k = w[j]; k <= (n >> 1); ++k){
    ff[k] -= ff[k - w[j]];

这样就可以去除掉一个物品的影响。
如此，整个算法的时间复杂度为$O(2704n+q)$。

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
#include <bits/stdc++.h>
#define INF 2000000000
#define P 1000000007
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
char s[100005];
int n, f[50005] = {0}, ans[55][55] = {0}, w[55] = {0};
int ff[50005] = {0}, cons;
int dfac[50005], inv[50005];
int getid(char c){
    return islower(c) ? c - 'a' + 26: c - 'A';
}
void init(){
    scanf("%s", s);
    n = strlen(s);
    for(int i = 0; i < n; ++i)
        w[getid(s[i])]++;
    dfac[0] = dfac[1] = inv[1] = 1;
    int fac = 1;
    for(int i = 2; i <= (n >> 1); ++i){
        inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
        fac = 1ll * fac * i % P;
        dfac[i] = 1ll * dfac[i - 1] * inv[i] % P;
    }
    cons = 1ll * fac * fac % P;
    for(int i = 0; i < 52; ++i)
        if(w[i] <= (n >> 1)) cons = 1ll * cons * dfac[w[i]] % P;
        else {
            cons = 0;
            break;
        }
    
    f[0] = 1;
    for(int i = 0; i < 52; ++i){
        if(!w[i]) continue;
        for(int j = (n >> 1); j >= w[i]; --j)
            f[j] = (f[j] + f[j - w[i]]) % P;
    }
        
    for(int i = 0; i < 52; ++i){
        for(int j = i; j < 52; ++j){
            memcpy(ff, f, sizeof(f));
            for(int k = w[i]; k <= (n >> 1); ++k){
                ff[k] -= ff[k - w[i]];
                if(ff[k] < 0) ff[k] += P;
            }
            if(i != j){
                for(int k = w[j]; k <= (n >> 1); ++k){
                    ff[k] -= ff[k - w[j]];
                    if(ff[k] < 0) ff[k] += P;
                }
            }
            ans[i][j] = ans[j][i] = ff[n >> 1];
        }
    }
}
void solve(){
    int q = read();
    while(q--){
        int i = read() - 1, j = read() - 1;
        printf("%d\n", 2ll * cons * ans[getid(s[i])][getid(s[j])] % P);
    }
}
int main(){
    init();
    solve();
    return 0;
}

E

题目大意：给定一棵无根树，有$q$个询问，每次询问给出$k$个节点编号，要求该树以$r$为根时，这$k$个节点分为最多$m$个非空组的方案数目，且要求不能有节点是同一组内另一节点的祖先。

假设1是根，那么设$f[i][j]$为分完前$i$个点，分为$j$组的方案数。有

其中$anc[i]$表示第$i$个节点之前有多少个节点是它的祖先，为了使转移更方便，应当对节点序列排序使得$anc[i]$不下降，这样后面节点的祖先在前面就可以全部出现了。
前一个式子表示可以把第$i$个顶点分配到已存在的组里，后一个式子表示可以第$i$个点自成一组。
再考虑根不定的情形。可以发现难点在于计算$anc[i]$。事实上，一个点是另一个点的祖先表明它出现在了该点到根的路径上，因此问题转化为快速统计两点间路径上被标定了的点数目。这个用树的DFS序+BIT+LCA可以解决。（树剖应该也可以）

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, q, to[200005], nxt[200005], at[100005] = {0}, cnt = 0;
int vs[200005], lvs = 0, dep[100005], dfn[100005];
int f[200005][20] = {0}, in[100005], out[100005], D = 0;
int dp[100005][305], bit[200005] = {0}, par[100005];
int lis[100005], lis2[100005];
inline int lowbit(int x){
    return x & (-x);
}
void add(int k, int r){
    while(r <= n + n)
        bit[r] += k, r += lowbit(r);
}
int _q(int r){
    int res = 0;
    while(r)
        res += bit[r], r -= lowbit(r);
    return res;
}
void dfs(int cur, int fa){
    vs[++lvs] = cur, dfn[cur] = lvs, dep[cur] = dep[fa] + 1;
    in[cur] = ++D, par[cur] = fa; 
    for(int i = at[cur]; i; i = nxt[i]){
        if(to[i] == fa) continue;
        dfs(to[i], cur), vs[++lvs] = cur;
    }
    out[cur] = ++D;
}
inline int minp(int u, int v){
    return dep[u] < dep[v] ? u: v;
}
void build_ST(){
    for(int i = 1; i <= lvs; ++i)
        f[i][0] = vs[i];
    int logg = 1;
    while((1 << logg) < lvs) logg++;
    for(int i = 1; i < logg; ++i){
        int p = (1 << i);
        for(int j = 1; j + p - 1 <= lvs; ++j)
            f[j][i] = minp(f[j][i - 1], f[j + (p >> 1)][i - 1]);
    }
    f[1][logg] = minp(f[1][logg - 1], f[1 << (logg - 1)][logg - 1]);
}
int query(int l, int r){
    if(l > r) swap(l, r);
    int od = 0;
    while((1 << od) <= (r - l + 1)) od++;
    od--;
    return minp(f[l][od], f[r - (1 << od) + 1][od]);
}
int calc(int u, int v){
    int lca = query(dfn[u], dfn[v]);
    return _q(in[u]) + _q(in[v]) - _q(in[lca]) - _q(in[par[lca]]);
}
void init(){
    n = read(), q = read();
    for(int i = 1; i < n; ++i){
        int u = read(), v = read();
        to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
        to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
    }
    dep[0] = 0, in[0] = 0, dfs(1, 0);
    build_ST();
}
void solve(){
    while(q--){
        int k = read(), m = read(), r = read();
        for(int i = 1; i <= k; ++i)
            lis2[i] = read(), add(1, in[lis2[i]]), add(-1, out[lis2[i]]);
        for(int i = 1; i <= k; ++i)
            lis[i] = calc(lis2[i], r) - 1;
        for(int i = 1; i <= k; ++i)
            add(-1, in[lis2[i]]), add(1, out[lis2[i]]);
        sort(lis + 1, lis + k + 1);
        dp[0][0] = 1;
        for(int i = 1; i <= k; ++i){
            int lim = min(i, m);
            for(int j = 1; j <= lim; ++j){
                if(j <= lis[i]) dp[i][j] = 0;
                else dp[i][j] = (1ll * dp[i - 1][j] * (j - lis[i]) + dp[i - 1][j - 1]) % 1000000007;
            }
        }
        int ans = 0;
        for(int i = 1; i <= m; ++i)
            ans = (ans + dp[k][i]) % 1000000007;
        printf("%d\n", ans);
    }
}
int main(){
    init();
    solve();
    return 0;
}

小结

这次比赛失误挺多，总共贡献了5发WA，还只写出来3道题目。。。
不过收获也很多。D题背包的逆是一个巧妙的想法，E中先建立转移方程，再根据转移方程中的关键变量可以发现问题的本质所在，这一点很值得参考。