Educational Codeforces Round 82

        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;
}

0%