fsy's blog

燃峥嵘岁月，烈日终破云。

Educational Codeforces Round 71 (Rated for Div. 2) 题解

发表于 更新于
本文字数： 9k 阅读时长 ≈ 8 分钟

比赛链接

昨天困得要命，就没打这场比赛。结果早上起来看到题目，瞬间想打死自己。

edu 场的确简单….

【其他大佬的表现】

zyx rk431 rating = 1670 %%%

yy rk641 rating = 1740 %%%

【A】 There Are Two Types Of Burgers

比较两个汉堡的价格，哪个贵先做哪个。如果还有多余材料，就做另外一种汉堡。

时间复杂度 $O(t)$

代码：

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>
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0;
    LL f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
template <typename T>
inline void write(T x) {
	if(x < 0) {putchar('-'); x = -x;}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
int t, b, p, f, h, c; 
int main() {
	read(t);
	while(t--) {
		read(b); read(p); read(f);
		read(h); read(c);
		int k = b / 2, income = 0;
		if(h > c) {
			income = min(p, k) * h;
			if(k > p) income += c * min(k - p, f);
		} else {
			income = min(f, k) * c;
			if(k > f) income += h * min(k - f, p);
		}
		write(income); puts("");
	}
	return 0;
}

【B】 Square Filling

题目中并未对操作次数做出限制。所以可以想到一种很暴力的做法：暴力扫描 $A$ 中每一个 $2 \times 2$ 的子矩阵，若该子矩阵内全为 $1$，就把 $B$ 中对应的子矩阵全部变成 $1$，反之不做任何操作。

扫描完所有的子矩阵后，若 $A$ 与 $B$ 有不同则无解。

时间复杂度 $O(mn)$。

代码：

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
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0;
    LL f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
template <typename T>
inline void write(T x) {
	if(x < 0) {putchar('-'); x = -x;}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
int n, m;
int a[55][55], b[55][55];
int tot = 0, x[2505], y[2505];
int main() {
	int n, m;
	read(n); read(m);
	_rep(i, 1, n) {
		_rep(j, 1, m) {
			read(a[i][j]);
		}
	}
	_rep(i, 1, n - 1) {
		_rep(j, 1, m - 1) {
			if(a[i][j] && a[i][j + 1] && a[i + 1][j] && a[i + 1][j + 1]) {
				x[++tot] = i; y[tot] = j;
				b[i][j] = 1; b[i][j + 1] = 1; b[i + 1][j] = 1; b[i + 1][j + 1] = 1;
			}
		}
	}
	_rep(i, 1, n) {
		_rep(j, 1, m) {
			if(a[i][j] != b[i][j]) {
				puts("-1"); return 0;
			}
		}
	}
	write(tot); puts("");
	_rep(i, 1, tot) {
		write(x[i]); putchar(' '); write(y[i]); puts("");
	}
	return 0;
}

【C】 Gas Pipeline

考虑 dp。

设 $dp[x][0/1]$ 表示当前已经建好了前 $x$ 个水管，当前高度为 $0/1$ 的最小代价，不难得到转移方程：

$dp[x][0] = \begin{cases} \text{INF when} ; s[x] = 1 \\ \min(dp[x-1][0]+a, dp[x-1][1]+2a) + b; \text{when} ; s[x] = 0 \end{cases}$

$dp[x][1] = \begin{cases} dp[x-1][1] + a + 2b\text{ when} ; s[x] = 1 \\ \min(dp[x-1][0]+2a, dp[x-1][1]+a) + 2b; \text{when} ; s[x] = 0 \end{cases}$

边界为 $dp[0][0] = b$, $dp[0][1] = \text{INF}$。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
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0;
    LL f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
template <typename T>
inline void write(T x) {
	if(x < 0) {putchar('-'); x = -x;}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = '\n') {
	write(x); putchar(sp);
}
int t, n;
LL a, b;
const LL inf = 1e17;
LL dp[200020][2];
string s; 
int main() {
	read(t);
	while(t--) {
		read(n); read(a); read(b);
		cin >> s;
		dp[0][0] = b; dp[0][1] = inf;
		_rep(i, 1, n) {
			if(s[i - 1] == '0') {
				dp[i][0] = min(dp[i - 1][1] + 2 * a, dp[i - 1][0] + a) + b;
				dp[i][1] = min(dp[i - 1][1] + a, dp[i - 1][0] + 2 * a) + 2 * b;
			} else {
				dp[i][0] = inf;
				dp[i][1] = dp[i - 1][1] + 2 * b + a;
			}
		}
		writesp(dp[n][0]);
	}
	return 0;
}

【D】 Number of Permutations

题目要求满足两维数字均不有序的序列的个数，很明显可以将其转化为一个容斥问题：$cnt(GoodSequence) = cnt(All) - cnt(ASorted) - cnt(BSorted) + cnt(ASorted \and BSorted)$

其次，考虑如何计数。

$cnt(All)$ 就等于其所有的可能排列个数，明显等于 $n!$。

再考虑如何计算 $cnt(ASorted)$。设第一维中不同元素个数为 $m$，从小到大排序后这 $m$ 个元素为 $a_1, a_2, \cdots, a_m$，其在第一维中出现的个数分别为 $c_1, c_2, \cdots, c_m$。很明显，对于一个元素 $a_i$，它只有 $c_i$ 个位置可放置，产生的不同情况数即为 $c_i !$。

举个例子，对于序列 $[1,2,2,2,3,1,2,2,3,3]$，$m = 3$，$a = [1, 2, 3]$，$c = [2, 5, 3]$。对于两个 $1$，它只有在前 $2$ 个位置的时候，数组才可能有序。不同的情况数为 $2!$。

所以，根据乘法原理，$cnt(ASorted) = \prod_{i=1}^{m}c_i !$。$cnt(BSorted)$ 做法类似。

$cnt(ASorted \and BSorted)$ 也可以用类似方法计算，但是可能存在第一维有序，但第二维无序的情况。所以要先将读进来的数对按照第一维为第一关键字，第二维为第二关键字排序。再线性扫一遍第二维。如果第二维中存在整数 $i$ 使得 $B[i] > B[i+1]$，则 $cnt(ASorted \and BSorted) = 0$，反之照上面的做法计算即可。

代码：

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
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0;
    LL f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
template <typename T>
inline void write(T x) {
	if(x < 0) {putchar('-'); x = -x;}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = '\n') {
	write(x); putchar(sp);
}
const int maxn = 3e5 + 10;
const LL mod = 998244353ll;
LL n, fac[maxn];
pair<int, int> perm[maxn];
map<pair<int, int>, int> ds;
map<int, int> aa, bb;
int main() {
	read(n);
	fac[0] = 1;
	_rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % mod;
	_rep(i, 1, n) {
		read(perm[i].first); read(perm[i].second);
        aa[perm[i].first]++; bb[perm[i].second]++;
        ds[perm[i]]++;
	}
    sort(perm + 1, perm + n + 1);
    LL ans = fac[n], tmpa = 1, tmpb = 1, tmpab = 1, valid = 1;
    _rep(i, 2, n) {
        if(perm[i].second < perm[i - 1].second) valid = 0;
    }
    map<int, int> :: iterator it;
    for(it = aa.begin(); it != aa.end(); it++) {
        pair<int, int> p = *it;
        tmpa = 1ll * tmpa * fac[p.second] % mod;
    }
    for(it = bb.begin(); it != bb.end(); it++) {
        pair<int, int> p = *it;
        tmpb = 1ll * tmpb * fac[p.second] % mod;
    }
    map<pair<int, int>, int> :: iterator ab;
    for(ab = ds.begin(); ab != ds.end(); ab++) {
        int cnt = (*ab).second;
        tmpab = 1ll * tmpab * fac[cnt] % mod;
    }
    writesp((ans - tmpa + mod - tmpb + mod + tmpab * valid + mod) % mod);
	return 0;
}

【E】 XOR Guessing

首先，设答案为 $X$，每次挑选到的两个数为 $A, B$，返回的异或值为 $C,D$，则可以得到以下两个方程：$X \text{ xor } A = C$，$X \text{ xor } B = D$。从而得到：$X \text{ xor } A \text{ xor } X \text{ xor } B = C \text{ xor } D$。由于 $X \text{ xor } X = 0$，故 $A \text{ xor } B = C \text{ xor } D$。

因此，我们只要构造出两个序列，使其满足：对于任意 $i, j$，满足 $A_i \text{ xor } B_j$ 唯一。就可以确定答案。

这样的序列很好构造。最简单的方法是：把第一个序列设为 $[1, 2, 3, \cdots, 100]$，第二个序列设为 $[1 \times 2^7, 2 \times 2^7, 3 \times 2^7, \cdots, 100 \times 2^7]$。这样子构造，第一个序列的前七位全为 $0$，第二个序列的后七位全为 $0$。二者不影响。则这个序列满足对于任意 $i, j$，$A_i \text{ xor } B_j = A_i + B_j$。明显，$A_i + B_j$ 是唯一的。

所以， 在询问到答案 $C, D$ 后，可以直接得到 $B = (C \text{ xor } D) \text{ Rsh } 7 \text{ Lsh } 7$。输出 $B \text{ xor } D$ 即可。

代码：

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
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0;
    LL f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
template <typename T>
inline void write(T x) {
	if(x < 0) {putchar('-'); x = -x;}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
int a[101], b[101], x;
int main() {
	_rep(i, 1, 100) {
		a[i] = i;
		b[i] = (i << 7);
	}
	cout << "?";
	_rep(i, 1, 100) {
		cout << " " << a[i];
	}
	cout << endl;
	fflush(stdout);
	int c; cin >> c;
	cout << "?";
	_rep(i, 1, 100) {
		cout << " " << b[i];
	}
	cout << endl;
	fflush(stdout);
	int d; cin >> d;
	int b = (c ^ d) >> 7;
	cout << "! " << ((b << 7) ^ d) << endl; 
	return 0;
}

【F】 Remainder Problem

可以考虑设置一个整数 $S$ 和一个二维数组 $sum$，在执行一操作时，对于所有的 $k \leq S$，将 $sum[x][k \mod x]$ 也做修改。如果在执行二操作时，$x \geq S$，就暴力扫每一个符合要求的数统计答案。反之直接返回 $sum[x][y]$。

如果这样做，一次操作的最坏时间复杂度为 $\max(S, \frac{n}{S})$，取 $S = \sqrt{n}$，时间复杂度 $q \sqrt{n}$，其中 $n = 500000$。时限 4 秒，可以通过本题。

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
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0;
    LL f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
template <typename T>
inline void write(T x) {
	if(x < 0) {putchar('-'); x = -x;}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = '\n') {
	write(x); putchar(sp);
}
const int maxn = 5e5 + 10, sq = 7e2 + 10;
int q = 0, opt = 0, x = 0, y = 0, sum[sq][sq], a[maxn];
int main() {
	read(q);
	_rep(i, 1, q) {
		read(opt); read(x); read(y);
		if(opt == 1) {
			a[x] += y;
			_rep(j, 1, sq - 5) {
				sum[j][x % j] += y;
			}
		} else {
			if(x <= sq - 5) {
				writesp(sum[x][y]);
			} else {
				int ans = 0;
				for(int j = y; j <= maxn - 5; j += x) {
					ans += a[j];
				}
				writesp(ans);
			}
		}
	}
	return 0;
}

【G】 Indie Album

暂时不会。留坑，等会了再填。