「Codeforces」Educational Round 46【题解】

简要题解

A. Codehorses T-shirts

贪心,对每种长度分别考虑。

B. Light It Up

插入的位置只可能是 ai±1a_i \pm 1 (i mod 2=1)(i \text{ mod } 2 = 1),枚举即可。

C. Covered Points Count

离散化,统计每一段被覆盖的次数,把长度加到答案里。

D. Yet Another Problem On a Subsequence

f(i)f(i) 表示以 ii 结尾的子序列的个数,枚举最后一个 good array\text{good array} 转移。

E. We Need More Bosses ()(\star)

题目大意:给你一个 nn 个点、mm 条边的无向图,确定两点 s,ts, t,使得 sts \to t 路径上的必经边最多。

一个环上不会有任何必经边,将无向图缩点后,答案就是树的直径。

F. One Occurrence

题目大意:给你一个长度为 nn 的序列 {a}\{ a \},有 qq 个询问,每次求一段区间 [l,r][l, r] 是否有恰好出现 11 次的数。如果有,输出这个数;否则,输出 00。保证 n,q,ai5×105n, q, a_i \leqslant 5 \times 10^5

pre(i)\text{pre}(i) 表示 aia_i 上一个出现的位置,nxt(i)\text{nxt}(i) 表示 aia_i 下一个出现的位置。那么 aia_i 恰好出现 11 次可以表示为:

pre(i)<l, lir, nxt(i)>r\text{pre(i)} < l,\ l \leqslant i \leqslant r,\ \text{nxt}(i) > r

对于 pre(i)\text{pre}(i) 建立主席树,以原序列中的位置作为下标,维护 nxt(i)\text{nxt}(i) 的最大值。

G. Two-Paths

题目大意:给你一棵 nn 个结点的树,点 ii 的点权为 aia_i,边 ee 的边权为 wew_e。有 qq 个询问,每次给出两个点 u,vu, v,求一条 uvu \to v 的路径 pp,使得每条边经过不超过 22 次。最大化下式的值,输出最大值,其中 kek_e 表示边 ee 经过的次数:

Pr(p)=vvertices in paveedges in pkewe\text{Pr}(p) = \sum_{v \in \text{vertices in } p} a_v - \sum_{e \in \text{edges in } p} k_e \cdot w_e

保证 n3×105,n \leqslant 3 \times 10^5, q4×105q \leqslant 4 \times 10^5

qq 表示 uvu \to v 的简单路径,pp 一定由 qqxx (xq)(x \in q) 往下走再回来、lca(u,v)\text{lca}(u, v) 往上走再回来构成。但是无论往上走还是往下走,都不能经过 qq 中的边。

up(v)\text{up}(v) 表示 vv 往上走的最大获益,down(v)\text{down}(v) 表示 vv 往下走的最大获益。down(v)\text{down}(v) 从根向下 DFS\text{DFS} 一遍即可求出,up(v)\text{up}(v) 需要做一遍换根 DP\text{DP}

需要注意的是,最后还需要减去 down(v)\text{down}(v)qq 上的收益 ((这个 DP\text{DP} 具有可减性))

:往下走指在子树中走,往上走指在非子树中走,不一定是一条简单路径来回走两遍。

代码实现

A. Codehorses T-shirts

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;

const int maxn = 110;
int n, ans, c[10][3];
string a[maxn], b[maxn];

int main() {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) {
if (a[i].back() == 'S') c[a[i].size()][0]++;
if (a[i].back() == 'M') c[a[i].size()][1]++;
if (a[i].back() == 'L') c[a[i].size()][2]++;
if (b[i].back() == 'S') c[a[i].size()][0]--;
if (b[i].back() == 'M') c[a[i].size()][1]--;
if (b[i].back() == 'L') c[a[i].size()][2]--;
}
for (int i = 1; i <= 5; i++) {
for (int j = 0; j < 3; j++) {
ans += abs(c[i][j]);
}
}
printf("%d\n", ans >> 1);
return 0;
}

B. Light It Up

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 100010;
int n; ll ans, m, a[maxn], suf1[maxn], suf2[maxn], pre1[maxn], pre2[maxn];

int main() {
scanf("%d %lld", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
if (i & 1) ans += a[i] - a[i - 1];
}
a[n + 1] = m;
if ((n + 1) & 1) ans += m - a[n];
for (int i = 1; i <= n + 1; i++) {
pre1[i] = pre1[i - 1], pre2[i] = pre2[i - 1];
if (i & 1) pre1[i] += a[i] - a[i - 1];
else pre2[i] += a[i] - a[i - 1];
}
for (int i = n; ~i; i--) {
suf1[i] = suf1[i + 1], suf2[i] = suf2[i + 1];
if (i & 1) suf2[i] += a[i + 1] - a[i];
else suf1[i] += a[i + 1] - a[i];
}
for (int i = 0; i <= n + 1; i++) if (i & 1) {
if (a[i] - 1 > 0 && a[i] - 1 > a[i - 1]) {
ans = max(ans, pre1[i - 1] + a[i] - 1 - a[i - 1] + suf2[i]);
}
if (a[i] + 1 < m && a[i] + 1 < a[i + 1]) {
ans = max(ans, pre1[i] + a[i + 1] - a[i] - 1 + suf2[i + 1]);
}
}
printf("%lld\n", ans);
return 0;
}

C. Covered Points Count

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>
using namespace std;

typedef long long ll;
const int maxn = 800010;
int n, tot, c[maxn];
ll l[maxn], r[maxn], x[maxn], ans[maxn], len[maxn];
map<ll, int> pos;

void add(int p, int v) {
for (; p <= (n << 2); p += p & -p) {
c[p] += v;
}
}

int query(int p) {
int s = 0;
for (; p; p -= p & -p) {
s += c[p];
}
return s;
}

void add_seg(int l, int r) {
add(l, 1), add(r + 1, -1);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld %lld", &l[i], &r[i]);
x[(i << 1) - 1] = l[i], x[i << 1] = r[i];
}
sort(x + 1, x + (n << 1) + 1);
tot = unique(x + 1, x + (n << 1) + 1) - x - 1;
for (int i = 1; i <= tot; i++) {
if (x[i] <= x[i - 1] + 1) {
len[pos[x[i]] = pos[x[i - 1]] + 1] = 1;
} else {
len[pos[x[i - 1]] + 1] = x[i] - x[i - 1] - 1;
len[pos[x[i]] = pos[x[i - 1]] + 2] = 1;
}
}
for (int i = 1; i <= n; i++) {
add_seg(pos[l[i]], pos[r[i]]);
}
for (int i = 1; i <= (n << 2); i++) {
ans[query(i)] += len[i];
}
for (int i = 1; i <= n; i++) {
printf("%lld ", ans[i]);
}
return 0;
}

D. Yet Another Problem On a Subsequence

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010, P = 998244353;
int n, a[maxn], f[maxn], g[maxn], C[maxn][maxn];

int main() {
scanf("%d", &n);
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
}
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[j] > 0 && i - j - 1 >= a[j] - 1) {
(f[i] += 1LL * C[i - j - 1][a[j] - 1] * (f[j - 1] + 1) % P) %= P;
}
}
(f[i] += f[i - 1]) %= P;
}
printf("%d\n", f[n]);
return 0;
}

E. We Need More Bosses

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 300010;
int n, m, tot, cnt, tp, st[maxn], dfn[maxn], low[maxn], bel[maxn], dep[maxn];
vector<int> G[maxn], H[maxn];

void tarjan(int v, int f) {
low[v] = dfn[v] = ++tot, st[++tp] = v;
for (int u : G[v]) if (u ^ f) {
if (!dfn[u]) {
tarjan(u, v), low[v] = min(low[v], low[u]);
} else {
low[v] = min(low[v], dfn[u]);
}
}
if (low[v] == dfn[v]) {
cnt++;
do {
bel[st[tp]] = cnt;
} while (tp && st[tp--] ^ v);
}
}

void dfs(int v, int f) {
dep[v] = dep[f] + 1;
for (int u : H[v]) if (u ^ f) dfs(u, v);
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
tarjan(1, 0);
for (int i = 1; i <= n; i++) for (int j : G[i]) {
if (bel[i] ^ bel[j]) H[bel[i]].push_back(bel[j]);
}
dep[0] = -1, dfs(1, 0);
dfs(max_element(dep + 1, dep + cnt + 1) - dep, 0);
printf("%d\n", *max_element(dep + 1, dep + cnt + 1));
return 0;
}

F. One Occurrence

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 mid (l + r >> 1)
using namespace std;

const int maxn = 500010;
int n, q, tot, a[maxn], b[maxn], rt[maxn], pre[maxn], nxt[maxn];
struct tmp { int id, pre, nxt; } p[maxn];
struct node { int l, r; pair<int, int> mx; } t[maxn << 5];
bool comp(tmp a, tmp b) { return a.pre < b.pre; }

void add(int &k1, int k2, int l, int r, int p) {
t[k1 = ++tot] = t[k2], t[k1].mx = {nxt[p], a[p]};
if (l == r) return;
if (mid >= p) add(t[k1].l, t[k2].l, l, mid, p);
else add(t[k1].r, t[k2].r, mid + 1, r, p);
t[k1].mx = max({t[k1].mx, t[t[k1].l].mx, t[t[k1].r].mx});
}

pair<int, int> query(int k, int l, int r, int ql, int qr) {
if (!k || l >= ql && r <= qr) return t[k].mx;
pair<int, int> tmp(0, 0);
if (mid >= ql) tmp = max(tmp, query(t[k].l, l, mid, ql, qr));
if (mid < qr) tmp = max(tmp, query(t[k].r, mid + 1, r, ql, qr));
return tmp;
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
pre[i] = b[a[i]], b[a[i]] = i;
}
fill(b + 1, b + 500001, n + 1);
for (int i = n; i; i--) {
nxt[i] = b[a[i]], b[a[i]] = i;
p[i] = (tmp){i, pre[i], nxt[i]};
}
sort(p + 1, p + n + 1, comp);
for (int i = 0, j = 1; i <= n; i++) {
rt[i] = !i ? 0 : rt[i - 1];
for (; j <= n && p[j].pre == i; j++) {
add(rt[i], rt[i], 1, n, p[j].id);
}
}
scanf("%d", &q);
// pre[x] < l, l <= x <= r, nxt[x] > r
for (int i = 1, l, r; i <= q; i++) {
scanf("%d %d", &l, &r);
pair<int, int> p = query(rt[l - 1], 1, n, l, r);
if (p.first <= r) printf("0\n");
else printf("%d\n", p.second);
}
return 0;
}

G. Two-Paths

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>
using namespace std;

typedef long long ll;
const int maxn = 300010;
int n, q, a[maxn], fa[maxn], dep[maxn], sz[maxn], son[maxn], top[maxn], tmp[maxn];
ll up[maxn], down[maxn], dist[maxn];
vector<int> G[maxn], W[maxn];

void dfs1(int v, int f) {
fa[v] = f, dep[v] = dep[f] + 1, sz[v] = 1;
for (int i = 0, u; i < G[v].size(); i++) {
if ((u = G[v][i]) == f) continue;
dfs1(u, v), sz[v] += sz[u];
if (sz[u] > sz[son[v]]) son[v] = u;
down[v] = max(down[v], down[v] + down[u] + a[u] - 2 * W[v][i]);
}
}

void dfs2(int v, int rt, int w) {
top[v] = rt, dist[v] = dist[fa[v]] + a[v] - (tmp[v] = w) + down[v];
dist[v] -= max(0LL, down[v] + a[v] - 2 * w);
for (int i = 0, u; i < G[v].size(); i++) {
if ((u = G[v][i]) == fa[v]) continue;
ll x = down[u] + a[u] - 2 * W[v][i], y = up[v] + a[v] - 2 * W[v][i];
up[u] = max(0LL, down[v] - max(0LL, x) + y);
u ^ son[v] ? dfs2(u, u, W[v][i]) : dfs2(u, rt, W[v][i]);
}
}

int lca(int u, int v) {
for (; top[u] ^ top[v]; u = fa[top[u]]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
}
return dep[u] < dep[v] ? u : v;
}

int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1, u, v, w; i < n; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u].push_back(v), W[u].push_back(w);
G[v].push_back(u), W[v].push_back(w);
}
dfs1(1, 0), dfs2(1, 1, 0);
for (int i = 1, u, v, p; i <= q; i++) {
scanf("%d %d", &u, &v), p = lca(u, v);
ll ans = dist[u] + dist[v] - dist[p] - dist[fa[p]] + up[p];
ans += tmp[p] + max(0LL, down[p] + a[p] - 2LL * tmp[p]);
printf("%lld\n", ans);
}
return 0;
}