2021CCPC东北四省赛 解题报告

2021CCPC东北四省赛

A. Matrix

大致题意

你需要用$[1,n^2]$的所有数字去填充一个$n\times n$的矩阵.

定义$a[]$, 其中$a_i$为矩阵中第$i$行中的最小值. 定义 S = { a 1 , a 2 , . . . , a n } ∩ { 1 , 2 , . . . , n } S = \{ a_1, a_2, ..., a _n\} \cap \{ 1, 2, ..., n\} S={a1​,a2​,...,an​}∩{1,2,...,n}.

我们需要计算所有情况的$\sum |S|$. 最后$\mathrm{m}\mathrm{o}\mathrm{d}998244353$ 输出答案.

解题思路

思维

我们考虑到可以产生贡献的数字区间为$[1,n]$, 因此我们不妨计算每个数字产生贡献的情况, 然后进行加和.

假设当前考虑$m$产生的贡献, 那么对于$m$我们可以从$n$行中选择出一行, 对于该行上的剩余$n-1$个数字, 应当都是大于$m$的数字, 因此选法为$C_{n^2-m}^{n-1}$, 同时该行的数字可以任意排列, 情况为$n!$. 对于剩余数字可以任意排列$(n^2-n)!$

因此最终$m$的贡献为: $n\times C_{n^2-m}^{n-1}\times n!\times (n^2-n)!$

(PS: 队友也想出了另外一种方式计算, 公式: $n^2\times (n^2-m)!\times A_{n^2-n}^{m-1}$)

---

我们只需要枚举$m\in [1,n]$, 然后把结果累加即可

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 5E3 + 10, M = N * N, mod = 998244353;
int fpow(int a, int b) {
	ll res = 1; a %= mod;
	while (b) {
		if (b & 1) res = res * a % mod;
		b >>= 1;
		a = 1ll * a * a % mod;
	}
	return res;
}

int num[M], innum[M];
void init(int n = M - 5)
{
	num[0] = innum[0] = 1;
	for (int i = 1; i <= n; ++i) {
		num[i] = 1ll * num[i - 1] * i % mod;
	}
	innum[n] = fpow(num[n], mod - 2) % mod;
	for (int i = n - 1; i >= 1; i--) {
		innum[i] = 1ll * innum[i + 1] * (i + 1) % mod;
	}
}
int C(int a, int b) { return 1ll * num[a] * innum[a - b] % mod * innum[b] % mod; }
int main()
{
	init();

	int t; scanf("%d", &t);
	while (t--) {
		ll n; scanf("%lld", &n);

		ll res = 0;
		rep(i, n) {
			res = (res + n * C(n * n - i, n - 1) % mod * num[n] % mod * num[n * n - n]) % mod;
		}
		printf("%lld\n", res);
	}

	return 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

---

C. Vertex Deletion

https://blog.csdn.net/qq_49494204/article/details/120112398

---

D. Lowbit

大致题意

给定一个长度为$n$的序列$a[]$, 有如下两种操作:

1 l r, 对于$[l,r]$的每个数字$a_i$, 都加上$lowbit(a_i)$.

2 l r 查询$[l,r]$区间的区间和.

解题思路

线段树

首先本题读完, 我们很容易想到这就是线段树的区间操作.

我们考虑到比较复杂的修改操作, 和通常的区间修改相比, 每个位置加lowbit, 好像是无法直接通过计算来维护的.

于是我们考虑$x+lowbit(x)$的性质. 我们发现如果 x ∈ { 2 的 整 次 幂 } x \in \{2的整次幂\} x∈{2的整次幂}, 则相当于每次操作, $x=x\times 2$.
我们再考虑到, 对于某个数字$x$而言, 其至多会加$logx$次$lowbit(x)$, 使得 x ′ ∈ { 2 的 整 次 幂 } x' \in \{ 2的整次幂\} x′∈{2的整次幂}.

因此我们得出结论: 对于不是2的整次幂的位置, 我们进行暴力修改, 总的暴力修改复杂度为$O(nlog|a_i|)$. 对于是2的整次幂的位置, 我们进行区间乘2操作即可.

树内需要维护的信息: 区间和, 区间内元素是否都为2的整次幂, 区间乘懒标记.

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10, mod = 998244353;

int lowbit(int x) { return x & -x; }
bool judge(int x) { return bitset<32>(x).count() == 1; }

int w[N];
struct node {
	int l, r;
	ll sum; bool flag;
	int lazy;
}t[N << 2];
void pushdown(node& op, int lazy) {
	op.lazy = 1ll * op.lazy * lazy % mod;
	op.sum = (op.sum * lazy) % mod;
}
void pushdown(int x) {
	if (t[x].lazy == 1) return;
	pushdown(t[x << 1], t[x].lazy), pushdown(t[x << 1 | 1], t[x].lazy);
	t[x].lazy = 1;
}

void pushup(int x) {
	t[x].sum = (t[x << 1].sum + t[x << 1 | 1].sum) % mod;
	t[x].flag = t[x << 1].flag and t[x << 1 | 1].flag;
}

void build(int l, int r, int x = 1) {
	t[x] = { l, r, w[l], 0, 1 };
	if (l == r) { t[x].flag = judge(w[l]); return; }
	int mid = l + r >> 1;
	build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
	pushup(x);
}

void modify(int l, int r, int x = 1) {
	if (l <= t[x].l and r >= t[x].r) {
		if (t[x].flag) { //区间都是2的整次幂, 直接乘2
			pushdown(t[x], 2);
			return;
		}

		if (t[x].l == t[x].r) {
			t[x].sum += lowbit(t[x].sum);
			t[x].flag = judge(t[x].sum);
			return;
		}
	}
	pushdown(x);
	int mid = t[x].l + t[x].r >> 1;
	if (l <= mid) modify(l, r, x << 1);
	if (r > mid) modify(l, r, x << 1 | 1);
	pushup(x);
}

ll ask(int l, int r, int x = 1) {
	if (l <= t[x].l and r >= t[x].r) return t[x].sum;
	pushdown(x);
	int mid = t[x].l + t[x].r >> 1;
	ll res = 0;
	if (l <= mid) res = ask(l, r, x << 1);
	if (r > mid) res = (res + ask(l, r, x << 1 | 1)) % mod;
	return res;
}
int main()
{
	int T; cin >> T;
	while (T--) {
		int n; scanf("%d", &n);
		rep(i, n) scanf("%d", &w[i]);
		build(1, n);

		int m; scanf("%d", &m);
		while (m--) {
			int tp, l, r; scanf("%d %d %d", &tp, &l, &r);
			if (tp == 1) modify(l, r);
			else printf("%lld\n", ask(l, r));
		}
	}
    
	return 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

---

E. Easy Math Problem

大致题意

给定数字$a$, 问能否找到一个$b$, 使得$b$是$a$的倍数, 且$b$可以表示为$b=x+y+z$, 其中$x,y,z$为$b$的不同因子.

解题思路

令$b=6a$, 则$b=a+2a+3a$.

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
int main(void)
{
    int t; cin >> t;
    while (t--) {
        ll n; scanf("%lld", &n);
        n *= 6;
        printf("%lld 3\n", n);
        printf("%lld %lld %lld\n", n / 6, n / 3, n / 2);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

I. Takeaway

不会, 太难了.

---

K. City

大致题意

给出$n$个点, $m$条无向边, $q$个询问.

每条边有权值$w$, 每次询问删除所有权值小于$p$的边后, 图中剩余的所有节点中, 能相互到达的节点对数.

解题思路

思维

首先考虑到所有边都是无向边, 因此如果某个块是连通的, 则块内所有节点均可相互到达. 因此产生的贡献为: $C_n^2,n为块大小$.

因此对于每个询问, 我知道需要知道当前有多少个连通块和每个连通块的大小即可.

---

并查集 + 离线询问

我们考虑用并查集去维护连通块信息.
由于是$q$次查询, 我们如果每次暴力维护连通块信息, 复杂度会是$O(mqlogn)$.

我们考虑把询问离线, 进行从大到小排序. 初始认为图是一个仅有$n$个点的空图, 设当前询问为$p_i$, 我们把所有边权$w_i\ge p_i$的边加入图中.

如果我们按照从小到大排序, 那么我们初始情况应认为m条边都存在图中, 每次我们要删除小于$p_i$的边. 由于并查集的删除操作并不好实现, 因此我们考虑从大到小排序.

---

考虑如何维护加边后的答案贡献$sum$:

首先对于初始空图的情况, $sum=0$. 当我们合并两个连通块$a$和$b$时, 我们可以先减去原先两个连通块的贡献, 然后再加上合并后的新连通块贡献.

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 1E5 + 10;
int p[N], cou[N];
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

ll res[N * 2]; //所以说好的2E5询问, 为什么上限只有1E5
ll sum = 0;
inline ll fact(ll x) { return x * (x - 1) / 2; } //计算C(n, 2)
void add(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	sum = sum - fact(cou[a]) - fact(cou[b]);
	cou[a] += cou[b], p[b] = a;
	sum += fact(cou[a]);
}
int main()
{
	int t; cin >> t;
	while (t--) {
		sum = 0;
		int n, m, q; scanf("%d %d %d", &n, &m, &q);
		rep(i, n) p[i] = i, cou[i] = 1; //dsu init

		map<int, vector<PII>, greater<>> edge; //省去离散化
		rep(i, m) {
			int a, b, c; scanf("%d %d %d", &a, &b, &c);
			edge[c].push_back({ a, b });
		}

		vector<PII> v;
		rep(i, q) {
			int k; scanf("%d", &k);
			v.push_back({ k, i });
		}
		sort(v.begin(), v.end(), greater<>());

		auto it = edge.begin();
		for (auto& [val, id] : v) {
			while (it != edge.end() and it->first >= val) {
				for (auto& [a, b] : it->second) {
					add(a, b);
				}
				++it;
			}

			res[id] = sum;
		}

		rep(i, q) printf("%lld\n", res[i]);
	}
    
	return 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

---

M. Master of Shuangpin

大致题意

模拟双拼

解题思路

按照题目要求模拟即可.

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1005;
char s[N];

unordered_map<string, char> mp = {
		{ "iu", 'q' }, { "ei", 'w' }, { "uan", 'r' }, { "ue", 't' },
		{ "un", 'y' }, { "sh", 'u' }, { "ch", 'i' }, { "uo", 'o' },
		{ "ie", 'p' }, { "ong", 's' }, { "iong", 's' }, { "ai", 'd' },
		{ "en", 'f' }, { "eng", 'g' }, { "ang", 'h' }, { "an", 'j' },
		{ "uai", 'k' }, { "ing", 'k' }, { "uang", 'l' }, { "iang", 'l' },
		{ "ou", 'z' }, { "ia", 'x' }, { "ua", 'x' }, { "ao", 'c' },
		{ "zh", 'v' }, { "ui", 'v' }, { "in", 'b' }, { "iao", 'n' },
		{ "ian", 'm' }
};
int main()
{
	for (char c = 'a'; c <= 'z'; ++c) {
		string ss(1, c);
		mp[ss] = c;
	}

	while (~scanf("%s", s + 1)) {
		int n = strlen(s + 1);
		if (n == 1) printf("%c%c", s[1], s[1]);
		else if (n == 2) printf("%s", s + 1);
		else {
			string str = s + 1;
			if (mp.count(str)) {
				printf("%c%c", str[0], mp[str]);
			}
			else {
				string a;
				for (int i = 0; i < str.size() - 1; ++i) {
					a += str[i];
					string b = str.substr(i + 1);

					if (mp.count(a) and mp.count(b)) {
						printf("%c%c", mp[a], mp[b]);
						break;
					}
				}
			}
		}
		putchar(getchar());
	}
	return 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

---

END