Educational Codeforces Round 93

        Educational Codeforces Round 93。论刚刚上紫名是一种什么体验。

A. Bad Triangle

        这。。把最小的两个加起来,与最大的一个比较大小即可。

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 N = 500000 + 5;
typedef long long ll;
int n, op[N];
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i);
if (op[1] + op[2] > op[n]) {
printf("-1\n");
} else {
printf("1 2 %d\n", n);
}
}
return 0;
}

B. Substring Removal Game

        每一个人的最佳策略一定是拿当前最长的一段连续的1,不可能拿0。因为如果拿0,要么没有影响,要么使得两段原本不相邻的1相邻,这对对手是有利的,总之拿0不会使自己有任何优势,较小的一段1同理。于是我们统计有哪些连续的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
#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5;
typedef long long ll;
char op[500];
vector<int> vec;
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", op), vec.clear();
int n = strlen(op), l = 0, r;
while (l < n) {
if (op[l] == '0') {
++l;
} else {
r = l;
while (r + 1 < n && op[r + 1] == '1') ++r;
vec.push_back(r - l + 1), l = r + 1;
}
}
sort(vec.begin(), vec.end(), greater<int>());
int ans = 0;
for (int i = 0; i < vec.size(); i += 2) ans += vec[i];
printf("%d\n", ans);
}
return 0;
}

C. Good Subarrays

        预处理前缀和,然后等价于$S(r)-S(l-1)=r-l+1$,即为$S(r)-r=S(l-1)-l+1$。然后我们对于一个$l$,统计有多少个$r$满足这个式子。统计的方法有很多,使用$map$是一个不错的策略,当然也可以用二分的方法。

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

#define N 200005
using namespace std;

int n, tmp[N], m;
char op[N];
int sum[N];
vector<int> vec[N];
set<int> ssp;
int fb(int l, int r, int s, int who)
{
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%s", &n, op + 1), ssp.clear();
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + op[i] - '0', tmp[i] = sum[i] - i;
vec[i].clear();
}
sort(tmp + 1, tmp + n + 1), m = unique(tmp + 1, tmp + n + 1) - tmp - 1;
for (int i = 1; i <= n; i++) {
int what = lower_bound(tmp + 1, tmp + m + 1, sum[i] - i) - tmp;
vec[what].push_back(i);
ssp.insert(sum[i] - i);
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
int ss = sum[i - 1] - i + 1;
if (ssp.count(ss) == 0) continue;
int at = lower_bound(tmp + 1, tmp + m + 1, ss) - tmp;
int l = -1, r = vec[at].size() - 1, mid;
while (l < r) {
if (r == l + 1) break;
mid = (l + r) >> 1;
if (vec[at][mid] >= i)
r = mid;
else
l = mid;
}
if (vec[at][r] >= i) ans += vec[at].size() - r;
}
printf("%lld\n", ans);
}
return 0;
}

D. Colored Rectangles

        首先贪心是不对的,考虑其它做法。
        容易发现,对于$ab+cd$,如果$a>d$且$c>b$,则$ac+bd>ab+cd$,这说明我们应该尽可能地使较大的数乘在一起(如果只有两个序列,贪心是可以的),但是这里有三个序列,于是需要$DP$,$DP$方程很好列。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
vector<int> R, G, B;
int n, r, g, bb;
ll dp[201][201][201];
ll DP(int a, int b, int c)
{
if (~dp[a][b][c]) return dp[a][b][c];
if ((a == 0 && b == 0) || (a == 0 && c == 0) || (b == 0 && c == 0)) return 0;
if (a > 0 && b > 0 && c > 0) {
return dp[a][b][c] =
max(R[a] * G[b] + DP(a - 1, b - 1, c), max(R[a] * B[c] + DP(a - 1, b, c - 1), G[b] * B[c] + DP(a, b - 1, c - 1)));
} else {
if (a == 0) {
return dp[a][b][c] = DP(a, b - 1, c - 1) + G[b] * B[c];
} else if (b == 0) {
return dp[a][b][c] = DP(a - 1, b, c - 1) + R[a] * B[c];
} else {
return dp[a][b][c] = DP(a - 1, b - 1, c) + R[a] * G[b];
}
}
}
int main()
{
scanf("%d%d%d", &r, &g, &bb), memset(dp, -1, sizeof(dp));
R.push_back(0), G.push_back(0), B.push_back(0);
for (int i = 1, x; i <= r; i++) scanf("%d", &x), R.push_back(x);
for (int i = 1, x; i <= g; i++) scanf("%d", &x), G.push_back(x);
for (int i = 1, x; i <= bb; i++) scanf("%d", &x), B.push_back(x);
sort(R.begin(), R.end());
sort(B.begin(), B.end());
sort(G.begin(), G.end());
printf("%lld", DP(r, g, bb));
return 0;
}

E. Two Types of Spells

        发现第二个$spell$的好处就是能把下一个卡的伤害乘个2,这给我们一个解题思路。假如现在有$x$个第二个$spell$,贪心地想,如果我们把最大的$x$个乘上二,这样显然是最优的。
        问题是一个二号$spell$可能也位于前$x$大中,这就需要分类讨论。如果前$x$个中有不到$x$个二号卡(假设$y$个),这样剩下的$x-y$个一号卡需要$x-y$个二号卡来做乘二的处理,刚好有$x-y$个二号卡不在前$x$大中,就拿它们来处理这$x-y$张一号卡,然后把$y$张二号卡全部插到某个二号卡和一号卡的间隙中(这个间隙是必然存在的,因为$x-y>0$),于是全部满足条件。也就是说$x>y$时,答案就是总的伤害加上前$x$大伤害。
        如果$x=y$,这样间隙就没有了,我们必须牺牲掉$x$张二号卡中的一张,当然是牺牲伤害最小的那一个,与此同时可以多出一个处理一号卡的名额,当然要处理一号卡中最大的那一个。即$x=y$时,答案就是总的伤害加上前$x-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
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct Node
{
int ch[2], v, num, key, type;
ll sum, tn;

Node()
: num(0)
{
ch[0] = ch[1] = 0;
}
} node[300005];

int root = 0, cnt = 0;

inline void update(int x)
{
node[x].num = node[node[x].ch[0]].num + node[node[x].ch[1]].num + 1;
node[x].tn = node[node[x].ch[0]].tn + node[node[x].ch[1]].tn + node[x].type;
node[x].sum = node[node[x].ch[0]].sum + node[node[x].ch[1]].sum + node[x].v;
}

inline int addNode(int x, int type)
{
node[++cnt].v = x, node[cnt].ch[0] = node[cnt].ch[1] = 0;
node[cnt].num = 1, node[cnt].key = rand(), node[cnt].type = type;
node[cnt].tn = type, node[cnt].sum = x;
return cnt;
}

void split(int rt, int& a, int& b, int v)
{
if (rt == 0) {
a = b = 0;
return;
}
if (node[node[rt].ch[0]].num < v)
a = rt, split(node[rt].ch[1], node[a].ch[1], b, v - node[node[rt].ch[0]].num - 1);
else
b = rt, split(node[rt].ch[0], a, node[b].ch[0], v);
update(rt);
}

void merge(int& rt, int a, int b)
{
if (a == 0 || b == 0) {
rt = a + b;
return;
}
if (node[a].key > node[b].key) {
rt = a, merge(node[a].ch[1], node[a].ch[1], b);
} else {
rt = b, merge(node[b].ch[0], a, node[b].ch[0]);
}
update(rt);
}

void split2(int rt, int& a, int& b, int v)
{
if (rt == 0) {
a = b = 0;
return;
}
if (node[rt].v <= v)
a = rt, split2(node[rt].ch[1], node[a].ch[1], b, v);
else
b = rt, split2(node[rt].ch[0], a, node[b].ch[0], v);
update(rt);
}
int n, num;
inline void add(int x, int tp)
{
int a, b, c;
split2(root, a, c, x);
split2(a, a, b, x - 1);
if (tp == 1)
merge(b, b, addNode(x, tp));
else
merge(b, addNode(x, tp), b);
merge(a, a, b), merge(root, a, c);
++num;
}
inline void del(int x, int tp)
{
int a, b, c;
split2(root, a, c, x);
split2(a, a, b, x - 1);
if (tp == 1) {
if (node[b].type == 0)
node[b].ch[1] = 0, update(b);
else
b = 0;
} else if (tp == 0) {
if (node[b].type == 1)
node[b].ch[0] = 0, update(b);
else
b = 0;
}
merge(a, a, b), merge(root, a, c);
--num;
}
int findR(int rt)
{
if (rt == 0) return 0;
if (node[rt].ch[1]) return findR(node[rt].ch[1]);
return node[rt].v;
}
int main()
{
srand(time(0));
scanf("%d", &n);
while (n--) {
int tp, d;
scanf("%d%d", &tp, &d);
if (d > 0) {
add(d, tp);
} else {
del(-d, tp);
}
ll ans = node[root].sum;
// cout << ans << endl;
int what = node[root].tn;
if (what == 0) {
printf("%lld\n", ans);
continue;
}
int a, b;
split(root, a, b, num - what);
if (node[b].tn < what) {
ans += node[b].sum;
} else {
ans += findR(a);
merge(root, a, b);
split(root, a, b, num - what + 1);
ans += node[b].sum;
}
merge(root, a, b);
printf("%lld\n", ans);
}

F. Controversial Rounds

        本题很好,强烈建议一做。
        首先可以想到一个$dp$,设$dp(x)$为前$x$段的答案,长度为$len$时,如果可以将$[x-len+1,x]$化为全$0$或者全$1$,这样就可以转移到$dp(x-len)+1$,另一个转移即为$dp(x-1)$。
        可以发现,当可以转移的时候必然有$dp(x-len)+1\geq dp(x-1)$,这告诉我们只要能凑够$len$的区间,就尽可能凑,这就变成一个贪心问题了。
        既然可以贪心,就从左向右尽可能凑长度为$len$的区间。暴力做每一次都是$O(n)$的,这样就是$O(n^2)$不可取。
        解决这种需要枚举长度的区间问题有一个通用思路:打点法。我们每$len$个单位打一个点,显然每一个$len$长的段都必然会包括唯一的一个点。我们通过枚举这些点就能求出最多有多少个合法区间。具体来说我们从左到右枚举这些点,同时维护上一个长度为$len$的段的右端点,然后贪心地选下一个(能选就选)。
        复杂度是$O(\sum_{i=1}^n\frac{n}{i})=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
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 5;
typedef long long ll;
int n, ltr[N][2], rtl[N][2];
char op[N];
inline int solve(int at, int last, int len, int who)
{
if (op[at] != '?' && op[at] != who + '0') return 0x3f3f3f3f;
int pre = max(last + 1, at - ltr[at][who] + 1);
int nxt = at + rtl[at][who] - 1;
if (nxt - pre + 1 < len) return 0x3f3f3f3f;
return pre + len - 1;
}
int main()
{
scanf("%d%s", &n, op + 1);
for (int i = 1; i <= n; i++) {
ltr[i][0] = op[i] == '1' ? 0 : ltr[i - 1][0] + 1;
ltr[i][1] = op[i] == '0' ? 0 : ltr[i - 1][1] + 1;
}
for (int i = n; i >= 1; i--) {
rtl[i][0] = op[i] == '1' ? 0 : rtl[i + 1][0] + 1;
rtl[i][1] = op[i] == '0' ? 0 : rtl[i + 1][1] + 1;
}
for (int len = 1; len <= n; len++) {
int last = 0, ans = 0;
for (int i = len; i <= n; i += len) {
int to = min(solve(i, last, len, 0), solve(i, last, len, 1));
if (to != 0x3f3f3f3f) last = to, ++ans;
}
printf("%d ", ans);
}
return 0;
}

G. Running Competition

        先考虑一个简单问题:给$n$个数,在给若干次询问,每次给一个数$x$,查询$x$是否可以表示成先前给的$n$个数中,某两个数的差。
        当数的范围不很大时,我们可以使用$FFT/NTT$在$O(nlogn)$预处理,$O(1)$查询的复杂度下优雅地解决这个问题。具体来说,我们构造多项式:

        其中$a_i$就是给定的第$i$个数。
        然后用$FFT/NTT$将两个多项式乘起来就可以很快地判断。
        本题中,每一个路径必然是一个矩形,长度可以表示成$2(a_j-a_i)+2y$,它需要是给定数的因子。
        枚举因子,然后判断它是否合法即可,预处理和判断即为上面的$FFT/NTT$思路。

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
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct Complex
{
double a, b;

Complex(double a = 0, double b = 0)
: a(a), b(b) {}

Complex operator+(Complex c)
{
return {a + c.a, b + c.b};
}

Complex operator*(Complex c)
{
return {a * c.a - b * c.b, a * c.b + b * c.a};
}

Complex operator-(Complex c)
{
return {a - c.a, b - c.b};
}
};
struct Pol
{
int l;
Complex op[N << 2];
} p1, p2, pa;
const double Pi = acos(-1.0);
int tr[N << 2];

inline void FFT(int l, Complex* c, int type)
{
for (int i = 0; i < l; i++)
if (i < tr[i]) swap(c[i], c[tr[i]]);
for (int mid = 1; mid < l; mid <<= 1) {
Complex wn(cos(Pi / mid), type * sin(Pi / mid));
for (int len = mid << 1, j = 0; j < l; j += len) {
Complex w(1.0, 0);
for (int k = 0; k < mid; k++, w = w * wn) {
Complex x = c[j + k], y = w * c[j + mid + k];
c[j + k] = x + y, c[j + mid + k] = x - y;
}
}
}
}

inline void multiple(Pol* ans, Pol* a, Pol* b)
{
int l = 1, le = 0;
while (l <= a->l + b->l) l <<= 1, ++le;
for (int i = 0; i < l; i++) {
tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (le - 1));
if (i > a->l) a->op[i] = 0;
if (i > b->l) b->op[i] = 0;
}
FFT(l, a->op, 1), FFT(l, b->op, 1);
for (int i = 0; i < l; i++) a->op[i] = a->op[i] * b->op[i];
FFT(l, a->op, -1), ans->l = a->l + b->l;
for (int i = 0; i <= ans->l; i++) ans->op[i].a = a->op[i].a / l;
}
int n, x, y;
vector<int> yz;
int main()
{
scanf("%d%d%d", &n, &x, &y);
p1.l = x, p2.l = x;
for (int i = 0, a; i <= n; i++) {
scanf("%d", &a);
// a = i;
p1.op[a] = Complex(1, 0), p2.op[x - a] = Complex(1, 0);
}
multiple(&pa, &p1, &p2);
// for (int i = 0; i <= pa.l; i++) cout << pa.op[i].a << " ";
// cout << endl;
int q;
scanf("%d", &q);
while (q--) {
int L;
scanf("%d", &L), yz.clear();
for (int i = 1; 1ll * i * i <= L; i++) {
if (L % i == 0) {
yz.push_back(i);
if (L / i != i) yz.push_back(L / i);
}
}
sort(yz.begin(), yz.end());
for (int i = yz.size() - 1; i >= 0; i--) {
if (yz[i] & 1) continue;
int sv = (yz[i] - 2 * y) >> 1;
// cout << sv << endl;
if (sv <= 0) continue;
if (fabs(pa.op[sv + x].a) >= 0.5) {
printf("%d ", yz[i]);
goto tag;
}
}
printf("-1 ");
tag:;
}
return 0;
}

0%