【蓝桥杯/算法】C/C++注意点；算法（Java版）
学习指南
每次b站的蓝桥云课在快比赛的时候，应该都会发这种学习指南，然后卖课
不用买课，可以看着指南自己学
时间紧的话，刷真题也没有必要了，难度高，刷的题目的算法也不一定考，在考场上也不一定写的出来
一定要巩固基础
这是蓝桥杯冲刺计划的提单
也是溶金的网站
up:
蓝桥杯三十天冲刺系列
BV18eQkY3EtP
网站：
C/C++注意
比赛时，devc++勾选c++11（必看）
必须勾选c++11一共有两个方法，任用一个就可以了。（方法一有两个c++11可以选，好像都可以）
如果不勾选，map、to_string等不能使用，无法编译
蓝桥杯用的是c++11，所以C++17自带gcd函数或GCC拓展的__gcd函数不能用
- 方法一：
- 方法二
c++大概一秒跑10⁸的数据
10^8，大约是2^26次
对于子集枚举的算法中，O(n)=2^n
int大约2.1*10^9
long long大约9.2*10^18
c++除法 / 是向0取整（对于正数就是向下取整）
return退出函数
return 可以用来退出函数，如果是嵌套的循环，想要直接退出，要在每一层循环都break
可以用return
一般在main函数中调用solve()函数，在solve()函数中写解题逻辑
void solve(){
for(){
for(){
for(){
//这里使用return，直接退出了循环
//如果用break，在这里要使用三次，每一层都写一遍
return;
}
}
}
}
int main(){
solve();
return 0;
}变量int _=1;
首先使用
_作为变量名是符合语法规则的使用 _ 来作为这种控制循环次数的变量。一种竞赛时的默认写法，有一定的通用性
#include <bits/stdc++.h>
using namespace std;
void solve(){
}
int main() {
//使用下划线
int _=1;
while(_--)solve();
return 0;
}万能头
定义万能头，不需要敲所有的头文件了，因为都包含了
缺点：影响编译速度，和运行速度没有关系，所以比赛可以用
#include <bits/stdc++.h>关闭缓冲流
提高运行效率
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}endl比'\n'慢
直接这样换，即打的轻松，又用了'\n'
#define endl '\n'#define int long long
如果代码中混合使用 int 和 long long，可能导致隐式类型转换错误。统一使用 long long 可以避免这类问题
int main必须改为signed main
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
return 0;
}数组开大一点点，定义到全局
对于题目给出的数组，自己定义的时候，开大一点点（数字随便，多10个甚至9个都行），为了防止数组越界
数组定义到全局里，不要定义在main中，c++中，如果把数组定义到main函数中，main函数是栈空间，空间比较小，一定义可能会把栈爆了
#include <bits/stdc++.h>
using namespace std;
//如果题目要求a数组最大是1000，开大一点点
//定义到全局，不要定义在main函数中
const int NN=1010;
int a[NN];
int main(){
return 0;
}记忆化搜索的dp，如果是多测（多组测试数据），不要写memset
memset的复杂度是数组的空间复杂度，如果是多组测试数据，用for循环手动把dp初始化成-1
main函数外声明的函数顺序影响调用
同理全部变量的声明也要放在最上面
#include <bits/stdc++.h>
using namespace std;
//可以在最上面使用函数声明（{}前的，带个分号），这么就无关定义顺序了
void f2();
//这个f3不可以使用，因为f3之中有f2，f2还没有定义，f3不知道调用什么
void f3(){
f2();
}
void f2(){
}
//这个f1可以使用，因为f2已经定义了，f1在调用f2的时候知道是什么函数
void f1(){
f2();
}
int main() {
return 0;
}由数据范围反推算法复杂度以及算法内容
Java注意点
换行符
PrintWriter性能更好
PrintWriter out = new PrintWriter(System.out);
// ...
out.println(); // 输出一个空行（相当于换行）性能较差，但更容易想到
System.out.println();//直接输出换行符蓝桥杯常见知识点
枚举
进制转换
将字符转换成数字
如果是数字字符，这个字符 c - '0' 就能直接转换为对应的数字值
如果是字母字符，判断条件字符 c >= 'A'，c - 'A' + 10 就能转换为对应的数字值（16进制，A表示10，所以字母对应数字是从10开始的）
提升位权（把字符变数字一定要提升位权）
之前累加的结果 ans 乘以进制 k，这相当于把之前的结果左移一位（也就是提升一位位权）
K进制转十进制
c是char类型，是字符。如字符'1'是按照ascii存，数字字符-'0'得到int类型的数字
int calc(char c) {
// 如果字符是字母（即大于 '9'）转换为对应的数字值（A=10, B=11, ...）
if(c >= 'A') return c - 'A'+10;
// 如果是数字字符，直接转换为对应的数字值
return c - '0';
}
int change(int k, string s) {
int ans = 0;
for(int i = 0; i < s.size(); i++) {
ans = ans * k + calc(s[i]); // 基于进制 k 进行累加
}
return ans; // 返回转换后的十进制数
}十进制转K进制（短除法）
关键：十进制x%=k（得到k进制的当前位），然后x/=k（更新x）
string change(int x, int k) {
string ans; // 初始化空字符串，用于存储转换结果
while (x) {
int tmp = x % k; // 计算 x 对 k 取余，得到当前位的值
// 如果余数小于等于9，直接将其转换为字符并追加到结果字符串
// 因为是字符串和字符，所以+代表拼接
if (tmp <= 9) {
// '0' + tmp 转为对应数字字符的ASCII码
//因为tmp是int，'0'强转成int，所以得到得是ASCII码中的整数
//需要强转成char才能获得真正对应的数字字符
ans = ans + (char)(tmp + '0');
} else {
// 如果余数大于9，表示需要用字母 A, B, C...表示（例如10为A，11为B等）
// tmp - 10 + 'A' 转为对应字母字符的ASCII码
ans = ans + (char)( tmp - 10 + 'A' );
}
x /= k; // 更新 x，x 除以 k
}
// 将结果字符串反转并返回，返回的字符串为转换后的进制表示
reverse(ans.begin(), ans.end()); // reverse反转字符串（注意：没有返回值）
//返回反转的字符串
return ans;
}题目
穿越时空之门
#include <bits/stdc++.h>
using namespace std;
int cnt=0;
//求k进制各数位之和
int calc(int n,int k){
int sum=0;
while(n){
sum=sum+n%k;
n/=k;
}
return sum;
}
void solve(){
for(int i=1;i<=2024;i++){
if(calc(i,2)==calc(i,4))cnt++;
}
}
int main(){
solve();
cout<<cnt;
return 0;
}一维前缀和
一维前缀和，即一个数列中，某个数的前n项和=前n-1项的和+这个数
计算前缀和时，索引从1开始，让prefix[0]用默认的0
区间和查询
sum[ l,r ]区间和，即 l~r 之间的和，即 r 的前缀和减去 l 前面一项的前缀和
不会看，直接无脑把区间和sum设置成long long类型后，就不管了
在题目求和中，运用了一维前缀和的思维，出现了int*int的情况，强转成long long防止溢出
sum=sum+(long long)a[i]*(prefix[n]-prefix[i]);
前缀和求差分得到原数组
差分，就是后一项减去前一项的行为
a[ i ] = prefix[ i ] - prefix[ i-1 ] // 对于 i > 0
题目
一维前缀和
#include <bits/stdc++.h>
using namespace std;
const int NN=1e5+10;
int n,q;
int a[NN];
int prefix[NN];
int main() {
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
prefix[i]=prefix[i-1]+a[i];
}
int sum=0;
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
int sum=prefix[r]-prefix[l-1];
cout<<sum<<endl;
}
return 0;
}求和（强转成long long类型，防止溢出）
思路：
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+10;
int a[NN];
int b[NN];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=b[i-1]+a[i];
}
long long sum=0;
for(int i=1;i<n;i++){
//i=1时，是a2+a3+...+an，第一个元素索引是i+1，b[i+1-1]
//这里int*int会溢出，强转成long long
sum=sum+(long long)a[i]*(b[n]-b[i]);
}
cout<<sum;
return 0;
}一维差分（解决区间修改问题）
对差分数组求前缀和得到原数组（个人理解：求第i项原数组=前一项（i-1）原数组+位置i-1到i的变化率（diff[ i ]））
a[ i ] = a[ i-1 ] + diff[ i ]
a[i-1]：表示前一个位置（i-1）的原始值
diff[i]：表示从位置i-1到位置i的"变化量"或"增量"（即变化率）
差分数组，即这一项与前一项之差
对于数组[ 2,3,7,4,5,1 ]，一维差分[ 2,1,4,-3,1,-4 ]
一维差分的前缀和就是原数组（可以看成积分求面积）
快速区间修改
在区间[ l,r ]修改
b[l] += d，相当于对后面所有的项都形成了“连坐”的反应，要求在[ l,r ]区间修改，即希望这个“连坐”只在这个区间有效，所以 b[r+1] -=d 来消除“连坐”影响（差分，就是变化率，对差分的修改，就是直接修改了变化率，而不是修改原数组）
对于数组[ 2,3,7,4,5,1 ]，一维差分[ 2,1,4,-3,1,-4]，希望[ 3,7,4 ]这个序列全部加上3，对应公式b[2]+=3，b[5]-=3
先看b[2]+=3，后面全部被影响了
再看b[5]-=3
判定序列中是否全部数字相同
已知：差分数组求前缀和就是原数组
当差分数组除第一项以外的所有项数均为0时，原数组一定所有数字相同（因为前缀和一致）
让某一项-1，再让某一项+1（相当于对原序列中的某一个连续的区间全部-1）
最后再让某一项-1
如：
1 2 -1
第二项-1，第三项+1：1 1 0
第二项-1，让不参与计算的n+1项+1: 1 0 0 [+1]
无解的情况
1 2 -3
无论如何 -3不能变成0，因为只能让某一项-1后，让某一项+1，第一项是不参与的，其他的正数和，比-3小，所以不够
在正数和<负数和时，无解
让原数组变成相同的数字
就是让一维差分数组的的b[1]有值，而且所有都是0
i==1时的特判
让一维差分方程b[i](i>1)变成0的操作数，就是所有一维差分数组中所有的正数的和
b[1] 作为差分数组的第一个元素，和其他 b[i]（i > 1） 一样，都是差分数组整体的一部分。在处理差分数组时，为了保证处理逻辑的一致性和完整性，把b[1]的值也加上，先把它视做和其他b[i]一样要归0的数
因为本题要求原数组最后全为1，即要b[1]=1，所以在代表操作数的ans+b[1]只有-1，表示留下数字，不要操作，比如这里希望b[1]=1，就要-1，表示操作时，要留下一个数字不操作，它就被保留下来了，最后就是b[1]=1。如果是-1，表示留下两个数字不操作，最后就是b[1]=2
i==1时的特判，按情况而定
long long ans=0;
for(int i=1;i<=n;i++){
//i=1时的特判
if(i==1){
ans=ans+diff[1]-1;
}else{
if(b[i]>0)ans=ans+diff[i];
}
}题目
一维差分
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+10;
int n,m;
int a[NN],b[NN];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
for(int i=1;i<=m;i++){
int l,r,d;
cin>>l>>r>>d;
b[l]+=d;
b[r+1]-=d;
}
for(int i=1;i<=n;i++){
b[i]=b[i-1]+b[i];
cout<<b[i]<<" ";
}
return 0;
}小蓝的操作数
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],diff[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
diff[i]=diff[i]-diff[i-1];
}
long long ans=0;
for(int i=1;i<=n;i++){
//i=1时的特判
if(i==1){
ans=ans+diff[1]-1;
}else{
if(b[i]>0)ans=ans+diff[i];
}
}
cout<<ans;
return 0;
}二维前缀和
二维前缀和
prefix是前缀和数组，a是原序列（即这个格子的值）
prefix[ i ][ j ] 表示从 a[ 1 ][ 1 ] 到 a[ i ][ j ] 的子矩阵中所有元素的和
构造二维前缀和数组公式：
prefix[ i ][ j ]=prefix[ i-1 ][ j ]+prefix[ i ][ j-1 ]-prefix[ i-1 ][ j-1 ]+a[ i ][ j ];
（s[ i ][ j ]=a[ i ][ j ]+s[ i-1 ][ j ]+s[ i ][ j-1 ]-s[ i-1 ][ j-1 ]，两个是一样的，用prefix名字清晰，图中忽视S，只看坐标就行）
通过二维前缀和数组，求解某个子矩阵数组的值：
求解（x1,y1）到(x2,y2）
prefix[ x2 ][ y2 ]-prefix[ x1-1 ][ y2 ]-prefix[ x2 ][ y1-1 ]+prefix[ x1-1 ][ y1-1 ]
前缀和求差分得到原数组（差分，就是前一项减去后一项）
a[ i ][ j ] =prefix[ i ][ j ]-prefix[ i−1 ][ j ]-prefix[ i ][ j−1 ]+prefix[ i−1 ] [ j−1 ]
二维前缀和
#include <bits/stdc++.h>
using namespace std;
const int NN=1010;
int a[NN][NN],s[NN][NN];
int n,m,q;
int main(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
//构建二维前缀和数组
prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=q;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<prefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]+prefix[x1-1][y1-1]<<endl;
}
return 0;
}二维差分（子矩阵修改问题）
用差分数组进行区间更新：
假设我们要对子矩阵 (x1,y1) 到 (x2,y2) 的所有元素加上 d，可以转化为对差分数组 diff[][] 的 4 个单点操作
这个一个二维的差分
希望对(x1,y1)到(x2,y2)这一块就加上d，对diff[x1][y1]+d之后，从（x1,y1）开始，一直到最右下角（某个点（n,m））都会加上d
这时候，我们要消除不需要的加d操作
diff[ x1 ] [y1 ] += d（标记左上角，表示从 (x1,y1) 开始的所有区域都 +d，一直加到了右下角，）
diff[ x2+1 ][ y1 ] -= d（标记左下角，表示从 (x2+1,y1) 开始的所有区域撤销 +d）
diff[ x1 ] [ y2+1 ] -= d（标记右上角，表示从 (x1,y2+1) 开始的所有区域撤销 +d）
diff[ x2+1 ][ y2+1 ] += d（右下角，多减的补回来）
二维差分求前缀和，得到原数组（原数组=前一项数组+变化率diff）：
a[ i ][ j ]=a[ i−1 ][ j ]+a[ i ][ j−1 ]−a[ i−1 ][ j−1 ]+diff[ i ][ j ]
构造差分数组（后一项减前一项）：
diff[ i ][ j ]=a[ i ][ j ]-a[ i−1 ][ j ]-a[ i ][ j−1 ]+a[ i−1 ][ j−1 ]
（对于差分的理解就是前一项减去后一项，但是在二维数组中，二维的“后一项”是从左上角到这个点（ i,j ）的，而“前一项”也是同理，对于二维，要减去这个点（ i,j ）的左侧（ i,j-1 ）和上侧（i-1,j），再补上多减的（ i-1,j-1 ））
题目
二维差分
#include <bits/stdc++.h>
using namespace std;
const int NN=1010;
int a[NN][NN];
int diff[NN][NN];
int n,m,q;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>q;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
diff[ i ][ j ]=a[ i ][ j ]-a[ i-1 ][ j ]-a[ i ][ j-1 ]+a[ i-1 ][ j-1 ];
}
}
//查询
while(q--) {
int x1,y1,x2,y2,d;
cin>>x1>>y1>>x2>>y2>>d;
diff[x1][y1]+=d;
diff[ x2+1 ][ y1 ] -= d;
diff[ x1 ] [y2+1 ] -= d;
diff[ x2+1 ][ y2+1 ] += d;
}
//求前缀和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = diff[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}棋盘
#include <bits/stdc++.h>
using namespace std;
const int NN=2010;
int a[NN][NN],diff[NN][NN];
int n,m;
int main()
{
cin>>n>>m;
while(m--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
//原数组是0，差分数组也是0，不用在构建差分数组了，直接操作
diff[x1][y1]+=1;
diff[x2+1][y1]-=1;
diff[x1][y2+1]-=1;
diff[x2+1][y2+1]+=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+diff[i][j];
//反转奇数次就是1，反转偶数次就是0
cout<<a[i][j]%2;
}
cout<<endl;
}
return 0;
}二分
左程云-二分搜索
BV1bX4y177uT
序列二分
"大于等于"和"等于的最左边"（即查找第一个满足条件的元素，即求最小，舍弃右边）可以使用同一个模板
"小于等于"和"等于的最右边"（即查找最后一个满足条件的元素，即求最大，舍弃左边）可以使用同一个模板
输出有序数组中等于 x 的最左边的数的下标
因为求的是最左边的x，所以把右边抛弃，a[mid] 在 x 右边，包含了mid这个位置（a[mid]>=x），右边不要（r=mid）（因为包含了mid这个位置，即a[mid]有等于x的可能，不能把mid这个位置舍去）
a[mid] 在 x 左边的可能，不包含mid这个位置（a[mid]<x），左边不要（l=mid+1）（因为不包括mid这个位置，a[mid]不等于x，
它一定不是要求的位置，把包含mid的左边部分舍去，由于舍弃的是左边，即要加1，在更右边的位置从算把mid一起舍弃）
while(l < r) {
int mid = l + r >> 1;
if(a[mid] >= x) r = mid;
else l = mid + 1;
}
if(a[l] == x) cout << l << endl;输出有序数组中等于 x 的最右边的数的下标（求最大，把左边抛弃）
思路和前面一样
只是把包含mid的右边部分舍去，由于舍弃的是右边，即要减1，在更左边的位置才算把mid一起舍弃
int mid=l+r+1>>1，记住和 mid-1 绑定
while(l < r) {
int mid = l + r + 1 >> 1;
if(a[mid] <= x) l = mid;
else r = mid - 1;
}
if(a[l] == x) cout << l << endl;查找第一个大于x的元素（不含等于）
对于a[mid]==x的情况
在大于等于x，和小于等于x的要求中，要把a[mid]保留
但在大于x或者小于x的要求中，要把a[mid]跳过
while(l < r) {
int mid = l + r >> 1;
if(a[mid] > x) { // 仅大于，不含等于
r = mid;
} else {
l = mid + 1; // 包括等于的情况都跳过
}
}查找最后一个小于x的元素（不含等于）
while(l < r) {
int mid = l + r + 1 >> 1;
if(a[mid] < x) { // 仅小于，不含等于
l = mid;
} else {
r = mid - 1; // 包括等于的情况都跳过
}
}upper_bound()和low_bound()函数
upper_bound()和lower_bound()，stl中的二分查找函数，返回的是一个指针/迭代器
upper_bound(first,last,value)：
在范围 [first,last) 内查找第一个大于value的元素位置（结果减1得到了最后一个小于等于value的位置，注意题目）lower_bound(first,last,value)：
在范围 [first,last) 内查找第一个不小于（大于等于）value的元素位置（用value+1来达成和upper_bound一样，找到大于value的元素）
对于引用：比如&a[3]，想要获得引用的值，只需要让引用减去第0项的引用，在这里就是&a[3]-&a[0]
对于数组，如int a[N]，a本身就是第0项的引用，所以也可以写成&a[3]-a，让得到的是元素在数组中的索引（从0开始）
题目
整数查找（模板题）
最大通过数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N],b[N];
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=1; i<=n; i++) {
cin>>a[i];
//原地做前缀和
a[i]=a[i-1]+a[i];
}
for(int i=1; i<=m; i++) {
cin>>b[i];
//原地做前缀和
b[i]=b[i-1]+b[i];
}
int ans=0;
//因为关卡或许连第一关都没过，所以索引从0开始
for(int i=0; i<=n; i++) {
//第一关水晶用完了，break
if(a[i]>k)break;
//第一关剩下的水晶
ll rest=k-a[i];
//upper_bound找到首个大于value的元素的迭代器，得到结果-1，获得最后一个小于等于value的迭代器，减去数组得到元素值
//b+m+1，+1确保搜索到最后一个元素，因为upper_bound和lower_bound都是[first,last)
int j=upper_bound(b,b+m+1,rest)-1-b;
ans=max(i+j,ans);
}
cout<<ans;
return 0;
}暴力
答案二分
左程云
BV1Mh4y1P7qE
阶乘后的0（额外）
阶乘尾数的0，是由1到n中，因子10的数量决定，每有一个10，新增一个0
而10=2*5
含有2的因子，每两个出现一次，含有5的因子，每五个出现一次
所以因子5的个数一定小于因子2的个数
所以求1到n中因子5的个数就是答案
含有5的因子，每五次出现一次（5，10，15……）
含有5的平方的因子，每25（5的平方）次，出现一次（25，50……）
含有5的三次方的因子，每125（5^3）次，出现一次（125……）
依此类推
int countTrailingZeros(int n) { int cnt = 0; while (n) { cnt += n/5; //除以5，方便进行迭代 n /= 5; } return cnt; }
题目
二分答案
解析
随着枚举的最小值变大，消耗的x越来越多，即x剩余的越来越少
对于枚举的 i，上限在本题中是10^6+10^13（操作数k+a的最大值），这里直接用1e14
进行二分，对中间的m进行左边的操作，如果不对，就不要了
然后就是普通二分的思路了
代码
暴力（过不了，了解一下思路）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN=1e5+10;
ll k;
int n;
int a[NN];
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
//用来枚举数组中最小值，即通过最多k次操作使得数组中的所有元素都至少为i
/*输入的a上限是1e6，操作次数k上限是1e13，当序列中只有一个数是1e6
k次操作后这个数最大的可能性是这个数最大可能性变成1e13+1e6*/
for(int i=1;i<=1e13+1e6;i++){
/*用ll cnt=0 //cnt表示操作数*/
//把操作数赋值给x
ll x=k;
//用来枚举序列中每一个数
for(int j=1;j<=n;j++){
//如果这个数小于最小值，更新操作数
if(a[j]<i){
k=k-(i-a[j]);
/*cnt+=i-a[j] //把每次需要的操作数加上，也可以这样想，不过对于答案二分的「给定条件」和「问题答案」之间的关系不明确*/;
}
//至少要把数组中每一个变成i，操作次数不够，就不能把每一个数变成i了
//i-1 是最后一个满足条件的 i（因为 i-1 时 k 还没耗尽）
/*if(cnt>k)*/
if(x<0){
cout<<i-1;
return;
}
}
}
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}答案二分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN=1e5+10;
ll k;
int n;
int a[NN];
bool check(ll m){
ll x=k;
for(int j=1;j<=n;j++){
if(a[j]<m){
//得到剩余操作数
x=x-(m-a[j]);
}
if(x<0){
return false;
}
}
return true;
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
//r表示上限，应该是a的最大值+k的最大值，1e6+1e13，这里用1e14方便写
ll l=1,r=1e14;
while(l<r){
ll mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}代码解析
贪心思想：
对于每个元素，严格按需分配操作次数：只提升不足m的部分。
不浪费操作次数在已经≥m的元素上
(m - a[ j ]) 的含义：
如果当前元素 a[ j ] 小于 m，则需要将它从 a[ j ] 提升到 m。需要操作的次数 = 两者的差值 = m - a[ j ]
（例如：a[ j ]=2，m=5 → 需要 5-2=3 次操作）
if(check(mid)) l=mid：
这里true的情况是所有元素>=mid的情况，所以包含了mid
求阶乘
代码（90%）
#include <bits/stdc++.h>
using namespace std;
#define int long long
int countZero(int n) {
int cnt = 0;
while (n){
cnt += n / 5;
n /= 5;
}
return cnt;
}
int K;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> K;
int l = 0, r = 1e18;
while (l < r) {
int mid = l + r >> 1;
if (countZero(mid) >= K) r = mid;
else l = mid + 1;
}
if (countZero(l) == K) cout << l;
else cout << -1;
return 0;
}数列分段
题目解析
数组4 2 4 5 1，要求分成三段
我们假设，每一段的最大值是1
放入第一个数组4，就直接爆了，不行
依次类推，枚举的最大值，从1开始到3，都会爆
直接看5
数组4 2 4 5 1，放了三个数字，5放不进，所以枚举的最大值5不行
枚举每一段的最大值是6
首先放入4，发现可以放后面的数字2，就继续放，第一段放了4和2
之后数组都能放进去
所以6是最先符合的
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN=1e5+10;
int a[NN];
int N,M;
bool check(ll mid){
//每一段内的和，用来判断分段
ll sum=0;
//段数，一开始默认段数就是1了
int cnt=1;
for(int i=1;i<=N;i++){
//这个数大于要求的最大值，怎么也放不进，直接false
if(a[i]>mid)return false;
if(sum+a[i]<=mid){
sum+=a[i];
}else{
//当这一段爆了之后，增加一段，里面的容量重新开始算
cnt++;
sum=a[i];
}
}
return cnt<=M;
}
void solve(){
cin>>N>>M;
for(int i=1;i<=N;i++){
cin>>a[i];
}
ll l=1,r=(ll)(1e13);
while(l<r){
ll mid=r+l>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--)solve();
return 0;
}代码解析
当枚举的最小值的二分后，mid所代表的cnt>m了，所以mid不行，二分逻辑上的mid的左边舍去
当枚举的最小值的二分后，mid所代表的cnt<m了，这里代表因为枚举出来的要求的最小值偏大了，所以实际的段数更少
如：一共五个数：4 2 2 5 1，要求分成三段
枚举的8作为最小值偏大了，所以用两段就足够了，但实际上，把枚举的最大值缩小，前两段中也有数字能放进第三段
所以check检查的逻辑是：段数cnt<=m
因为比要求的段数m更少的段数cnt也可以，只是没有达到二分上mid最好的值
浮点数二分
up说不大可能会考，所以没看
高精度加法
栈
指针一开始指向栈的第一格的下面
题目
模拟栈
#include <bits/stdc++.h>
using namespace std;
const int NN = 1e5 + 10;
int stk[NN];
int top = -1;
void push(int x) {
stk[++top]=x;
}
void pop() {
top--;
}
bool empty() {
return top==-1;
}
int query() {
return stk[top];
}
void solve() {
int m;
cin >> m;
while (m--) {
string op;
cin>>op;
if (op=="push") {
int x;
cin>>x;
push(x);
} else if (op=="empty") {
if(empty())cout<<"YES\n";
else cout<<"NO\n";
} else if (op == "pop") {
if (!empty()) pop();
} else{
if (empty()) cout<<"empty\n";
else cout<<query()<<"\n";
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
while (t--) solve();
return 0;
}递归
对于递归，只需模拟最后两层，剩下所有的递归和最后两层是一样的
回溯
dfs一种是正常的回溯法，一种是在图上进行的dfs操作
子集枚举（递归实现指数型枚举，O(n)=2^n）
对于每个东西，是选和不选，删和不删，留和不留
一旦涉及到两个状态，就是子集枚举
对角线（额外）
主对角线（正对角线）：n - j + i（主对角线是从方阵的左上角延伸到右下角的一条线，该线上每个元素的行索引和列索引相等，即i=j）
方向：从 左上到右下（↘️）数学性质：同一主对角线上的所有点满足 行号 - 列号 = 常数（即 i - j = C）
例如：点 (3,1) 和 (4,2) 在同一条主对角线上，因为 3-1 = 4-2 = 2
索引处理：
原始公式 i - j 可能为负数（如 i=1, j=2 → 1-2=-1）
通过变形 n - j + i 确保索引为正数
辅对角线（反对角线）：i + j（在二维数组中，对于一个n*n的方阵，若以 0 开始计数，辅对角线元素的行索引 i 和列索引 j 满足i + j = n - 1）
方向：从 右上到左下（↙️）
数学性质：同一副对角线上的所有点满足 行号 + 列号 = 常数（即 i + j = C）
例如：棋盘上的点 (2,3) 和 (1,4) 在同一条副对角线上，因为 2+3 = 1+4 = 5
对角线的数量是2*N-1（对角线是所有斜着的线，不光是中间的那根）
题目
递归实现排列型枚举
#include <iostream>
using namespace std;
const int NN=10;
int path[NN];
bool vis[NN];
int n;
void dfs(int u){
//出递归
if(u>n){
for(int i=1;i<=n;i++){
cout<<path[i]<<" ";
}
cout<<"\n";
return;
}
//
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
//path用来记录已经确定的排列顺序
path[u]=i;
//下一层
dfs(u+1);
//回溯
vis[i]=0;
}
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}N皇后
N*N的方格放置N个皇后
即要求每一行都放置一个皇后
#include <bits/stdc++.h>
using namespace std;
const int NN=20;
//fan反对角线，zhu主对角线
bool col[NN],zhu[NN],fu[NN];
int N;
int cnt=0;
//i表示当前正在处理的行号，看每一行是否有位置
void dfs(int i) {
//可以填棋子，如果能填完最后一行，就是一个可行解
//代表当前行号的u大于要求的行数n，因为i==n时，最后一行还没有开始填
if(i>N) {
cnt++;
return;
}
for(int j=1; j<=N; j++) {
if(!col[j]&&!zhu[N-j+i]&&!fu[i+j]) {
//dfs()中的数是按行枚举，如果这个位置有了，它所在的列、主对角线、反对角线不能有棋子
//在这个位置有棋子时，可以标记所在的列、主对角线、反对角线为访问过，下次不能访问
col[j]=1;
zhu[N-j+i]=1;
fu[i+j]=1;
//访问下一个
dfs(i+1);
//回溯
col[j]=0;
zhu[N-j+i]=0;
fu[i+j]=0;
}
}
}
void solve() {
cin>>N;
dfs(1);
cout<<cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--)solve();
return 0;
}递归实现指数型枚举（n<=25都可以用）
题目解析
x代表不选，数字代表选了，？代表正在选
代码
二进制枚举（O(n)=n*2^n）
基本位运算：
左移<<：二进制位中，在右边补0
这里1<<3，在二进制中补三个0，就是1000，就是8
对于一个十进制数：
<<1，就是*2
>>1，就是/2
&1，就是保留二进制位最后一位的值
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n; // 输入集合的大小 n
// 遍历所有可能的子集（2^n 种）
for (int i = 0; i < (1 << n); i++) {
// 检查每个元素是否被选中
for (int j = 0; j < n; j++) {
if ((i >> j & 1) == 1) { // 如果 i 的第 j 位为 1
// 这里可以处理选中的元素
// 例如：输出选中的元素
cout << j << " ";
}
}
cout << "\n"; // 换行，表示一个子集结束
}
return 0;
}行==0或列==0或对角线==0，五子棋也没有获胜（额外）
当 row 或者 col 的值等于 0 时，这表明当前行或者当前列上没有放置任何一方的棋子，或者全部放置的是另一方的棋子
在代码逻辑里，同样把这种情况视为一方获胜（因为另一方没有在这一行或列落子），所以也判定当前棋盘状态不是平局对于主对角线和辅对角线也同理
dfs
全排列
这个视频让我学到了：
- dfs(int u)，这个u表示题目要求数字范围的第u个数字，也代表dfs下的第u层循环
- st[i]表示数字i是否被使用过
- path[i]表示第i个循环下，第i位置的数字是多少（这个位置的数字，是从1开始循环的）
- dfs就是把一个n层循环改成递归
这个视频演示了暴力的for循环写法，然后用st数组来标记数字是否使用，最后演示dfs，层层递进，讲解的很好
dfs和bfs题目
acwing，课程中的kuangbin
bfs
这个视频让我学到了：
bfs遍历和队列一样，先进先出
将下一个点加入队列，dist[nx][ny] = dist[x][y] + 1;。因为当前点(x,y)和下一个点(nx,ny）距离是1（这个距离，在别的题目中可以理解成操作数）
经典的网格图上的最短路径问题
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int n;
static char[][] map;
// 往下是x轴，往右是y轴
// 方向数组：上、下、左、右
// 有些题目偏移量dx，dy不同，因为是从其他方向开始的：
// BFS 不关心你先走哪个方向，只要四个方向都走到就行。最终结果（最短路径长度）是一样的
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 1. 读取地图大小 n
n = scanner.nextInt();
// 2. 读取地图
// 地图用 char[][] 存储，0 表示路，1 表示店铺
map = new char[n][n];
for (int i = 0; i < n; i++) {
String line = scanner.next();
map[i] = line.toCharArray();
}
// 3. 读取起点和终点坐标
// 题目输入是 1-based，需要转换为 0-based（Java严格遵循数组原生 0-based，C/C++能用 1~n 的下标）
int x1 = scanner.nextInt() - 1;
int y1 = scanner.nextInt() - 1;
int x2 = scanner.nextInt() - 1;
int y2 = scanner.nextInt() - 1;
// 4. 执行 BFS 并输出结果
System.out.println(bfs(x1, y1, x2, y2));
}
/**
* 广度优先搜索寻找最短路径
*
* @param n 地图大小
* @param map 地图数据
* @param startX 起点 x
* @param startY 起点 y
* @param endX 终点 x
* @param endY 终点 y
* @return 最短距离，如果不可达返回 -1
*/
private static int bfs(int startX, int startY, int endX, int endY) {
// 如果起点就是终点
if (startX == endX && startY == endY) {
return 0;
}
// dist 数组记录步数，同时起到 visited 标记的作用
// 初始化为 -1 表示未访问
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = -1;
}
}
// 队列存储坐标，使用 int[] {x, y}
Queue<int[]> queue = new LinkedList<>();
// 起点入队
queue.offer(new int[] { startX, startY });
dist[startX][startY] = 0;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 边界检查
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
// 检查是否是马路 ('0') 且 未访问过 (dist == -1)
if (map[nx][ny] == '0' && dist[nx][ny] == -1) {
// (x,y）是当前的点，(nx,ny)是下一个点，将下一个点加入队列中
dist[nx][ny] = dist[x][y] + 1;
// 入队时检查，如果到达终点，直接返回距离
if (nx == endX && ny == endY) {
return dist[nx][ny];
}
queue.offer(new int[] { nx, ny });
}
}
}
}
// 如果循环结束还没找到，返回 -1
return -1;
}
}这个视频让我学到了：
这种问题也是一层层拓展的，但不是按照网格来十字形拓展，而是按照一种规则，所以也可以用bfs
数值本身，代表一个具体的数值，不需要 -1
最小操作数问题
数组/图的下标，代表“第几个元素”，需要 -1
坐标系
二维网格坐标系
和数学的笛卡尔坐标系不同，X向下，Y向右
在三维坐标系中，通常采用 右手坐标系（X向右，Y向前，Z向上）
// 右、左、前、后、上、下
int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1}; 棋盘问题（dfs）
地牢大师（三维迷宫bfs）
抓住那头牛（一维位置移动bfs）
找倍数（状态唯一，没有访问数组，结果唯一，没有答案数组bfs）
质数路径（位权）
代码解析（新整数=原整数+对应位权*对应数位变化量）
(i - a[j]) 计算的是将整数 p 的第 j 位从 a[j] 修改为 i 时，该位数字的变化量
例如，如果 a[j] = 3，i = 5，那么 (i - a[j]) = 5 - 3 = 2，表示该位数字需要增加 2
d[j] * (i - a[j]) 则是将该位数字的变化量乘以对应的位权，得到由于这一位数字变化对整个整数的影响值。例如，对于百位（d[1] = 100），如果数字变化量是 2，那么 d[1] * (i - a[1]) = 100 * 2 = 200，表示百位数字变化 2 会使整个整数变化 200
p + d[j] * (i - a[j]) 就是在原整数 p 的基础上，加上由于第 j 位数字变化对整个整数的影响值，从而得到修改后的新整数 nx
罐子（把操作看成二维坐标）
把两个罐子倒水的操作看成二维坐标
题目
#include <bits/stdc++.h>
using namespace std;
struct Point {
// 当前两个容器的水量
int x, y;
// 操作步骤记录
//定义成string类型，将多个操作编号按顺序拼接起来
string steps;
};
const int NN = 110;
string op[6] = {
"FILL(1)", "FILL(2)", "DROP(1)",
"DROP(2)", "POUR(1,2)", "POUR(2,1)"
};
int ans[NN][NN]; // 记录到达每个状态的最少步数
bool vis[NN][NN]; // 标记状态是否被访问过
queue<Point> que;
int a, b, c; // 容器容量和目标水量
int bfs() {
while (!que.empty()) {
auto p = que.front();que.pop();
// 检查是否达到目标
if (p.x == c || p.y == c) {
cout << ans[p.x][p.y] << endl;
//在结构体中，每一个操作都拼接成了一个字符串，用增强for获得每一个操作，变成数字
for (char i : p.steps) {
cout << op[i - '0'] << endl;
}
return 0;
}
// 计算6种操作的水量变化
//pour1 表示从罐子 x（容量为 a）向罐子 y（容量为 b）倒水时，能够倒过去的水量
//取 p.x（罐子 x 当前的水量）和 b - p.y（罐子 y 还能容纳的水量）中的较小值
int pour1 = min(p.x, b - p.y); // POUR(1,2)
int pour2 = min(a - p.x, p.y); // POUR(2,1)
//两个罐子的变化量，六个操作对应六个值
int dx[] = {a - p.x, 0, -p.x, 0, -pour1, pour2};
int dy[] = {0, b - p.y, 0, -p.y, pour1, -pour2};
for (int i = 0; i < 6; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
// 检查新状态是否合法且未访问
if (nx >= 0 && nx <= a && ny >= 0 && ny <= b &&!vis[nx][ny]) {
vis[nx][ny] = 1;
ans[nx][ny] = ans[p.x][p.y] + 1;
//结构体中定义了操作步骤是string，用+可以拼接
que.push({nx, ny, p.steps + to_string(i)});
}
}
}
return -1;
}
int main() {
cin >> a >> b >> c;
memset(ans, 0, sizeof ans);
memset(vis, 0, sizeof vis);
//放入起点，一开始两个罐子都是空的，且没有操作
que.push({0, 0, ""});
vis[0][0] = 1;
int res=bfs();
if(res==-1)cout<<"impossible"<<endl;
return 0;
}全球变暖（两个bfs）
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int NN = 1010;
char g[NN][NN];
bool vis[NN][NN];
struct Point {
int x, y;
};
queue<Point> que; // 全局队列
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int N, sum=0, notYanMo=0;
// 判断岛屿是否会被完全淹没
bool willBeFlooded(int x, int y) {
queue<Point> empty;swap(que, empty);// 清空队列
que.push({x, y});
vis[x][y] = 1;
bool isFlooded = true; // 初始假设会被淹没
while (!que.empty()) {
auto p = que.front();que.pop();
//必须在 while 循环内部，确保每次处理新的陆地节点时，都能正确判断其是否有邻接海洋
bool hasAdjacentSea = false; // 当前陆地是否有邻接海洋
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
if (g[nx][ny] == '.') {
hasAdjacentSea = true; // 当前陆地有邻接海洋
} else if (g[nx][ny] == '#' &&!vis[nx][ny]) {
que.push({nx, ny});
vis[nx][ny] = 1;
}
}
}
// 如果当前陆地没有邻接海洋，整个岛屿不会被完全淹没
if (!hasAdjacentSea) {
isFlooded = false;
}
}
return isFlooded;
}
void bfs() {
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (g[i][j] == '#' &&!vis[i][j]) {
//因为willBeFlooded函数对每个陆地都bfs了
//所以bfs函数中的!vis[i][j] 保证了这个位置没有被其他 BFS 过程访问过
//所以当进入这个分支时，意味着发现了一个新的、独立的岛屿
sum++;//连通岛总数
if (!willBeFlooded(i, j)) {
notYanMo++;
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> g[i][j];
}
}
bfs();
cout << sum - notYanMo << endl;
return 0;
}代码解析（isFlooded和hasAdjacentSea的bool值）
组合数
不选第n个数，在n-1个数中选m个数，就是n个数中选m个数的部分方案数
选第n个数，在n-1个数中，选择m-1个数，把这第n个数一加，就是n个数中选m个数的部分方案数
题目
递归求组合数
#include <iostream>
using namespace std;
int n,m,t;
int f(int m,int n){
if(n==m||m==0)return 1;
return f(m-1,n-1)+f(m,n-1);
}
void solve(){
cin>>n>>m;
int ans=0;
ans=f(m,n);
cout<<ans<<"\n";
}
int main()
{
cin>>t;
while(t--)solve();
return 0;
}记忆化搜索
数组的维度通常与问题的状态空间一致：
与dfs函数的参数一致
实现搜索函数：
检查当前状态是否已经被计算过
这一步要在递归边界下面写
一般写dfs函数，返回值是void，使用记忆化搜索，dfs的返回值写成int
#include <bits/stdc++.h>
using namespace std;
//1.定义记忆化数组
//记忆化数组的维度和问题的状态空间一致
//因为问题是求斐波那契数列，只有一个参数，所以一维
int dp[50];
int f(int n){
//递归边界
if(n==1||n==2)return 1;
//3.实现搜索函数，检查当前状状态是否被计算过
//这一步放在递归边界下
if(dp[n]!=-1)return dp[n];
//3.实现搜索函数，保存记忆化数组
//本来return f(n-1)+f(n-2);
//增加一个dp[n]=
return dp[n]=f(n-1)+f(n-2);
}
int main(){
//2.初始化记忆化数组
memset(dp,-1,sizeof(dp));
cout<<f(19);
return 0;
}题目
01背包
01 背包，即一种 DP 问题，以放置物品为模型，每个物品只能放一次
题目解题
递归分治
分而治之：将问题分解为若干子问题，递归解决子问题，最后合并结果无记忆化：子问题可能被重复计算，导致效率低下
特点
自顶向下：从原问题出发，逐步分解为子问题可能重复计算：同一子问题会被多次求解（这个背包问题）
代码直观：直接反映问题逻辑，但时间复杂度高
dfs(1,0)往右，表示对第一个物品选，到dfs(2,1)表示第一个物品选了，虽然参数是2，但第二个物品还没有选
这个dfs不是当前的状态，而是当前选完之后会进入到的状态
（代码中，我的变成习惯是从1开始到i<=N，所以第一个物品在索引为1的位置，别的代码可能在索引为0的位置）
代表选的ans2的ans2=dfs(u+1,sum+v[u])+w[u]是递归（题中是价值）返回值的累加
如：dfs(4,5)，因为选了第三个物品，第三个物品的价值是四，把4带回去
代码
不用记忆化搜索（时间复杂度2^n，超时）
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int w[N],v[N];
int n,m;
int dfs(int u,int sum) {
//u代表当前选择的是第几个物品
//sum表示当前的总体积，用当前体积隔离不同递归层的状态，没有（用数组的）显式回溯的使用
//递归函数返回值代表最大价值
if(u>n) {
return 0;
}
//ans1不选，ans2选
int ans1=0,ans2=0;
//ans1不选，直接跳过第u个物品，
ans1=dfs(u+1,sum);
//ans2选第u个物品，并增加价值 w[u]
//这里的ans2=dfs(u+1,sum+v[u])+w[u]是递归返回值的累加
if(sum+v[u]<=m) ans2=dfs(u+1,sum+v[u])+w[u];
return max(ans1,ans2);
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>v[i]>>w[i];
cout<<dfs(1,0);
}使用记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int w[N],v[N];
//1.定义记忆化数组，参数和递归函数参数一样
int dp[N][N];
int n,m;
int dfs(int u,int sum) {
//u代表当前选择的是第几个物品
//sum表示当前的总体积
//递归函数返回值代表最大价值
if(u>n) {
return 0;
}
//3.搜索的时候记忆
// - 在递归边界下判断当前状态是否访问过，访问过，直接返回
if(dp[u][sum]!=-1) return dp[u][sum];
//ans1是不选，ans2是选
int ans1=0,ans2=dfs(u+1,sum);
if(sum+v[u]<=m) ans1=dfs(u+1,sum+v[u])+w[u];
// - 没访问过，正常搜索，记忆下来
return dp[u][sum]=max(ans1,ans2);
}
int main() {
//2.初始化记忆化数组为 -1
memset(dp,-1,sizeof(dp));
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>v[i]>>w[i];
cout<<dfs(1,0);
}使用动态规划
01背包问题，也是选与不选的问题，可以通过子集枚举枚举出来，但是子集枚举时间复杂度为2^n，很高
如果不选，就从上面转移过来，如果选
看选这个物品和不选这个物品那个是最优的
dp[ i ][ j ]=max(dp[ i-1 ][ j-v[ i ]]+w[ i ],dp[ i-1 ][ j ]);
如图：对于dp[ 2 ][ 2 ]，选是从dp[ 1 ][ 0 ]过来，不选是从dp[ 1 ][ 2 ]过来
所以代码中选要 j-v[ i ]
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N][N];
int n,m;
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
//第一维枚举每件物品
for(int i=1;i<=n;i++){
//第二维枚举体积
for(int j=0;j<=m;j++){
if(j<v[i]){
//如果容积不够，不能选
dp[i][j]=dp[i-1][j];
}else{
//容积够，能选这个物品
//看选这个物品和不选这个物品那个是最优的
dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
}
/*优化
//默认不选
dp[i][j]dp[i-1][j];
if(j>=v[i]){
//当容积允许选第i件物品时，才选
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
}
*/
}
}
cout<<dp[n][m];
return 0;
}数组分割（没看）
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N];
int dp[N][2];//统计奇偶性
int n;
const int mod=1000000007;
int dfs(int u,int sum) { //前u个数中选出奇偶性为1/0
if(u>n) {
//如果奇偶性总和sum是0，是偶数，return 1；是奇数，return 0
return sum==0;
}
if(dp[u][sum]!=-1) return dp[u][sum];
//对数字有选和不选，进行判断
int ans=0;
if(a[u]%2==1) {
//当前这个数是奇数
//dfs(u+1,sum^1)，选这个数
//如果当前的数是奇数，奇数+奇数就是偶数，奇偶性sum变成0
//dfs(u+1,sum)，不选这个数
ans=ans+dfs(u+1,sum^1)+dfs(u+1,sum);
} else {
//当前这个数是偶数
//dfs(u+1,sum)，奇数选偶数奇偶性不变
//dfs(u+1,sum)，不选这个数，奇偶性也不便
ans=ans+dfs(u+1,sum)+dfs(u+1,sum);
}//可以合二为一，直接写成dfs(u+1,sum^(a[u]%2))+dfs(u+1,sum);
return dp[u][sum]=ans%mod;
}
void solve() {
int sum=0;
cin>>n;
for(int i=1; i<=n; i++)
//只关注奇偶性，范围缩小
for(int i=1; i<=n; i++) {
//多组测试数据，手动初始化dp
dp[i][0]=dp[i][1]=-1;
int x;
cin>>x;
x%=2;
a[i]=x;
sum+=a[i];
}
//总和为奇数，只能拆成一组偶数，用一组奇数，不能拆成两组都为偶数
if(sum%2==1) {
cout<<"0\n";
return;
}
cout<<dfs(1,0);
}
int main() {
int t;
cin>>t;
while(t--) solve();
return 0;
}动态规划
动态规划，O(n)=n^3，对于n<=100的情况下使用的算法
动态规划的特点：
有后效性，当前的决策会影响到后面的决策。具有最优子结构的特征
解这类题的步骤：
1.定义数组（数学归纳法中的定义函数）：如dp[i]（dp代表方案）表示的是什么，时刻记住定义的数组的含义2.初始化dp：初始化dp，初始化的方法有两种：根据数组定义来写或根据实际意思。
3.遍历所有的情况：用子结构递推到最终的结果
4.写状态转移方程：dp[i]由前一个怎样转移过来的
题目
李白打酒加强版（三维dp）
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int NN=110;
//1.定义数组
//含义：dp是前i个店遇到j朵花，剩k斗酒的方案
int dp[NN][NN][NN];//三维dp数组
int n,m;
int main()
{
cin>>n>>m;
//2.初始化
//这里根据数组定义写
//题目：一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗，所以遇0店0花有2酒方案数是1
dp[0][0][2]=1;
//3.遍历所有的情况
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m-1;j++)
{
if(i==0&&j==0) continue;
for(int k=0;k<=100;k++)//因为最多出现100次操作2，故va最大为100
{
//4.写状态转移方程：dp[i]由什么转移过来
//i代表店，逢店加一倍。所以对于i-1时，是从k/2的状态转移到k的
//因为i-1，所以i>=1。因为k/2，所以k要是偶数
if(k%2==0&&i>=1) dp[i][j][k]=(dp[i][j][k]%mod+dp[i-1][j][k/2]%mod)%mod;
//j代表花，遇花喝一斗。所以对于j-1，是从k+1的状态转移到k的
if(j>=1) dp[i][j][k]=(dp[i][j][k]%mod+dp[i][j-1][k+1]%mod)%mod;
}
}
}
//最后的结果，题目：最后一次遇到的是花，他正好把酒喝光了
//即对于花m-1的情况，还有1酒
cout<<dp[n][m-1][1]%mod;
}跳石头（使用bitset的dp）
#include <bits/stdc++.h>
using namespace std;
const int NN=4e4+10;
/*
这个数组的大小是 MAXN，即数组有 MAXN 个元素
而数组中的每个元素的类型是 bitset<MAXN> 。即，数组的每个元素本身都是一个 bitset 对象
每个这样的 bitset 对象可以存储 MAXN 个二进制位
*/
bitset<NN> dp[NN];
int c[NN];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>c[i];
int ans=0;
//动态规划的依赖关系：dp [j] 依赖于 dp [j + c [j]] 和 dp [2*j]，即 后面的状态会影响前面的状态
//如果从 j = 1 开始，dp[j + c[j]] 和 dp[j * 2] 可能还未计算，导致错误
for(int j=n;j>=1;j--){
/*
bitset 的本质是 二进制位数组，每一位只能是 0 或 1
f因此，dp[j][c[j]] = 1 就是在 dp[j] 的二进制位中，把第c[j]位设为1，表示这个数字可以被访问
*/
dp[j][c[j]]=1;
/*
dp[j + c[j]] 存储了从位置 j + c[j] 出发能到达的状态集合，dp[2*j] 存储了从位置 2*j 出发能到达的状态集合
通过按位或操作，将这些状态集合合并到 dp[j] 中
即从位置 j 出发不仅能到达自身直接能到达的状态，还能到达通过 j + c[j] 或 2*j 这些位置能到达的状态
*/
if(j+c[j]<=n)dp[j]|=dp[j+c[j]];
if(2*j<=n)dp[j]|=dp[2*j];
/*
利用 bitset 的 count() 函数统计 dp[j] 中值为 1 的位的数量
即从位置 i 出发能到达的不同状态的数量
通过不断更新 ans 取最大值，最终得到小明最多能获得的分数
*/
ans=max(ans,(int)dp[j].count());
}
cout<<ans;
return 0;
}dijkstra（最短路）
图-最短路径-Dijkstra(迪杰斯特拉)算法_哔哩哔哩_bilibili
dijkstra算法求单元最短路问题，即图中某一确定的点到另一点的最短路
使用堆（优先队列）时，堆能够自动依据距离对所有点进行排序。在每一轮迭代时，直接从堆顶取出当前距离源点最近的点
邻接表存储图（额外）
//用邻接表存图
int h[NN],e[NN],ne[NN],w[NN],idx;
void add(int a,int b,int c){
w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}dijkstra模板
#include <bits/stdc++.h>
using namespace std;
//注意：对于无向图，边的存储量是实际的2倍，看情况提高最大值
const int NN= ;
int n,m;
typedef pair<int,int> PII; //first存距离，second存结点编号
//dist储从起点（源点）到各个结点的当前最短距离
//st标记某个结点的最短距离是否已经确定
int dist[NN],st[NN];
//用邻接表存图
int h[NN],e[NN],ne[NN],w[NN],idx;
void add(int a,int b,int c) {
w[idx]=c;
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dijkstra() {
memset(dist,0x3f,sizeof(dist)); // 将所有距离初始化正无穷
priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
dist[1] = 0; // 第一个点到起点的距离为 0
//把 1 号点放入堆中，0代表到1号点的最短路径，1是坐标
heap.push({0,1});
while(!heap.empty()) { // 堆不空
//找到当前距离最小的点
auto p = heap.top();
heap.pop();
//second就是点的编号，如果这个点的最短路确定了，就不用更新其他点了
if(st[p.second]) continue;
st[p.first] = true;//标记p已经确定最短路
// 遍历节点 p.second 的所有邻边（p.second 是当前距离起点最近的节点）
for(int i = h[p.second]; i != -1; i = ne[i]) {
// e[i] 是当前边的终点（即 p.second 的邻居节点）
int j = e[i];
// 如果从起点到 j 的当前最短距离 > 从起点到 p.second 的最短距离 + 当前边的权重
if(dist[j] > dist[p.second] + w[i]) {
// 更新到 j 的最短距离
dist[j] = dist[p.second] + w[i];
// 将 {新距离, 节点j} 加入堆
heap.push({dist[j], j});
}
}
}
// 说明 1 和 n 是不连通的，不存在最短路
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
//h 数组存储的是每个顶点的第一条边在 e 数组中的索引
//若 h[i] 为 -1，则表示顶点 i 没有出边
memset(h,-1,sizeof(h));
cin >> n >> m;
while(m--) {
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
//add(b,a,c); //如果题目要求双向，再来add
}
cout << dijkstra();
return 0;
}题目
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//注意：对于无向图，边的存储量是实际的2倍
const int NN=2e5+10;
int n,m;
int a[NN];
typedef pair<int,int> PII; //first存距离，second存结点编号
int dist[NN],st[NN];
//用邻接表存图
int h[NN],e[NN],ne[NN],w[NN],idx;
void add(int a,int b,int c){
w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int dijkstra(){
memset(dist,0x3f,sizeof(dist)); // 将所有距离初始化正无穷
priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
//把 1 号点放入堆中，0代表到1号点的最短路径，1是坐标
heap.push({0,1});
dist[1] = 0; // 第一个点到起点的距离为 0
while(!heap.empty()) // 堆不空
{
//找到当前距离最小的点
auto p = heap.top();heap.pop();
//second就是点的编号，如果这个点的最短路确定了，就不用更新其他点了
if(st[p.second]) continue;
st[p.second] = true;//标记p已经确定最短路
//i赋值成头节点，一直遍历到下一条边
for(int i = h[p.second]; i!=-1; i=ne[i]){
//取出这个节点孩子的编号
int j = e[i];
//题目中：dist[j]是未确定的最短路的点，w[i]是路程的时间，a[j]是隔离的时间
if(dist[j] > dist[p.second] + w[i]+a[j]){
dist[j] = dist[p.second] + w[i]+a[j];
heap.push({dist[j],j}); //入堆
}
}
}
// 说明 1 和 n 是不连通的，不存在最短路
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//h 数组存储的是每个顶点的第一条边在 e 数组中的索引
//若 h[i] 为 -1，则表示顶点 i 没有出边
memset(h,-1,sizeof(h));
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
while(m--){
int x,y,z;cin>>x>>y>>z;
//x,y是两个顶点，z是权重，题目要求路线双向，所以两个add构建无向图
add(x,y,z);
add(y,x,z);
}
//到第n个城市不需要隔离，要把n减掉
int res=dijkstra();
if(res!=-1)cout<<res-a[n];
return 0;
}数学
求最大公因数（最大公约数）
【基础算法与基础数学】：最大公约数与最小公倍数1_哔哩哔哩_bilibili
欧基里得算法（辗转相除法）
//求最大公因数
static int gcd(int a,int b) {
if(b==0)return a;
return gcd(b,a%b);
}求最小公倍数
两个数相乘，然后除以它们的最大公因数
//求最小公倍数
static int LCM(int a,int b){
return ((a*b)/GCD(a,b));
}分解质因数
给定正整数，打印出所有的因数都是质数
对正整数n进行分解质因数，先找到一个最小的质数
1.该正整数n为质数，则说明不需要分解
2.如果该正整数n不是质数，但是能被最小的质数整除，就打印最小的质数，然后从正整数n除以最小质数，作为新的正整数重复执行1和2
从小到大遍历 i
循环从 i=2 开始，逐步增加 i
由于 i 从小到大遍历，第一个满足 x % i == 0 的 i 一定是 x 的最小质因数：
如果 i 是合数，它一定已经被更小的质因数分解过：
例如 i=4：
如果 x % 4 == 0，说明 x 是 4 的倍数。
但 4 本身可以分解为 2*2，所以 x 一定已经被 i=2 分解过。
因此，x 不可能再被 4 整除（因为 2 已经分解完了）
结论：i 只会是质数，因为合数因数已经被更小的质因数分解
if(n>1)：
处理可能剩余的大于sqrt(n)的质因数
假设输入 n = 15
首先，i = 2，15 % 2 != 0，不执行内层循环。
接着，i = 3，15 % 3 == 0，进入内层循环，n 变为 5
此时，i = 4，4 * 4 > 5，外层循环结束
此时 n = 5 > 1，需要处理
//分解质因数核心步骤
//用 i*i <= n 动态判断，整数运算更快，用i<=sqrt(n)慢
for(int i=2;i*i<=n;i++){
//确认当前的 i 是否为 n 的因数。只有当 n 能被 i 整除时，i 才有可能是 n 的质因数
if(n%i==0){
//内层的 while 循环来进一步分解 n 中包含的所有 i 因子
while(n%i==0){
n/=i;
}
}
}
// 处理可能剩余的大于 sqrt(n) 的质因数
if(n>1){
//...
}唯一分解定理（额外）
完全平方数
题目解析
由唯一分解定理：任何一个数，都可以分解成若干个质数的乘积
如果这个数是完全平方数，那么这若干个质数的指数一定是偶数
对于本题，需要记录指数不是偶数的数字
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;cin>>n;
map<int,int>mp;
//分解质因数
for(int i=2;i*i<=n;i++){
while(n%i==0){
n/=i;
//这里i就是分解出来的质因子
//把 n 中包含的 i 因子去除，然后将 mp[i] 的值加 1，以此记录 i 作为质因数出现的次数
mp[i]++;
}
}
if(n>1)mp[n]++;
int ans=1;
for(auto i:mp){
//如果分解出的质因子只出现了一次
if(i.second%2==1)ans*=i.first;
}
cout<<ans;
return 0;
}判断素数（平方根试除法）
质数，又称素数，除了1和该数自身外，无法被其他自然数整除的数
1既不是质数（素数）也不是合数
平方根法判断素数：
对于一个数字 n，根号n*根号n=n
因数是关于根号 n 对称分布的
所以只需要遍历到根号 n，如果在根号n内没有因数，那么之后也没有了
bool isPrime(int num) {
//有的题目，传入的num就直接从2开始，这个if(num<2)可以不写
if (num < 2) return false;
//不要写sqrt，比i*i慢
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}问题：
P12157 [蓝桥杯 2025 省 Java B] 魔法科考试 - 洛谷
试除法：逐个尝试除数（适合单次判断）
筛法：批量筛选（适合多次判断，比如两层for循环）
判断素数（埃氏筛）
/**
* 埃拉托斯特尼筛法，用于找出 0 到 max 之间的所有素数。
* @param max 筛法的上限
* @return 一个布尔数组，isPrime[i] 表示 i 是否为素数
*/
private static boolean[] sieve(int max) {
boolean[] isPrime = new boolean[max + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
// 只需遍历到 sqrt(max)
for (int i = 2; i * i <= max; i++) {
if (isPrime[i]) {
// 如果 i 是素数，那么它的倍数都不是素数
// 从 i*i 开始标记，因为更小的倍数已经被标记过了
for (int j = i * i; j <= max; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}模运算性质（额外）
对于减法的取模，在成为负数时，要再加上p
快速幂
蓝桥云课-快速幂
BV1nd4y1A7vF
n&1：
判断n的二进制形式最后一位是否为1
//这个mod可以不用
ll qmi(ll a,ll n,ll mod) { //计算a^n
ll ans=1;//用ans返回结果
while(n) { //把n看成二进制，逐个处理它的最后一位
if(n&1)ans=ans*a%mod;//n的最后一位是1表示这一位要计算，需要乘a，这个mod自己定义，1000或某个数
a=a*a%mod;//加倍，a^2->a^4->a^8...
n>>=1;//n右移1位，把n的最后一位去掉
}
return ans;
}
乘法逆元
乘法逆元
BV195411w75c
视频里还讲了p不是质数的情况，用扩展欧几里得算法
但题目中一般是10^9+7
欧拉算法
题目
最大公约数
筛质数
#include <bits/stdc++.h>
using namespace std;
//不要用sqrt，比用i*i慢
bool isPrime(int num) {
if (num < 2) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
int n;
int cnt=0;
int main()
{
cin>>n;
//1既不是质数（素数）也不是合数，遍历从2开始
for(int i=2;i<=n;i++){
if(isPrime(i))cnt++;
}
cout<<cnt;
return 0;
}分解质因数
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
void divide(int n){
cout<<n<<"=";
for(int i=2;i*i<=n;i++){
if(n%i==0){
while(n%i==0){
cout<<i;
n/=i;
//如果还有剩余，输出乘号
if(n>1)cout<<"*";
}
}
}
// 处理剩余的质数
if(n>1)cout<<n;
cout<<endl;
}
int a,b;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>a>>b;
for(int i=a;i<=b;i++)divide(i);
return 0;
}快速幂
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qmi(ll a,ll n,ll mod){
ll ans=1;
while(n){
if(n&1)ans=ans*a%mod;
a=a*a%mod;
n>>=1;
}
return ans;
}
ll b,p,k;
int main()
{
cin>>b>>p>>k;
cout<<qmi(b,p,k);
return 0;
}乘法逆元
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll p=1e9+7;
int T;
ll qmi(ll a,ll n){
ll ans=1;
while(n){
if(n&1)ans=ans*a%p;
a=a*a%p;
n>>=1;
}
return ans;
}
int main()
{
cin>>T;
while(T--){
ll N;
cin>>N;
cout<<qmi(N,p-2)<<endl;
}
return 0;
}高斯求和
高斯求和是一种快速计算连续整数和的方法
同余定理
给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余
记作a≡b(mod m)
a 和 b 除以 m 后的余数相同，即a-b是m的倍数（m能整除a-b）
即，如果a%m==b%m，(a-b)%m==0
两个数模 m 同余，所以它们的差能被 m 整除
题目
k倍区间（前缀和，同余定理，组合数）
题目解析
k=2，对1 2 3 4 5这个序列求前缀和
然后再对k进行取余
已知同余定理：对于余数相同的两个数字，它们的差能被某个正整数k整除（a≡b(mod k)）
在这里，“它们的差”就是区间和（用前缀和求差就是求区间和）
而这个区间和能被k整除，符合题目要求
所以要计算不同余数，相同的次数出现了几次
然后用组合数的基本定义（组合数的基本定义是阶乘的方式，和递推公式数学本质一样）求有几个区间
因为是在出现相同余数的前缀和中选两个，即在出现的同余次数中选两个
所以公式为n(n-1)/2
对于两个不同的模 K 为 0 的前缀和，它们之间的子数组和是 K 的倍数，这样的组合数可以用组合公式 C(n, 2) = n * (n - 1) / 2 计算（从 n 个元素中选 2 个的组合数）
但是，单个模 K 为 0 的前缀和本身也算一种满足条件的情况，所以需要额外加上这 n 种情况。而 n * (n - 1) / 2 + n = n * (n + 1) / 2
代码
AC
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,K;
const int NN=1e5+10;
int a[NN];
ll prefix[NN];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N>>K;
map<int,int>mp;
for(int i=1;i<=N;i++){
cin>>a[i];
//对每一个前缀和取模
prefix[i]=(prefix[i-1]+a[i])%K;
//计算不同余数出现的次数
mp[prefix[i]]++;
}
ll ans=0;
for(auto i:mp){
//组合数C(n,2)=n(n-1)/2
if(i.first==0){
//ans+=i.second*(i.second+1)/2;//简写
ans+=(ll)i.second*(i.second-1)/2+i.second;
}
else ans+=(ll)i.second*(i.second-1)/2;
}
cout<<ans;
return 0;
}暴力（只通过2个）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,K;
const int NN=1e5+10;
ll a[NN],prefix[NN];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N>>K;
for(int i=1;i<=N;i++){
cin>>a[i];
prefix[i]=prefix[i-1]+a[i];
}
int cnt=0;
//求区间，O(n^2)
for(int i=1;i<=N;i++){
for(int j=i;j<=N;j++){
if((prefix[j]-prefix[i-1])%K==0)cnt++;
}
}
cout<<cnt;
return 0;
}等差数列
等差数列求和
题目要求中包含连续的正整数相加，这就可以联想到等差数列求和公式
判断是否是2^n
bool check(int n){
//如果是2^n，一直除2，最后会等于1，所以在n=1是循环停止，循环进行条件是n!=1
while(n!=1){
//n为偶，除2
if(n%2==0)n/=2;
//n是奇数且不等于1（比如 3、5 等），返回false，因为它不可能是2的幂次方数
else return false;
}
return true;
}题目
等差数列
题目分析
题目要求项数最少，即公差 d 最大。
而由于等差数列的任意两项之差都是公差的倍数，所以我们只需要求出给出的数两两之差的最大公因数即可
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int NN=1e5+10;
int a[NN];
int n;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
if (a[1] == a[n]){
//公差d为0的情况
//都排完序了第一个和最后一个还是相等
//肯定是全部都相等，直接结束
cout << n << endl;
return 0;
}
int d = a[2] - a[1];//初值设为一个公差的若干倍
for (int i = 3; i <= n; i++)
d = __gcd(d, a[i] - a[i - 1]);
cout << (a[n] - a[1]) / d + 1 << endl;//求项数
return 0;
}数字诗意
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool check(int n){
while(n!=1){
if(n%2==0)n/=2;
else return false;
}
return true;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
int x;cin>>x;
if(check(x))ans++;
}
cout<<ans;
return 0;
}并查集
BV1Bh4y1k7fZ
用并查集或者bfs求连通块
并查集也可以判断两个点在不在同一个集合（就是判断两个点连不连通）
并查集优化方式有：
题目
并查集
朴素代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int NN=1e5+10;
//父节点是前一个节点
int pre[NN];
//函数命名成root，因为并查集，查的是元素的根节点，而且避免和stl中的find重名
int root(int x){
//朴素写法
//当 pre[x]=x 时，说明x的父节点就是它自身，此时x就是所在集合的根节点，直接返回 x
//x不是根节点，传入pre[x]，继续查找 x 的父节点的根节点，直到找到根节点为止
//return pre[x]==x?x:root(pre[x]);
//路径压缩优化
//找到节点x的根节点后，将节点x的父节点直接设置为根节点，实现了路径压缩
return pre[x]=pre[x]==x?x:root(pre[x]);
}
void merge(int x,int y){
//此时，x和y代表的是两个集合的根节点
x=root(x),y=root(y);
//x和y的根节点相同，已经在同一个集合中，此时不需要进行合并操作，直接返回
if(x==y)return;
//x和y不相等，分别属于不同的集合。将x的父节点设置为y（将y的父节点设置为x没区别）
pre[x]=y;
}
void solve(){
int n,m;
cin>>n>>m;
//初始化，把每个节点变成自己的父节点（自环）
for(int i=1;i<=n;i++) pre[i]=i;
while(m--){
int op,x,y;
cin>>op>>x>>y;
//如果操作是1，合并
if(op==1)merge(x,y);
else cout<<(root(x)==root(y)?'Y':'N')<<endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _=1;
while(_--)solve();
return 0;
}
路径压缩（优化）
原本
优化
优化的代码只有一个改动，在朴素代码中注释了
合根植物（是否属于同一个集合）
#include <bits/stdc++.h>
using namespace std;
const int M=1000;
const int N=1000;
//父节点
int pre[M*N];
int m,n,k;
int root(int x){
return pre[x]=pre[x]==x?x:root(pre[x]);
}
void merge(int x,int y){
x=root(x);y=root(y);
if(x==y)return;
pre[x]=y;
}
void solve(){
cin>>m>>n>>k;
for(int i=1;i<=m*n;i++)pre[i]=i;
while(k--){
int a,b;
cin>>a>>b;
merge(a,b);
}
int cnt=0;
for(int i=1;i<=n*m;i++){
//如果根节点等于自身，说明没有成为别人的子节点
if(root(i)==i)cnt++;
}
cout<<cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _=1;
while(_--)solve();
return 0;
}修改数组（先把所有可能都设置成父节点，是否出现过，出现就修改）
题目
题目分析
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int NN=1e5+10;
int pre[NN];
int N;
int root(int x){
return pre[x]=pre[x]==x?x:root(pre[x]);
}
void merge(int x,int y){
x=root(x);y=root(y);
if(x==y)return;
pre[x]=y;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N;
for(int i=1;i<=1e5+5;i++){
pre[i]=i;
}
int A;
for(int i=1;i<=N;i++){
cin>>A;
A=root(A);//找到A的根节点
cout<<A<<' ';
merge(A,A+1);//将A与A+1相连
}
return 0;
}数据结构
优先队列
2025蓝桥杯省赛-javaB组-（6）数组翻转_哔哩哔哩_bilibili
双指针
题目
最长子序列
题目解析
一个指针指向S，一个指针指向T
遍历S，如果S[i]==T[j]，j++
代码
#include <bits/stdc++.h>
using namespace std;
string S,T;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>S>>T;
int ans=0;
for(int i=0,j=0;i<S.size()and j<T.size();i++){
if(S[i]==T[j]){
j++;
ans++;
}
}
cout<<ans;
return 0;
}#include <bits/stdc++.h>
using namespace std;
#define int long long
int a,b,n;
int ans=0;
void solve(){
cin>>a>>b>>n;
int cnt=0;
for(int week=1;;week++){
week%=7;
if(week>=1&&week<=5){
cnt+=a;
ans++;
}else{
cnt+=b;
ans++;
}
if(cnt>=n)return;
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int _=1;
while(_--)solve();
cout<<ans;
return 0;
}几何
拼正方形
要拼成一个正方形，需要的相同的小正方形的个数必须是完全平方数
题目
题目分析
要使边长尽可能的大，就肯定是要多用 2×2 的方块
我们先用 2×2 的方块拼一个最大正方形
的结果2717561.0183988509662675986152793⋯，向下取整后值为 2717561，因为用的是2*2的方块，所以边长要*2（不然就是用1×1小正方形拼成正方形时的边长），目前正方形最大边长就是 2717561×2=5435122
这时，再用1*1的方块补
到这里要想让边长 +1 就要用 5435122×4+4 个 1×1 的正方形
但是5435122×4+4>10470245，故不能再拼一层
答案
5435122
打表
【蓝桥杯真题讲解】2026 蓝桥杯省赛真题讲解（C++B组）_哔哩哔哩_bilibili
第二题打表
欢迎加入DeepSeek 技术社区。在这里，你可以找到志同道合的朋友，共同探索AI技术的奥秘。
更多推荐
18
0- 0
已为社区贡献1条内容
所有评论(0)