Educational Codeforces Round 82 (Rated for Div. 2)题解。

A. Erasing Zeroes

        找到最左边和最右边的1，然后数一数中间有多少个0即可。

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
#include <bits/stdc++.h>
using namespace std;
char op[500];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", op + 1);
        int len = strlen(op + 1);
        int l = -1, r;
        for (int i = 1; i <= len; i++) {
            if (op[i] == '1') {
                l = i;
                break;
            }
        }
        if (l == -1) {
            printf("0\n");
        } else {
            for (int i = len; i >= 1; i--) {
                if (op[i] == '1') {
                    r = i;
                    break;
                }
            }
            int ans = 0;
            for (int i = l; i <= r; i++) {
                if (op[i] == '0') ++ans;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

B. National Project

        先求出需要修的高质量的部分，即$\lceil \frac {n}{2}\rceil$这么多。先保证有这些天的好天气，求出至少需要的天数，此时检查是否合法，合法的标准是当前天数的坏天气天数不小于$n-\lceil\frac {n}{2}\rceil $，否则就需要向后延长时间。

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
#include <bits/stdc++.h>
using namespace std;
int ness;
int main()
{
    int t, n, g, b;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &g, &b);
        ness = n % 2 == 0 ? n / 2 : n / 2 + 1;
        int zq;
        if (ness % g == 0) {
            zq = ness / g - 1;
        } else {
            zq = ness / g;
        }
        long long ans = 1ll * zq * (g + b) + ness - 1ll * zq * g;
        long long sy = ans - ness;
        if (sy >= n - ness) {
            printf("%lld\n", ans);
        } else {
            printf("%lld\n", ans + n - ness - sy);
        }
    }
    return 0;
}

C. Perfect Keyboard

        根据相邻关系构造一个图，若这个图是一条链，则可行，遍历一遍链，后边再跟上没出现过的字母就是答案。
        判断一个连通图是不是链可以这样判断：

  • 不存在度数大于2的点。
  • 至少存在一个度数为1的点。
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>
using namespace std;
char op[500];
int ss[50][50], vis[50];
string asd;
vector<int> to[50];
 
void DFS(int x)
{
    for (int i = 0; i < 26; i++) {
        if (ss[x][i] && vis[i] == 0) vis[i] = 1, asd.push_back(i + 'a'), DFS(i);
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", op), memset(ss, 0, sizeof(ss));
        int len = strlen(op);
        for (int i = 0; i < len; i++) {
            if (i - 1 >= 0) ss[op[i] - 'a'][op[i - 1] - 'a'] = 1;
            if (i + 1 < len) ss[op[i] - 'a'][op[i + 1] - 'a'] = 1;
        }
        if (len == 1) {
            printf("YES\nabcdefghijklmnopqrstuvwxyz\n");
        } else {
            int num1 = 0, num2 = 0, n3 = 0;
            for (int i = 0; i < 26; i++) {
                int tmp = 0;
                for (int j = 0; j < 26; j++) {
                    if (ss[i][j]) ++tmp;
                }
                if (tmp == 1)
                    ++num1;
                else if (tmp == 2)
                    ++num2;
                else if (tmp >= 3)
                    ++n3;
            }
            if (n3 || num1 != 2) {
                printf("NO\n");
            } else {
                memset(vis, 0, sizeof(vis));
                for (int i = 0; i < 26; i++) {
                    int tmp = 0;
                    for (int j = 0; j < 26; j++) {
                        if (ss[i][j]) ++tmp;
                    }
                    if (tmp == 1) {
                        asd.clear(), asd.push_back(i + 'a'), vis[i] = 1, DFS(i);
                        break;
                    }
                }
                for (int i = 0; i < 26; i++) {
                    if (!vis[i]) asd.push_back(i + 'a');
                }
                printf("YES\n");
                for (int i = 0; i < 26; i++) printf("%c", asd[i]);
                printf("\n");
            }
        }
    }
    return 0;
}

D. Fill The Bag

        本题是一个稍微难一点的贪心。
        现将所有的数放到对应的桶中（比如$2^3=8$，把$8$放到$3$号桶中）。从小到大依次进位，尽可能将较小的数进位到较大的位置上。当进位到某一位，若$n$在该位值为$1$，则考察此时桶中的数是否可以满足，若可以满足，则数量减一，继续向上进位。否则就查找该位向上第一个数量非零的桶，取其中一个数，减半至该位，更新数量。

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
#include <bits/stdc++.h>
using namespace std;
int m;
long long num[80], n;
inline int get(int x)
{
    for (int i = 0; i <= 63; i++) {
        if ((1ll << i) & x) return i;
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%d", &n, &m), memset(num, 0, sizeof(num));
        for (int i = 1, x; i <= m; i++) scanf("%d", &x), ++num[get(x)];
        int now = 0, r = 0, ans = 0;
        for (int at = 0; at <= 63; at++) {
            if (((1ll << at) & n) == 0) continue;
            while (true) {
                if (now == at) {
                    num[now] += r, r = 0;
                    break;
                } else {
                    int tmp = num[now] + r;
                    r = tmp / 2, num[now] = tmp % 2;
                }
                ++now;
            }
            if (num[at] != 0) {
                --num[at];
            } else {
                int flag = 0;
                for (int i = at + 1; i <= 63; i++) {
                    if (num[i]) {
                        flag = 1, --num[i], num[at] += 1ll << (i - at);
                        --num[at], ans += i - at;
                        break;
                    }
                }
                if (!flag) {
                    printf("-1\n");
                    goto to;
                }
            }
        }
        printf("%d\n", ans);
    to:;
    }
    return 0;
}

E. Erase Subsequences

        正解是$DP$。将目标串分为两个部分$A$和$B$，枚举前半部分，然后进行$DP$。设$dp(i,j)$表示对于原串前$i$位置，$A$串匹配了前$j$位，$B$串能够匹配的最长长度，若最后$dp(|s|,|A|)=|B|$，则可行。复杂度$O(n^3)$。
        状态转移方程不难列。

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
#include <bits/stdc++.h>
using namespace std;
int dp[500][500], l1, l2;
char s1[500], s2[500];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s%s", s1 + 1, s2 + 1);
        l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);
        for (int i = 1; i <= l2; i++) {
            for (int b = 1; b <= i; b++) dp[0][b] = -0x3f3f3f3f;
            for (int a = 1; a <= l1; a++) {
                dp[a][0] = dp[a - 1][0];
                if (dp[a - 1][0] < l2 - i && s2[i + dp[a - 1][0] + 1] == s1[a]) ++dp[a][0];
                for (int b = 1; b <= i; b++) {
                    dp[a][b] = dp[a - 1][b];
                    if (s1[a] == s2[b]) dp[a][b] = max(dp[a][b], dp[a - 1][b - 1]);
                    if (dp[a - 1][b] >= 0 && dp[a - 1][b] < l2 - i && s1[a] == s2[i + dp[a - 1][b] + 1]) {
                        dp[a][b] = max(dp[a][b], dp[a - 1][b] + 1);
                    }
                }
            }
            if (dp[l1][i] == l2 - i) {
                printf("YES\n");
                goto to;
            }
        }
        printf("NO\n");
    to:;
    }
    return 0;
}

F. Number of Components

        可以离线的动态连通性问题，常规的做法有线段树分治配合可撤销并查集，以及$LCT$维护最大生成树做法，然而这两种做法在本题会被卡时间空间。
        注意到$nmc$不大，可以考虑对每一个颜色维护连通块，这样每一个修改操作都可以看做对某些颜色插入节点或者删除节点。由于$c_i\leq c_{i+1}$这条限制，对于任意一个颜色，它一定在所有插入节点的过程完成后，才会有删除操作。这是一条很好的性质，可以优化复杂度。
        先只考虑插入的所有过程，用并查集维护，可以得到一些答案。这些答案当然是不对的，因为还有删除操作。
        由于删除全部在插入操作之后，于是删除操作就是倒着插入。将操作顺序反过来再来一遍并查集，就可以得到最终的答案。

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
#include <bits/stdc++.h>
 
#define N 2000005
#define ID(x, y) ((x)*m+y)
 
using namespace std;
typedef pair<int, int> pt;
int n, m, q, op[300][300], C, diff[N], tmp[300][300], fa[90000];
vector<pt> add[N], del[N];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
 
int ff(int x) {
    return fa[x] == x ? x : fa[x] = ff(fa[x]);
}
 
inline int merge(int x, int y) {
    int f1 = ff(x), f2 = ff(y);
    if (f1 == f2)return 0;
    fa[f1] = f2;
    return 1;
}
 
inline void solve(const vector<pt> &vec, int ps) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)tmp[i][j] = 0;
    }
    for (int i = 0; i < n * m; i++)fa[i] = i;
    for (pt s:vec) {
        int x = s.first / m, y = s.first % m, sv = 1;
        tmp[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && tmp[xx][yy])sv -= merge(ID(x, y), ID(xx, yy));
        }
        diff[s.second] += ps * sv;
    }
}
 
int main() {
    scanf("%d%d%d", &n, &m, &q), C = 1;
    for (int i = 0, x, y, v; i < q; i++) {
        scanf("%d%d%d", &x, &y, &v), --x, --y;
        if (op[x][y] == v)continue;
        add[v].push_back(make_pair(ID(x, y), i)), del[op[x][y]].push_back(make_pair(ID(x, y), i));
        op[x][y] = v, C = v + 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)del[op[i][j]].push_back(make_pair(ID(i, j), q));
    }
    for (int i = 0; i < C; i++)reverse(del[i].begin(), del[i].end());
    for (int i = 0; i < C; i++)solve(add[i], 1);
    for (int i = 0; i < C; i++)solve(del[i], -1);
    int ans = 1;
    for (int i = 0; i < q; i++) ans += diff[i], printf("%d\n", ans);
    return 0;
}

G. Sum of Prefix Sums

        看起来就像一个点分治，关键在于如何更新答案。
        假定现在的树根是$c$，那么对于两个点$u$和$v$（$lca$是$c$），假设$u$到$c$路径上的序列是$a_1$到$a_k$，有$k$个值，$c$到$v$有$m$个值。维护两个值$sum_u=\sum_{i=1}^ka_i$，$psum_u=\sum_{i=1}^k(k-i+1)a_i$（$v$同理）那么容易发现答案就是：

        观察上面的式子，我们固定$v$，那么答案就是求一些一次函数的最大值，这个可以用凸包维护（一种斜率优化方法）优化到$O(nlogn)$，也可以用李超线段树。
        本题细节较多。

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
#include <bits/stdc++.h>
#define N 160000
using namespace std;
struct Edge
{
    int next, to;
} edge[N << 1];
typedef long long ll;
struct Node
{
    ll k, b;
    int l, r;
} nd[N << 2];
int head[N], cnt = 1, v[N], n, vis[N], ftot, froot, fminn, fsz[N], son[N], ndcnt, lcroot;
ll s[N], p[N], num[N], ans;
inline int newNode()
{
    nd[ndcnt].k = nd[ndcnt].b = nd[ndcnt].l = nd[ndcnt].r = 0;
    return ndcnt++;
}
inline ll f(ll kk, ll bb, ll x)
{
    return kk * x + bb;
}
void modify(int l, int r, ll K, ll B, int& rt, int L = 1, int R = n)
{
    if (rt == 0) rt = newNode();
    int mid = (L + R) >> 1;
    if (L >= l && R <= r) {
        if (f(K, B, L) >= f(nd[rt].k, nd[rt].b, L) && f(K, B, R) >= f(nd[rt].k, nd[rt].b, R)) {
            nd[rt].k = K, nd[rt].b = B;
        } else if (f(K, B, L) <= f(nd[rt].k, nd[rt].b, L) && f(K, B, R) <= f(nd[rt].k, nd[rt].b, R)) {
            return;
        } else {
            double xx = 1.0 * (B - nd[rt].b) / (nd[rt].k - K);
            if (f(K, B, mid) > f(nd[rt].k, nd[rt].b, mid)) swap(nd[rt].k, K), swap(nd[rt].b, B);
            if (xx <= mid)
                modify(L, mid, K, B, nd[rt].l, L, mid);
            else
                modify(mid + 1, R, K, B, nd[rt].r, mid + 1, R);
        }
        return;
    }
    if (r <= mid)
        modify(l, r, K, B, nd[rt].l, L, mid);
    else if (l > mid)
        modify(l, r, K, B, nd[rt].r, mid + 1, R);
    else
        modify(l, mid, K, B, nd[rt].l, L, mid), modify(mid + 1, r, K, B, nd[rt].r, mid + 1, R);
}
ll query(int at, int rt, int L = 1, int R = n)
{
    if (rt == 0) return 0;
    if (L == R) return f(nd[rt].k, nd[rt].b, at);
    int mid = (L + R) >> 1;
    if (at <= mid) return max(f(nd[rt].k, nd[rt].b, at), query(at, nd[rt].l, L, mid));
    return max(f(nd[rt].k, nd[rt].b, at), query(at, nd[rt].r, mid + 1, R));
}
inline void add(int x, int y)
{
    edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
void fDFS(int x, int fa)
{
    int ms = 0;
    fsz[x] = 1;
    for (int i = head[x]; i; i = edge[i].next) {
        if (!vis[edge[i].to] && edge[i].to != fa) fDFS(edge[i].to, x), fsz[x] += fsz[edge[i].to], ms = max(ms, fsz[edge[i].to]);
    }
    ms = max(ms, ftot - fsz[x]);
    if (ms < fminn) fminn = ms, froot = x;
}
inline void findRoot(int x, int nm)
{
    ftot = nm, fminn = 0x3f3f3f3f, fDFS(x, 0);
}
void DFS(int x, int dep, int fa, ll ss, ll pp)
{
    num[x] = dep, s[x] = ss + v[x], p[x] = pp + 1ll * dep * v[x];
    ans = max(ans, p[x] + s[x] + v[froot]), modify(1, n, s[x], p[x], lcroot);
    for (int i = head[x]; i; i = edge[i].next) {
        if (!vis[edge[i].to] && edge[i].to != fa) DFS(edge[i].to, dep + 1, x, s[x], p[x]);
    }
}
void DFSans(int x, int dep, int fa, ll ss, ll pp)
{
    num[x] = dep, s[x] = ss + v[x], p[x] = pp + ss + v[x];
    ans = max(ans, query(dep + 1, lcroot) + p[x] + 1ll * (dep + 1) * v[froot]);
    for (int i = head[x]; i; i = edge[i].next) {
        if (!vis[edge[i].to] && edge[i].to != fa) DFSans(edge[i].to, dep + 1, x, s[x], p[x]);
    }
}
inline void get(int at)
{
    if (at == 0) return;
    lcroot = 0, ndcnt = 1, DFS(son[1], 1, 0, 0, 0);
    for (int i = 2; i <= at; i++) DFSans(son[i], 1, 0, 0, 0), DFS(son[i], 1, 0, 0, 0);
}
void DFSsz(int x, int fa)
{
    fsz[x] = 1;
    for (int i = head[x]; i; i = edge[i].next) {
        if (!vis[edge[i].to] && edge[i].to != fa) DFSsz(edge[i].to, x), fsz[x] += fsz[edge[i].to];
    }
}
void solve(int x)
{
    vis[x] = 1, ans = max(ans, 1ll * v[x]);
    int at = 0;
    for (int i = head[x]; i; i = edge[i].next) {
        if (!vis[edge[i].to]) son[++at] = edge[i].to;
    }
    get(at), reverse(son + 1, son + at + 1), get(at);
    for (int i = head[x]; i; i = edge[i].next) {
        if (!vis[edge[i].to]) DFSsz(edge[i].to, x), findRoot(edge[i].to, fsz[edge[i].to]), solve(froot);
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
    for (int i = 1; i <= n; i++) scanf("%d", v + i);
    findRoot(1, n), solve(froot), printf("%lld", ans);
    // PAUSE;
    return 0;
}