C++java算法
2023 第十四届蓝桥杯国赛 C/C++ 大学 B 组真题及题解
2023 年第十四届蓝桥杯大赛软件赛国赛 C/C++ 大学 B 组的真题及题解，涵盖子 2023、双子数、班级活动、合并数列、数三角、删边问题、AB 路线、抓娃娃等八个题目。内容包含 C++ 与 Java 两种语言的代码实现，涉及动态规划、筛法、贪心、前缀和、几何优化、Tarjan 算法、BFS 及差分等核心算法知识点。文章对关键解题思路进行了说明，并修正了部分代码细节，旨在帮助参赛者理解算法逻辑与实现技巧。
2023 年第十四届蓝桥杯大赛软件赛国赛 C/C++ 大学 B 组的真题及题解，涵盖子 2023、双子数、班级活动、合并数列、数三角、删边问题、AB 路线、抓娃娃等八个题目。内容包含 C++ 与 Java 两种语言的代码实现，涉及动态规划、筛法、贪心、前缀和、几何优化、Tarjan 算法、BFS 及差分等核心算法知识点。文章对关键解题思路进行了说明，并修正了部分代码细节，旨在帮助参赛者理解算法逻辑与实现技巧。
问题描述
小蓝在黑板上连续写下从 1 到 2023 之间所有的整数，得到了一个数字序列：S=12345678910111213...20222023。小蓝想知道 S 中有多少种子序列恰好等于 2023？
以下是 3 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：
1[2]3456789[0]111[2]1[3]14151617181920212223... 1[2]3456789[0]111[2]13141516171819202122[3]... 1[2]3456789[0]111213141516171819[2]021222[3]...
注意以下是不满足条件的子序列，虽然包含了 2、0、2、3 四个数字，但是顺序不对：
1[2]345678910111[2]131415161718192[0]21222[3]...
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数。
本题解法属于状态推导，通过遍历字符串统计目标子序列出现的次数。
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<unsigned long long> dp(4, 0);
string str = "";
for(int i = 1; i <= 2023; ++i) str += to_string(i);
// 动态规划过程
for(char c : str){
if(c == '2'){
dp[0]++;
dp[2] += dp[1];
}
if(c == '0') dp[1] += dp[0];
if(c == '3') dp[3] += dp[2];
}
cout << dp[3] << endl;
return 0;
}
public class DpProblem {
public static void main(String[] args) {
long[] dp = new long[4];
StringBuilder str = new StringBuilder();
for (int i = 1; i <= 2023; i++) {
str.append(i);
}
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '2') {
dp[0]++;
dp[2] += dp[1];
}
if (c == '0') {
dp[1] += dp[0];
}
if (c == '3') {
dp[3] += dp[2];
}
}
System.out.println(dp[3]);
}
}
问题描述
若一个正整数 x 可以被表示为 p^2 * q^2，其中 p、q 为质数且 p≠q，则 x 是一个双子数。请计算区间 [2333, 23333333333333] 内有多少个双子数？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数。
// 注意数据类型使用 unsigned long long 防止溢出 // int->1e9, long long->1e18, unsigned long long 范围更大
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
const int N = 1e7 + 10;
vector<bool> vec(N, true);
vector<ll> res;
void sieve(){
vec[0] = vec[1] = false;
for(int i = 2; i < vec.size(); ++i){
if(vec[i]) res.push_back((ll)i);
for(ll num : res){
if(num * i > vec.size()) break;
vec[i * num] = false;
if(i % num == 0) break;
}
}
}
int main(){
sieve();
ll num = 0;
for(ll i = 0; i < res.size(); i++){
unsigned long long pp = res[i] * res[i];
if(pp * pp > 23333333333333) break;
(ll j = i + ; j < res.(); j++){
ll qq = res[j] * res[j];
(pp * qq > ) ;
(pp * qq < ) ;
num++;
}
}
cout << num << endl;
;
}
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class PrimeNumberCombination {
static final int N = 10000010;
static boolean[] isPrime = new boolean[N];
static List<Integer> primes = new ArrayList<>();
public static void sieve() {
for (int i = 0; i < N; i++) isPrime[i] = true;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i < N; i++) {
if (isPrime[i]) primes.add(i);
for (int prime : primes) {
if (prime * i >= N) break;
isPrime[prime * i] = false;
if (i % prime == 0) break;
}
}
}
public static void main(String[] args) {
sieve();
BigInteger.valueOf();
BigInteger.valueOf();
;
( ; i < primes.size(); i++) {
BigInteger.valueOf(primes.get(i)).pow();
(pp.pow().compareTo(limit1) > ) ;
( i + ; j < primes.size(); j++) {
BigInteger.valueOf(primes.get(j)).pow();
pp.multiply(qq);
(product.compareTo(limit1) > ) ;
(product.compareTo(limit2) < ) ;
num++;
}
}
System.out.println(num);
}
}
问题描述
班上一共有 n 名 (n 为偶数) 同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 n 以内的正整数作为 id。老师希望通过更改若干名同学的 id 使得对于任意一名同学 i，有且仅有另一名同学 j 的 id 与其相同。请问老师最少需要更改多少名同学的 id？
输入格式
第一行为一个正整数 n。 第二行为 n 个由空格隔开的整数 a1,a2,...,an。
输出格式
输出共 1 行，一个整数。
// 思路：统计每个 ID 出现的次数 // 如果某个 ID 出现次数大于 2，超出部分需要修改 // 如果某个 ID 出现次数为 1，需要配对
#include <iostream>
const int N = 1e5 + 5;
using namespace std;
int arr[N];
int main() {
int n;
cin >> n;
for(int i = 0; i < n; ++i){
int num;
cin >> num;
arr[num]++;
}
int num1 = 0, num2 = 0;
for(int i : arr){
if(i > 2) num1 += i - 2;
else if(i == 1) num2++;
}
int sum = 0;
if(num1 > num2){
sum = num1;
} else {
sum = num2 + (num1 - num2) / 2;
}
cout << sum << endl;
return 0;
}
import java.util.Scanner;
public class StudentIdAdjustment {
static final int N = 100005;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = new int[N];
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
int num = scanner.nextInt();
arr[num]++;
}
int num1 = 0, num2 = 0;
for (int i : arr) {
if (i > 2) num1 += i - 2;
else if (i == 1) num2++;
}
int sum = 0;
if (num1 > num2) {
sum = num1;
} else {
sum = num2 + (num1 - num2) / ;
}
System.out.println(sum);
scanner.close();
}
}
问题描述
小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将他们列为两个数组 {a1,a2,...,an} 和 {b1,b2,...,bm}。两个数组的和相同。 定义一次合并操作可以将某数组内相邻的两个数合并为一个新数，新数的值是原来两个数的和。小明想通过若干次合并操作将两个数组变成一模一样。请计算至少需要多少次合并操作可以完成小明的目标。
输入格式
第一行为两个正整数 n, m。 第二行为 n 个由空格隔开的整数。 第三行为 m 个由空格隔开的整数。
// 思路：双指针与前缀和结合 // 从头开始计算前缀和，如果相同时，代表俩数列第 i 位已经相同，更新起始位置
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n, 0);
vector<int> b(m, 0);
for(int i = 0; i < n; ++i) cin >> a[i];
for(int i = 0; i < m; ++i) cin >> b[i];
long long sum_a = 0, sum_b = 0;
int cnt_a = 0, cnt_b = 0;
int cnt_sum = 0;
while(true){
if(sum_a == sum_b){
if(cnt_a < n) sum_a += a[cnt_a++];
if(cnt_b < m) sum_b += b[cnt_b++];
} else if(sum_a < sum_b){
sum_a += a[cnt_a++];
cnt_sum++;
} else if(sum_b < sum_a){
sum_b += b[cnt_b++];
cnt_sum++;
}
if(cnt_a == n && cnt_b == m) break;
}
cout << cnt_sum;
return 0;
}
import java.util.Scanner;
public class MergeArrays {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] a = new int[n];
int[] b = new int[m];
for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
for (int i = 0; i < m; i++) b[i] = scanner.nextInt();
long sum_a = 0, sum_b = 0;
int cnt_a = 0, cnt_b = 0;
int cnt_sum = 0;
while (true) {
if (sum_a == sum_b) {
if (cnt_a < n) sum_a += a[cnt_a++];
(cnt_b < m) sum_b += b[cnt_b++];
} (sum_a < sum_b) {
sum_a += a[cnt_a++];
cnt_sum++;
} {
sum_b += b[cnt_b++];
cnt_sum++;
}
(cnt_a == n && cnt_b == m) ;
}
System.out.println(cnt_sum);
scanner.close();
}
}
问题描述
小明在二维坐标系中放置了 n 个点，他想在其中选出一个包含三个点的子集，这三个点能组成三角形。然而这样的方案太多了，他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形？
输入格式
第一行为一个正整数 n。 后面 n 行，每行两个整数 xi, yi 表示第 i 个点的坐标。
// 优化思路：根据半径求解，叉乘判是否三点在一条直线 // 预处理分组，避免 O(n^3) 暴力
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
#define ll long long
const ll N = 2e3 + 5;
struct point{ int x; int y; }p[N];
ll get_radius(int i, int j){
return (ll)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (ll)(p[i].y - p[j].y) * (p[i].y - p[j].y);
}
bool is_parallel(int i, int j, int k){
ll v = (ll)(p[j].x - p[i].x) * (p[k].y - p[i].y) - (ll)(p[j].y - p[i].y) * (p[k].x - p[i].x);
if(v == 0) return true;
else return false;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
vector<unordered_map<ll, vector<int>>> vec(n);
for(int i = 0; i < n; ++i){
unordered_map<ll, vector<int>> m;
( j = ; j < n; ++j){
(i == j) ;
ll len = (i, j);
m[len].(j);
}
vec[i] = m;
}
sum = ;
( i = ; i < n; ++i){
m = vec[i];
( it = m.(); it != m.(); ++it){
vector<> p_m = it->second;
(p_m.() <= ) ;
( j = ; j < p_m.(); ++j){
( k = j + ; k < p_m.(); ++k){
((i, p_m[j], p_m[k])) ;
sum++;
}
}
}
}
cout << sum << endl;
;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] x = new int[n];
int[] y = new int[n];
HashMap<String, Integer> s = new HashMap<>();
for(int i = 0; i < n; i++){
x[i] = sc.nextInt();
y[i] = sc.nextInt();
String t = x[i] + " " + y[i];
s.put(t, s.getOrDefault(t, 0) + 1);
}
long res = 0;
for(int i = 0; i < n; i++){
HashMap<Long, List<Integer>> map = new HashMap<>();
for(int j = 0; j < n; j++){
if(i == j) ;
()Math.pow(x[i] - x[j], ) + ()Math.pow(y[i] - y[j], );
List<Integer> list = map.getOrDefault(d, <>());
list.add(j);
map.put(d, list);
}
( b : map.keySet()){
List<Integer> list = map.get(b);
res += ()list.size() * (list.size() - ) / ;
;
( j : list){
* x[i] - x[j], y3 = * y[i] - y[j];
(s.containsKey(x3 + + y3)){
c += s.get(x3 + + y3);
}
}
res -= c / ;
}
}
System.out.println(res);
}
}
问题描述
给定一个包含 N 个结点 M 条边的无向图 G，结点编号 1...N。其中每个结点都有一个点权 Wi。 你可以从 M 条边中任选恰好一条边删除，如果剩下的图恰好包含 2 个连通分量，就称这是一种合法的删除方案。 对于一种合法的删除方案，我们假设 2 个连通分量包含的点的权值之和分别为 X 和 Y，请你找出一种使得 X 与 Y 的差值最小的方案。输出 X 与 Y 的差值。
// 本题为 tarjan 算法的变种，涉及割边问题 // 使用 dfn 和 low 数组判断割边
#include <iostream>
#include <cmath>
#include <vector>
#define ll long long
using namespace std;
const ll N = 1e6 + 5;
const ll maxn = 0x3f3f3f3f3f3f3f3f;
ll n, m, sum_value = 0, cnt = 0, ans = maxn;
vector<ll> dfn(N, 0), low(N, 0);
vector<int> vec[N];
vector<ll> value(N, 0);
void tarjan(int u, int fa){
dfn[u] = low[u] = ++cnt;
for(int v : vec[u]){
if(dfn[v] == 0){
tarjan(v, u);
low[u] = min(low[v], low[u]);
if(dfn[u] < low[v]) ans = min(ans, abs(sum_value - 2 * value[v]));
value[u] += value[v];
} else if(v != fa){
low[u] = min(low[u], low[v]);
}
}
}
int main(){
cin >> n >> m;
( i = ; i <= n; ++i) cin >> value[i], sum_value += value[i];
( i = ; i < m; ++i){
r1, r2;
cin >> r1 >> r2;
vec[r1].(r2);
vec[r2].(r1);
}
(, );
(value[] != sum_value) cout << (sum_value - * value[]) << endl;
(ans != maxn) cout << ans << endl;
cout << << endl;
;
}
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static final long N = (long) (1e6 + 5);
static final long maxn = 0x3f3f3f3f3f3f3f3fL;
static long n, m, sum_value = 0, cnt = 0, ans = maxn;
static List<Long> dfn = new ArrayList<>();
static List<Long> low = new ArrayList<>();
static List<List<Integer>> vec = new ArrayList<>();
static List<Long> value = new ArrayList<>();
static void tarjan(int u, int fa) {
dfn.set(u, ++cnt);
low.set(u, cnt);
for (int v : vec.get(u)) {
if (dfn.get(v) == 0) {
tarjan(v, u);
low.set(u, Math.min(low.get(u), low.get(v)));
if (dfn.get(u) < low.get(v)) {
ans = Math.min(ans, Math.abs(sum_value - 2 * value.get(v)));
}
value.set(u, value.get(u) + value.get(v));
} (v != fa) {
low.set(u, Math.min(low.get(u), low.get(v)));
}
}
}
{
(System.in);
n = scanner.nextLong();
m = scanner.nextLong();
( ; i <= n; i++) {
dfn.add(); low.add(); value.add(); vec.add( <>());
}
( ; i <= n; i++) {
value.set(i, scanner.nextLong());
sum_value += value.get(i);
}
( ; i < m; i++) {
scanner.nextInt();
scanner.nextInt();
vec.get(r1).add(r2);
vec.get(r2).add(r1);
}
tarjan(, );
(value.get() != sum_value) {
System.out.println(Math.abs(sum_value - * value.get()));
} (ans != maxn) {
System.out.println(ans);
} {
System.out.println(-);
}
}
}
问题描述
小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上，第 i 条线段的左端点在 li，右端点在 ri。小明用 m 个区间去框这些线段，第 i 个区间的范围是 [Li, Ri]。如果一个线段有至少一半的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段？
// 审题：最短路径，BFS 解决图的最短路径问题 // 引入记忆化搜索，used[i][j][k] 标记状态
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e3 + 5;
const int step = 1e1 + 5;
struct node{ int x; int y; int step; };
int n, m, k;
queue<node> q;
bool used[N][N][step];
int res[N][N][step];
char grid[N][N];
int xf[] = {1, -1, 0, 0};
int yf[] = {0, 0, 1, -1};
int BFS(){
q.push({0, 0, 0});
while(!q.empty()){
node u = q.front();
q.pop();
if(u.x == n - 1 && u.y == m - 1) return res[u.x][u.y][u.step];
for(int i = 0; i < 4; ++i){
int X = u.x + xf[i], Y = u.y + yf[i], st = u.step + 1;
(X < || X >= n || Y < || Y >= m) ;
(st < k && grid[X][Y] != grid[u.x][u.y]) ;
(st == k && grid[X][Y] == grid[u.x][u.y]) ;
st = st % k;
(used[X][Y][st]) ;
used[X][Y][st] = ;
res[X][Y][st] = res[u.x][u.y][u.step] + ;
q.({X, Y, st});
}
}
;
}
{
cin >> n >> m >> k;
string str;
( i = ; i < n; ++i){
cin >> str;
( j = ; j < m; ++j) grid[i][j] = str[j];
}
cout << ();
;
}
import java.util.*;
public class Main {
static long INF = (long) 1e18;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
sc.nextLine();
char[][] mg = new char[n][m];
for (int i = 0; i < n; i++) {
mg[i] = sc.nextLine().toCharArray();
}
LinkedList<Pair> qu = new LinkedList<>();
qu.add(new Pair(0, 0, 1));
int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
boolean[][][] visited = new [n][m][ * k];
( ; !qu.isEmpty(); step++) {
qu.size();
( ; i < num; i++) {
qu.pollFirst();
pair.x, py = pair.y, pf = pair.flag;
(visited[px][py][pf]) ;
visited[px][py][pf] = ;
(pair.x == n - && pair.y == m - ) {
System.out.print(step);
;
}
( ; j < ; j++) {
px + d[j][];
py + d[j][];
(pf + ) % ( * k);
(x >= && x < n && y >= && y < m) {
(visited[x][y][f]) ;
(pf < k && mg[x][y] == || pf >= k && mg[x][y] == ) {
qu.addLast( (x, y, f));
}
}
}
}
}
System.out.print(-);
}
}
{
x, y, flag;
{
.x = x; .y = y; .flag = flag;
}
}
问题描述
小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上，第 i 条线段的左端点在 li，右端点在 ri。小明用 m 个区间去框这些线段，第 i 个区间的范围是 [Li, Ri]。如果一个线段有至少一半的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段？
// 思路：差分 + 前缀和 // 注意处理边界条件
#include <iostream>
#include <vector>
const int N = 2e6 + 5;
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> res(N, 0);
for(int i = 0, r, l; i < n; ++i) cin >> l >> r, res[r + l]++;
for(int i = 1; i < N; ++i) res[i] += res[i - 1];
for(int i = 1, L, R; i <= m; ++i){
cin >> L >> R;
L *= 2; R *= 2;
if(L == 0) cout << res[R] << endl;
else cout << res[R] - res[L - 1] << endl;
}
return 0;
}
import java.util.Scanner;
public class SegmentQuery {
public static void main(String[] args) {
final int N = 2000005;
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] res = new int[N];
for (int i = 0; i < n; i++) {
int l = scanner.nextInt();
int r = scanner.nextInt();
res[l + r]++;
}
for (int i = 1; i < N; i++) {
res[i] += res[i - 1];
}
for (int i = 1; i <= m; i++) {
int L = scanner.nextInt();
int scanner.nextInt();
L *= ; R *= ;
result;
(L == ) {
result = res[R];
} {
result = res[R] - res[L - ];
}
System.out.println(result);
}
scanner.close();
}
}
abs(a-b)<1e-6。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online