一、set
定义：set<int>s;
插入：s.insert();
长度：len=s.size()
遍历：for(auto x:s) cout<<x<<" ";
二、前缀和
一维
构建：s[i]=s[i-1]+a[i];
区间和(l,r)：sum=s[r]-s[l-1];
二维
构建：s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
区间和(x1,y1)到(x2,y1)：sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
三、二分
左边界
while(l<r)
{
int mid=l+r>>1;
if(mid>=x)//当前数在目标值的右边
r=mid;
else
l=mid+1;
}
右边界
while(l<r)
{
int mid=l+r+1>>1;
if(mid<=x)//当前数在目标值左边
l=mid;
else
r=mid-1;
}
四、DFS（n<=30）
搜索方案
1、爆搜
（1）非地图类
#include<bits/stdc++.h>
using namespace std;
int a[10]={5,5,10,10,15,15,20,20,25,25};
set<int>s;
bool st[10];
void dfs(int u)//完成的题目和分数
{
if(u==10)//全部完成了
{
int score=0;
for(int i=0;i<10;i++)
score+=st[i]*a[i];
s.insert(score);
return;
}
//遍历所有情况
//做对
st[u]=true;
dfs(u+1);
st[u]=false;//恢复现场
//做错
st[u]=false;
dfs(u+1);
st[u]=true;//恢复现场
}
int main()
{
dfs(0);
for(auto x:s)
cout<<x<<" ";
printf("\n");
printf("%d",s.size());
return 0;
}
（2）地图类
#include<bits/stdc++.h>
using namespace std;
const int N=32;
int n,m;
int cnt;
int g[N][N];
int next2[2][2]={{0,1},{1,0}};
void dfs(int a,int b)
{
if(a==n&&b==m)
{
cnt++;
return;
}
for(int i=0;i<2;i++)
{
int x=a+next2[i][0],y=b+next2[i][1];
if(x>n||y>m) continue;
if(x%2==0&&y%2==0) continue;
dfs(x,y);
}
}
int main()
{
scanf("%d%d",&n,&m);
dfs(1,1);
printf("%d",cnt);
return 0;
}
2、记忆化搜索
核心思想是：保存已计算的结果来避免重复计算
使用dp[i][j] 记录从坐标 (i,j) 到终点 (n,m) 的路径数量
#include<bits/stdc++.h>
using namespace std;
const int N=32;
int n,m;
int g[N][N];
int next2[2][2]={{0,1},{1,0}};
int dp[N][N];//记忆化数组
int dfs(int a,int b)//每次返回的是从(a,b)到(n,m)的路径数
{
//从(n,m)到(n,m)只有一条路径
if(a==n&&b==m)
return 1;
//如果已经计算过了，就直接返回结果（关键步骤）
if(dp[a][b]!=-1)
return dp[a][b];
int cnt=0;
for(int i=0;i<2;i++)
{
int x=a+next2[i][0],y=b+next2[i][1];
if(x>n||y>m) continue;
if(x%2==0&&y%2==0) continue;
//每一次递归结束就会往上叠加直到(1,1)
cnt+=dfs(x,y);
}
return dp[a][b]=cnt;
}
int main()
{
memset(dp,-1,sizeof dp);
scanf("%d%d",&n,&m);
printf("%d",dfs(1,1));
return 0;
}
搜索路径
要用一个额外的空间来存路径，比如排列数字的int path[]和数字接龙的string path
（1）非地图类
#include<bits/stdc++.h>
using namespace std;
const int N=12;
struct node{
int t;
int d;
int l;
}f[N];
int n;
bool st[N];
bool dfs(int u,int last)//u表示已经降落的飞机数量，last表示上一架飞机降落完毕的时间
{
if(u==n)
return true;
//遍历所有飞机
for(int i=1;i<=n;i++)
{
//如果没有飞并且可以飞
if(st[i]==false&&(f[i].t+f[i].d)>=last)
{
st[i]=true;
int time;//开始降落的时间
if(f[i].t>=last) time=f[i].t;
else time=last;
if(dfs(u+1,time+f[i].l))
return true;
st[i]=false;
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
for(int i=0;i<T;i++)
{
memset(st,0,sizeof st);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&f[i].t,&f[i].d,&f[i].l);
if(dfs(0,0)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
（2）地图类
#include<bits/stdc++.h>
using namespace std;
const int N=12;
int next8[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int g[N][N];
string path;
bool edge[N][N][N][N];
bool st[N][N];
int n,k;
bool dfs(int a,int b)
{
//到达终点
if(a==n-1&&b==n-1)
return path.length()==n*n-1;
st[a][b]=true;
for(int i=0;i<8;i++)
{
//下一个位置
int x=a+next8[i][0],y=b+next8[i][1];
//如果越界
if(x<0||y<0||x>n-1||y>n-1) continue;
//如果没有走过
if(st[x][y]) continue;
//按照大小顺序
if(g[x][y]!=(g[a][b]+1)%n) continue;
//不可以交叉
if(i%2!=0)//斜方向走时
if(edge[x][b][a][y]||edge[a][y][x][b])
continue;
st[x][y]=true;
edge[a][b][x][y]=true;
path+=i+'0';
if(dfs(x,y)) return true;
st[x][y]=false;
path.pop_back();
edge[a][b][x][y]=false;
}
st[a][b]=false;
return false;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&g[i][j]);
if(dfs(0,0))
cout<<path<<endl;
else
printf("-1");
return 0;
}
搜数量（可以dfs，也可以bfs）
如果是搜全图xx的数量，就不用恢复现场
五、BFS（n<=1e6）
搜最短路
建立一个d[i][j]来存路径
#include<bits/stdc++.h>
using namespace std;
const int N=210;
typedef pair<int,int> PII;
int t,r,c;
char g[N][N];
int next4[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool st[N][N];
int d[N][N];//用来存路径长度
bool bfs(int a,int b)
{
queue<PII>q;//一定要每次使用都初始化
q.push({a,b});
st[a][b]=true;
while(!q.empty())
{
PII start=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=start.first+next4[i][0],y=start.second+next4[i][1];
if(st[x][y]==false&&x<=r&&x>=1&&y<=c&&y>=1)//如果可以走
{
st[x][y]=true;
d[x][y]=d[start.first][start.second]+1;
q.push({x,y});
if(g[x][y]=='E')
return true;
}
}
}
return false;
}
int main()
{
scanf("%d",&t);
getchar();
while(t--)
{
//初始化
memset(st,0,sizeof st);
memset(d,0,sizeof d);
memset(g,0,sizeof g);
scanf("%d %d",&r,&c);
getchar();
int a,b;//起始位置
int A,B;//结束位置
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
scanf("%c",&g[i][j]);
if(g[i][j]=='S')
{
a=i;
b=j;
st[i][j]=true;
}
if(g[i][j]=='#')
st[i][j]=true;
if(g[i][j]=='E')
{
A=i;
B=j;
}
}
getchar();
}
if(bfs(a,b)) printf("%d\n",d[A][B]);
else printf("oop!\n");
}
return 0;
}
搜数量
感觉用bfs好理解一点
#include<bits/stdc++.h>
using namespace std;
const int N=22;
typedef pair<int,int> PII;
int w,h;
char g[N][N];
int next4[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int cnt;
bool st[N][N];
int bfs(int a,int b)
{
cnt=1;
queue<PII>q;
q.push({a,b});
st[a][b]=true;
while(!q.empty())
{
PII start=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=start.first+next4[i][0],y=start.second+next4[i][1];
if(st[x][y]==false&&x>=1&&x<=h&&y>=1&&y<=w)
{
st[x][y]=true;
cnt++;
q.push({x,y});
}
}
}
return cnt;
}
int main()
{
while(1)
{
//初始化
int a,b;//起始位置
cnt=1;
memset(st,0,sizeof st);
cin>>w>>h;
if(w==0&&h==0)
break;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
{
cin>>g[i][j];
if(g[i][j]=='@')
{
a=i;
b=j;
}
if(g[i][j]=='#')
st[i][j]=true;
}
printf("%d\n",bfs(a,b));
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=55;
typedef pair<int,int> PII;
queue<PII> q1;//岛屿
queue<PII> q;//海水
int m,n;
char g[N][N];
bool st[N][N];//标记岛屿有没有被搜过
int next4[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int next8[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int cnt;
//岛屿bfs，四个方向
void bfs_(int a,int b)
{
q1.push({a,b});
st[a][b]=true;
while(!q1.empty())
{
PII start=q1.front();//取出队首元素
q1.pop();//移除第一个元素
//往四个方向走
for(int i=0;i<4;i++)
{
int x=start.first+next4[i][0],y=start.second+next4[i][1];
if(x>=0&&x<=m+1&&y>=0&&y<=n+1&&st[x][y]==false)
if(g[x][y]=='1')//如果是岛屿且没有搜过
{
st[x][y]=true;
q1.push({x,y});
}
}
}
}
//海水bfs，八个方向
void bfs(int a,int b)
{
q.push({a,b});
while(!q.empty())
{
PII start=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int x=start.first+next8[i][0],y=start.second+next8[i][1];
//如果没有越界且没有搜过
if(x>=0&&x<=m+1&&y>=0&&y<=n+1&&st[x][y]==false)
{
if(g[x][y]=='1')//如果是岛屿，就全部搜一遍
{
bfs_(x,y);
cnt++;
}
else//如果是海水就继续
{
st[x][y]=true;
q.push({x,y});
}
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
getchar();
while(t--)
{
cnt=0;
memset(g,'0',sizeof g);
memset(st,0,sizeof st);
scanf("%d%d",&m,&n);
getchar();
//读入地图
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
scanf("%c",&g[i][j]);
getchar();
}
bfs(0,0);
printf("%d\n",cnt);
}
return 0;
}
六、DP
最长上升子序列模型 可以求最长接龙子序列，再用n减去
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e9;
char s[M];
int a1[N];//首位
int a2[N];//末位
int dp[N];
//dp[i]表示以第i个字母结尾的接龙序列的长度
//属性：最大值
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>s;
a1[i]=s[0]-'0';
a2[i]=s[strlen(s)-1]-'0';
}
//初始化
for(int i=1;i<=n;i++)
dp[i]=1;//每个元素都可以单独构成一个长度为1的接龙序列
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
//选
if(a1[i]==a2[j])
dp[i]=max(dp[i],dp[j]+1);
}
}
int M=0;
for(int i=1;i<=n;i++)
M=max(dp[i],M);
printf("%d",n-M);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=110,MOD=1000000007;
int dp[N][N][N];
//dp[i][j][c]表示遇到i次店，j次花还剩c斗酒的方案
//属性：数量
//1、最后一步遇到店，需要满足i>=1和c%2==0，dp[i+1][j][c]+=dp[i][j][c/2]
//2、最后一步遇到花，需要满足j>=1，dp[i][j+1][c]+=dp[i][j][c+1]
int main()
{
int n,m;
scanf("%d%d",&n,&m);
//初始化
dp[0][0][2]=1;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=m;k++)// 最多就是花的数量，如果大于这个数，就肯定喝不完
{
if(i>=1&&k%2==0)//注意这里要写i>=1和下面的j>=1
dp[i][j][k]=(dp[i-1][j][k/2]+dp[i][j][k])%MOD;
if(j>=1)
dp[i][j][k]=(dp[i][j-1][k+1]+dp[i][j][k])%MOD;
}
printf("%d",dp[n][m-1][1]);
return 0;
}
图类
#include<bits/stdc++.h>
using namespace std;
const int N=32;
int dp[N][N];
//dp[i][j]表示从起点到(i,j)的路径
//属性：数量
bool isValid(int a,int b)
{
return !(a%2==0&&b%2==0);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
//初始化
dp[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
//向右走
if(isValid(i,j+1)&&j+1<=m)
dp[i][j+1]+=dp[i][j];
//向下走
if(isValid(i+1,j)&&i+1<=n)
dp[i+1][j]+=dp[i][j];
}
printf("%d",dp[n][m]);
return 0;
}
状态压缩DP
#include<bits/stdc++.h>
using namespace std;
const int N=10000010,MOD=1000000007;
int dp[N][4];
//dp[i][j]表示第i-1列已经放好时，第i列的状态为j
//属性：数量
//放第i列
//j=00，i+1列有00、01、10、11
//j=01，i+1列有10、11
//j=10，i+1列有01、11
//j=11，i+1列有00
int g[4][4]=
{{1,1,1,1},
{0,0,1,1},
{0,1,0,1},
{1,0,0,0}};
int main()
{
int n;
scanf("%d",&n);
//初始化
dp[1][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<4;j++)
for(int k=0;k<4;k++)
dp[i+1][k]=(dp[i+1][k]+dp[i][j]*g[j][k])%MOD;
printf("%d",dp[n+1][0]);
return 0;
}
七、双指针
双指针是把i,j写在一个for里面，整个区间左右移动
千万别把strlen写在循环里面，会增加运行时间
一般方案数都要用longlong
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long LL;
char c1,c2;
char s[N];
LL cnt;
LL ans;
int main()
{
int k;
scanf("%d",&k);
cin>>s>>c1>>c2;
int n=strlen(s);
for(int i=0,j=k-1;j<n;i++,j++)
{
if(s[i]==c1)
cnt++;
if(s[j]==c2)
ans+=cnt;
}
printf("%lld",ans);
return 0;
}
八、其他
算一个序列里两数之差最小值：可以先sort,再遍历序列找相邻两数的最小值
数据到1e9最好开longlong
数组l的大小是N*(n-1)/2，从n个里面选两个，有C(2,n)个
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=N*(N-1)/2;
typedef long long LL;
LL a[N];
LL s[N];
LL l[M];//从n个里面选两个
int main()
{
int n;
scanf("%lld",&n);
for(LL i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
LL cnt=0;
//将每个区间的力量和存在一个数组里
for(LL i=1;i<=n;i++)
for(LL j=i;j<=n;j++)
{
if(i==1&&j==n) continue;
l[cnt++]=s[j]-s[i-1];
}
sort(l,l+cnt);
LL m=1e9;
for(LL i=1;i<cnt;i++)
m=min(m,l[i]-l[i-1]);
printf("%lld",m);
return 0;
}
