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 并初始化为 0
        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]);
    }
}    

#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 的部分并累加到 num1
            if (i > 2) {
                num1 += i - 2;
            } 
            // 如果某个 ID 只出现了 1 次，将 num2 加 1
            else if (i == 1) {
                num2++;
            }
        }

        // 初始化最终结果变量
        int sum = 0;
        // 当 num1 大于 num2 时，说明已被占用的 ID 数量更多，sum 等于 num1
        if (num1 > num2) {
            sum = num1;
        } 
        // 当 num2 大于等于 num1 时，按照相应规则计算 sum
        else {
            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、父节点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]);
        }
    }
}

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，边的数量 m
    static 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 并初始化为 0
        int[] res = new int[N];
        // 读取 n 条线段的左右端点信息
        for (int i = 0; i < n; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            // 对线段中点对应的数组元素加 1
            res[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();
            // 将查询区间的左右端点乘以 2
            L *= 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