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

本来想刷省赛题呢，结果一不小心刷成国赛了
真是个小迷糊〒▽〒
但，又如何( •̀ ω •́ )✧
记录刷题的过程、感悟、题解。
希望能帮到，那些与我一同前行的，来自远方的朋友😉

注：感谢@Witton的提示，题目部分已完成修改( •̀ ω •́ )y

大纲：

一、子2023-（题解）-递推or动态规划

二、双子数-（题解）-筛法、类型(unsigned long long)😥

三、班级活动-（题解）-不出所料、贪心+计数

四、合并数列-（题解）-妥妥的前缀和😥，当然双指针也能做

五、数三角-（题解）-这个真的就是算术题了，还要用到各种优化（叉乘、用半径分组）

六、删边问题-（题解）-图(tarjan算法)割边、割点，经典板子题

七、AB路线-（题解）-BFS广搜，最短路径、记忆话搜索😉

八、抓娃娃-（题解）-简单点的差分+前缀和😊

九、十，等后续冲击国赛时，再解决。

一、子2023

问题描述

小蓝在黑板上连续写下从 1 到 2023之间所有的整数，得到了一个数字序列： S=12345678910111213...20222023。 小蓝想知道 S 中有多少种子序列恰好等于 2023？

以下是 3 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：

1[2]34567891[0]111[2]1[3]14151617181920212223...
1[2]34567891[0]111[2]131415161718192021222[3]...
1[2]34567891[0]111213141516171819[2]021222[3]...

注意以下是不满足条件的子序列，虽然包含了 2、0、2、3 四个数字，但是顺序不对：

1[2]345678910111[2]131415161718192[0]21222[3]...

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

动态规划解法：

本题解法，说成是状态规划，可能会引起恐惧，其实它就是一道简单的状态推导题( •̀ ω •́ )✧

C++

#include <iostream> #include <vector> using namespace std; // 是个简单的动态规划就算了 // 怎么又是一道越界题目 // 以后统一不用long long改用 unsigned long long。更大。 int main(){ vector<unsigned long long> dp(4,0); string; 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; }

Java

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]); } } 

二、双子数

问题描述

若一个正整数 x 可以被表示为 p2×q2，其中 p、q 为质数且 p≠q，则 x 是一个双子数。请计算区间 [2333,‭23333333333333‬] 内有多少个双子数？

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

// 我本以为，本题最难的是欧拉筛，也就是线性筛
// 后来我发现，我错了，而且错的离谱
// 欧拉筛，能用埃氏筛代替，能用朴素也就是暴力法代替。
// 而本题最大的难点是符号位，如果你开到(long long)，答案会始终多10，让你痛不欲生。
// 本题要开到，unsigned long long
// int->1e9 , long long->1e18, unsigned long long是longlong的两倍

// 切记，不会欧拉筛的，可以用线性筛代替，或者直接暴力（会慢一些）:: 四种筛法 ::

C++

#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; }

Java

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); } } 

三、班级活动

问题描述

小明的老师准备组织一次班级活动。班上一共有 n 名 (n 为偶数) 同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 n 以内的正整数作为 id，第 i 名同学的 id 为 ai​。

老师希望通过更改若干名同学的 id 使得对于任意一名同学 i，有且仅有另一名同学 jj 的 idid 与其相同 (ai=aj​)。请问老师最少需要更改多少名同学的 id？

输入格式

输入共 2 行。

第一行为一个正整数 n。

第二行为 n 个由空格隔开的整数 a1,a2,...,an。

输出格式

输出共 1 行，一个整数。

样例输入

样例输出

样例说明

仅需要把 a1​ 改为 3 或者把 a3​ 改为 1 即可。

评测用例规模与约定

对于 20% 的数据，保证 n≤10^3。

对于 100% 的数据，保证 n≤10^5

// ⚆_⚆？当我找到哪里错了之后，泪流满面
// 本题其实挺简单
// 读题：“每名同学，随机分配n以内的正整数作为id” 
// 这说明，每个同学的id有两种情况。
// 此时举一个简单的例子就OK了
// 像题目中举得例子，1 2 2 3 一组（2,2）就能配对，仅需更改3变成1（1->3也行）就OK了，只需一次。
// 推算成公式，也就是 2/1=1 -> 散列的总数/2
// 进阶一点，当id为 2 2 2 1时，此时一组（2,2）就能配对，这时仅需更改剩下的2变成1就OK了，也只需要更改一次。
// 如果是 2 2 2 2 2 1 呢，要先去掉一组（2,2）
// 此时剩下 2 2 2 1，因为不能与已经配对的（2,2）重复，
// 所以先把其中一个2改为1，需要一次。
// 此时剩下 2 2，只需将它们改成其他数就行，如改成（3,3），需要两次。
// 一共用了3次，也就是2的总数 减去2 也就是减去（2,2）这个不需要改变的组合。
// 也就是 当已被占用的id的数量，大于未被占用id时，总数等于 重复 id的数量。

C++

#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; }

Java

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(); } } 

四、合并数列

问题描述

小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将他们列为两个数组 {a1,a2,...,an}和 {b1,b2,...,bm}。两个数组的和相同。

定义一次合并操作可以将某数组内相邻的两个数合并为一个新数，新数的值是原来两个数的和。小明想通过若干次合并操作将两个数组变成一模一样，即 n=m 且对于任意下标 i 满足 ai=bi。请计算至少需要多少次合并操作可以完成小明的目标。

输入格式

输入共 3 行。

第一行为两个正整数 n, m。

第二行为 n 个由空格隔开的整数 a1,a2,...,an​。

第三行为 m 个由空格隔开的整数 b1,b2,...,bm​。

输出格式

输出共 1 行，一个整数。

样例输入



样例输出



样例说明

只需要将 a2​ 和 a3 合并，数组 a 变为 {1,5,4}，即和 b 相同。

评测用例规模与约定

对于 20% 的数据，保证 n, m≤10^3。

对于 100% 的数据，保证 n, m≤10^5，0<ai, bi≤10^5。

// 本题原意：“两个数列，通过不断合并相邻的两个数，使两个数列相同”
// 注意-“相邻” “合并（相加）”，也就意味着可能要使用前缀和。
// 用反向思维来看，两个数列最终是相同的。
// 也就意味着从俩数列，第一个数开始，就要是相同的。
// 我们只需要从头开始计算前缀和，如果相同时，代表俩数列第i位已经相同，
// 此时更新俩前缀和的计算起始位置即可。
// 所以本题是，双指针与前缀和的结合。

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

// 本题又让我痛哭不已，类型开小了，本题最大有1e10左右，int不太行

C++

#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; }

Java

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(); } }

五、数三角

问题描述

小明在二维坐标系中放置了 n 个点，他想在其中选出一个包含三个点的子集，这三个点能组成三角形。然而这样的方案太多了，他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形？

输入格式

输入共 n+1 行。

第一行为一个正整数 n。

后面 n 行，每行两个整数 xi, yi表示第 i 个点的坐标。

输出格式

输出共 1 行，一个整数。

样例输入



样例输出



样例说明

一共有 4 种选法: {3,4,5}、{1,3,4}、{5,2,3}、{1,4,5}。

评测用例规模与约定

对于 20% 的数据，保证 n≤200。

对于 100% 的数据，保证 n≤2000，0≤xi,yi≤10^9。

/*
  本题要是直接3层暴力，肯定对，但是只能获取60%的分！
  所以要用上很多优化方式
  如：根据半径求解，叉乘(在本文下方有讲解，也可上网搜)判是否三点在一条直线上
  通过vector<map<ll,vector<int>>> 预处理分组。
  最后用unordered_map存储，O(1)

  其实最开始，我也是有疑问的，这是怎么将O(n^3)优化到接近O(n^2)
  毕竟预处理分组后下方仍有4层循环呢
  其实画个图就好了。
  没优化之前，每个节点都要判断(n^2)次,优化之后，每个节点仅需判断分组过后的就行(哪怕是4层，其实有效的点不多，可近似成线性)。
*/

 C++

#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; }

Java

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); } }

六、删边问题

问题描述

给定一个包含 N 个结点 M 条边的无向图 G，结点编号 1...N。其中每个结点都有一个点权 Wi​。

你可以从 M 条边中任选恰好一条边删除，如果剩下的图恰好包含 2 个连通分量，就称这是一种合法的删除方案。

对于一种合法的删除方案，我们假设 2 个连通分量包含的点的权值之和分别为 X和 Y，请你找出一种使得 X与 Y 的差值最小的方案。输出 X 与 Y 的差值。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N个整数，W1,W2,...WN​。

以下 M 行每行包含 2 个整数 U 和 V，代表结点 U 和 V之间有一条边。

输出格式

一个整数代表最小的差值。如果不存在合法的删除方案，输出 −1。

样例输入



样例输出



样例说明

由于 1 和 2 之间实际有 2 条边，所以合法的删除方案有 2 种，分别是删除 (2,3) 之间的边和删除 (3,4) 之间的边。

删除 (2,3) 之间的边，剩下的图包含 22 个连通分量: {1,2} 和{3,4}，点权和分别是 30、70，差为 40。

删除 (3,4) 之间的边，剩下的图包含 22 个连通分量: {1,2,3} 和 {4}，点权和分别是 60、40，差为 20。

评测用例规模与约定

对于 20% 的数据，1≤N,M≤10000。

对于另外 20%的数据，每个结点的度数不超过 2。

对于 100% 的数据，1≤N,M≤200000，0≤Wi≤10^9，1≤U,V≤N。

// 本题为tarjan算法的变种，不懂的，可以先搜一下基本用法（涉及图的知识），本文最底部，也有优质视频的链接
/*
  其实本题不难，只要有图的基础就行--（能看懂答案的前提）
  连通分量：图的一个子图，这个子图中，任意两点之间，都存在可达路径
  然后就是 tarjan 算法（懂得可以不用看，建议先看视频，知道tarjan是啥）
  *
    用dfn（发现时间戳）与low（最低可达祖先的发现时间戳）。确切的说，他俩都是个编号。
    然后用cnt（count）这个设置时间戳。每次++。
    --以上是tarjan算法模版--
    建立一个函数tarjan(n,fa) // n是现节点，fa是父节点，避免重复用的
    然后，递归调用每个现阶段子节点（大致会先将所有）
    此时有三种情况
      1、是未被遍历过的新节点
        （这时可以继续向下搜索，等回退到这里时，
        （更新一下low值，若果现节点的dfn小于子节点的low值(dfn<low)，代表连通两节点的边能被割去
        （为了计数，可以在维护一个w集合，用于储存以本节点为结尾的总和
      2、遍历到了父节点
        （可以毫不犹豫的退回了）
      3、遍历到了非父节点的旧节点
        （这个可是更新low值的好时候
        （是为了给，回溯时，判断是否能构成联通图    做准备
  *
  // 拓展-从割边问题 -> 割点问题
  (割点问题时，需要将low小于等于dfn(low<=dfn)
  (为啥<=中，多了个等于？因为一旦删掉这个点，整个链子就会断开，Java解析下方有图解
*/

C++

#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; } 

Java

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(); } }

 拓展（割点）：

​

七、AB路线

问题描述

小明拿了 n条线段练习抓娃娃。他将所有线段铺在数轴上，第 i 条线段的左端点在 li​，右端点在 ri​。小明用 m 个区间去框这些线段，第 i 个区间的范围是 [Li​, Ri​]。如果一个线段有 至少一半 的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?

输入格式

输入共 n+m+1 行。

第一行为两个正整数 n, m。

后面 n 行，每行两个整数 li​, ri​。

后面 m 行，每行两个整数 Li​, Ri​。

输出格式

输出共 m 行，每行一个整数。

样例输入



样例输出



评测用例规模与约定

对于 20% 的数据，保证 n,m≤10^3。

对于 100% 的数据，保证 n,m≤10^5，li​<ri​，0<li,ri,Li,Ri≤10^6，max{ri​−li​}≤min{Ri​−Li​}.

/*
   审题 “小蓝最少要走多少步？”，“最少”
   BFS就是解决图-最短路径的特效药，
   DFS深搜也能搜到，但不一定是最短的，深搜更倾向于排列组合、解数独、八皇后，这种尝试性的算法。
   好了，确定本题的基调，就是广搜

   在开始之前，还需考虑一个问题，就是暴力搜索必然会超时，因此，枝减操作，必不可少。也就是要引入记忆化搜索。
   这个时候，就要思考，用什么存储记忆化搜索
   注意本题 "格子数，要是K的倍数，所以这里涉及到了k"
   -used[i][j][k]; 其中k来储存走到这个格式，连续走的步数。
   步数相同时，代表该地址已经被走过。相同的符号，相同的步数，所以可以直接跳过。
   （注意，这里不用三维数组标记，是会超时的）。

   所以本题用queue广搜、used[i][j][k]记忆化搜索、res[i][j][k]标记走的这个位置，用了多少步。
*/

C++ 

#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; } 

Java

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; } }

八、抓娃娃

问题描述

小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上，第 i 条线段的左端点在 li​，右端点在 ri。小明用 m 个区间去框这些线段，第 i 个区间的范围是 [Li​, Ri​]。如果一个线段有 至少一半 的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?

输入格式

输入共 n+m+1 行。

第一行为两个正整数 n, m。

后面 n 行，每行两个整数 li​, ri​。

后面 m 行，每行两个整数 Li​, Ri​。

输出格式

输出共 m 行，每行一个整数。

样例输入



样例输出



评测用例规模与约定

对于 20% 的数据，保证 n,m≤10^3。

对于 100% 的数据，保证 n,m≤10^5，li​<ri​，0<li,ri,Li,Ri≤10^6，max{ri​−li​}≤min{Ri​−Li​}.

// 聪明的你，一定用的暴力，聪明的你，一定超时o(*￣▽￣*)ブ 
// 本题，用差分+前缀和，就能非常完美的解决问题
// 此外，本题预处理化的时候，一定要看清楚！
// 不要处理成2e5+5了，要开r、l、R、L。而不是n,m;

C++

#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; }

Java

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(); } } 

后面的两道题，咱时间有限，就先跳过啦(～￣▽￣)～

等后续打国赛时，在拐回来写写。

当然大家有好的代码、解析，也可以发给我，让我瞅瞅。( •̀ ω •́ )✧，我贴上去。

知识点：

一、向量、点乘、叉乘

（AI整理）

1、向量：

由来：

早在古希腊时期，数学家与物理学家已经意识到某些量（如力、速度）兼具大小和方向。此时
已经蕴含了向量，但此时并未形成明确的概念与理论。

17世纪笛卡尔创建解析几何后，点的位置可用坐标来表示，线段的长度和方向可通过坐标差量化。
这为向量的代数表达，奠定了基础。

后来经过负数、四元数的启发、线性扩张论...等几代人努力与知识的迭代，向量才最终别确定下来。

定义：

​

基本属性：

​

常见运算：

​

2、点乘：

不要问，为啥叫点乘，这是一个非常可爱的问题 --> 因为两向量之间用 “点号” 相乘。

定义：

两向量之间相乘，结果为标量。

​

应用：

• 判断两条边之间，是钝角（负数）、直角（0）、还是锐角（正数）
• 一条边在另一条边上映射的长度。
• 计算力的做功。

3、叉乘：

也不要问，为啥叫叉乘，这是一个非常可爱的问题 --> 因为两向量之间用 “叉号” 相乘。

二维：

​

三维：

​应用：

切记，判断点时，叉乘边的方向很重要。点的那条边，放在第二个。

求平行四边形与三角形的面积：

二维 两向量叉乘，求的是平行四边形的面积。除于2，求的是三角形。

点与直线的关系：

​

线段相交的检测：

​

点与直线关系，详解！！

​

二、浮点数比较

在编程中，通常不用==号，来进行浮点数比较。因为会出现精度误差。即便在数学中相等，在计算机中也不一定相等。

abs(a-b)<1e-6

通常用小于1e-6来测试差值。

1e-6在通常情况下是够用的，
它既不是那么严格（把本应该相同的数，判为不同）
它也不是那么宽松（把本不同的数，判为相同）

三、map与unordered_map

map底层为红黑树，unordered_map底层为哈希表

存or取，map(O(logN))的效率皆低于unordered_map(O(1))。

四、极大值（32位、64位、16进制）

• INT32_MAX 是 32 位有符号整数的最大值，为 2,147,483,647。（2.15 × 10⁹）
• 0x3f3f3f3f3f3f3f3f：转换为十进制为：1,082,367,756,170,655,743。（约 1.08 × 10¹⁸）
• INT64_MAX：约 9.22 × 10¹⁸。

INT32_MAX是32位，标准最大值。
INT64_MAX是64位下，标准最大值。
0x3f3f3f3f3f3f3f3f，常常被归纳于“伪最大值”，它即起到最大值的作用，又能适当的相加。在图、树中，常被赋予权值，表示不可抵达的点。

五、广搜(BFS)与深搜(DFS)

广搜：

（队列）

• 最短路径问题，常用于判断最短路径问题。
• 图或树的层序遍历问题。
• 判断连通性。

深搜：

（递归、栈）

• 路径问题，寻找某一个点到另一个点的路径，可能不是最短路径。
• 回溯问题，可用于某些需要试错的算法（解数独、八皇后）
• 求解组合问题（全排列、组合等问题）DFS可以遍历所有有解空间。
• 拓扑排序，暂时还不熟悉

六、vector的比较方案-map

在C++中，两个vector比较，是通过operate==，进行比较的。

先比较数组大小，在依次、逐个比较具体内容。

map可以以vector为键

std::map 基于红黑树（一种自平衡的二叉搜索树）。会通过排序确定位置。（operate<）

且vector已经重载过(operate <) 了，比较时，自动按照字典序比较。

unordered_map不可以以vector为键

键的要求是

1、能满足 哈希函数 转化为 哈希值。

2、能通过operate== 进行比较

虽然vector中定义了operate==，但是没有定义，哈希函数。

（总结：map都具备，unordered_map不能将vector转化为哈希函数）

借鉴视频、博客：

1、[算法]轻松掌握tarjan强连通分量 - 图