题面：

A - Maliang Learning Painting

签到题问你a + b + c等于多少

C - Liar

n 个人每人有一个数，分别宣称自己的数为 a1, a2, . . . , an。已知所有人的 数的和为 s，求至多有多少人没撒谎。

显然如果$ \sum a_i == s $那么最优的是每个人都说了真话答案是n，如果不相等那就贪心的认为只有一个人说了谎其他人都没说谎，答案是n-1。

G - Multiples of 5

给出一个 11 进制的数，问这个数是否是 5 的倍数。数的长度比较长，以 二元组 (x, y) 的形式逐个给出，表示接下来有 x 个 y 将要拼接到右侧。

每一位拆开来看，对于长度为n的数可以理解为

$\sum a_i*(11)^{i-1} $

因为任意个11相乘模5等于1，即

$ (11)^{n}\%5 = 1 $即

$ (11)^n\equiv 1\ (mod\ 5) $

所以原式可以化为

$ \sum a_i*(11)^{i-1} \%5=\sum a_i\%5 $

所以求和取模即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
	int n;
	cin >> n;
	int tot = 0;
	char c;
	for (int i = 0, cnt; i < n; ++i) {
		cin >> cnt >> c;
		int t = 0;
		if (c == 'A') t = 10;
		else t = c - '0';
		(tot += cnt * t) %= 5;
	}
	if (tot) cout << "No" << endl;
	else cout << "Yes" << endl;
}

K - Magic Tree

2 × n 格子从 (1, 1) 走四连通进行 dfs，每次随机选择一个没走过的格子扩 展。问一共有多少种可能的方案，答案对998244353取模。

方案数是2的n-1次方，找规律猜结论猜出来的。

因为每增加一列，都有两种走法：

1：换行，换行走还不能重复走，所以只能走当前列

2：不换行，因为四联通走法，只能走当前列

所以就是$ 2^{n-1} $。甚至不需要快速幂。

1
2
3
4
5
6
7
8
const int mod = 998244353;

void solve() {
	int n, ans = 1;
	cin >> n;
	for (int i = 1; i < n; ++i) (ans <<= 1) %= mod;
	cout << ans << endl;
}

J - Magic Mahjong

给出初始的 14 张麻将手牌，判断是否达成对应的条件。

模拟题，队友写的。

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
#include<bits/stdc++.h>
#define int long long
#define si(x) (int) x.size()
#define all(x) x.begin(),x.end()
//#define endl '\n'
#define debug cerr<<"******"<<endl;
using namespace std;

const int mod = 998244353;

void solve() {
	map<string, int> mp;
	string s;
	cin >> s;
	int cnt = 0;
	for (int i = 0; i < si(s); i += 2) {
		string t = s.substr(i, 2);
		mp[t]++;
	}
	for (auto [x, y] : mp) cnt += y == 2;
	if (cnt == 7) return cout << "7 Pairs"<<endl,void();
	if (mp["1z"] >= 1 && 
        mp["2z"] >= 1 && 
        mp["3z"] >= 1 && 
        mp["4z"] >= 1 && 
        mp["5z"] >= 1 && 
        mp["6z"] >= 1 && 
        mp["7z"] >= 1 && 
        mp["1s"] >= 1 && 
        mp["9s"] >= 1 && 
        mp["1p"] >= 1 && 
        mp["9p"] >= 1 && 
        mp["1m"] >= 1 && 
        mp["9m"] >= 1) return cout << "Thirteen Orphans"<<endl,void();
	cout << "Otherwise"<<endl;
}

signed main() {
	cin.tie(nullptr), cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;
	int T = 1;
	cin >> T;
	while (T--) solve();
	return 0;
}

H - Convolution

给定一个二维矩阵 I 以及卷积核 K 的大小，其中卷积核中每个元素只能 是 −1 或 0 或 1。矩阵 I 在卷积核的作用下会生成一个新的矩阵 O。 在所有可能的卷积核中，求输出矩阵 O 中的所有元素和的最大值。

打一半去上厕所了然后回来队友就说自己做出来了……题目有点抽象大概意思就是对于一个二维矩阵I对于每个大小为K的子矩阵和K相乘之后最大化结果，K是你自己构造的。

像矩阵这样的题目一般都是对公式进行变形拆分之后进行计算的。

分开考虑贡献，比如原式矩阵是4×4的，卷积核是2×2的。

那么就有左上角的三行三列都是能够和卷积核的第一行第一例这个位置相乘一次，同样的右上角就能够和卷积核的第一行第二列元素相乘一次，考虑如何构造卷积核的元素，那么如果说这个前缀和是负数的，对应的卷积核的位置就应该是-1，相乘能到达正数，反之则是1。所以直接前缀和一遍取绝对值累加就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 例如4*4，2*2的
// 卷积核可以这样相乘
|1 2| 3 4
|5 6| 7 8
3 5 6 7
2 0 1 4
// 也可以这样
1 |2 3| 4
5 |6 7| 8
3 5 6 7
2 0 1 4
// 所以对于左上角的三行三列都有一次乘以卷积核的第一行第一列元素
|1 2 3| 4
|5 6 7| 8
|3 5 6| 7
2 0 1 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
52
53
54
55
56
57
58
59
60
//#pragma GCC optimize(3)
#include <bits/stdc++.h>

#define endl '\n'
#define int long long
#define N 106
#define fi first
#define se second
#define si(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug cerr<<"*******\n";
using namespace std;

typedef pair<int, int> PII;
const long long inf = 1ll << 60;

void solve() {
	int n, m, k, l;
	cin >> n >> m >> k >> l;
	vector<vector<int>> mat(n + 1, vector<int>(m + 1, 0ll));
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			cin >> mat[i][j];
			mat[i][j] += mat[i][j - 1] + mat[i - 1][j] - mat[i - 1][j - 1];
		}
	int ans = 0;

	function<int(int, int, int, int)> sum = [&](int l1, int r1, int l2, int r2)->int{
		return mat[l2][r2] - mat[l1 - 1][r2] - mat[l2][r1 - 1] + mat[l1 - 1][r1 - 1];
	};

//	for(int i = 1;i<=n;++i)
//		for(int j = 1;j<=m;++j)
//			cerr<<mat[i][j]<<" \n"[j == m];
	int sizel = n - k + 1,sizew = m - l + 1;
	
	for (int i = 1; i <= n - sizel + 1; ++i) {
		for (int j = 1; j <= m - sizew + 1; ++j) {
			int L = i, R = j;
			int L1 = L + sizel - 1, R1 = R + sizew - 1;
			ans += llabs(sum(L, R, L1, R1));
		}
	}
	cout << ans << endl;
}

signed main() {
//	freopen("in.txt", "r", stdin);
//	freopen("my.txt", "w", stdout);
	cin.tie(nullptr), cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;
	int T = 1;
//	cin >> T;
	while (T--) solve();
//	cerr<<1e3 * clock() / CLOCKS_PER_SEC<<" ms"<<endl;
//	fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
	return 0;
}

L - Campus

一个 n 个点 m 条边的无向图，每个节点上有 ai 个人。n 个节点中有 k 个节点为出口，每个出口有一个开放时间$ [l_i,r_i] $。求第 1 ∼ T 时刻所有人到 最近的开放出口的路径长度之和。

注意到k很小，所以考虑在k的上面跑暴力单源最短路。

题目给的限制很多，考虑从简单的版本入手，因为k很小，而且有一些情况对于答案影响不是很大，那么就考虑所有出口的开放时间无限。

那么就是建立一个超级源点，将源点连一条无向边到出口，然后跑一遍dij就行。

那么如果有时间限制呢？不难想到对于每一刻时间来说开放的出口是固定的，进而想到可以对[1,t]进行分段，连续的有相同开放出口的时间为同一段。这个最多最多只能达到2k个，对这些都建图跑dij就行。

具体可以用差分数组来实现。

比如有这样的2个出口开放时间是[1,4],[3,5];

那么对时间进行差分，求前缀和得到：

1
2
1 1 2 2 1
1 2 3 4 5

那么就[1,2],[3,4],[5,5]这样分段即可。

然后考虑每一段有多少的出口是开放的，开放的出口连边道源点。

然后每一段都分别跑dij就行。

注意判断无解的情况。

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
143
144
145
#include<bits/stdc++.h>
#define int long long
#define si(x) (int) x.size()
#define all(x) x.begin(),x.end()
#define N 100005
//#define endl '\n'
#define debug cerr<<"******"<<endl;
using namespace std;

const int mod = 998244353;

typedef pair<int, int> PII;

struct SP {
	int n{}, s{}, t{};

	struct Edge {
		int to{};
		int w{};

		Edge(int a, int b) {
			to = a;
			w = b;
		}
	};

	typedef pair<int, int> PII;
	vector<Edge> edge[N];
	int dist[N] {};
	bitset<N> st{};

	void clear() {
		for (auto &i : edge) i.clear();
	}

	int dijkstra() {
		fill(dist + 1, dist + n + 1, 1e9);
		dist[s] = 0;
		priority_queue<PII, vector<PII>, greater<PII>> heap;
		heap.emplace(0, s);
		while (!heap.empty()) {
			auto ver = heap.top().second;
			heap.pop();
			if (st[ver]) continue;
			st[ver] = true;
			for (auto &i : edge[ver]) {
				int j = i.to;
				if (dist[j] >= dist[ver] + i.w) {
					dist[j] = dist[ver] + i.w;
					heap.emplace(dist[j], j);
				}
			}
		}
		return dist[t];
	}
} sp[35];

int diff[N];

void solve() {
	int n, m, k, t;
	cin >> n >> m >> k >> t;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	vector<array<int, 3>> gate(k);
    // gate存出口的信息
	for (int i = 0; i < k; ++i) 
		cin >> gate[i][0] >> gate[i][1] >> gate[i][2];
    // 对出口进行差分，求前缀和
	for (auto [p, l, r] : gate)	diff[l]++,diff[r+1]--;	
	for(int i = 1;i<N;++i) diff[i] += diff[i-1];
    // 双指针求区间
	vector<PII> vis;
	for(int i = 1,j = 1;i<=N;++i){
		if(i == N) vis.push_back({j,i});
		else{
			if(diff[i] == diff[j]) continue;
			vis.push_back({j,i-1});
			j = i;
		}
	}
    // 存边的信息
	vector<array<int,3>> edge(m);
	for (int i = 0; i < m; ++i) 
		cin >> edge[i][0] >> edge[i][1] >> edge[i][2];
	// tot为总共有多少个区间
    int tot = si(vis);
    // 每一个时间区间内的开放的出口是一样的，都是同一张图，
    // 每张图设0号点是超级源点，出口向源点连边。从0开始跑dij，
    // dist[i]表示第i个区间中的超级源点到所有点的距离之和，即所有点到开放的出口的距离之和
	vector<int> dist(tot);
	for (int i = 0; i < tot; ++i) {
		auto [x, y] = vis[i];
        // 一共有n+1个点（这题不写也没事）
		sp[i].n = n+1;
        // 起点是0号源点
		sp[i].s = 0;
        // 终止点（可不写）
		// sp[i].t = n;
		for (auto [p, l, r] : gate) {
            // 如果这个出口在这个区间是开放的那就连一条边到0号源点
			if (l <= x && x <= r) {
				sp[i].edge[p].push_back({0, 0});
				sp[i].edge[0].push_back({p, 0});
			}
		}
        // 连其他的边
		for (auto [u, v, w] : edge) {
			sp[i].edge[u].push_back({v, w});
			sp[i].edge[v].push_back({u, w});
		}
        // 跑dij
		sp[i].dijkstra();
		for(int j = 1;j<=n;++j){
            // 如果有点到不了出口，即0号点到这个点没有最短路，
            // 那么说明这个图没有出口，这个时间段是无解的
			if(sp[i].dist[j] == 1e9){
				dist[i] = -1;
				break;
			}
            // 否则就计算距离
			dist[i] += sp[i].dist[j] * a[j-1];
		}
	}
    // 查询时间输出
	for (int i = 1; i <= t; ++i) 
		for (int j = 0;j<tot;++j){
            // 区间数很少直接跑暴力找这个时间属于哪一段
			if(vis[j].first <= i && i <= vis[j].second){
			 	cout<<dist[j]<<endl;
				break;
			}
		}
}

signed main() {
	cin.tie(nullptr), cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;
	int T = 1;
//	cin >> T;
	while (T--) solve();
	return 0;
}

D - Magic LCM

给你一个长 n 的序列 ，每次可以选择两个位置，把其中一个位置变为 它们的最大公约数，另一个变为最小公倍数，求无限次操作后最大的序列之和。

对于两个数a和b，

将a和b分解质因数：

$ a= P_1^{a_1}P_2^{a_2}…P_k^{a_k},b=P_1^{b_1}P_2^{b_2}…P_k^{b_k} $

他们的gcd和lcm有这样的结论：

$ gcd(a,b)=\prod p_i^{min(a_i,b_i)},lcm[a,b]=\prod p_i^{max(a_i,b_i)} $

首先如果能操作的话那么一定是变换后最优。

假设两个数A和B分解质因数之后是A = a,B = bc。如果能变换则可假设a整除c(即a|c)，a + bc显然是小于c + ba，因为作差后得到c + ba - (a + bc) = (b-1)(a-c)，因为b是质因子显然是大于等于2的，那么作差结果大于0。

其他情况也可以归纳证明。

观察这个变换，其实在变换对应的质因子，所以无论按照什么顺序变换，质因子的个数种类都是不会变的，所以只要变换到不能再变时一定是最优解。

所以只需要对每个数进行质因数分解，独立考虑每个质因子的次幂，将它们排序，只要将$ P_i^{j} $大的和大的合在一起就一定是最优的。

用代码中用了map<int,vector<int>>来存每个质因子的幂，这样写方便修改，49-61行这里如果不进行erase操作就会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
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
//#pragma GCC optimize(3)
#include <bits/stdc++.h>

#define endl '\n'
#define int long long
#define N 1000006
#define fi first
#define se second
#define si(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug cerr<<"*******\n";
using namespace std;

typedef pair<int, int> PII;
const long long inf = 1ll << 60;

const int mod = 998244353;

void solve() {
	int n;
	cin >> n;
//	auto &fac = sieve.fac;
	map<int, vector<int>> m;
	map<int, int> mp;
	for (int i = 0, a; i < n; ++i) {
		cin >> a;
//		分解质因数
		for (int j = 2; j * j <= a; ++j) {
			if (a % j == 0) {
				int res = 1;
				while (a % j == 0) {
					res *= j;
					a /= j;
				}
				m[j].push_back(res);
			}
		}
		if (a != 1) {
			m[a].emplace_back(a);
		}
	}
	int maxn = 0;
//	从小到大排序，这样就能保证大数在后面
	for (auto &[p, v] : m) {
		sort(v.begin(), v.end());
		maxn = max(maxn, si(v));
	}
	int ans = (n - maxn) % mod;
	while (!m.empty()) {
		int res = 1;
		vector<int> del;
		for (auto &[p, v] : m) {
			(res *= v.back()) %= mod;
			v.pop_back();
//			直接去掉对于迭代器来说会出问题
//			if(v.empty()) m.erase(p);
			if (v.empty()) del.push_back(p);
		}
		for (auto x : del) m.erase(x);
		(ans += res) %= mod;
	}
	cout << ans << endl;
}

signed main() {
//	freopen("in.txt", "r", stdin);
//	freopen("my.txt", "w", stdout);
	cin.tie(nullptr), cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;
	int T = 1;
	cin >> T;
	while (T--) solve();
//	cerr<<1e3 * clock() / CLOCKS_PER_SEC<<" ms"<<endl;
//	fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
	return 0;
}

这份代码跑了2s多，瓶颈在于分解质因数，如果想要快些可以先线性筛出1e6范围内的数中每一个数的最小质因子。然后每次就能在大概在ln级别的找齐所有的质因子。

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
//#pragma GCC optimize(3)
#include <bits/stdc++.h>

#define endl '\n'
#define int long long
#define N 1000006
#define fi first
#define se second
#define si(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug cerr<<"*******\n";
using namespace std;

typedef pair<int, int> PII;
const long long inf = 1ll << 60;

const int mod = 998244353;

struct EulerSieve {
	bitset < N + 5 > isprime;
	vector<int> prime;
	vector<int> fac;
	void Euler() {
		fac.assign(N + 1, 0);
		for (int i = 2; i <= N; i++) {
			if (!isprime[i]) prime.push_back(i), fac[i] = i;
			for (int j = 0; j < (int)prime.size() && i * prime[j] <= N; ++j) {
				isprime[i * prime[j]] = true;
				fac[i * prime[j]] = prime[j];
				if (i % prime[j] == 0) break;
			}
		}
	}
} sieve;

void solve() {
	int n;
	cin >> n;
	auto &fac = sieve.fac;
	map<int, vector<int>> m;
	for (int i = 0, a; i < n; ++i) {
		cin >> a;
//		ln级别的分解质因数
		while (fac[a]) {
			int res = 1, p = fac[a];
			while (a % p == 0) {
				res *= p;
				a /= p;
			}
			m[p].emplace_back(res);
		}
	}
	int maxn = 0;
//	从小到大排序，这样就能保证大数在后面
	for (auto &[p, v] : m) {
		sort(v.begin(), v.end());
		maxn = max(maxn, si(v));
	}
	int ans = (n - maxn) % mod;
	while (!m.empty()) {
		int res = 1;
		vector<int> del;
		for (auto &[p, v] : m) {
			(res *= v.back()) %= mod;
			v.pop_back();
//			直接去掉对于迭代器来说会出问题
//			if(v.empty()) m.erase(p);
			if (v.empty()) del.push_back(p);
		}
		for (auto x : del) m.erase(x);
		(ans += res) %= mod;
	}
	cout << ans << endl;
}

signed main() {
//	freopen("in.txt", "r", stdin);
//	freopen("my.txt", "w", stdout);
	cin.tie(nullptr), cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;
	int T = 1;
//	先筛出每一个数的最小质因子
	sieve.Euler();
	cin >> T;
	while (T--) solve();
//	cerr<<1e3 * clock() / CLOCKS_PER_SEC<<" ms"<<endl;
//	fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
	return 0;
}