第十五届蓝桥杯国赛 C/C++ 大学B组

nuo534202

2762人浏览 · 2024-06-03 23:17:07

nuo534202 · 2024-06-03 23:17:07 发布

C++11 编译命令

g++ A.cpp -o A -Wall -lm -std=c++11
./A

A. 合法密码

暴力枚举所长度在 [8, 10] 之间的子串，判断是否合法，但是 pdf 有换行，复制的时候要小心处理一下，答案是 400。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    string s;
    cin >> s;
    int ans = 0;
    for (int len = 8; len <= 16; len++) {
        for (int l = 0; l + len - 1 < s.size(); l++) {
            int r = l + len - 1, tag = 0, flag = 0;
            for (int i = l; i <= r; i++) {
                if (isdigit(s[i])) tag = 1;
                else if (!isalpha(s[i])) flag = 1;
            }
            if (tag && flag) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

B. 选数概率

根据题目条件可以得出 $\frac{b}{a} = \frac{2632}{1540}$ ， $\frac{a}{c} = \frac{2585}{2632}$ ，那么可以得出 $b : a : c = 2632 \times 2585 : 1540 \times 2585 : 2632 \times 1540 = 94 : 55 : 56$ ，最终答案就是 a = 55，b = 94，c = 56。

C 蚂蚁开会

对于每一条线段，枚举所有线段经过的整数点，用 map 记录所有整数点出现过的次数，出现次数大于 1 次的整数点即为线段的交点，所以只需要统计 map 中出现次数大于 1 的整数点的数量即可。

时间复杂度： $O(n(\max(x, y) + \log\max(x,y)))$ 。

#include <bits/stdc++.h>
using namespace std;

int n, ux, uy, vx, vy, g, dx, dy;
map<pair<int, int>, int> mp;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	n = read();
	for (int i = 1; i <= n; i++) {
		ux = read(), uy = read(), vx = read(), vy = read();
		g = __gcd(abs(vx - ux), abs(vy - uy));
		dx = (vx - ux) / g, dy = (vy - uy) / g;
		for (int x = ux, y = uy; ; x += dx, y += dy) {
			mp[{x, y}]++;
			if (x == vx && y == vy) break;
		}
	}
	int ans = 0;
	for (map<pair<int, int>, int>::iterator it = mp.begin(); it != mp.end(); it++)
		ans += (it->second > 1);
	cout << ans << endl;
	return 0;
}

D 立定跳远

这道题是一道很明显的二分答案的题目，首先去二分跳跃长度，再去判断这个长度是不是符合题目的要求。

使用特长跳跃 2L 的长度也就是可以少设一个检查点，所以检查时只需要判断每次最多跳 L 所需要设的检查站的数量 - 1 是否小于等于 m 即可。

时间复杂度： $O(n\log A)$ 。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, m, a[N];

bool check(int mid) {
	int num = 0, maxm = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] - a[i - 1] > mid) {
			num += (a[i] - a[i - 1] - 1) / mid;
		}
	}
	return num - 1 <= m;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int l = 1, r = a[n];
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
    return 0;
}

E 最小字符串

先将所有给定的字母 c 按照字典序进行排序，再将所有字母 c 分别插入到字符串 s 中第一个字典序大于字母 c 的字母前，整体做法类似于归并排序。

时间复杂度： $O(n + m + m\log m)$ 。

#include <bits/stdc++.h>
using namespace std;

int n, m;
string s, c;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m >> s >> c;
	sort(c.begin(), c.end());
	string ans;
	int i = 0, j = 0;
	while (i < n || j < m) {
		if (i >= n) ans += c[j++];
		else if (j >= m) ans += s[i++];
		else if (s[i] <= c[j]) ans += s[i++];
		else ans += c[j++];
	}
	cout << ans << endl;
    return 0;
}

F 数位翻转

我先暴力预处理出来了 a 的一个翻转序列 b，然后用再用 dp（动态规划）来做。可以设表示前 i 个数，已经翻转了 j 个区间，第 i 个数翻转与否的序列和的最大值。初始化为序列 a 的前缀和，状态转移方程为

$f_{i, j, 0} = \max(f_{i - 1, j, 0}, f_{i - 1, j, 1}) + a[i]$
$f_{i, j, 1} = \max(f_{i - 1, j - 1, 0}, f_{i - 1, j - 1, 1}) + b[i]$
特判： $j = 0$ 时， $f_{i, j, 0} = f_{i - 1, j, 0} + a[i]$ ， $f[i][j][1]$ 不存在。

最后结果是。

时间复杂度： $O(n^2 + n\log A)$ ，其中 $n\log A$ 是前面处理 b 数组部分的复杂度。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1005;
int dp[N][N][2], a[N], b[N], n, m;

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		string s;
		int res = a[i];
		while (res) s.push_back((res & 1) + '0'), res >>= 1;
		b[i] = 0;
		for (char c : s) b[i] = b[i] * 2 + c - '0';
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (j) {
				dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i];
				dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]) + b[i];
			} else {
				dp[i][j][0] = dp[i - 1][j][0] + a[i];
				dp[i][j][1] = LLONG_MIN;
			}
		}
	}
	cout << max(dp[n][m][0], dp[n][m][1]) << endl;
	return 0;
}

G 数星星

感觉不是很擅长就没有仔细看

H 套手镯

没有想到应该怎么做，比赛时只想到把圆转换成正方形来做。

I 跳石头

对于每一个位置 $1 \le i \le n$ 维护一个 bitset，记录这个位置开始能到达的所有位置上的 c[i]。每一个位置的 bitset 可以直接或上后面能到达的位置的 bitset，同时第 c[i] 位再或上 1。

时间复杂度： $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;

const int N = 40005;
int n, dp[N], c[N];
bitset<N> bs[N];

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> c[i];
	int ans = 0;
	for (int i = n; i; i--) {
		bs[i][c[i]] = 1;
		if (i * 2 <= n) bs[i] |= bs[i * 2];
		if (i + c[i] <= n) bs[i] |= bs[i + c[i]];
		ans = max(ans, (int)bs[i].count());
	}
	cout << ans << endl;
	return 0;
}

J 最长回文前后缀

先利用双指针找出字符串 s 本身的最长回文前后缀长度，这样之后，问题就变成了删除中间的子串的一段前缀或者后缀使得该子串的回文前后缀长度最长。
利用 KMP 即可解决这个问题，判断前后缀不相交的条件是 $m - i > nxt_i$ 。

时间复杂度： $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;

int n;

int cal(string s, string t) {
	string str = s + " " + t;
	int m = str.size(), oup = 0;
	vector<int> nxt(m, 0);
	for (int i = 1; i < m; i++) {
		int j = nxt[i - 1];
		while (j && str[i] != str[j]) j = nxt[j - 1];
		if (str[i] == str[j]) j++;
		nxt[i] = j;
		if (i > n && m - i > nxt[i]) oup = max(oup, nxt[i]);
	}
	return oup;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	string s, t;
	cin >> s;
	int l = 0, r = s.size() - 1;
	while (l < r && s[l] == s[r]) l++, r--;
	s = t = s.substr(l, r - l + 1);
	n = s.size();
	reverse(t.begin(), t.end());
	cout << l + max(cal(s, t), cal(t, s)) << endl;
	return 0;
}

// avas sava

快读模板

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

如果题目中有的变量需要用 long long 的话，可以直接在宏里面把 int 扩展到 long long，这样比较方便（如下图）。

#include <bits/stdc++.h>
using namespace std;

#define int long long

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

// 代码

signed main() {
    // 代码
    return 0;
}

对拍代码

整个对拍需要以下文件。bf.cpp文件里是暴力代码，std.cpp文件里是用了算法的代码，data.cpp用来生成输入样例，pai.cpp用来比较bf.cpp和stdcpp.out的结果是否相同。

注意：每次更改bf.cpp，std.cpp或data.cpp之后都需要重新编译之后再运行pai.cpp进行对拍。

接下来以输出 a + b 的程序来说明。

bf.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	int a, b, oup = 0;
	cin >> a >> b;
	for (int i = 1; i <= a; i++) oup++;
	for (int i = 1; i <= b; i++) oup++;
	cout << oup;
	return 0;
}

std.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if (a > 0) cout << a << endl;
	cout << a + b << endl;
	return 0;
}

data.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	srand(time(0));
	int a = rand(), b = rand(); // 随机生成两个数字
	cout << a << ' ' << b << endl; // 按照格式输出
	return 0;
}

pai.cpp

可以不用自己创建txt文件，编译运行一次pai.cpp之后会自动生成相应txt文件

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t = 1;
	while (1) {
		printf("test%d: ", t++);
		system("data.exe > in.txt"); // 用 data.exe 生成输入样例，并存入 in.txt 文件中
		system("std.exe < in.txt > stdout.txt");
        // 将 in.txt 文件中的输入样例用来测试 std.cpp 中的代码，并将结果输出到 stdout.txt 文件中
		system("bf.exe < in.txt > bfout.txt");
        // 将 in.txt 文件中的输入样例用来测试 bf.cpp 中的代码，并将结果输出到 bf.out 文件中

        // 比较 stdout.txt 和 bfout.txt 文件是否一样，一样返回 false，不一样返回 true
		if (system("fc stdout.txt bfout.txt")) {
			cout << "WA\n";
			return 0;
		}
		cout << "AC\n";
	}
	cout << "AC\n";
}

下图是pai.cpp运行后的输出结果，会显示WA和输出不一样的地方。