Educational Codeforces Round 76 (Rated for Div. 2)
/ / 阅读耗时 18 分钟 Educational Codeforces Round 76 (Rated for Div. 2)题解。比赛链接
A. Two Rival Students
很水，尽可能地把两个人向两侧靠即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
int n, x, a, b;
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d%d", &n, &x, &a, &b);
if (a > b)swap(a, b);
int most = a - 1 + n - b;
if (x >= most)cout << n - 1 << endl;
else cout << b - a + x << endl;
}
return 0;
}
B. Magic Stick
我们只要把这个数尽可能变大即可，变大就需要第一种操作，可以理解为把质因子2换为3。
这样的话，从$2^1m_1$找到$2^sm_s$，这里的$m_i$都可以$O(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
using namespace std;
int b;
long long getMax(long long a) {
long long ans = 1, s = 0, maxn = a;
while ((ans << 1) <= a)ans <<= 1, ++s;
for (int i = 1; i <= s; i++) {
long long z = a / (1 << i);
maxn = max(maxn, 1ll * z * int(pow(3, i)));
}
if (maxn >= b)return maxn;
else if (maxn <= a)return a;
else return max(getMax(maxn), a);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int a;
scanf("%d%d", &a, &b);
if (b <= a)cout << "YES" << endl;
else {
long long maxn = getMax(a);
if (maxn >= b)cout << "YES" << endl;
else cout << "NO" << endl;
}
}
return 0;
}
C. Dominated Subarray
对于最短的一个串，它的两侧一定是相同的，并且就是那一个出现次数最多的数字，并且其中所有的数字都只出现一次。根据这样的性质，扫一遍数组就出答案了。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
using namespace std;
int op[200005], to[200005], now;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, ans = 0x7fffffff;
scanf("%d", &n), memset(to, 0, sizeof(to));
for (int i = 1; i <= n; i++)scanf("%d", op + i);
if (n == 1) {
cout << -1 << endl;
continue;
} else if (n == 2) {
if (op[1] == op[2])cout << 2 << endl;
else cout << -1 << endl;
continue;
}
to[op[1]] = 1, to[op[2]] = 2;
if (op[1] != op[2])now = 1;
else {
cout << 2 << endl;
continue;
}
for (int i = 3; i <= n; i++) {
if (to[op[i]] == 0);
else now = to[op[i]] + 1, ans = min(ans, i - now + 2);
to[op[i]] = i;
}
if (ans == 0x7fffffff)cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}
D. Yet Another Monster Killing Problem
贪心地想，我们应该最大化每一天的击杀数量，可以证明这样一定是最优的。
我们将所有英雄按其力量值排序，排完后对耐力建立后缀最大值数组（我这里脑子抽了，建了ST表，不过这样当然也是可以的）。从1开始遍历所有怪物，用它的力量值去截取英雄的区间（显然，这是一段$[l,m]$的区间，并且$l$一定是递增的），这一步可以二分出来。截取区间之后，找出这一段区间的耐力最大值，如果不小于当前击杀数，这说明至少存在一名英雄满足当前要求，这样就继续遍历下一个怪物。否则就说明已经没有满足条件的英雄，那么就进入下一天。
时间复杂度$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
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
using namespace std;
int n, mp[200005], m, ans, bin[25], lg[200005], st[25][200005];
struct Node {
int p, s;
bool operator<(Node a) {
return p < a.p;
}
} hero[200005];
inline int getMax(int l, int r = m) {
int t = lg[r - l + 1];
return max(st[t][l], st[t][r - bin[t] + 1]);
}
inline int getRight(int at) {
int l = 0, r = m, mid;
while (l < r) {//(,]
if (r == l + 1) {
if (hero[r].p >= at)return r;
else return inf;
}
mid = (l + r) >> 1;
if (hero[mid].p >= at)r = mid;
else l = mid;
}
}
int main() {
int t;
scanf("%d", &t);
bin[0] = 1, lg[0] = -1;
for (int i = 1; i < 25; i++)bin[i] = bin[i - 1] << 1;
for (int i = 1; i <= 200000; i++)lg[i] = lg[i >> 1] + 1;
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", mp + i);
scanf("%d", &m);
for (int i = 1; i <= m; i++)scanf("%d%d", &hero[i].p, &hero[i].s);
ans = 1, sort(hero + 1, hero + m + 1);
for (int i = 1; i <= m; i++)st[0][i] = hero[i].s;
for (int i = 1; i < 25; i++) {
for (int j = 1; j <= m; j++) {
if (j + bin[i] - 1 <= m)st[i][j] = max(st[i - 1][j], st[i - 1][j + bin[i - 1]]);
}
}
for (int i = 1, at = 1, num = 0; i <= n;) {
at = max(at, getRight(mp[i]));
if (at == inf) {
printf("-1\n");
goto to;
}
if (num + 1 <= getMax(at))++num, ++i;
else at = 1, num = 0, ++ans;
}
printf("%d\n", ans);
to:;
}
return 0;
}
E. The Contest
设$S1,S2,S3$是三种值的前缀和数组，答案显然下式的最小值：
枚举$a$的值，可以发现对于$b$来说，只有$S2(b)-S3(b)$影响答案，那么对于每一个$b$维护这个值，用后缀最大值数组$O(1)$找出最值即可。复杂度$O(n)$。（我又脑抽用了ST表，升复杂度为$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
36
using namespace std;
int s1[N], s2[N], s3[N], k1, k2, k3, n, op[N], bin[20], lg[N], st[20][N];
inline int getMax(int l, int r = n) {
int t = lg[r - l + 1];
return max(st[t][l], st[t][r - bin[t] + 1]);
}
int main() {
scanf("%d%d%d", &k1, &k2, &k3);
n = k1 + k2 + k3;
for (int i = 1, x; i <= k1; i++)scanf("%d", &x), op[x] = 1;
for (int i = 1, x; i <= k2; i++)scanf("%d", &x), op[x] = 2;
for (int i = 1, x; i <= k3; i++)scanf("%d", &x), op[x] = 3;
for (int i = 1; i <= n; i++) {
s1[i] = s1[i - 1] + (op[i] == 1);
s2[i] = s2[i - 1] + (op[i] == 2);
s3[i] = s3[i - 1] + (op[i] == 3);
}
bin[0] = 1, lg[0] = -1;
for (int i = 1; i < 20; i++)bin[i] = bin[i - 1] << 1;
for (int i = 1; i <= 200000; i++)lg[i] = lg[i >> 1] + 1;
for (int i = 0; i <= n; i++)st[0][i] = s2[i] - s3[i];
for (int i = 1; i < 20; i++) {
for (int j = 0; j <= n; j++) {
if (j + bin[i] - 1 <= n)st[i][j] = max(st[i - 1][j], st[i - 1][j + bin[i - 1]]);
}
}
int ans = 0x7fffffff;
for (int i = 0; i <= n; i++)ans = min(ans, n - (s1[i] + getMax(i) + s3[n] - s2[i]));
printf("%d", ans);
return 0;
}
F. Make Them Similar
神奇的meet-in-the-middle算法。
一眼看过去没什么好办法，上暴力的话，$2^{30}$复杂度过高。这样我们可以枚举$x$的前半部分，再枚举后半部分，只需要$2^{16}$计算量。
对于这两部分，我们需要合并答案。如果暴力合并，又回到$2^{30}$计算量，需要考虑其它做法。
对于每一部分的每一种情况，都需要记录所有数的二进制位含1的数量，会得到一个n维向量。我们希望在这两部分找到这样一对组合，使得它们的向量相加后各个维上的数相等。
显然，这种匹配方式看上去只能暴力，不过这里有一个很巧妙的做法：将第一部分的所有维上的数减去最小值。对于第二维，先用15减去自身，再减去最小值。这样找到两个相等的向量即可，可以哈希也可以用map+vector暴力。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
using namespace std;
int op[300], n;
inline int get(int x) {
int p = 0;
while (x) {
if (x & 1)++p;
x >>= 1;
}
return p;
}
map<vector<int>, int> mmp;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", op + i);
for (int i = 0; i < (1 << 15); i++) {
vector<int> vvp;
for (int j = 1; j <= n; j++)vvp.push_back(get((op[j] ^ (i << 15)) & (((1 << 15) - 1) << 15)));
int minn = *min_element(vvp.begin(), vvp.end());
for (int &j : vvp)j -= minn;
mmp.insert(pair<vector<int>, int>(vvp, i));
}
for (int i = 0; i < (1 << 15); i++) {
vector<int> vvp;
for (int j = 1; j <= n; j++)vvp.push_back(get((op[j] ^ i) & ((1 << 15) - 1)));
for (int &j : vvp)j = 15 - j;
int minn = *min_element(vvp.begin(), vvp.end());
for (int &j : vvp)j -= minn;
if (mmp.count(vvp)) {
printf("%d", mmp[vvp] << 15 | i);
return 0;
}
}
printf("-1");
return 0;
}
G. Divisor Set
最佳答案集合肯定是这样的：所有恰包含有$k$个质因子的所有$x$的因子组成的集合，更明确地说是包含$\lfloor \frac {n}{2}\rfloor$个质因子的因子集合。为什么是这样我也不会证
这样只需要找到有多少中情况得到恰好$k$个质因子的因子数，考虑生成函数。
对于指数为$s$的质因子$p$，构造多项式：
把所有的质因子都构造这样一个多项式，然后乘起来，然后$k$次方项就是方案数。
这些多项式乘起来的最高次是$n$次的，但是如果暴力地乘，会使得后期较大的多项式去乘较小的多项式，无形中提升了复杂度，会TLE。为了防止这种情况的发生，我们可以尽可能将较小的先乘在一起，然后再不断向上合并，这一步需要分治乘。
多项式乘法的话，当然是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
using namespace std;
int tr[N << 2];
struct Pol {
int l, op[N << 2] = {0};
} a, b;
int qPow(int a, int b) {
int ans = 1, x = a;
while (b) {
if (b & 1)ans = 1ll * ans * x % MOD;
x = 1ll * x * x % MOD, b >>= 1;
}
return ans;
}
inline void NTT(int l, int *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) {
int wn = qPow(G, (MOD - 1) / (mid << 1));
if (type == -1)wn = qPow(wn, MOD - 2);
for (int len = mid << 1, j = 0; j < l; j += len) {
int w = 1;
for (int k = 0; k < mid; k++, w = 1ll * w * wn % MOD) {
int x = c[j + k], y = 1ll * w * c[j + mid + k] % MOD;
c[j + k] = (1ll * x + y) % MOD, c[j + mid + k] = (1ll * x - y) % MOD;
}
}
}
}
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;
}
NTT(l, a->op, 1), NTT(l, b->op, 1);
for (int i = 0; i < l; i++)a->op[i] = 1ll * a->op[i] * b->op[i] % MOD;
NTT(l, a->op, -1), l = qPow(l, MOD - 2), ans->l = a->l + b->l;
for (int i = 0; i <= ans->l; i++)ans->op[i] = 1ll * a->op[i] * l % MOD;
}
vector<int> vvp;
map<int, int> mmp;
int n;
vector<int> solve(int l, int r) {
if (l == r) {
vector<int> s;
for (int i = 0; i <= vvp[l]; i++)s.push_back(1);
return s;
}
int mid = (l + r) >> 1;
vector<int> aa = solve(l, mid), bb = solve(mid + 1, r);
for (int i = 0; i < aa.size(); i++)a.op[i] = aa[i];
for (int i = 0; i < bb.size(); i++)b.op[i] = bb[i];
a.l = aa.size() - 1, b.l = bb.size() - 1;
multiple(&a, &a, &b);
vector<int> ans;
for (int i = 0; i <= a.l && i <= (n >> 1); i++)ans.push_back(a.op[i]);
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1, x; i <= n; i++)scanf("%d", &x), ++mmp[x];
for (pair<int, int> s:mmp)vvp.push_back(s.second);
vector<int> a = solve(0, vvp.size() - 1);
printf("%d", (a[n >> 1] + MOD) % MOD);
return 0;
}