「Codeforces」Educational Round 44【题解】

简要题解

A. Chess Placing

模拟。

B. Switches and Lamps

模拟。

C. Liebig`s Barrels

如果没有 x,y, vxvyl\forall x, y,\ \lvert v_x - v_y \rvert \leqslant l 的条件,显然可以分为:

[v1vk],[vk+1v2k],,[v(n1)k+1vnk][v_1 \sim v_k], [v_{k + 1} \sim v_{2k}], \cdots, [v_{(n - 1)k + 1} \sim v_{nk}]

如果有这个条件,就在满足条件的情况下,让每个组占据尽量靠前的位置。

D. Sand Fortress ()(\star)

题目问的是 ``总和为 nn、个数为 kk、首项 H\leqslant H 的序列是否存在"",这个较难求出,不妨考虑 ``所有个数为 kk、首项 H\leqslant H 的序列的总和是否可能为 n"n"

如果确定了 kk,那么满足条件的序列是一个连续的范围,证明略去。显然下界是 kk ((全填 1)1),考虑如何求出上界。根据奇偶性的不同,可能有下面两种情况 ((其中紫色部分为 HH,如果 kk 比较小可能只有黄色部分))

两种情况的示意图

显然 kk 越大,上界也越大,所以可以对 kk 进行二分。将二分上界估计为 2n2 \sqrt n

E. Pencils and Boxes

{a}\{ a \} 排序后,每组一定是连续的一段。从前往后 DP\text{DP},用单调队列优化即可。

F. Isomorphic Strings

对于每个字符,将出现的位置 Hash\text{Hash}。两个字符串同构当且仅当,所有字符出现的位置的 Hash\text{Hash} 值排序后,可以一一对应。

另外,本题卡 unsinged long long\text{unsinged long long} 自然溢出 Hash\text{Hash},所以需要选一个大质数来取模。

G. Team Players

容斥原理,答案即为 a0a1+a2a3a_0 - a_1 + a_2 - a_3

  • a0a_0 为总的方案数,对每个点分别计算。
  • a1a_1 为至少包含 11 条边的,对每条边分别计算。
  • a2a_2 为至少包含 22 条边的,对每个点分别计算。
  • a3a_3 为都相互连接的,枚举三元环计算。

代码实现

A. Chess Placing

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

const int maxn = 110;
int n, p[maxn], ans1, ans2;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n / 2; i++) {
scanf("%d", &p[i]);
}
sort(p + 1, p + n / 2 + 1);
for (int i = 1; i <= n / 2; i++) {
ans1 += abs(p[i] - (i << 1));
ans2 += abs(p[i] - (i << 1) + 1);
}
printf("%d\n", min(ans1, ans2));
return 0;
}

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

const int maxn = 2010;
int n, m, cnt[maxn][maxn], s1[maxn][maxn], s2[maxn][maxn];

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%1d", &cnt[i][j]);
s1[i][j] = s1[i - 1][j] + cnt[i][j];
}
}
for (int i = n; i; i--) {
for (int j = 1; j <= m; j++) {
s2[i][j] = s2[i + 1][j] + cnt[i][j];
}
}
for (int i = 1; i <= n; i++) {
bool flag = 1;
for (int j = 1; j <= m; j++) {
int sum = s1[i - 1][j] + s2[i + 1][j];
if (!sum) flag = 0;
}
if (flag) printf("YES\n"), exit(0);
}
printf("NO\n");
return 0;
}

C. Liebig`s Barrels

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 = 100010;
int n, k, l, a[maxn];
long long ans;

int main() {
scanf("%d %d %d", &n, &k, &l);
for (int i = 1; i <= n * k; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n * k + 1);
if (abs(a[1] - a[n]) > l) {
printf("0\n"), exit(0);
}
int mx = 0;
for (int i = 1; i <= n * k; i++) {
if (abs(a[i] - a[1]) <= l) mx = i;
else break;
}
for (int i = 1, j = 1; i <= n; i++) {
ans += a[j];
if (n - i == mx - j) {
j++; continue;
}
if (n - i < mx - j) {
int tmp = mx - j - (n - i);
j += min(tmp, k - 1) + 1;
}
}
printf("%lld\n", ans);
return 0;
}

D. Sand Fortress

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

typedef long long ll;
ll n, H;
ll S(ll l, ll r) { return (r + l) * (r - l + 1) / 2; }

ll chk(ll x) {
if (x <= H) return S(1, x);
ll ans = S(1, H - 1); x -= H;
if (x & 1) ans += S(H, H + x / 2) + S(H, H + x / 2);
else ans += S(H, H + x / 2) + S(H, H + x / 2 - 1);
return ans;
}

int main() {
scanf("%lld %lld", &n, &H);
ll l = 1, r = 2 * sqrt(n) + 10, ans;
while (l <= r) {
ll mid = (l + r) >> 1;
chk(mid) >= n ? r = (ans = mid) - 1 : l = mid + 1;
}
printf("%lld\n", ans);
return 0;
}

E. Pencils and Boxes

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

const int maxn = 500010;
int n, k, d, h, t, a[maxn], q[maxn];
bool f[maxn];

int main() {
scanf("%d %d %d", &n, &k, &d);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1), f[0] = 1;
h = 1, t = 0;
for (int i = k; i <= n; i++) {
while (h <= t && f[q[t]] <= f[i - k]) t--;
q[++t] = i - k;
while (h <= t && a[i] - a[q[h] + 1] > d) h++;
if (h <= t) f[i] = f[q[h]];
}
printf("%s\n", f[n] ? "YES" : "NO");
return 0;
}

F. Isomorphic Strings

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 = 200010, P = 1000000007;
int n, m;
char s[maxn];
ll h[26][maxn], pw[maxn], h1[26], h2[26];

ll get(int i, int l, int r) {
return (h[i][r] - pw[r - l + 1] * h[i][l - 1] % P + P) % P;
}

int main() {
scanf("%d %d %s", &n, &m, s + 1);
for (int i = pw[0] = 1; i <= n; i++) {
pw[i] = pw[i - 1] * 43 % P;
for (int j = 0; j < 26; j++) {
h[j][i] = (h[j][i - 1] * 43 + (s[i] == j + 'a')) % P;
}
}
for (int i = 1, x, y, l; i <= m; i++) {
scanf("%d %d %d", &x, &y, &l);
for (int j = 0; j < 26; j++) {
h1[j] = get(j, x, x + l - 1);
h2[j] = get(j, y, y + l - 1);
}
sort(h1, h1 + 26), sort(h2, h2 + 26);
bool flag = 1;
for (int j = 0; j < 26; j++) {
flag &= (h1[j] == h2[j]);
}
printf("%s\n", flag ? "YES" : "NO");
}
return 0;
}

G. Team Players

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

typedef unsigned long long ll;
const int maxn = 200010;
int n, m, u[maxn], v[maxn], d[maxn];
ll A, B, C, ans, s1[maxn], s2[maxn], vis[maxn], t1[maxn], t2[maxn];
vector<ll> G[maxn], H[maxn], W1[maxn], W2[maxn], W3[maxn], W4[maxn];
ll S(ll x) { return 1LL * x * (x - 1) / 2; }

int main() {
scanf("%d %d %llu %llu %llu", &n, &m, &A, &B, &C);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &u[i], &v[i]);
if (u[i] > v[i]) swap(u[i], v[i]);
d[++u[i]]++, d[++v[i]]++;
W1[v[i]].push_back(u[i] - 1);
W2[u[i]].push_back(v[i] - 1);
s1[v[i]] += u[i] - 1, s2[u[i]] += v[i] - 1;
ans -= (B * (u[i] - 1) + C * (v[i] - 1)) * (u[i] - 1);
ans -= (A * (u[i] - 1) + C * (v[i] - 1)) * (v[i] - u[i] - 1);
ans -= (A * (u[i] - 1) + B * (v[i] - 1)) * (n - v[i]);
ans -= A * S(u[i] - 1) + B * (S(v[i] - 1) - S(u[i])) + C * (S(n) - S(v[i]));
}
for (int i = 1; i <= n; i++) {
ans += A * (i - 1) * S(n - i);
ans += B * (i - 1) * (i - 1) * (n - i);
ans += C * (i - 1) * S(i - 1);
sort(W1[i].begin(), W1[i].end());
sort(W2[i].begin(), W2[i].end());
W3[i].push_back(0), W4[i].push_back(0);
for (int j = 1; j < W1[i].size(); j++) {
W3[i].push_back(W3[i].back() + W1[i][j] * j);
}
for (int j = 1; j < W2[i].size(); j++) {
W4[i].push_back(W4[i].back() + W2[i][j] * j);
}
for (int j = 0; j < W1[i].size(); j++) W1[i][j] *= (W1[i].size() - j - 1);
for (int j = 1; j < W1[i].size(); j++) W1[i][j] += W1[i][j - 1];
for (int j = 0; j < W2[i].size(); j++) W2[i][j] *= (W2[i].size() - j - 1);
for (int j = 1; j < W2[i].size(); j++) W2[i][j] += W2[i][j - 1];
}
for (int i = 1; i <= n; i++) {
if (W2[i].size()) {
ans += A * (i - 1) * S(W2[i].size()) + B * W2[i].back() + C * W4[i].back();
}
if (W1[i].size() && W2[i].size()) {
ans += B * (i - 1) * W1[i].size() * W2[i].size();
ans += A * s1[i] * W2[i].size() + C * W1[i].size() * s2[i];
}
if (W1[i].size()) {
ans += A * W1[i].back() + B * W3[i].back() + C * (i - 1) * S(W1[i].size());
}
}
for (int i = 1; i <= m; i++) {
if (d[u[i]] < d[v[i]] || (d[u[i]] == d[v[i]]
&& u[i] > v[i])) swap(u[i], v[i]);
G[u[i]].push_back(v[i]);
}
for (int i = 1; i <= n; i++) {
for (int j : G[i]) vis[j] = i;
for (int j : G[i]) for (int k : G[j]) if (vis[k] == i) {
int a[3] = {i, j, k}; sort(a, a + 3);
ans -= A * --a[0] + B * --a[1] + C * --a[2];
}
}
printf("%llu\n", ans);
return 0;
}