2023第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 B 组(真题题解)（C++/Java题解）

#include <iostream>
#include <vector>
using namespace std;
// 是个简单的动态规划就算了
// 怎么又是一道越界题目
// 以后统一不用long long改用 unsigned long long。更大。
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) {// 创建一个长度为 4 的 long 类型数组 dp 并初始化为 0long[] 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]);}
}    

#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 ll pp = res[i]*res[i];if(pp * pp >23333333333333) break;//一点小优化for(ll j=i+1;j<res.size();j++){ll qq = res[j]*res[j];if(pp*qq>23333333333333) break;if(pp*qq<2333) continue;num++;}}cout<<num<<endl;return 0;
}

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;public class PrimeNumberCombination {// 定义常量 N，用于筛法范围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;}// 0 和 1 不是质数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 limit1 = BigInteger.valueOf(23333333333333L);BigInteger limit2 = BigInteger.valueOf(2333L);long num = 0;for (int i = 0; i < primes.size(); i++) {BigInteger pp = BigInteger.valueOf(primes.get(i)).pow(2);if (pp.pow(2).compareTo(limit1) > 0) {break;}for (int j = i + 1; j < primes.size(); j++) {BigInteger qq = BigInteger.valueOf(primes.get(j)).pow(2);BigInteger product = pp.multiply(qq);if (product.compareTo(limit1) > 0) {break;}if (product.compareTo(limit2) < 0) {continue;}num++;}}// 输出满足条件的组合数量System.out.println(num);}
}    

#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; // 求取数量相同的数在减2；else if(i==1) num2++;}int sum = 0;// 当已被占用的id的数量，大于未被占用id时，那么sum = num1;if(num1>num2){sum = num1;  }else{ // num2<num1的情况sum = num2 + (num1-num2)/2;}cout<<sum<<endl;return 0;
}

import java.util.Scanner;public class StudentIdAdjustment {// 定义常量 N，用于数组大小static final int N = 100005;public static void main(String[] args) {// 创建 Scanner 对象用于读取输入Scanner scanner = new Scanner(System.in);// 定义一个数组来记录每个 ID 出现的次数int[] arr = new int[N];// 读取学生的数量int n = scanner.nextInt();// 循环读取每个学生的 ID，并统计每个 ID 出现的次数for (int i = 0; i < n; i++) {int num = scanner.nextInt();arr[num]++;}// 初始化两个变量，用于统计需要处理的不同情况的数量int num1 = 0;int num2 = 0;// 遍历数组，统计 num1 和 num2 的值for (int i : arr) {// 如果某个 ID 出现的次数大于 2，计算超出 2 的部分并累加到 num1if (i > 2) {num1 += i - 2;} // 如果某个 ID 只出现了 1 次，将 num2 加 1else if (i == 1) {num2++;}}// 初始化最终结果变量int sum = 0;// 当 num1 大于 num2 时，说明已被占用的 ID 数量更多，sum 等于 num1if (num1 > num2) {sum = num1;} // 当 num2 大于等于 num1 时，按照相应规则计算 sumelse {sum = num2 + (num1 - num2) / 2;}// 输出最终结果System.out.println(sum);// 关闭 Scanner 对象，释放资源scanner.close();}
}    

1 2 3 4
1 5 4
------------
对比两个数列的第一位，相同，不用变
------------
3 3 4
6 4
第一位不同，合并小的前两位
----------
6 4
6 4
....

#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];// sum_a a数列的前缀和// sum_b b数列的前缀和// cnt_a a的位数// cnt_b b的位数// cnt_sum 总共需要的次数long long sum_a=0,sum_b=0,cnt_a=0,cnt_b=0,cnt_sum=0;while(true){if(sum_a==sum_b){sum_a+=a[cnt_a++];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; // 使用long避免大数溢出int cnt_a = 0, cnt_b = 0; // 数组a和b的当前指针位置int cnt_sum = 0; // 记录合并次数// 循环处理直到两个数组都遍历完毕while (true) {// 当两个前缀和相等时，移动到下一个元素if (sum_a == sum_b) {// 注意边界条件：避免数组越界if (cnt_a < n) {sum_a += a[cnt_a++]; // 移动a的指针并累加值}if (cnt_b < m) {sum_b += b[cnt_b++]; // 移动b的指针并累加值}} else if (sum_a < sum_b) {// a的前缀和较小，需要合并下一个元素sum_a += a[cnt_a++]; // 合并a的下一个元素cnt_sum++; // 合并次数加1} else {// b的前缀和较小，需要合并下一个元素sum_b += b[cnt_b++]; // 合并b的下一个元素cnt_sum++; // 合并次数加1}// 检查是否已经遍历完两个数组的所有元素if (cnt_a == n && cnt_b == m) {break;}}// 输出最终的合并次数System.out.println(cnt_sum);scanner.close();}
}

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;#define ll long long // 因为不可能出现负数，直接开到最大(unsigned long long)
const ll N = 2e3+5;struct point{int x;int y;
}p[N]; // 定义节点-预处理ll get_radius(int i, int j){ // 半径的平方return (p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y);
}bool is_parallel(int i, int j, int k){ // 用叉乘的方法，快速判断，这一步不会的，可以上网查询叉乘的作用，以及用法。ll v = (p[j].x-p[i].x)*(p[k].y-p[i].y)-(p[j].y-p[i].y)*(p[k].x-p[i].x); // i-j(p[j].x-p[i].x),(p[j].y-p[i].y) 与 i-k(p[k].x-p[i].x),(p[k].y-p[i].y)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); // 存// 预处理，只需要耗时O(n^2)，即可分堆，避免3层暴力的大量重复计算for(int i=0; i<n; ++i){unordered_map<ll,vector<int>> m; // 用半径的平方储存，这样就不用开方了for(int j=0; j<n; ++j){if(i==j) continue;ll len = get_radius(i,j);m[len].push_back(j); // 把这个点存进去}vec[i] = m; // 把map存入}// 最大的优点就是避免了许多无意义的重复计算int sum = 0;for(int i=0; i<n; ++i){ // 找到这个点，判断其内部的存储auto m = vec[i]; // 这个的出来的知识map结合，里面幼嫩多for(auto it=m.begin(); it!=m.end(); ++it){vector<int> p_m = it->second;if(p_m.size()<=1) continue; // 这种情况下，跳过for(int j=0; j<p_m.size(); ++j){for(int k=j+1; k<p_m.size(); ++k){if(is_parallel(i,p_m[j],p_m[k])) continue; // 共线sum++;}}}}cout<<sum<<endl;return 0;
}

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 + 10];//存储每个点的x坐标int[] y = new int [n + 10];//存储每个点的y坐标HashMap<String, Integer> s = new HashMap<>();//统计每个点的出现次数//键是点的坐标，如（"1 2")for(int i = 0; i < n; i++){x[i] = sc.nextInt();//输入第i个点的x坐标y[i] = sc.nextInt();//输入第i个点的y坐标String t = x[i] + " " + y[i];//将坐标拼接成字符串作为键s.put(t, s.getOrDefault(t , 0) + 1);//统计读点的出现次数}//计算核心部分//对于每个点i，计算它与其他所有点j的距离，并将距离相同的点分组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) continue;//跳过自己long d = (long)(Math.pow(x[i] - x[j], 2) + Math.pow(y[i] - y[j] , 2));//计算距离的平方List<Integer> list = map.getOrDefault(d, new ArrayList<>());//初始化列表list.add(j);//将点j加入对应的列表map.put(d,list);//更新map}//map是一个哈希表，键是距离的平方（d）值是一个列表，存储所有与点i距离为d的点的索引//d是点i和点j之间的距离的平方（为了节省计算量，没有开平方）for(long b : map.keySet()){List<Integer>list = map.get(b);//获取距离为b的所有点res += (list.size() * (list.size() - 1)) /2;//统计点的数量long c = 0;for(int j : list){long x3 = 2 * x[i] - x[j], y3 = 2 * y[i] - y[j];//计算对称带点x与y的坐标if(s.containsKey(x3 + " " + y3)){//拼接成字符串c += s.get(x3 + " " + y3);//统计对称点的出现次数}}res -= c/2;//减去重复统计的点对}}System.out.println(res);}
}

#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; // sum_value总和,cnt计数器vector<ll> dfn(N,0),low(N,0);
vector<int> vec[N]; // 定义邻接表
vector<ll> value(N,0); // 每个节点的权值
vector<ll> node_sum(N,0); // 回退回来的节点总和void tarjan(int u, int fa){ // 现节点u、父节点fadfn[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]);}}
}void slove(){ // 作为中转站cin>>n>>m;for(int i=1; i<=n; ++i) cin>>value[i],sum_value+=value[i];for(int i=0; i<m; ++i){ // 将无向图存入int r1,r2;cin>>r1>>r2;vec[r1].push_back(r2);vec[r2].push_back(r1);}// 现在啥都有了tarjan(1,0);if(value[1]!=sum_value) cout<<abs(sum_value-2*value[1])<<endl;else if(ans!=maxn) cout<<ans<<endl;else cout<<-1<<endl;
}int main(){slove();return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {// 定义常量 N 作为数组大小static final long N = (long) (1e6 + 5);// 定义“伪最大值”static final long maxn = 0x3f3f3f3f3f3f3f3fL;// 节点数量 n，边的数量 mstatic long n, m;// 所有节点权值总和static long sum_value = 0;// 时间戳计数器static long cnt = 0;// 存储最终结果static long 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<>();// Tarjan 算法核心函数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 算法处理邻接节点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));} else if (v != fa) { // 如果邻接节点已被访问且不是父节点// 更新当前节点的最早祖先时间戳low.set(u, Math.min(low.get(u), low.get(v)));}}}// 主处理函数static void solve() {Scanner scanner = new Scanner(System.in);// 读取节点数量和边的数量n = scanner.nextLong();m = scanner.nextLong();// 初始化列表for (int i = 0; i <= n; i++) {dfn.add(0L);low.add(0L);value.add(0L);vec.add(new ArrayList<>());}// 读取每个节点的权值并计算总和for (int i = 1; i <= n; i++) {value.set(i, scanner.nextLong());sum_value += value.get(i);}// 读取边的信息并构建邻接表for (int i = 0; i < m; i++) {int r1 = scanner.nextInt();int r2 = scanner.nextInt();vec.get(r1).add(r2);vec.get(r2).add(r1);}// 从节点 1 开始进行 Tarjan 算法tarjan(1, 0);// 如果节点 1 的权值总和不等于所有节点的权值总和if (value.get(1) != sum_value) {System.out.println(Math.abs(sum_value - 2 * value.get(1)));} else if (ans != maxn) { // 如果找到了割边System.out.println(ans);} else { // 没有找到符合条件的割边System.out.println(-1);}}public static void main(String[] args) {// 调用主处理函数solve();}
}

#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;if(X<0||X>=n||Y<0||Y>=m) continue; // 出边界if(st<k&&grid[X][Y]!=grid[u.x][u.y]) continue;if(st==k&&grid[X][Y]==grid[u.x][u.y]) continue;st = st%k; // 时刻更新着if(used[X][Y][st]) continue; // 都是更新之后，在遍历的used[X][Y][st]=true; // 表示遍历过res[X][Y][st]=res[u.x][u.y][u.step]+1; // 多走了一步q.push({X,Y,st});}}return -1; // 此时还没有解释，只能说明一件事，遍历到头了，没有结果。
}int main(){// 基本处理cin>>n>>m>>k;string str;for(int i=0; i<n; ++i){cin>>str;for(int j=0; j<m; ++j) grid[i][j]=str[j];}cout<<BFS();return 0;
}

import java.math.BigInteger;
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<Pair>();qu.add(new Pair(0, 0, 1));int[][] d = new int[][] {{0,1},{1,0},{0,-1},{-1,0}};boolean[][][] visited = new boolean[n][m][2 * k];for (int step = 0; !qu.isEmpty(); step++) {int num = qu.size();for (int i = 0; i < num; i++) {Pair pair = qu.pollFirst();int px = pair.x, py = pair.y, pf = pair.flag;if (visited[px][py][pf]) {continue;}visited[px][py][pf] = true;if (pair.x == n - 1 && pair.y == m - 1) {System.out.print(step);return;}for (int j = 0; j < 4; j++) {int x = px + d[j][0];int y = py + d[j][1];int f = (pf + 1) % (2 * k);if (x >= 0 && x < n && y >= 0 && y < m) {if (visited[x][y][f]) {continue;}if (pf < k && mg[x][y] == 'A' || pf >= k && mg[x][y] == 'B') {qu.addLast(new Pair(x, y, f));}}}}}System.out.print(-1);}
}class Pair {int x, y, flag;public Pair(int x, int y, int flag) {super();this.x = x;this.y = y;this.flag = flag;}
}

#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) {// 定义常量 N，用于数组大小final int N = 2000005;Scanner scanner = new Scanner(System.in);// 读取 n 和 m 的值int n = scanner.nextInt();int m = scanner.nextInt();// 创建长度为 N 的数组 res 并初始化为 0int[] res = new int[N];// 读取 n 条线段的左右端点信息for (int i = 0; i < n; i++) {int l = scanner.nextInt();int r = scanner.nextInt();// 对线段中点对应的数组元素加 1res[l + r]++;}// 构建前缀和数组for (int i = 1; i < N; i++) {res[i] += res[i - 1];}// 处理 m 个查询区间for (int i = 1; i <= m; i++) {int L = scanner.nextInt();int R = scanner.nextInt();// 将查询区间的左右端点乘以 2L *= 2;R *= 2;int result;// 处理左端点为 0 的边界情况if (L == 0) {result = res[R];} else {result = res[R] - res[L - 1];}// 输出结果System.out.println(result);}scanner.close();}
}    

abs(a-b)<1e-6