「Codeforces」Educational Round 45【题解】

简要题解

A. Commentary Boxes

模拟。

B. Micro-World

贪心。

C. Bracket Sequences Concatenation Problem

题目大意:给你 nn 个括号序列 sis_i,求有多少对 (i,j)(i, j) 使得 si+sjs_i + s_j 是合法的括号序列。保证 n,si3×105n, \sum \lvert s_i \rvert \leqslant 3 \times 10^5

任意的括号序列都可以化简为如下形式 ((否则可以继续化简))

))))"+ (((("``)) \cdots ))" +\ ``(( \cdots (("

两个括号序列对答案有贡献,当且仅当分别只由 ("``(")"``)" 构成且数量相同。

D. Graph And Its Complement

题目大意:构造一个 nn 个点、连通块个数为 aa、补图的连通块个数为 bb 的无向图,或者输出不可能。保证 a,bn1000a, b \leqslant n \leqslant 1000

可以发现,如果 min{a,b}1\min \{ a, b \} \neq 1,那么不存在合法答案。

还有 2n3,2 \leqslant n \leqslant 3, a=b=1a = b = 1 的特殊情况,也不存在合法答案。

对于其他的所有情况,都可以将 max{a,b}n\max \{ a, b \} \sim n 连成一条链,得到合法答案。

E. Post Lamps

模拟。

F. Flow Control ()(\star)

题目大意:给你一张 nn 个点、mm 条边的有向图,问是否存在一种边的流量的分配方案,使得点 ii 的流入总量 - 流出总量为 sis_i。如果存在,就输出一种合法方案。保证 n,m2×105n, m \leqslant 2 \times 10^5,图是连通的。

显然答案是 Possible 当且仅当 si=0\sum s_i = 0,先得到一棵生成树,考虑强制只用树上的边,将每个点的权值设为其子树中的点的 ss 之和,每条边的权值即为深度较深的点的权值 ((的相反数)​。

G. GCD Counting

题目大意:给你一棵带点权 aa 的树,对于所有 1xyn1 \leqslant x \leqslant y \leqslant n,求 xyx \to y 路径上的点权的 gcd\gcd 的种类数以及每种种类的个数。保证 n,ai2×105n, a_i \leqslant 2 \times 10^5

f(i)f(i)gcd\gcdii 的倍数的链的个数,g(i)g(i)gcd\gcdii 的链的个数:

g(i)=f(i)ij,ijg(j)g(i) = f(i) - \sum_{i \mid j, i \neq j} g(j)

为了求出 f(i)f(i),可以每次求出所有点权是 ii 的倍数的点 ((设为关键点)),将相邻的关键点合并,对于每个连通块分别计算答案即可。

时间复杂度是 O(n×160)O(n \times 160),其中 160=max{d(i)}160 = \max \{ d(i) \}d(i)d(i) 表示 ii 的因数个数。

另外,由于 gcd\gcd 种数很少,也可以用树形 DP+map\text{DP} + \text{map} 通过,可以参考这份代码

代码实现

A. Commentary Boxes

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, m, a, b;

int main() {
cin >> n >> m >> a >> b;
ll ans1 = b * (n - n / m * m);
ll ans2 = a * (n / m * m + m - n);
cout << min(ans1, ans2) << endl;
return 0;
}

B. Micro-World

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010;
int n, K, ans, a[maxn];

int main() {
scanf("%d %d", &n, &K);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
for (int i = 1, j = 0; i <= n; i++) {
j = max(j, i + 1);
while (j <= n && a[j] <= a[i] + K) j++;
if (a[j - 1] > a[i] && a[j - 1] <= a[i] + K) ans++;
}
printf("%d\n", n - ans);
return 0;
}

C. Bracket Sequences Concatenation Problem

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

const int maxn = 300010;
int n;
unordered_map<int, int> mp1, mp2;
string s[maxn];
stack<int> st;
long long ans;

int main() {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
int len = s[i].length();
string t;
for (int j = 0; j < len; j++) {
if (s[i][j] == '(') {
st.push(1);
} else {
if (st.empty()) t.push_back(')');
else st.pop();
}
}
while (!st.empty()) {
t.push_back('('), st.pop();
}
s[i] = t;
if (s[i].empty()) ans++;
else if (s[i][0] == '(') mp1[s[i].size()]++;
else if (s[i].back() == ')') mp2[s[i].size()]++;
}
ans *= ans;
for (auto p : mp1) {
ans += 1LL * p.second * mp2[p.first];
}
printf("%lld\n", ans);
return 0;
}

D. Graph And Its Complement

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

const int maxn = 1010;
int n, a, b;
vector<int> V[maxn];
bool G[maxn][maxn];

int main() {
scanf("%d %d %d", &n, &a, &b);
bool tmp = 1;
if (a > b) swap(a, b), tmp = 0;
if (a != 1) printf("NO\n"), exit(0);
if (n > 1 && n <= 3 && a == 1 && b == 1) printf("NO\n"), exit(0);
for (int i = b; i < n; i++) {
G[i][i + 1] = G[i + 1][i] = 1;
}
if (tmp) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) if (i ^ j) {
G[i][j] ^= 1;
}
}
}
printf("YES\n");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%d", G[i][j]);
}
printf("\n");
}
return 0;
}

E. Post Lamps

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 = 1000010;
int n, m, k, s[maxn], a[maxn], b[maxn], c[maxn << 1];
vector<int> V;
ll ans = 1e18;

int main() {
scanf("%d %d %d", &n, &m, &k);
fill(b + 1, b + n + 1, 1);
for (int i = 1; i <= m; i++) {
scanf("%d", &s[i]), b[++s[i]] = 0;
}
for (int i = 1, lst = 0; i <= n; i++) {
if (b[i]) lst = i;
c[i] = lst;
}
for (int i = n + 1; i <= 2000000; i++) {
c[i] = c[i - 1];
}
for (int i = 1; i <= k; i++) {
scanf("%d", &a[i]);
int cnt = 0, flag = 1;
for (int j = 1; j <= n; j = c[i + j]) {
cnt++;
if (b[j] && i + j > n) break;
if (b[j] == 0 || c[i + j] <= j) { flag = 0; break; }
}
if (flag) ans = min(ans, 1LL * a[i] * cnt);
}
if (ans == 1e18) ans = -1;
printf("%lld\n", ans);
return 0;
}

F. Flow Control

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

const int maxn = 200010;
int n, m, sum, s[maxn], fa[maxn], u[maxn], v[maxn], d[maxn];
bool used[maxn]; vector<int> G[maxn];

int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}

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

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]), sum += s[fa[i] = i];
}
if (sum) printf("Impossible\n"), exit(0);
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &u[i], &v[i]);
if (find(u[i]) ^ find(v[i])) {
used[i] = 1, fa[find(u[i])] = find(v[i]);
G[u[i]].push_back(v[i]), G[v[i]].push_back(u[i]);
}
}
dfs(1, 0), printf("Possible\n");
for (int i = 1; i <= m; i++) {
if (!used[i]) printf("0\n");
else printf("%d\n", d[u[i]] < d[v[i]] ? s[v[i]] : -s[u[i]]);
}
return 0;
}

G. GCD Counting

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;

typedef long long ll;
const int maxn = 200010;
int n, a[maxn], fa[maxn], sz[maxn];
ll f[maxn];
vector<int> G[maxn], H[maxn], V;
vector<pair<int, ll> > ans;

int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
fa[x] = y, sz[y] += sz[x];
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]), H[a[i]].push_back(i);
}
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
for (int i = 200000; i; i--, V.clear()) {
for (int j = i; j <= 200000; j += i) {
for (int k : H[j]) V.push_back(k);
}
for (int j : V) fa[j] = j, sz[j] = 1;
for (int j : V) for (int k : G[j]) if (a[k] % i == 0) unite(j, k);
for (int j : V) if (j == find(j)) f[i] += 1LL * sz[j] * (sz[j] + 1) / 2;
for (int j = i + i; j <= 200000; j += i) f[i] -= f[j];
if (f[i]) ans.push_back({i, f[i]});
}
for (int i = ans.size() - 1; ~i; i--) {
printf("%d %lld\n", ans[i].first, ans[i].second);
}
return 0;
}