A题 抓钱

截屏2024-03-13 21.47.06

这道题很简单，就是贪心，从最大的钱开始拿。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;

int n, money[6] = {1, 5, 10, 20, 50, 100}, a[6];
long long ans;

int main() {
	for (int i = 0; i < 6; ++i) cin >> a[i];
	cin >> n;
	for (int i = 5; n > 0 && i >= 0; --i) {
		if (n >= a[i]) ans += a[i] * money[i];
		else ans += n * money[i];
		n -= a[i];
	}
	cout << ans << endl;

	return 0;
}

B题 格点问题—不同的直线数目

截屏2024-03-13 21.47.31

这道题其实就从原点出发的斜率有多少种。从原点出发的斜率其实就是求 $\dfrac{y}{x}$ 的最简分式的个数。

然后x轴和y轴上分别只有一个，特判一下即可。

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
#include <iostream>
#include <set>

using namespace std;

set<pair<int, int> > st;
long long ans;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
	int n, m;
	cin >> n >> m;
	if (n > 0) ans ++;
	if (m > 0) ans ++;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			int d = gcd(i, j);
			if (!st.count({i/d, j/d})) ans ++;
			st.insert({i/d, j/d});
		}
	cout << ans << endl;

	return 0;
}

C题 贪吃蛇

截屏2024-03-13 21.48.00

这道题可以发现，没有空白陆地，也就是贪吃蛇每走一步一定会变长，所以可以将贪吃蛇走过的地方标记一下，不能再走即可。

这里要求最大的长度，就要用dfs遍历，注意点就是回溯。

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 <iostream>

using namespace std;


const int N = 22;

int n, m, sx, sy;
char g[N][N];
bool st[N][N];
long long ans = -1;
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool check(int x, int y) {
	// 越界
	if (x < 0 || x >= n || y < 0 || y >= m) return false;
	if (g[x][y] == '#' || st[x][y]) return false;
	return true;
}

void dfs(int x, int y, int len) {
	bool flag = false;
	for (int i = 0; i < 4; ++i) {
		int nx = x + d[i][0], ny = y + d[i][1];
		if (check(nx, ny)) {
			flag = true;
			st[nx][ny] = true;
			dfs(nx, ny, len+1);
			st[nx][ny] = false;
		}
	}
	if (!flag && len > ans) ans = len;
}

int main () {
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m ; ++j) {
			cin >> g[i][j];
			if (g[i][j] == 'S') sx = i, sy = j;
		}
	st[sx][sy] = true;
	dfs(sx, sy, 1);
	cout << ans << endl;

	return 0;
}

D题 矩阵变幻

截屏2024-03-13 21.49.31

注意：样例输出有问题，正确的看题目中的矩阵

这道题看着这个数据范围就知道一定是递归。

然后分析这个问题，也是子问题的形式。

我们可以分析到假设n，最终的结果一定是$2^n 2^n$的矩阵，那么它的左上角矩阵大小就是$2^n/2 \; 2^n/2 $。

于是可以设计一个dfs函数：dfs(x, y, n, y, k),其中x，y表示子矩阵的左上角坐标，n表示现在要求的变换次数，t为当前该位的数，k为子矩阵的阶数。

终止条件当然是n == 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
#include <iostream>

using namespace std;
 
const int N = 1 << 10;

int n, res[N][N];
 
void dfs(int x, int y, int n, int t, int k){
	if(n == 0) {
		res[x][y]= t;
		return;
	}
	dfs(x, y, n-1, t, k/2); // 求左上角
	dfs(x, y+k, n-1, t, k/2); // 求右上角
	dfs(x+k, y, n-1, t, k/2); // 求左下角
	dfs(x+k, y+k, n-1, !t, k/2); // 求右下角
}
 
int main(){
	cin >> n;

	int len = 1 << n; // 2的n次方
	dfs(0, 0, n, 0, len/2);
	for(int i = 0; i < len; ++i){
		for(int j = 0; j < len; ++j)
			cout << res[i][j] << " ";
		puts(" ");
	}

	return 0;
}

E题 二叉树的恢复

截屏2024-03-13 21.50.20

这道题可以看我的另一篇文章：二叉树的恢复（上次的校赛题目，几乎一样）

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 <iostream>
#include <cstring>
#include <map>

using namespace std;

int n, m, ans; // n为树的节点个数，m为样例数量，ans判断有无结果
string pre, in, post, res; // 前序遍历字符串，中序遍历字符串，后序遍历字符串
map<char, pair<char, char> > g;	// 存重构后的二叉树，第一个char为当前节点值
								//pair<char, char>为其{left, right}

void init() {
	g.clear(); // 把重构二叉树置为空
	res = ""; // 重构二叉树的后序遍历结果置为空
}

// 重构二叉树
char find_root (int pr, int il, int ir) {
	if (il > ir) return '0'; // 避免评判数据中根本不可能构成树的情况
    char root = pre[pr]; // 当前子树的根
    if (il == ir) { // 刚好一个节点，为叶子节点，其左右节点均为空
    	g[root] = {'0', '0'};
    	return root;
    }
    int pos = in.find(root);
    if (pos < il) return '0'; // 避免评判中根本不可能构成树的情况
    
	char left = find_root(pr+1, il, pos-1); // 继续遍历左子树
	char right = find_root(pr+pos-il+1, pos+1, ir); // 继续遍历右子树
	g[root] = {left, right};
	
	return root;
}

// 后序遍历二叉树
void dfs(char u) { // 当前节点
    if (u == '0') return; // 为空不遍历
	if (g[u].first != '0') // 左节点不为空，则遍历左节点
		dfs(g[u].first); // 左节点
	if (g[u].second != '0') // 右节点不为空，则遍历右节点
		dfs(g[u].second); // 右节点
	
	res = res + u;
}

int main() {
	cin >> pre >> in;
	n = pre.size();
	char root = find_root(0, 0, n-1); // 重构二叉树
	dfs(root); // 后序遍历二叉树
	cout << res << endl;

	return 0;
}

F题 循环位移运算

截屏2024-03-13 21.50.48

我先用了一个笨办法，先把整数转为二进制存到数组中，然后再逻辑位移计算整数。（但是这种情况WA了，正解看本题最后一个代码）

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
#include <iostream>

using namespace std;

const int N = 60;
int m, a[N];
unsigned int n, ansleft, ansright, temp;

int main() {
	int idx = 0;
	cin >> n >> m;

	// 转换为二进制
	while (n) {
		a[idx] = n&1;
		n /= 2;
		idx++;
	}

	temp = 1;
	// 左移
	for (int i = 32-m; i < 32; ++i) {
		if (a[i] & 1) ansleft += temp;
		temp *= 2;
	}
	for (int i = 0; i < 32-m; ++i) {
		if (a[i] & 1) ansleft += temp;
		temp *= 2;
	}
	cout << ansleft << " ";

	// 右移
	temp = 1;
	for (int i = m; i < 32; ++i) {
		if (a[i] & 1) ansright += temp;
		temp *= 2;
	}
	for (int i = 0; i < m; ++i) {
		if (a[i] & 1) ansright += temp;
		temp *= 2;
	}
	cout << ansright << endl;
}

之后我就开始考虑用真正的位运算来操作：

为了方便表示，这里将二进制串表示成123456。

123456 左移两位结果为 345612。其实可以看成两部分，12和3456。

12到对应位置就是右移（6-4）位（6是整个串的长度），这样就变为000012了。

3456到对应位置就是左移 2 位，变成345600。

此时000012 ｜ 345600 = 345612了。

右移类似。

注意：使用位运算就不要用 + - * / % 这些运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

const int N = 60;
int m, a[N];
unsigned int n;

int main() {
	int idx = 0;
	cin >> n >> m;

	unsigned int a = (n >> (32-m)) | (n << m);
    unsigned int b = (n << (32-m)) | (n >> m);
	cout << a << " " << b << endl;

	return 0;
}

G题 根据点阵输出字符串

截屏2024-03-13 21.51.34

注意：这里截图输入不完整

这道题我有点取巧了，我先用如下代码得到了map映射：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cstring>

using namespace std;

string str;

int main() {
	for (int i = 0; i < 26; ++i) {
		getline(cin, str, '\n');
        str = "\"" + str + "\"";
		cout << "mp[" << str << "] = '" << char('A' + i) << "';" << endl;
	}

	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
mp["255 231 231 219 129 189 126 255"] = 'A';
mp["255 193 189 193 189 125 129 255"] = 'B';
mp["255 195 189 253 253 121 131 255"] = 'C';
mp["255 193 157 189 189 157 193 255"] = 'D';
mp["255 129 253 129 253 253 129 255"] = 'E';
mp["255 129 253 129 253 253 253 255"] = 'F';
mp["255 195 185 253 141 185 131 255"] = 'G';
mp["255 189 189 129 189 189 189 255"] = 'H';
mp["255 247 247 247 247 247 247 255"] = 'I';
mp["255 191 191 191 191 189 195 255"] = 'J';
mp["255 157 237 245 233 221 189 255"] = 'K';
mp["255 253 253 253 253 253 129 255"] = 'L';
mp["255 153 153 153 165 165 165 255"] = 'M';
mp["255 185 185 181 173 157 157 255"] = 'N';
mp["255 195 153 189 189 153 195 255"] = 'O';
mp["255 193 189 189 193 253 253 255"] = 'P';
mp["255 195 153 189 189 169 195 191"] = 'Q';
mp["255 193 189 129 189 189 189 255"] = 'R';
mp["255 195 189 195 63 125 131 255"] = 'S';
mp["255 128 247 247 247 247 247 255"] = 'T';
mp["255 189 189 189 189 189 195 255"] = 'U';
mp["255 126 189 221 219 227 247 255"] = 'V';
mp["255 255 255 102 166 153 153 255"] = 'W';
mp["255 221 235 247 227 217 188 255"] = 'X';
mp["255 188 217 227 247 247 247 255"] = 'Y';
mp["255 128 223 231 251 253 128 255"] = 'Z';

然后写答案：

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 <iostream>
#include <cstring>
#include <map>

using namespace std;

int n;
string str;
map<string, char> mp;

int main() {
	mp["255 231 231 219 129 189 126 255"] = 'A';
	mp["255 193 189 193 189 125 129 255"] = 'B';
	mp["255 195 189 253 253 121 131 255"] = 'C';
	mp["255 193 157 189 189 157 193 255"] = 'D';
	mp["255 129 253 129 253 253 129 255"] = 'E';
	mp["255 129 253 129 253 253 253 255"] = 'F';
	mp["255 195 185 253 141 185 131 255"] = 'G';
	mp["255 189 189 129 189 189 189 255"] = 'H';
	mp["255 247 247 247 247 247 247 255"] = 'I';
	mp["255 191 191 191 191 189 195 255"] = 'J';
	mp["255 157 237 245 233 221 189 255"] = 'K';
	mp["255 253 253 253 253 253 129 255"] = 'L';
	mp["255 153 153 153 165 165 165 255"] = 'M';
	mp["255 185 185 181 173 157 157 255"] = 'N';
	mp["255 195 153 189 189 153 195 255"] = 'O';
	mp["255 193 189 189 193 253 253 255"] = 'P';
	mp["255 195 153 189 189 169 195 191"] = 'Q';
	mp["255 193 189 129 189 189 189 255"] = 'R';
	mp["255 195 189 195 63 125 131 255"] = 'S';
	mp["255 128 247 247 247 247 247 255"] = 'T';
	mp["255 189 189 189 189 189 195 255"] = 'U';
	mp["255 126 189 221 219 227 247 255"] = 'V';
	mp["255 255 255 102 166 153 153 255"] = 'W';
	mp["255 221 235 247 227 217 188 255"] = 'X';
	mp["255 188 217 227 247 247 247 255"] = 'Y';
	mp["255 128 223 231 251 253 128 255"] = 'Z';

	cin >> n;
	getline(cin, str, '\n');
	for (int i = 0; i < n; ++i) {
		getline(cin, str, '\n');
		cout << mp[str];
	}

	return 0;
}

H题 翻转数

截屏2024-03-13 21.52.47

这道题就是经典的动态规划问题：

我们可以定义对于一对数，只操作后一个数，操作之后这一对数都取反。

定义状态：

dp[i][0]表示累加到第i个数，并且不翻转第i位和第i-1位

dp[i][1]表示累加到第i个数，并且翻转第i位和第i-1位

动态转移方程：

  • dp[i][0]

    如果上一步没翻转：dp[i-1][0] + a[i]

    如果上一步翻转了：dp[i-1][1] + a[i]

    然后取最大值

  • dp[i][1]

    如果上一步没翻转：dp[i-1][0] - a[i] - 2*a[i-1]

    如果上一步翻转了：dp[i-1][1] - a[i] + 2*a[i-1]

    然后取最大值

最终结果为dp[n-1][0]和dp[n-1][1]中的最大值

初始条件：dp[1][0] = a[0] + a[1], dp[1][1] = -a[0]-a[1];（i=0时不用管）

注意数据范围很大，有可能会爆int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

using namespace std;

const int N = 2e5+5;
int n, a[N];
long long dp[N][2];

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i];
	dp[1][0] = a[0] + a[1], dp[1][1] = -a[0]-a[1];
	for (int i = 2; i < n; ++i) {
		dp[i][0] = max(dp[i-1][0] + a[i], dp[i-1][1] + a[i]);
		dp[i][1] = max(dp[i-1][0] - a[i] - 2*a[i-1], dp[i-1][1] - a[i] + 2*a[i-1]);
	}

	cout << max(dp[n-1][0], dp[n-1][1]) << endl;

	return 0;
}

I题 吃坚果

截屏2024-03-13 21.53.26

这道题一开始读错意思了，以为要用大根堆来维护最大值，结果发现不用。如果一个罐子不能取了就直接无视该罐子（不管它的坚果数是否是最大），那就直接加就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

using namespace std;

int n, b, a;
long long ans = 0;

int main() {
	cin >> n >> b;
	for (int i = 0; i < n; ++i) {
		cin >> a;
		if (a / b >= 3) ans += a - 3*b;
		else if (a/b == 2) ans += a - 2*b;
		else if (a/b == 1) ans += a - b;
		else ans += a;
	}

	cout << ans << endl;

	return 0;
}

J题 数压岁钱

截屏2024-03-13 21.53.49

这其实就是一道简单的思维题，求位数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

long long n;

int main() {
	cin >> n;
	n /= 100;
	int k = 0, a;
	int nn = n; 
	while (nn) {
		if (nn != 0) a = nn;
		nn /= 10;
		k++;
	}
	k--;
	long long ans = (k*10 - k + a) * 100;
	cout << ans << endl;

	return 0;
}