# # Educational Codeforces Round 93 (CF1398) 题解

## # Problem A - Bad Triangle

### # 题解

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
if (a[0] + a[1] <= a[n - 1])
printf("1 2 %d\n", n);
else
printf("-1\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

## # Problem B - Substring Removal Game

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
string s;
cin >> s;
s += "0";
vector<int> v;
int d = '\$', cnt = 0;
for (char c : s) {
if (c == d)
cnt++;
else {
if (d == '1')
v.emplace_back(cnt);
d = c;
cnt = 1;
}
}
sort(v.rbegin(), v.rend());
int ans = 0;
for (int i = 0; i < v.size(); i += 2)
ans += v[i];
printf("%d\n", ans);
}
};

int main() {
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem C - Good Subarrays

### # 题解

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
string s;
cin >> s;
vector<int> a(n);
for (int i = 0; i < n; ++i)
a[i] = s[i] - '0' - 1;
map<int, int> cnt;
cnt[0] = 1;
int sum = 0;
ll ans = 0;
for (int i = 0; i < n; ++i) {
sum += a[i];
ans += cnt[sum];
cnt[sum]++;
}
printf("%lld\n", ans);
}
};

int main() {
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem D - Colored Rectangles

### # 题解

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

ll dp[202][202][202];

class Solution {
public:
void solve() {
int R, G, B;
vector<int> r(R), g(G), b(B);
for (int i = 0; i < R; ++i)
for (int i = 0; i < G; ++i)
for (int i = 0; i < B; ++i)
sort(r.rbegin(), r.rend());
sort(g.rbegin(), g.rend());
sort(b.rbegin(), b.rend());
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= R; ++i)
for (int j = 0; j <= G; ++j)
for (int k = 0; k <= B; ++k) {
if (i < R && j < G)
dp[i + 1][j + 1][k] =
max(dp[i + 1][j + 1][k], dp[i][j][k] + r[i] * g[j]);
if (i < R && k < B)
dp[i + 1][j][k + 1] =
max(dp[i + 1][j][k + 1], dp[i][j][k] + r[i] * b[k]);
if (j < G && k < B)
dp[i][j + 1][k + 1] =
max(dp[i][j + 1][k + 1], dp[i][j][k] + g[j] * b[k]);
}
ll ans = 0;
for (int i = 0; i <= R; ++i)
for (int j = 0; j <= G; ++j)
for (int k = 0; k <= B; ++k)
ans = max(ans, dp[i][j][k]);
printf("%lld", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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

## # Problem E - Two Types of Spells

### # 题解

#include <cstdio>
#include <iostream>
#include <set>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
set<int> fire, lightning, topk, rest, rf;
int l = 0, tl = 0;
ll ans = 0;
auto move_from_rest_to_topk = [&](int k) {
rest.erase(k);
topk.insert(k);
if (fire.count(k))
rf.erase(k);
else
tl++;
ans += k;
};
auto move_from_topk_to_rest = [&](int k) {
topk.erase(k);
rest.insert(k);
if (fire.count(k))
rf.insert(k);
else
tl--;
ans -= k;
};
for (int i = 0; i < n; ++i) {
int tp, p;
if (tp == 0) {
if (p > 0) {
fire.insert(p);
if (l > 0 && p > *topk.begin()) {
int rep = *topk.begin();
move_from_topk_to_rest(rep);
topk.insert(p);
ans += 2 * p;
} else {
rest.insert(p);
rf.insert(p);
ans += p;
}
} else {
p = -p;
fire.erase(p);
if (rest.count(p)) {
ans -= p;
rest.erase(p);
rf.erase(p);
} else {
topk.erase(p);
int rep = *rest.rbegin();
move_from_rest_to_topk(rep);
ans -= 2 * p;
}
}
} else {
if (p > 0) {
lightning.insert(p);
l++;
rest.insert(p);
ans += p;
int rep = *rest.rbegin();
move_from_rest_to_topk(rep);
} else {
p = -p;
lightning.erase(p);
l--;
if (rest.count(p)) {
rest.erase(p);
ans -= p;
int rep = *topk.begin();
move_from_topk_to_rest(rep);
} else {
topk.erase(p);
ans -= p * 2;
tl--;
}
}
}
ll cans = ans;
if (tl == l && tl > 0) {
int rep = *topk.begin();
cans -= rep;
int other = 0;
if (!rf.empty())
other = *rf.rbegin();
cans += other;
}
printf("%lld\n", cans);
}
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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

## # Problem F - Controversial Rounds

### # 题解

$O(n)$时间内，我们可以预处理得到从每个位置开始的最长连续子串长度$p$$q$。同时，我们可以预处理得到$s$串每个位置的下一个'0'串的起点$np$，以及$t$串每个位置的下一个'1'串的起点$nq$

#include <cstdio>
#include <iostream>
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
string s;
cin >> s;
string t(s);
for (int i = 0; i < n; ++i)
if (s[i] == '?')
s[i] = '0', t[i] = '1';
vector<int> p(n + 2), q(n + 2);
for (int i = n; i >= 1; --i)
p[i] = s[i - 1] == '0' ? p[i + 1] + 1 : 0,
q[i] = t[i - 1] == '1' ? q[i + 1] + 1 : 0;
vector<int> np(n + 1), nq(n + 1);
for (int i = n, pp = INF, qq = INF, npp = INF, nqq = INF; i >= 1; --i) {
if (s[i - 1] == '0')
pp = i;
if (s[i - 1] == '1')
npp = pp;
np[i] = npp;

if (t[i - 1] == '0')
nqq = qq;
if (t[i - 1] == '1')
qq = i;
nq[i] = nqq;
}
printf("%d ", n);
for (int i = 2; i <= n; ++i) {
int cnt = 0, idx = 1, last = 0;
while (idx + i - 1 <= n) {
int delta = max(p[idx], q[idx]);
if (p[idx] <= i && np[last] == idx)
np[last] = np[idx];
if (q[idx] <= i && nq[last] == idx)
nq[last] = nq[idx];
last = idx;
if (delta >= i)
cnt += delta / i, idx += delta / i * i;
else
idx = min(np[idx], nq[idx]);
}
printf("%d ", cnt);
}
}
};

int main() {
Solution solution = Solution();
solution.solve();
}
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

## # Problem G - Running Competition

### # 题解

$f(x)=\sum_{i=0}^nx^{x_i}$

$g(x)=\sum_{i=0}^nx^{-x_i}$

#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <vector>
#ifndef M_PI
#define M_PI 3.14159265358979323846264338327950288
#endif

using namespace std;
typedef complex<double> cd;
const cd I{0, 1};

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

void change(vector<cd> &f, int n) {
for (int i = 1, j = n / 2; i < n - 1; i++) {
if (i < j)
swap(f[i], f[j]);
int k = n / 2;
while (j >= k) {
j = j - k;
k = k / 2;
}
if (j < k)
j += k;
}
}

void fft(vector<cd> &f, int n, int rev) {
change(f, n);
for (int len = 2; len <= n; len <<= 1) {
cd omega = exp(I * (2 * M_PI / len * rev));
for (int j = 0; j < n; j += len) {
cd now = 1;
for (int k = j; k < j + len / 2; ++k) {
cd g = f[k], h = now * f[k + len / 2];
f[k] = g + h, f[k + len / 2] = g - h;
now *= omega;
}
}
}
if (rev == -1)
for (int i = 0; i < n; ++i)
f[i] /= n;
}

class Solution {
public:
void solve() {
int n, x, y;
vector<int> a(n + 1);
for (int i = 0; i <= n; ++i)
int q;
vector<bool> vis(x + y + 1);
int k = 1 << (32 - __builtin_clz(x * 8 + 2));
vector<cd> A(k), B(k);
for (int i = 0; i <= n; ++i)
A[a[i] + x] = cd{1, 0}, B[x - a[i]] = cd{1, 0};
fft(A, k, 1);
fft(B, k, 1);
for (int i = 0; i < k; ++i)
A[i] *= B[i];
fft(A, k, -1);
for (int i = 2 * x + 1; i < 4 * x; ++i)
if ((int)round(A[i].real()) > 0)
vis[i - 2 * x + y] = true;
int hi = x + y;
for (int i = 0; i < q; ++i) {
int l;
l >>= 1;
int ans = -1;
for (int j = 1; j * j <= l; ++j) {
if (l % j == 0) {
if (j <= hi && vis[j])
ans = j;
if (l / j <= hi && vis[l / j]) {
ans = l / j;
break;
}
}
}
printf("%d ", ans == -1 ? ans : ans * 2);
}
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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