根据时间复杂度选择算法

## 总览

n≤30 → 指数级别

dfs + 剪枝，数字排列， n皇后问题，八数码问题

状态压缩 dp，蒙德里安的梦想，最短Hamilton路径
n≤100 → O(n^3)

floyd，dp
n≤1000 → O(n^2)，O(n^2log_n)

dp，二分，朴素版dijkstra，朴素版prim，Bellman-Ford
n≤10000 → O(n*\sqrt{n})

块状链表，分块，莫队
n≤100000 → O(nlog_n)

各种排序sort，线段树，树状数组，set/map，heap，dijkstra+heap，prim+heap，spfa，凸包，半平面交，二分
n≤1000000 → O(n)，常数较小的 O(nlog_n)

hash，双指针，并查集，kmp，AC自动机

常数较小的 O(nlog_n)：sort，树状数组，heap，dijkstra，spfa
n≤10000000 → O(n)

双指针，kmp，AC自动机，线性筛素数
n≤10^9 → O(\sqrt{n})

判断质数
n≤10^{18} → O(log_n)

最大公约数，快速幂
n≤10^{1000} → O((log_n)^2)

高精度加减乘除
n≤ 10^{100000} → O(logn * loglogn)

高精度加减，FFT/NTT
其他 trie树、前缀和差分、区间合并、日期问题、单调栈单调队列、其他数学、输入输出、库函数

N<=30

dfs bfs

每位可选所有情况枚举位置枚举选法dfs 指数型枚举

int path[N];
void dfs(int u,int cut){
    if(cut) return;
    if(u>n){
        for(int i=1;i<=n;i++){
            check
            dosomething
        }
        return;
    }
    for(int i=0;i<choice;i++){
        path[u]=i;
        dfs(u+1,cut+calc(i));
        path[u]=-1;
    }
}
mian: dfs(1,0);

每数都选且不重复不同顺序算不同种全排列

vector<int> a={...};
main:
    do{
        int A=calc(...);
        int B=calc(...);
        int C=calc(...);
        if(check(A,B,C)){
            dosomething
        }
    }while(permutation(a.begin(),a.end()));

n中选m 不同顺序算同一种组合型枚举

int way[N];
int a[N]={...};
int n,m;

void dfs(int u,int start){
    if(u+n-start<m)	return;
    if(u>m){
        dosthing
        return;
    }
    for(int i=start;i<=n;i++){
        way[u]=a[i];
        dfs(u+1,i+1);
        way[u]=0;
    }
}
main: dfs(1,1);

图

拓展

4方
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
8向
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
日
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
日加田
int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
int dy[12]={1,2,2,2,2,1,-1,-2,-2,-2,-2,-1};

bfs回溯路径

char p[choice]={'U','D','L','R'}; 有优先级 对应
void print_path(int x,int y){
    if(x==startx && y==starty)   if(x<startx || y<starty)  看要不要输出起点
        return;
    if(pre[x][y]==上)
        print_path(x+1,y);
    if(pre[x][y]==右)
        print_path(x,y-1);
    if(pre[x][y]==下)
        print_path(x-1,y);
    if(pre[x][y]==左)
        print_path(x,y+1);
    cout<<pre[x][y];  cout<<x<<" "<<y<<endl; 看要的是左边还是方向
}

合法

bool isVaild(int x,int y){
    return x>=0 && x<=n-1 && y>=0 && y<=m-1 && !st[x][y]; 0起
    return x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1;   1起
    return x>=0 && x<=n+1 && y>=0 && y<=m+1 && !st[x][y]; 染色
}

读图

每行无空格
char g[N][M];
for(int i=0;i<n;i++)
    cin>>g[i];
每行有空格
int g[N][M];
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        cin>>g[i][j];
    }
}
每行无空格的且长度不定 或字符需补圈0
int g[N][M];
for(int i=1;i<=n;i++){
    string s;
    cin>>s;  数据中带空格用getline(cin,s);
    for(int j=1;j<=m;j++){
        g[i][j]=s[j-1]-'0';
    }
}

//题目说读n行 又给了空格 不知道是不是g[i][j]一个一个读入 万一只读3次就寄了
//按行处理 防恶心
cin>>n>>k;
string s;
getline(cin,s);
for(int i=0;i<n;i++){
    getline(cin,s);
    for(int k=0,j=0;k<s.size();k++){
        if(s[k]!=' ')
            g[i][j++]=s[k]-'0';
    }
}

dfs

const int N,M;

int n,m;

char g[N][M]; int g[N][M];

bool st[N][M];

dx,dy,isVaild

void dfs(int x,int y){

    终止

    for(int i=0;i<choice;i++){

        int nx=x+dx[i],ny=y+dy[i];

        if(isVaild(nx,ny) && g[nx][ny]=='路'){

            st[nx][ny]=true;

            dfs(nx,ny);

            st[nx][ny]=false; 走多次要回溯

        }

    }

}

main:

    读图

    找起点

    st[i][j]=true;

    dfs(i,j);

bfs

typedef pair<int,int> PII;
const int N,M;
int n,m;
char g[N][M]; int g[N][M];
int d[N][M];
int startx,starty,targetx,targety;
??char pre[N][M]; char p[choice]={...}; print_path()
dx,dy,isVaild
void bfs(int x,int y){
    queue<PII> q;
    memset(d,-1,sizeof d);
    q.push({x,y});
    d[x][y]=0;
    while(!q.empty()){
        auto cur=q.front();q.pop();
        int ux=cur.first,uy=cur.second;
        对取出来的点的操作
        if(ux==targetx && uy==targety){
            dosomething
            print_path(ux,uy);
            return;  return d[ux][uy];无需全找可以提前退出
        }
        拓展操作
        for(int i=0;i<choice;i++){
            int nx=ux+dx[i],ny=uy+dy[i];
            if(isVaild(nx,ny) && g[nx][ny]=='路'){
                q.push({nx,ny});
                d[nx][ny]=d[ux][uy]+1;  pre[nx][ny]=p[i];
            }
        }
    }
    return d[targetx][targety];需要全找 如洪水 只能这里退出
}
main:
    读图
    确定startx,starty,targetx,targety;
    bfs(startx,starty);
多源直接把d的重置和q的定义放外面 把所有起点都先放进去

洪水

找到某个未被标记的点用dfs或bfs把所有它能拓展到的点都标记一共被标记几次就有几个连通块

另加一个引用判断该块是否符合性质符合则++

一来可以得到总的块数和满足条件的块数

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(g[i][j]=='判断字符' && !st[i][j]){
            bool check=false;
            st[i][j]=true;
            dfs(i,j,check);  bfs(i,j,check);
            res++;
            if(check){
                cnt++;
            }
        }
    }
}

染色

被包裹着的一部分和没被包裹住的一部分把图扩大一圈在00处染色可区分两部分

主要在于读图

int g[N][M];
main:
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        string line;
        cin>>line;
        for(int j=1;j<=m;j++){
            g[i][j]=line[j-1]-'0';
        }
    }
    bfs(0,0);

棋盘：

x,y
(0,0) (0,1) (0,2) (0,3) (0,4)
(1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
(3,0) (3,1) (3,2) (3,3) (3,4)
(4,0) (4,1) (4,2) (4,3) (4,4)

x+y
(0) (1) (2) (3) (4)
(1) (2) (3) (4) (5)
(2) (3) (4) (5) (6)
(3) (4) (5) (6) (7)
(4) (5) (6) (7) (8)

x-y+n
(5) (4) (3) (2) (1)
(6) (5) (4) (3) (2)
(7) (6) (5) (4) (3)
(8) (7) (6) (5) (4)
(9) (8) (7) (6) (5)

n-x+y
(5) (6) (7) (8) (9)
(4) (5) (6) (7) (8)
(3) (4) (5) (6) (7)
(2) (3) (4) (5) (6)
(1) (2) (3) (4) (5)

正对角线 x+y  反对角线： n-x+y或者x-y+n

枚举每个位置或每一行 放与不放枚举

n皇后问题
//从点入手
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=10;
char g[N][N];
bool row[N],col[N],dg[N*2],udg[N*2];
int n;

void dfs(int x,int y,int cnt){
    if(cnt>n)   return;
    if(y==n)    y=0,x++;
    if(x==n){
        if(cnt==n){
            for(int i=0;i<n;i++)
                puts(g[i]);
            puts("");
        }
        return;
    }

    //不放
    g[x][y]='.';
    dfs(x,y+1,cnt);
    //放 满足横纵斜都没放过才行
    if(!row[x] && !col[y] && !dg[x+y] && !udg[n-x+y]){
        row[x]=col[y]=dg[x+y]=udg[n-x+y]=true;
        g[x][y]='Q';
        dfs(x,y+1,cnt+1);
        g[x][y]='.';
        row[x]=col[y]=dg[x+y]=udg[n-x+y]=false;
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    dfs(0,0,0);
    return 0;
}

//从行入手
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=10;
char g[N][N];
bool col[N],dg[N*2],udg[N*2];
int n;

void dfs(int u/*,int cnt*/){
    // if(cnt>n)   return;//与下面同理 n一定是刚好满足的 所以剪枝失效 cnt也可以不传入
    if(u==n){
        //if(cnt==n){
            for(int i=0;i<n;i++)
                puts(g[i]);
            puts("");
        //}
        return;
    }

    for(int i=0;i<n;i++){
        //不放 由于n皇后是n*n放n个 所以每行必须有一个 现在不存在不放的情况
        // g[u][i]='.';
        // dfs(u+1,cnt);
        //放 满足横纵斜都没放过才行
        if(!col[i] && !dg[u+i] && !udg[n-u+i]){
            col[i]=dg[u+i]=udg[n-u+i]=true;
            g[u][i]='Q';
            dfs(u+1/*,cnt+1*/);
            g[u][i]='.';
            col[i]=dg[u+i]=udg[n-u+i]=false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0/*,0*/);
    return 0;
}

场景： 30以内用dfs,bfs 超过考虑改成dp

N<=100

floyd

#include<bits/stdc++.h>
using namespace std;

const int N=210,INF=0x3f3f3f3f;
int d[N][N];
int n,m,Q;

void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
}

int main()
{
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j)
                d[i][j]=0;
            else
                d[i][j]=INF;

    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        d[a][b]=min(d[a][b],w);
    }

    floyd();

    while(Q--)
    {
        int a,b;
        cin>>a>>b;

        int result=d[a][b];
        if(result>INF/2)
            cout<<"impossible"<<endl;
        else
            cout<<result<<endl;
    }

    return 0;
}

dp

把过去当已知现在由过去转移而来将过去的几种情况分入集合进行考虑得出状态转移方程最后再考虑最初始的情况应该如何设置

背包

有限制的选择问题价值与体积

01背包第i层状态由第i-1层转移而来使用滚动数组的话需要从大到小枚举体积

for(int i=1;i<=n;i++){
    for(int j=m;j>=v[i];j--){
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
}
cout<<f[m];

完全背包第i层状态由第i层转移来从小到大枚举体积

for(int i=1;i<=n;i++){
    for(int j=v[i];j<=m;j++){
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
}
cout<<f[m];

多重背包将物品二进制拆解成多份每份当做01背包的一个物品

for(int i=1;i<=n;i++){
    for(int k=1;k<=s[i];k*=2){
        for(int j=m;j>=k*v[i];j--){
            f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
        }
        s[i]-=k;
    }
    if(s[i]){
       for(int j=m;j>=s[i]*v[i];j--){
           f[j]=max(f[j],f[j-s[i]*v[i]]+s[i]*w[i]);
       }
    }
}

混合背包将01当做s[i]=1的多重背包再将多重背包转成01背包求解完全背包另做一种情况

for(int i=1;i<=n;i++){
    if(s[i]==0)
        for(int j=v[i];j<=m;j++)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    else{
        if(s[i]==-1)
            s[i]=1;
        for(int k=1;k<=s[i];k*=2){
            for(int j=m;j>=k*v[i];j--){
                f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
            }
            s[i]-=k;
        }
        if(s[i]){
            for(int j=m;j>=s[i]*v[i];j--){
                f[j]=max(f[j],f[j-s[i]*v[i]]+s[i]*w[i]);
            }
        }
    }
}
cout<<f[m];

添加维度添加同体积的限制条件如重量在f[][]中加上一维变成f[][][] 循环时和枚举体积一样多枚举一个东西即可注意状态转移右边集合上一个状态的这一维也要减去

int f[N][M][M];
int n,m1,m2;
for(int i=1;i<=n;i++){
    for(int j1=0;j1<=m1;j1++){
        for(int j2=0;j2<=m2;j2++){
            f[i][j1][j2]=f[i-1][j1][j2];
            if(j1>=v[i] && j2>=m[i])
                 f[i][j1][j2]=max(f[i-1][j1][j2],f[i-1][j1-v[i]][j2-m[i]]+w[i]);
        }
    }
}
cout<<f[n][m1][m2];

物品中添加维度（种类）也就是分组背包问题

int v[N][N],w[N][N],s[N];
int f[N][N];
for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        f[i][j]=f[i-1][j];
        for(int k=0;k<s[i];k++){
            if(j>=v[i][k])
                f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
        }
    }
}
cout<<f[n][m];

方案问题

求方案数结合普通01背包问题求出最大价值和变形01背包问题求出各选法的选法数量在一次dp中算两个东西考察以count为属性时f[n][1-m]的含义明白f[n][k]是所有在前n个物品中选总体积不超过k的所有选法的数量即可这个数量如果为0 就说明这种体积凑不到如果不是就区别它是要具体个数还是说只要有没有如果是只要有没有 count属性就可以演变成bool属性所以背包dp还是不外乎三种属性 max min count 根据情况将count变成bool

for (int i = 0; i <= n; i++)
    g[i][0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        f[i][j] = f[i-1][j];
        g[i][j] = g[i-1][j];
        if (j >= v[i]) {
            if (f[i][j] < f[i-1][j-v[i]] + w[i]) {
                f[i][j] = f[i-1][j-v[i]] + w[i];
                g[i][j] = g[i-1][j-v[i]];
            } else if(f[i][j] == f[i-1][j-v[i]] + w[i]) {
                g[i][j] = (g[i][j] + g[i-1][j-v[i]]) % mod;
            }
        }
    }
}
int res = 0;
for (int j = 0; j <= m; j++) {
    if (f[n][j] == f[n][m]){
        res = (res + g[n][j]) % mod;
    }
}
cout << res;

求具体方案（路径）求完最大价值后回过头来反着推一遍看某个i是等于左边集合的状态还是右边集合的状态若处于右边就说明这个i被选过记录这些i

//1-n还是n-1看具体情况 1-n就是从小推大 上层i-1 反之亦然
for(int i=n;i>=1;i--){
    for(int j=0;j<=m;j++){
        f[i][j]=f[i+1][j];
        if(j>=v[i])
            f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
    }
}
for(int i=1,j=m;i<=n;i++){
    if(j>= v[i] && f[i][j]==f[i+1][j-v[i]]+w[i]){
        path[cnt++]=i;
        j-=v[i];
    }
}
for(int i=0;i<cnt;i++)
    cout<<path[i]<<" ";

三种常用属性以及初始化问题

体积最多是j (求max) f[0,i] 一件物品都不选的情况下体积最多为i时的最大价值 i不管取多少什么都不选是一种方案每个f[0,i]至少包含一个方案 f[0,i]的最大值为0

int f[N][N];
    可不初始化 全局变量默认全0
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v)
               f[i][j]=max(f[i][j],f[i-1][j-v]+w);
        }
    }

体积恰好是j (求count/bool) 恰好是j 计数Count f[0][0]=1 没有选择任何物品且背包体积为0的方法只有1种即不选任何物品其他的f[0][k] k > 0 都初始化为0 在没有物品可选的情况下不可能恰好填满非零体积的背包

int f[N][N];
    memset(f, 0, sizeof f); 可忽略
    f[0][0] = 1; 不选择任何物品，且背包体积为0的情况
    for(int i = 1; i <= n; i++) {
       for(int j = 0; j <= m; j++) {
           f[i][j] = f[i-1][j];
           if(j >= v[i])
              f[i][j]+=f[i-1][j-v[i]];
    }
}
f[n][m]为恰好填满容量为m的背包的方法总数

恰好是j 布尔Bool f[0][0]初始化为true 不选择任何物品且背包体积为0是一种可能的情况其他的f[0][k] k > 0 初始化为false 在没有物品可选的情况下不能恰好填满非零体积的背包

bool f[N][N];
  memset(f, false, sizeof f);
  f[0][0] = true;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= m; j++) {
       f[i][j] = f[i-1][j];
       if(j >= v[i])
          f[i][j] ｜= f[i-1][j-v[i]];
    }
}
f[n][m]最终会告诉我们是否存在至少一种方法来恰好填满容量为m的背包。

恰好为j max f[0][0]之外的所有值为负无穷大表示初始时除了体积为0的情况外其他所有体积的最大价值都是不可达的

int f[N][M];
    memset(f, -0x3f, sizeof(f));
    f[0][0] = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= m; ++j) {
            f[i][j] = f[i-1][j];
            if(j >= v[i]) {
                f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
            }
        }
    }
    int result = -1;
    for(int j = 0; j <= m; ++j) {
        if(f[n][j] > result) {
            result = f[n][j];
        }
    }
    cout<<result<<endl; 不超过背包容量能得到的最大价值

至少为j (求min)

f[0][0] = 0 没有选择任何物品时唯一可达的状态是体积为0的状态其他正无穷体积大于0 还没有开始选择物品在初始状态下它们不可达的

int f[N][N];
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=f[i-1][j];
            f[i][j]=min(f[i][j],f[i-1][max(j-v,0)]+w);
        }
    }

线性

递推方程具有明显的线性关系

数字三角形

正三角形每个点从左下右下推出 ans在顶部

    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i+1][j+1],f[i+1][j])+f[i][j];
                         右下          左下
        }
    }
    cout<<f[1][1];

矩形左上->右下和右下->左上合成左上->右下上下左右四个方向只会走右下走两次不能走同一点和一点只取一次等价两条路径不会走同点两次所以每点状态由左边和上边推出

求最大

 for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j]+w[i][j],f[i][j-1]+w[i][j]);
        }
    }
    cout<<f[n][m]<<endl;

求最小

  memset(f,0x3f,sizeof f);
    f[1][1]=w[1][1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=min({f[i][j],f[i][j - 1] + w[i][j],f[i - 1][j] + w[i][j]});
        }
    }
    cout<<f[n][n];

走两次 max 用k,x1,x2 代替x1,y1,x2,y2 节省一维 k表示总步数(x+y) 每个位置可能由上上左左上左左上四种情况得到 f[n+m][n][n]处为右下角答案

    for(int k=2;k<=n+m;k++){
        for(int i=1;i<k&&i<=n;i++){
            for(int j=1;j<k&&j<=n;j++){
                int v=w[i][k-i];
                if(i!=j)
                    v+=w[j][k-j];
                f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;
            }
        }
    }
    cout<<f[n+m][n][n]<<endl;

最长上升子序列两种——以a[i]结尾的上升子序列的最大长度或最大权和

长度

int res=0;
for(int i=1;i<=n;i++){
    f[i]=1;
    for(int j=1;j<i;j++){
        if(a[j]<a[i]){
            f[i]=max(f[i],f[j]+1);
        }
    }
    res=max(res,f[i]);
}
cout<<res;

权和

int res=0;
for(int i=1;i<=n;i++){
    f[i]=w[i];
    for(int j=0;j<i;j++){
        if(w[j]<w[i]){
            f[i]=max(f[i],f[j]+w[i]);
        }
    }
    res=max(res,f[i]);
}
cout<<res;

三种模型直接降先升后降直接升把下降的转变成从右往左的单调上升变成熟悉的模型

    从左往右的上升子序列
    for(int i=1;i<=n;i++){
        f_up[i]=1;
        for(int j=1;j<i;j++){
            if(w[j]<w[i]){
                f_up[i]=max(f_up(i),f_up(j)+1);
            }
        }
    }

    从左往右的下降子序列
    即从右往左的上升子序列
    for(int i=n;i>=1;i--){
        f_dw[i]=1;
        for(int j=n;j>i;j--){
            if(w[j]<w[i]){
                f_dw[i]=max(f_dw[i],f_dw[j]+1);
            }
        }
    }

关于答案

若答案只需要最大(不管方向 全局最大)
int res=0;
for(int i=1;i<=n;i++){
    res=max({res,f_up[i],f_dw[i]});
}
cout<<res<<endl;

需要综合最大(左加右)
int res=0;
for(int i=1;i<=n;i++){
    res=max(res,f_up[i]+f_dw[i]-1);
    正反向之和 i算了两次
}

若只需要不考虑方向的全局最大
可以用单调栈加二分优化
(不保留各点的情况 只维护最长长度 即栈长度)
int stk[N],top;
for(int i=1;i<=n;i++){
    if(top==0 || a[i]>stk[top]){
        stk[++top]=a[i];
    }
    else{
        *lower_bound(stk+1,stk+top+1,a[i])=a[i];
    }
}
cout<<top; 序列长度

一个序列可以拆分成多少个上升子序列或下降子序列
综合的太麻烦 只能单个
已有的单调栈只需要用一个栈顶元素表示 可以组成一个数组(单调)
每个数看能不能放在已有的栈里 且贪心的是栈顶离自己最近的
用二分找里自己最近的栈顶 若没有 就新开一个栈
最后看栈的数量 也就是数组的长度
int q[N],cnt;
for(int i=1;i<=n;i++){
    int l=0,r=cnt;
    while(l<r){
        int mid=l+r>>1;
        if(q[mid]>=w[i])
            r=mid;
        else
            l=mid+1;
    }
    if(q[r]<w[i]){
        r++;
    }
    cnt=max(cnt,r);
    q[r]=w[i];
}
cout<<cnt;

区间

f[i][j]表示 i到j这个区间的所有合并方案的集合属性：max min 根据此初始化为-inf 或 inf 三部曲枚举区间长度枚举起点终点枚举分界点起点终点较好确定只需要枚举起点根据起点算出终点主要是分析区间到底是分成 [i,k][k+1,j]还是[i,k][k,j]还是 [i][k][j]

memset(f,[+/—]0x3f,sizeof f);//初始化 求max 设-inf   求min 设inf
for(intlen=[1/2];len<=[n/n+1];len++) { //枚举区间长度1-n 还是 2-n+1
    for(int i=1;i+len-1<=[n/2*n]; n++) { //枚举起点 环形翻倍
        int j =i+len-1;  // 由起点计算终点
        if(len==[1/2]) {//边界（最小）区间1或2 由区间长度分析中确定
            dp[i][j] = 初始值
            continue;
        }
        for(int k=i;k<j;k++) { // 枚举分割点，构造状态转移方程 3种情况
            dp[i][j] = [min/max](dp[i][j], dp[i][k] ? dp[k + 1][j] ? w[i][j]);
                                           dp[i][k] ? dp[k][j] ? w[i] ? w[k] ? w[j]);
                                           dp[k-1] ? dp[k] ? dp[k+1]);
        }
    }
}

[i,k][k+1,j] 对两个区间进行合并 k只能严格在某一边要么在左要么在右习惯在左从实际含义出发最小情况是 k=i k+1=j时把两个单独的石子进行合并最小区间长度为1 所以枚举区间从1~n 内部特判为if(len==1) 分割点在i,j范围内状态转移左价值加右价值加该步价值

for(int len=1;len<=n;len++){//最小区间为1 最大为n
    for(int i=1;i+len-1<=n;i++){//枚举起点
        int j=i+len-1;//计算终点
        if(len==1){//最小区间特判
            f[i][j]=?;
            continue;
        }
        for(int k=i;k<=j-1;k++){//枚举分割点 状态转移
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
    }
}

环形翻倍再做

[i,k][k,j] ab bc 合并成ac b公用最小区间长度应该是2 实际变成合并n+1个石头

for(int len=2;len<=n+1;len++){
    for(int i=1;i+len-1<=n*2;i++){
        int j=i+len-1;
        if(len==2){
            f[i][k]=?;
            continue;
        }
        for(int k=i+1;k<j;k++){
            f[i][k]=max(f[i][j],f[i][k]+f[k][j]+w[i]*w[k]*w[j]);
        }
    }
}

[i][j][k] 树状左中右中间部分另算最小区间为1

for(int len=1;len<=n;len++){
    for(int i=1;i+len-1<=n;i++){
        int j=i+len-1;
        if(len==1){
            f[i][j]=w[i];
            g[i][j]=i;
            continue;
        }
        for(int k=i;k<=j;k++){//k可能在边界 特判
            f[i][j]=max(f[i][j],((k==i?1:f[i][k-1])*(k==j?1:f[k+1][j])+w[k]));
        }
    }
}

N<=1000

二分

关键字最大最小数据范围 1000~100000 考虑二分思路答案能不能套出来？具不具有二段性？即随便套了一个答案发现小了能不能往大的找

两个模版

---- |----  找最小(最左边)
int l=0,r=N;
while(l<r){
    int m=l+r>>1;
    if(check(m))
        r=mid;
    else
        l=mid+1;
}
return r;
SL(0,n-1,k)
等价于 lower_bound(nums,nums+n,k)-nums;
       返回的是指针 减去首地址即为答案下标

----| ---- 找最大(最右边)
int l=0,r=N;
while(l<r){
    int m=l+r+1>>1;
    if(check(m))
        l=mid;
    else
        r=mid-1;
}
return r;
等价于 upper_bound(nums,nums+n,k)-nums-1;

升序数组中
upper_bound(a.begin(), a.end(), x); 查找第一个 > x的元素
lower_bound(a.begin(), a.end(), x); 查找第一个 >= x的元素
降序数组中：
upper_bound(a.begin(), a.end(), x, greater<type>()); 查找第一个 < x的元素
lower_bound(a.begin(), a.end(), x, greater<type>()); 查找第一个 <= x的元素

dp

见n<=100

dijkstra

正权边最短路贪心思想

#include<bits/stdc++.h>
using namespace std;

const int N=510;
int n,m;
int g[N][N];//稠密图用邻接矩阵
int dist[N];//起点到各点的距离
bool st[N];

int dijkstra(){
    //距离初始化成正无穷
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;//起点距离初始化为0 以它为中心 找其他点

    for (int i = 0; i < n - 1; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ ) //找到一个离该点最近的点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        for(int j = 1; j <= n; j ++ ) //以新点为中心更新距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f)
        return -1;
    return dist[n];

}
int main()
{
    scanf("%d%d", &n, &m);
    memset(g,0x3f,sizeof g);
    while(m--){//读入m条边
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        //a和b间可能有多条边 保留最短的就够了
        g[a][b]=min(g[a][b],c);
    }
    printf("%d\n", dijkstra());
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;

const int N=1e6+10;
int n,m;
int h[N],w[N],e[N],ne[N],idx;//稀疏图用邻接表 比之前多了一个W[]表示权
int dist[N];
bool st[N];

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    //优先队列（小根堆）里面存距离和点 队头永远是最小的 所以可以直接取出来操作
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});//把距离0 第一个点 放入小根堆
    while(!heap.empty()){
        //取队头 也就是最近的一个点 把它加入集合
        auto t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        if(st[ver])
            continue;
        st[ver]=true;

        //根据这个点进行拓展
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[ver]+w[i] < dist[j]){
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)
        return -1;
    return dist[n];

}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra();
    return 0;
}

prim

最小生成树

#include<bits/stdc++.h>
using namespace std;

const int N=510,INF=0x3f3f3f3f;
int n,m;
int g[N][N];//稠密
int dist[N];
bool st[N];

int prim(){
    memset(dist,0x3f,sizeof dist);
    int res=0;

    //集合最初为空 在里面加点 所以0~n
    for(int i=0;i<n;i++){
        int t=-1;
        //找到一个不在集合中的最近的点 加入集合
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1 || dist[t]>dist[j]))
                t=j;

        if(i && dist[t]==INF)
            return INF;
        //先标记再更新（防止环）
        if(i)
            res+=dist[t];
        st[t]=true;

        //更新其他点到加入该点后的集合的距离（其实就是以该点为中心更新距离）
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}

int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
    if(t==INF)
        puts("impossible");
    else
        cout<<t;
    return 0;
}

Bellman-Ford

负权边最短路 dp思想

#include<bits/stdc++.h>
using  namespace std;

const int N=510,M=10010;//点数500，边数10000 稠密图
int n,m,k;
int dist[N],backup[N];//距离和备份数组

//虽然为稠密图 但是并不用矩阵去存储
//用结构体数组去存储边（起点终点权）
//然后直接遍历这个结构体数组
struct Edge{
    int a,b,w;
}edges[M];

void bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i=0;i<k;i++){
        //迭代前 备份上一次的结果
        /*
        在进行第k次遍历的时候，如果我们更新a->b的边，得到dist[b],
        在更新b->c的边的时候，如果使用了已经更新的dist[b]去更新dist[c]，
        其实是遍历了两条边，但bellman_ford算法在每一次遍历的时候，
        只允许更新一条边，所以需要用一个backup数据，
        保证不会发生一次遍历中更新多条边
        */
        memcpy(backup,dist,sizeof dist);

        for(int j=0;j<m;j++){
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
}

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }

    /*
    是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，
    而并非是if(dist[n] == INF)判断，
    原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，
    dist[n]大于某个与INF相同数量级的数即可
    */
    bellman_ford();
    if(dist[n]>0x3f3f3f3f/2)
        puts("impossible");
    else
        printf("%d\n",dist[n]);

    return 0;
}

N<=1e4

块状链表

分块

莫队

N<=1e5

贪心，sort，heap

贪心问题没什么迹可寻一般就是排个序区间模型里的左右端点排序哈夫曼模型的堆排序短作业优先重权值优先的sort排序中位数平均数的sort排序一种奇怪的是短视把较长的选择缩小成小选择逢升就卖

数据范围还是蛮大的到了1e6 到了这个数据范围确实没什么可写了就想一下贪心能不能行后面几题的话想不出来写法其实就可以直接蒙贪心反正不亏

主要熟悉排序的自定义

单关键字
sort(a.begin(),a.end(),greater<int>);

struct People{
    string name;
    int score;
    // 默认<表升序 重载变降序
    bool operator<(const Peoplet& rhs) const {
        return score > rhs.score;
    }
};
vector<People> a;
sort(a.begin(),a.end());

struct {
    bool operator()(int a, int b) const{
        return a < b;
    }
}cmp;
sort(a.begin(),a.end(),cmp);

多关键字
struct Product {
    string name;
    int sales;
    double rating;

    //先按销量降序 再按评分降序
    bool operator<(const Product& rhs) const {
        if (sales != rhs.sales)
            return sales > rhs.sales;
        return rating > rhs.rating;
    }

};

bool compareProduct(const Product& a, const Product& b) {
    if (a.sales != b.sales)
        return a.sales > b.sales;
    return a.rating > b.rating;
}
sort(products.begin(), products.end(), compareProduct);

优先队列
//升序队列 小顶堆 great小到大
priority_queue <int,vector<int>,greater<int>> minheap;

//降序队列 大顶堆 Less大到小 默认
priority_queue<int,vector<int>,less<int>> maxheap;
priority_queue<int> maxheap;

struct node1{
    int x,y;
    bool operator<(const node1& other)const{
        return x<other.x;
    }
};
priority_queue<node1> maxheap;

struct node2{
    int x,y;
    bool operator<(const node2& other)const{
        return x>other.x;
    }
};
priority_queue<node2> minheap;

struct Person {
    string name;
    int age;
    Person(string n, int a) : name(n), age(a) {}
};
struct CompareAge_max {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age; // 较大的年龄优先
    }
};
struct CompareAge_min {
    bool operator()(const Person& a, const Person& b) {
        return a.age > b.age; // 较大的年龄优先
    }
};
priority_queue<Person, vector<Person>, CompareAge_max> people_maxheap;
priority_queue<Person, vector<Person>, CompareAge_min> people_minheap;

//默认都是Less
sort(vec.begin(),vec.end(),less<int>());//内置类型从小到大升序
priority_queue <int,vector<int>,less<int> > pql;//top出数据从大到小降序
sort(vec.begin(),vec.end(),greater<int>());//内置类型从大到小降序
priority_queue<int,vector<int>,greater<int>>pqg;//top出数据从小到大升序

struct node{
    int x,y;
}point;
bool operator<(const node &a,const node &b)
{
    if(a.x==b.x)
        return a.y>b.y;
    else
        return a.x<b.x;
}
priority_queue<node> Q;

set，map

set 特点：set是一个存储唯一键值的有序容器。它不允许存储重复的元素。底层实现：通常基于红黑树，元素按照特定顺序排序。用途：适用于需要有序不重复元素集合的场景。

multiset 特点：与set类似，但它允许存储重复的元素。底层实现：同样基于红黑树，元素自动排序。用途：适用于需要有序可重复集合的场景。

unordered_set 特点：存储唯一键值的无序容器，不允许重复元素。底层实现：基于哈希表，元素无序存储。用途：适用于追求高效插入、删除和查找操作的场景，不关心元素顺序。

map 特点：存储键值对，键唯一，自动根据键排序。底层实现：通常基于红黑树。用途：当需要根据键快速查找值时使用，适合需要有序键值对的场景。

multimap 特点：与map类似，但允许键重复，即一个键可以映射多个值。底层实现：基于红黑树，元素自动按键排序。用途：适用于需要将单个键映射到多个值的有序键值对集合场景。

unordered_map 特点：存储键值对，键唯一，但存储无序。底层实现：基于哈希表。用途：当不需要元素排序，且追求高效的插入、删除和查找操作时使用。

有序与无序： set、multiset、map、multimap是有序容器，根据元素或键的顺序自动排序；而unordered_set和unordered_map是无序容器，存储元素时不考虑顺序。

唯一与非唯一： set和unordered_set只允许存储唯一元素，map和unordered_map的键是唯一的；而multiset和multimap允许存储重复的元素或键。

底层数据结构：有序容器通常基于红黑树实现，保证了元素的有序性和较高的操作效率；无序容器基于哈希表实现，提供了快速的访问速度。

二分

见n<=1000

spfa

最短路
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    queue<int> q;
    q.push(1);
    while(!q.empty()){
        auto t=q.front();
        q.pop();

        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[t]+w[i] < dist[j]){
                dist[j]=dist[t]+w[i];
                if (!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);

    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    int ans=spfa();
    if(ans==0x3f3f3f3f)
        cout<<"impossible"<<endl;
    else
        cout<<ans<<endl;
    return 0;
}

判负环
#include<bits/stdc++.h>
using namespace std;

const int N=2010,M=10010;
int h[N],w[M],e[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];
int n,m;

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool spfa(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        st[i]=true;
        q.push(i);
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)
                    return true;
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    if(spfa())
        puts("Yes");
    else
        puts("No");
    return 0;
}

dijkstra,prim-heap

见n<=1000

线段树

树状数组

凸包

半平面交

N<=1e6

双指针

（1）前后指针在一个区间里面用i和j维护一个答案区间当答案不在区间内的时候再移动ij指针使得答案包含在内

for(int i=0,j=0;i<n;i++){
    if(!s[a[i]])
        cnt++;
    s[a[i]]++;
    while(cnt>2){
        s[a[j]]--;
        if(!s[a[j]])
            cnt--;
        j++;
    }
    res=max(res,i-j+1);
}

在这里面有一个特殊的问题判断环路——快慢指针

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
              slow = slow->next;
              fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

（2）对撞指针利用单调性用俩指针（一个最大一个最小）去找到某个值（和）根据值的情况调动指针可以用在一个区间也可以用在两个区间里面本质一样

for(int i=1,j=N-1;i<N;i++){
    while(j>=1 && a[i]+a[j]>x)
        j--;
    if(j>=1 && a[i]+a[j]==x){
        cout<<"YES"<<endl;
        return 0;
    }
}
cout<<"NO"<<endl;
return 0;

（3）两个序列的匹配前提是单调性 j在走后不会回头然后就是和第一类差不多找满足某个性质典型的就是找到小于a[i]的最大的一个b[j](与二分功能相似）

/*
    int i=0,j=0;
    while(i<n && j<m)
    {
        if(a[i]==b[j])
            i++;
        j++;
    }
*/
    int i=0;
    for(int j=0;j<m;j++)
    {
        if(i<n && a[i]==b[j])
            i++;
    }

并查集

用一个数组去记录各点的祖宗结点是什么下标标识各个点本身一开始所有点都是独立的就把各下标对应的father都设为本身要使某点从属入某集合就直接在该点的fa[]存放另一结点当然优化时做了数组中不记录直接父节点而是记录祖宗结点所以在进行合并操作时要先进行find操作找到祖宗结点再把祖宗结点插入到另一个集合的祖宗结点下实现合并 fa[find(a)]=find(b); 而判断两个结点是否从属一个集合要做的就是比较一下祖宗结点是否相等 if(find(a)==find(b)) 显然核心就在于这个find() //返回x所在集合的编号（祖宗结点） int find(int x){ if(fa[x]!=x) fa[x]=find(fa[x]);//路径压缩优化 return fa[x]; } 递归的过程中让直接存上祖宗结点

#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int fa[N];

//返回x所在集合的编号（祖宗结点）
int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);//路径压缩优化
    return fa[x];
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;//初始化 让父节点指向自己
    }
    while(m--){
        char op[2];
        int a,b;
        cin>>op>>a>>b;
        if(op[0]=='M'){
            fa[find(a)]=find(b);//让a的祖宗结点等于b的祖宗结点 把a插在b里面
        }
        else{
            if(find(a)==find(b))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }

    return 0;
}

哈希

离散化

手写离散化本质是把下标做值存在从0开始的数组里这样就可以得到一个新的下标为了使这些下标唯一映射要进行排序去重核心就在于find find使得真实下标和映射下标得到了对应只有对应了离散化才具有意义用法大概是找原区间里某个数的映射出的新下标在这个新下标处干一些事情把每一步的意义记清楚不然容易晕头转向的

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=300010;//插入：10万 l：10万 r：10万 最大可能30万

int a[N],s[N];//a存的all中对应下标映射到原数轴对应的值 s为a求前缀和的数组
//存储（所有与插入和查询有关的）坐标
vector<int> alls;
//要进行两种操作 添加、查询 这两种操作都有两个数据 某位置插几、左右区间
//所以可以把这些待操作数作为一对pair来存入vector
vector<PII> add,query;

int find(int x)
{
    //find做的就是让a数组的下标与alls数组下标对应 但是alls存的是下标 而a是有意义的值
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=x)
            r=mid;
        else
            l=mid+1;
    }
    //这里映射为1完全是为了后面做前缀和操作 如果没这需求就直接一一对应就完事了
    return r+1;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int x,c;//在x处插入c 这个x为数轴有值的下标 要放入alls中
        cin>>x>>c;
        add.push_back({x,c});

        alls.push_back(x);
    }
    for(int i=0;i<m;i++)
    {
        int l,r;//这俩下标都是要用的 所以也要放在alls中
        cin>>l>>r;
        query.push_back({l,r});

        alls.push_back(l);
        alls.push_back(r);
    }
    //此时 alls数组中已经有了所有要用的下标 对它进行去重排序
    sort(alls.begin(),alls.end());
    //unique把不重复的放前面 重复了的放后面 返回不重复区间的末尾
    //那么直接把unique返回的迭代器作为起始 把alls.end()为结束 删除这部分 就实现了去重
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    //处理添加操作
    for(auto item:add)
    {
        int x=find(item.first);
        a[x]+=item.second;        //注意这里 错两次了 他可能在同一个位置插入几次 所以是+=
    }

    //把a[]做前缀和 得到s[]
    for(int i=1;i<=alls.size();i++)
        s[i]=s[i-1]+a[i];

    //处理询问操作
    for(auto item:query)
    {
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }

    return 0;
}

stl

unordered_map

insert({key, value}) 或 emplace(key, value): 向映射中插入键值对。

find(key): 	查找键key，如果找到，返回一个指向该键值对的迭代器；
            如果未找到，返回end()迭代器。

erase(key): 从映射中删除键为key的元素。

operator[key]: 访问键key对应的值。如果key不存在，将会插入一个新的元素。

count(key): 返回映射中等于key的元素的数量。对于unordered_map，结果为0或1，因为键是唯一的。

size(): 返回映射中元素的数量。

empty(): 检查映射是否为空。

插入：将("ABC" -> 5.45)插入unordered_map<string, double> hash中hash["ABC"]=5.45
查询：hash["ABC"]会返回5.45
判断key是否存在：hash.count("ABC") != 0 或 hash.find("ABC") != hash.end()
遍历
for (auto &item : hash){
     cout << item.first << ' ' << item.second << endl;
}
或
for (unordered_map<string, double>::iterator it = hash.begin(); it != hash.end(); it ++ {
     cout << it->first << ' ' << it->second << endl;
}

字符串哈希

用P进制换10进制的方式 P取经验值 131 即131进制的数转变成10进制(把字符串当成一个131进制数) 模上\(2^{64}\)等价于一个8字节的东西溢出直接用unsigned long long存将本该是问题的溢出巧妙转变成对\(2^{64}\)取模由此可以处理出所有字符串的一个哈希值为了求某一段显然是前缀和问题预处理出所有前缀字符串的哈希值的前缀和数组求某一段s[r]-s[l] 发现错了几位得把前缀（l）部分左移到与r 的高位匹配位置上去（后几位补0）左移一次就是p 左移两位就是\(p^2\) 以此类推要让l与r对齐实际上是要左移r-l+1位要快速求到\(p^{r-l+1}\) 每一位是乘上一个p的n次方可以把p预处理出来

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int N=100010,P=131;
char str[N];
ULL h[N],p[N];
int n,m;

ULL get(ULL h[],int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
    cin>>n>>m;
    cin>>str+1;
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*P+str[i];
        p[i]=p[i-1]*P;
    }

    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(h,l1,r1)==get(h,l2,r2))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

KMP

下标从1开始
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ ){
        while (j && p[i] != p[j + 1])
            j = ne[j];
        if (p[i] == p[j + 1])
            j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ ){
        while (j && s[i] != p[j + 1])
            j = ne[j];
        if (s[i] == p[j + 1])
            j ++ ;
        if (j == n){
            //匹配成功的操作
            //printf("%d ", i - n);
            //……
            j=ne[j];//还原现场 因情况而定 可以省略 也可能是从头开始 j=0;
        }
    }
    return 0;
}

下标从0开始
#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

int n, m;
char s[N], p[N];
int ne[N];

int main()
{
    cin >> m >> p >> n >> s;

    ne[0] = -1;
    for (int i = 1, j = -1; i < m; i ++ ){
        while (j >= 0 && p[j + 1] != p[i])
            j = ne[j];
        if (p[j + 1] == p[i])
            j ++ ;
        ne[i] = j;
    }

    for (int i = 0, j = -1; i < n; i ++ ){
        while (j != -1 && s[i] != p[j + 1])
            j = ne[j];
        if (s[i] == p[j + 1])
            j ++ ;
        if (j == m - 1)
        {
           //匹配成功的操作
            //printf("%d ", i - n);
            //……
            j = ne[j];//还原现场 因情况而定 可以省略 也可能是从头开始 j=0;
        }
    }
    return 0;
}

AC自动机

其他

常数较小的O(nlogn)也能做如 sort 树状数组 heap dijkstra spfa 见1e5

N<=1e7

筛法

埃氏筛
从2开始 把所有质数的倍数都筛掉 没被筛的就是质数 保存起来
void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i]){ //可以用质数就把所有的合数都筛掉;
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i)
                st[j]=true;
        }
    }
}
//用set方便些
set<int> primes;
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!isnot_prime[i]){
            primes.insert(i);
            for(int j=i;j<=n;j+=i)
                isnot_prime[j]=true;
        }
    }
}

线性筛
只需要用最小的质因数进行筛除
注意避免重复标记if(i%primes[j]==0)
10^7用线性筛
void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i])
            primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)
                break;
        }
    }
}

区间筛
一个指定的区间 [L, U] 内筛选出所有的素数
与传统的埃拉托斯特尼筛法或线性筛法不同
区间筛专注于一个特定的区间
而不是从最小的素数开始对一个连续的整数序列进行筛选
这使得区间筛在处理大数值区间的素数查询时更加高效
（数据范围很大时 传统的从2开始的筛法就不符事宜了）

1. 筛选小于等于 sqrt{U} 的素数：
    使用传统的埃筛或线筛筛出所有小于等于sqrt{U}的素数
    区间[L, U]内的任何合数都可以被不大于sqrt{U}的素数筛去

2. 区间内素数筛选：
    用得到的素数来筛选区间 [L, U] 内的素数
    对于每一个小于等于sqrt{U}的素数p
    找到它在区间[L,U]内的最小倍数
    如果 L 不是 p 的倍数，则是下一个最近的 p 的倍数
    然后从这个最小倍数开始，步进为 p，去除区间内所有 p 的倍数

const int N = 1e6 + 10; // 适用于大多数情况
bool isPrime[N]; // 标记数组
vector<int> primes; // 存储小于等于 sqrt(U) 的素数

// 获取小于等于 n 的所有素数
void getPrimes(int n) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false; // 0 和 1 不是素数
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = 2 * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// 区间筛，筛选 [L, U] 内的素数
void segmentSieve(long long L, long long U) {
    memset(isPrime, true, sizeof(isPrime));
    if (L < 2)
        L = 2;
    for (int p : primes) {
        if ((long long)p * p > U)
            break;
        long long start = max((long long)p * p, (L + p - 1) / p * p);
        for (long long j = start; j <= U; j += p) {
            isPrime[j - L] = false;
        }
    }

    for (long long i = 0; i <= U - L; i++) {
        if (isPrime[i])
            cout << (L + i) << endl; // 输出区间 [L, U] 内的素数
    }
}

int main() {
    int L, U;
    cin >> L >> U; // 输入区间
    getPrimes((int)sqrt(U) + 1); // 预筛小于等于 sqrt(U) 的素数
    segmentSieve(L, U); // 筛选区间 [L, U] 内的素数
    return 0;
}

双指针 KMP AC自动机

见1e6

N<=1e9

约数

试除法判断约数
从1到n枚举 找可以被n整除的数
又因为是成对出现的 所以又能缩小到求一半 另一半可以通过n/i求出来
set自动排序加去重
set<int> get_divisors(int n){
    set<int> res;
    for(int i=1;i<=n/i;i++){
        if(n%i==0){
            res.insert(i);
            res.insert(n/i);
        }
    }
    return res;
}

约数个数
类似排列问题
先求出所有的质因数 再使用 质因数的权值（指数）相乘 来计算出总个数
把一个数N 写成：N = (p_1^{x1})(p_2^{x2})(p_3^{x3})…(p_k^{xk})，其中pi为质数
则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)
unordered_map<int,int> weight;
      for(int i=2;i<=n/i;i++){
          while(n%i==0){
              weight[i]++;
              n/=i;
          }
      }
      if(n>1)
          weight[n]++;

     for(auto x:weight){
        res=res*(x.second+1);
    }

约数之和
同上 求出所有质因数
然后对于 每个基数都从 0~指数 累加起来 再进行相乘
把一个数N 写成：N = (p_1^{x1})(p_2^{x2})(p_3^{x3})…(p_k^{xk})，其中pi为质数
这N个约数之和为 (p_1^0+p_1^1+……+p_1^{x1})*……*(P_k^0+p_k^1+……+p_k^{xk})
至于怎么算某一个(P_k^0+p_k^1+……+p_k^{xk})
可以用秦九韶算法 也可以用一个temp每轮增长*base 再或者还可以用快速幂 以及等比数列公式……
unordered_map<int,int> weight;
        for(int i=2;i<=n/i;i++){
            while(n%i==0){
                weight[i]++;
                n/=i;
            }
        }
        if(n>1)
            weight[n]++;

    LL res=1;
    for(auto prime:weight){
        int base=prime.first,index=prime.second;
        LL temp=1,sum=1;
        while(index--){
            temp=temp*base%mod;
            sum=(sum+temp)%mod;
        }
        res=res*sum%mod;
    }
    cout<<res;

/*
//秦九韶
    LL res=1;
    for(auto prime:weight){
        int base=prime.first,index=prime.second;
        LL temp=1;
        while(index--){
            temp=(temp*base+1)%mod;
        }
        res=res*temp%mod;
    }
    cout<<res;
*/

在一堆数中找每个数在这堆数中有多少个约数如果我们想知道一个数 N 有多少个约数，我们不需要一个个检查每个数是否能整除 N，而是可以用倍数的思想来优化这个过程。（类似于阶乘分解）用count[]记录每个数在这堆数中的约数数量它的约数一定会它的倍数约所以它的约数数量可以同步累加进它的倍数的约数数量里面去把每个数当成被约的数从它入手同步更新所有倍数的数量而不是累加完后把每个数当成约其他数的数再去遍历判断可约的数的数量从按列算转变成按行算大大提高速度

初始化一个数组来记录每个数的约数计数。
遍历每个数，对于每个数，遍历它的所有倍数，并将当前数的出现次数累加到这些倍数的约数计数上。
一旦所有数都被处理过，每个数的约数计数就可以从数组中获得。

const int MAX_N = 1e6 + 10;
//每个数字的约数数量
vector<int> divisor_count(MAX_N, 0);
// 计算每个数的约数数量
void calculate_divisors(int n) {
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            divisor_count[j]++; // i 是 j 的一个约数
        }
    }
}
    // 每个数的约数数量
    for (int i = 0; i < n; ++i) {
        cout << "Number " << numbers[i] <<
                " has " << divisor_count[numbers[i]] << " divisors." << endl;
    }

质数

合数成对出现只需判断前半段使用i≤n/i 效率高于sqrt(n) 避免出现i*i≤n的越界危险

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i <= n / i;i ++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

分解质因数

质因数的底数和指数：底数指质数的基数比如在分解12=223中 2和3就是底数而指数是指底数出现的次数 2出现了两次所以指数是2

x 的质因子最多只包含一个大于根号x 的质数如果有两个这两个因子的乘积就会大于 x 矛盾所以借鉴之前的思路只需要枚举sqrt(x) i 从 2 遍历到根号x 用 x / i，如果余数为 0，则 i 是一个质因子 s 表示质因子 i 的指数，x /= i 为 0，则 s++， x = x / i 最后检查是否有大于根号x 的质因子，如果有，输出（如果有只会有一个）

void divide(int x){
    for (int i = 2; i <= x / i; i ++ ){//i <= x / i:防止越界，速度快于 i < sqrt(x)
        if (x % i == 0){//i为底数
            int s = 0;//s为指数
            while (x % i == 0)
                x /= i, s ++ ;
            cout << i << ' ' << s << endl;//输出
        }
    }
    if (x > 1)
        cout << x << ' ' << 1 << endl;//如果x还有剩余，单独处理
    cout << endl;
}

//或者
for(int i=2;i<=n/i;i++){
    while(n%i==0){
        h[i]++,n/=i;
    }
}
if(n>1)
    h[n]++;//大于sqrt(n) 的质因子 要么没有 要么只有一个

阶乘分解

求8!中的质因数分解先针对单独的一个质因子2来说 1 2 3 4 5 6 7 8 乘完之后一直while去模上2 就可以得到2的数量 2作为底数数量作为指数可以抽象成是一种按列算的方式这里的阶乘特化可以以一种按行算的角度来看问题 1 2 3 4 5 6 7 8 我们求得在8！中2的个数 1 1 1 1 首先我们先计算出2的倍数的个数：8/2=4

  1       1 其次我们计算出4的倍数的个数： 8/4=2（上面求出了第一层，现在求第二层）

          1 最后我们解出第三层的2的个数： 8/8=1

我们把4+2+1=7，所以一共7个2出现了。

即：cnt(x)=[n/(x^1)]+[n/(x^2)]+[n/(x^3)]+...(直到x的次方大于n)

const int N=1e6+10;
bool isnot_prime[2*N];
set<int> get_primes(int n){
    set<int> primes;
    for(int i=2;i<=n;i++){
        if(!isnot_prime[i]){
            primes.insert(i);
            for(int j=i;j<=n;j+=i)
                isnot_prime[j]=true;
        }
    }
    return primes;
}

// 计算N!的质因数分解
void factorize_factorial(int n, const set<int>& primes) {
    for (int p : primes) {
        if (p > n)
            break;
        int count = 0;
        for (long long k = p; k <= n; k *= p) {
            count += n / k;
        }
        cout << p << " " << count << endl;
    }
}

N<=1e18

gcd、lcm

最大公因数对（a， b）连续使用辗转相除直到小括号内右边数字b为0 左边的数a 就是两数最大公约数

    while(b){
        int c=a%b;
        a=b;
        b=c;
    }
    cout<<a<<endl;

//或者
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

//另外还有库函数 __gcd
cout<<__gcd(a,b)<<endl;

最小公倍数 lcm a*b/gcd(a,b)

LL lcm(LL a,LL b){
    return (a*b)/gcd(a,b);
}

// 计算三个数的最大公约数
int gcd(int a, int b, int c){
    return gcd(gcd(a, b), c);
}

// 计算三个数的最小公倍数
int lcm(int a, int b, int c){
    return lcm(lcm(a, b), c);
}

快速幂

把指数 k 当成二进制进行处理预处理出\(a^{2^0},a^{2^1},a^{2^2},…,a^{2^{log_k}}\)这k个数将\(a^k\)用\(a^{2^0},a^{2^1},a^{2^2},…,a^{2^{log_k}}\)这k种数来组合如何组合（判断某位用不用？）某位为1 就用为0 就不用两个问题 1、如何预处理出来\(a^{2^0},a^{2^1},a^{2^2},…,a^{2^{log_k}}\) 2、如何取得处理k的每一位

1、\(a^{2^0},a^{2^1},a^{2^2},…,a^{2^{log_k}}\)的每一位都是前一位 \(*a\) 而每一次只需要用到上一次的结果所以没必要把所有的数都存下来只需要用一个变量a 这个a每轮不管被没被选都累乘上a

2、二进制里了解到直接k不断取得最后一位然后划掉最后一位 while(k) if(k&1) …; k>>=1;

long long qmi(long long a,int k,int p){ //注意a要传入long long  a是指数级增长的 容易爆int
    long long res=1%p;  //防止p=1 res=1%1=0 而不是 1
    while(k){
        if(k&1)
           res=res*a%p;
        k>>=1;
        a=a*a%p;   //不传long long 的话 这里用 a=(long long)a*a%p;
    }
    return res;
}

N<=1e1000

是位数不超过10的几次方还是范围不超过10的几次方

int_128

int: 2147483648, 即 \(2^{31}≈ 2×10^{10}\) long long ：9223372036854775807 , 即 \(2^{63}≈9×10^{19}\) _int128的最大值是：85070591730234615865843651857942052864 , 约为 \(10^{38}\) 换算成位的话大概就是能表示38位的10进制数字

在大部分时候是可以解决高精度问题的除非说什么涉及到 \(10^{几百位}\) 这样的数

#include <bits/stdc++.h>
using namespace std;

typedef __int128 LL;

LL read() {
    LL x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * f;
}

void write(LL x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    LL a = read();
    LL b = read();

    LL sum = a + b;
    LL del = a - b;
    LL mul = a * b;
    LL div = a / b;
    LL mod = a % b;

    cout<<"sum: "; write(sum); cout<<endl;
    cout<<"del: "; write(del); cout<<endl;
    cout<<"mul: "; write(mul); cout<<endl;
    cout<<"div: "; write(div); cout<<endl;
    cout<<"mod: "; write(mod); cout<<endl;

    putchar('\n');
    return 0;
}

高精度模拟

超过38位只能上高精度了

高加加法不外乎就是从低位开始加每一位其实就是上一位的进位 + A的该位（如果存在）+ B的该位（如果存在）那么用一个数去记录这个和个位其实就是当前位的值十位（如果存在）其实就是对下一位的进位

#include<bits/stdc++.h>
using namespace std;

vector<int> add(vector<int> &A,vector<int> &B)
{//本质就是模拟加法竖式运算
    vector<int> C;
    //举个例子 79+23
    //先是个位9+3 得12 其中1是要进到下一位的 2才是本位的值
    //对于十位 实际上是7+2+1 为A的十位加B的十位加前面进的位
    //回到个位其实也是这样 只不过前面进的位为0罢了 （9+3+0）
    //再回到十位 7+2+1=10 这时已经加完了 1不能进入下一轮的加法 所以得拎出来 push_back(1)
    //so 每一位实际是 当前位加当前位加上一位的进位 可以把这个值使用t去存储 然后将t分解成两部分 作为当前位和进位
    int t=0;
    for(int i=0;i<A.size() || i<B.size();i++)
    {
        if(i<A.size())
            t+=A[i];
        if(i<B.size())
            t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t)//7+2+1的情况 最高位算完了 还有进位 但是循环已经结束 要自己补上1在最前面 但是因为逆序 所以补在vector后面
        C.push_back(1);
    return C;
}

int main()
{
    //将大整数逆序存在vector中 因为如果要进位的话 末尾加1比开头加1要方便得多
    string a,b;
    vector<int> A,B;
    cin>>a>>b;

    for(int i=a.size()-1;i>=0;i--)
        A.push_back(a[i]-'0');

     for(int i=b.size()-1;i>=0;i--)
        B.push_back(b[i]-'0');

    auto C=add(A,B);

    //记得取出来的时候也是要逆着取
    for(int i=C.size()-1;i>=0;i--)
        printf("%d",C[i]);
    return 0;
}

高减当前位等于 a的当前位*10 - b的当前位 - 上一位借的位（没借为0 借了为1）借的位为 a-b的结果大于0 说明无需借为0 小于0 说明需要借为1 当然为避免负值采用先判断大小让计算始终是大的减小的如果要求是小的减大的则计算大的减小的把结果加个负号

#include<bits/stdc++.h>
using namespace std;

bool cmp(vector<int> &A,vector<int> &B)
{
    //先比较位数 如果位数不等 直接返回A.size>B.size的判断结果 ture or false
    if(A.size()!=B.size())
        return A.size()>B.size();
    //如果位数相等 就逐个比 找到那个不同的数 返回A[i]>B[i]的判断结果
    for(int i=A.size()-1;i>=0;i--)
    {
        if(A[i]!=B[i])
        {
            return A[i]>B[i];
        }
    }
    return true;
}

vector<int> sub(vector<int> &A,vector<int> &B)
{
    vector<int> C;

    int t=0;
    //A的size一定大于B的size了 所以以A.size作为循环条件
    //1234 存在数组为 [0]:4 [1]:3 [2]:2 [3]:1
    //运算就是从低位开始算 [0]-[0]再考虑[1]-[1]
    //所以这里for循环用0~A.size
    for(int i=0;i<A.size();i++)
    {
        t=A[i]-t;
        if(i<B.size())
            t-=B[i];
        C.push_back((t+10)%10);
        if(t<0)
            t=1;
        else
            t=0;
    }

    //还要去掉前导0 比如123-120 得到的会是003 但想要的应该是3
    while(C.size()>1 && C.back()==0)
        C.pop_back();

    return C;
}

int main()
{
    string a,b;
    vector<int> A,B;
    cin>>a>>b;

    for(int i=a.size()-1;i>=0;i--)
        A.push_back(a[i]-'0');

     for(int i=b.size()-1;i>=0;i--)
        B.push_back(b[i]-'0');

    //比较一下大小 做运算时始终是大的减小的（更好算）如果要求是小减大就变成大减小 结果填负号
    if(cmp(A,B))
    {
        auto C=sub(A,B);
        for(int i=C.size()-1;i>=0;i--)
            printf("%d",C[i]);
    }
    else
    {
        auto C=sub(B,A);
        cout<<"-";
        for(int i=C.size()-1;i>=0;i--)
            printf("%d",C[i]);
    }

    return 0;
}

高乘每一位等于（当前位 * x + 上一位进位）% 10 进位等于（当前位 * x + 上一位进位）/ 10

#include<bits/stdc++.h>
using namespace std;

//123*9
//3*9=27 7为当前位 进2  t%10 t/10
//2*9+2=20 0为当前位 进2
//1*9+2 11 1为当前位 进1
//得1107
//跟加法类似 就是一个取模得当前位 取余得进位的循环
//与手动计算乘法不一样的是 被乘数不是拆开来算的 而是当成一个整体
//比如 123*12 也是3*12=36 当前位6 进3 这样的一个过程
//需要注意的还有一点 循环截止条件不仅有高精度数取完
//还有一个就是最后要进位的情况 它是push_back在最后
//可以合并在一起 放在循环中 i<A.size() || t存在
vector<int> mul(vector<int>& A,int b)
{
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size() || t;i++)
    {
        if(i<A.size())
            t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    //同理 要去除前导0
    while(C.size()>1 && C.back()==0)
        C.pop_back();
    return C;
}

int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i=a.size()-1;i>=0;i--)
        A.push_back(a[i]-'0');

    auto C=mul(A,b);

    for(int i=C.size()-1;i>=0;i--)
        printf("%d",C[i]);

    return 0;
}

高除与之前不同这里从高位开始算每位等于（前一位除以x的余数10 +当前位）除以 x 留给下一位的就是这个（前一位除以x的余数10 +当前位）模上x

#include<bits/stdc++.h>
using namespace std;
//除法的话正着存其实会更好算些 但是因为这种高精度的计算要出现的话往往是同时出现
//所以为了统一 对于除法也用这种逆序储存
//123/3
//1/3=0 余1
//1*10+2 /3 =12 余0
//0*3+3 /3 =1 余0
//结果为41 余0
//注意的是 与加减乘不同 除是从高位开始算的
//每轮的被除数都是前轮的余数*10+当前位的数
//结果就是/b
//余数就是%b
//捋清楚其实也是很简单的一个循环
//最后要注意的就是 因为刚开始是从高位开始算的 而结果是push_back进去的 所以最后要反转一下C
//别忘了取出前导0的问题

vector<int> div(vector<int> &A,int b,int &r)
{
    vector<int> C;
    r=0;

    for(int i=A.size()-1;i>=0;i--)
    {
        r=r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }

    reverse(C.begin(),C.end());
    while(C.size()>1 && C.back()==0)
        C.pop_back();
    return C;
}

int main()
{
    string a;
    int b;
    cin>>a>>b;

    vector<int> A;
    for(int i=a.size()-1;i>=0;i--)
        A.push_back(a[i]-'0');

    int r;
    auto C=div(A,b,r);

    for(int i=C.size()-1;i>=0;i--)
        printf("%d",C[i]);
    cout<<endl<<r<<endl;

    return 0;
}

其他

前缀和与差分

一维前缀和下标1开始

s[i]=s[i-1]+x; or s[i]=s[i-1]+a[i]; or s[i]+=s[i-1];
s[r]-s[l-1];

二维前缀和

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }
}
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;

一维差分

void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}
for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
    insert(i,i,a[i]);
while(m--){
    int l,r,c;
    cin>>l>>r>>c;
    insert(l,r,c);
}
for(int i=1;i<=n;i++){
    //s[i]=s[i-1]+b[i]
    b[i]+=b[i-1];
}
for(int i=1;i<=n;i++){
    cout<<b[i]<<" ";
}

二维差分

void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        scanf("%d",&a[i][j]);
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        insert(i,j,i,j,a[i][j]);
    }
}
while(q--){
    int x1,y1,x2,y2,c;
    cin>>x1>>y1>>x2>>y2>>c;
    insert(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<b[i][j]<<" ";
    }
    cout<<endl;
}

日期问题

组合拳

int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool is_leap(int y){
    return y%100 && y%4==0 || y%400==0;
}

int get_days(int y,int m){
    return days[m]+(m==2 && is_leap(y));
}

void next_day(int &y,int &m,int &d){//注意 传的是引用
    d++;
    if(d>get_days(y,m)){
        d=1;
        m++;
        if(m>12){
            m=1;
            y++;
        }
    }
}

bool check_date(int y, int m, int d) {
    if (m < 1 || m > 12)
          return false;
    if(d < 1 || d > getdays(y,m))
          return false;
    return true;
}

while ((curYear < 给定年份) ||
       (curYear == 给定年份 && curMonth < 给定月份) ||
       (curYear == 给定年份 && curMonth == 给定月份 && curDay < 给定日子)) {
    // 执行 next_day 操作
}

单调栈

单调栈找最近

用于找每个数左/右边最近的比它小/大的数

(1)左边最近的小于它的数

从1~n遍历

序列应该是单调递增（保证栈头为最优解）

所以如果出现向下趋势就不断出栈

while(tt && x <= stk[tt])
    tt--;
//具体操作
//…… //把栈头作为答案保存
stk[++tt]=x;//把该元素入栈

(2)左边最近的大于它的数

从1~n遍历

序列应该是单调递减

所以如果出现向上趋势就不断出栈

while(tt && x >= stk[tt])
    tt--;
//具体操作
//…… //把栈头作为答案保存
stk[++tt]=x;//把该元素入栈

(3)右边最近的小于它的数

从n~1遍历

序列应该是单调递增

所以如果出现向下趋势就不断出栈

for(int i=n;i>=1;i--){
    while(tt && h[i] <= h[stk[tt]])
      tt--;
    //具体操作
    //…… //把栈头作为答案保存
    stk[++tt]=i;//把该下标入栈
}

(4)右边最近的大于它的数

从n~1遍历

序列应该是单调递减

所以如果出现向上趋势就不断出栈

for(int i=n;i>=1;i--){
    while(tt && h[i] >= h[stk[tt]])
      tt--;
    //具体操作
    //…… //把栈头作为答案保存
    stk[++tt]=i;//把该下标入栈
}

想清楚要找什么

考虑遍历方向

和答案应该是较大的还是较小的

较小的话栈里应该是单调递增这样才能保证栈顶是最合适的答案

较大的话反过来栈里应该是单调递减

单调栈+二分找最远

(1)左边最远的大于它的数

比如对于3来说如果左边已经有了5 在53中间再来一个4是完全没有必要的因为3肯定找到的是那个5 因为更大且更远由此发现是一个不出现递减趋势的序列

但个53中间有个7的话这个7虽然不会被3找到但是它可能会被后面的一个6找到

综上构造一个单调递增的序列

若这个新加的数能保持递增趋势说明不存在比它更大的数没必要去找了直接加进去供后面的数去找

如果不能保持递增趋势就说明左边有一个比它更大的数在这个已有的单调序列中二分找到

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    //需要注意的一点是 stk存的是下标
    for(int i=1;i<=n;i++){
        //a[i]>a[stk.back()] 还是 a[i]>=a[stk.back()]
        //加不加等号看题意
        //找严格小于它的数的话 这里加等号 意味着找到它自己
        //找前面小于等于它的数的话 这里不加等号
        if(stk.empty() || a[i]>=a[stk.back()]){//发现该元素比栈顶元素还大（保持单调递增）
            stk.push_back(i);//直接入栈
            ans[i]=i;//记录答案 可能求长度等等
        }
        else{//发现该元素不是最大  那么原单调序列里肯定存在一些比他大的数 二分找到最远的那个
            int l=1,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]>a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

(2)左边最远的小于它的数

同理现在找最小的数如果本身已经是最小了就没必要找直接加入单调栈保持单调性如果自身不是最小也不做什么踢出操作直接在单调栈里找答案就行只不过它也没必要加进去

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<=n;i++){
        if(stk.empty() || a[i]<a[stk.back()]){//只要改两处
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]<a[i]) //只要改两处
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

(3)右边最远的大于它的数

从右边开始枚举罢了 1-n变成n-1即可

找最远的大于若该数是最大的直接加入栈中如果不是再二分找一下

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=n;i>=1;i--){//只需改循环
        if(stk.empty() || a[i]>a[stk.back()]){
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]>a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

(4)右边最远的小于它的数

n-1 最小若该数为最小直接加入否则二分找

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=n;i>=1;i--){
        if(stk.empty() || a[i]<a[stk.back()]){
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]<a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

总结：

一个是以当前元素维护单调栈不断剔除里面元素使其保持单调性

一个是判断当前元素是否符合单调栈的特性符合就加入不符合可以直接在栈里找答案

单调队列

滑动窗口并不对应单调队列

滑动窗口问题可以用双指针和队列两种方式实现

单调队列只是针对这个窗口里的某个性质将不必要的元素舍去

从而能在O(1)的时间内找到这个最值

一般也就两个场景

找窗口的最小值

void get_min(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k)
            hh++;
        //求最小 递增区间 若出现向下 出队
        while(hh<=tt && a[i]<=a[q[tt]])
            tt--;
        q[++tt]=i;
        //当前区间的最大值为队头
        b[i] = a[q[hh]];
    }
}

找窗口的最大值

void get_max(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k)
            hh++;
        //求最大 递减区间 若出现向上 出队
        while(hh<=tt && a[i]>=a[q[tt]])
            tt--;
        q[++tt]=i;
        //当前区间的最大值为队头
        b[i] = a[q[hh]];
    }
}

另外注意分析我们要的答案是在插入新元素之前还是在插入新元素之后

void get_max/* min */(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k) //这里一定有等于 因为要腾空间放新元素 满了就得出去
            hh++;

        //具体操作也可能放在这里
        //这是把新元素放进去之前就找答案

        //最大最小只要改这里 最大应该是递减 最小应该是递增 出现异常就出队
        //另外注意代入情景看等于是否影响结果 一般是也剔除 除非是要什么最左边的 才考虑去=
        while(hh<=tt && a[i]>/* < */=a[q[tt]])
            tt--;
        q[++tt]=i;

        //具体操作可能放在这里
        //这是把新元素放进去后再找答案
    }
}

stl版

class Solution {
public:
    vector<int> maxInWindows/* minInWindows */(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for(int i=0;i<nums.size();i++)
        {
            if(!q.empty() && i-q.front()>=k)
                q.pop_front();

            //具体操作 情况2
            //……

            while(!q.empty() && nums[i]>= /* <= */ nums[q.back()])
                q.pop_back();
            q.push_back(i);

            //具体操作 情况1
            //……
            if(i>=k-1)
                res.push_back(nums[q.front()]);
        }
        return res;
    }
};

区间合并

多次要对一个大区间的某些段做标记可以暴力对每一段做标记最后枚举整个区间看是否有没标记过的很多时候也可以用差分某段处理后就在该段++ 不过我们要的结果不在乎具体是多少只是有值就1 没值就0 然后对于暴力对每段做标记和差分的话都会存在一个问题有很多地方做了重复操作这个时候就可以使用区间合并进行优化把能合并的区间都合并起来再对他们去做操作就可以省去一些重复功

对于合并操作得分析一个问题题目中诸如：1~~3 4~~5 这样的能不能合并如果能模版处就改成ed+1<range.first

typedef pair<int,int> PII;
PII range[N];
int cnt;

range[cnt++]={l,r};
sort(range,range+cnt);

int st=0,ed=0;
for(int i=0;i<cnt;i++)
{
    if(ed/*+1*/<range[i].first)//这里因情况而定 看相邻的合不合并
    {
        //具体操作
        //……
        st=range[i].first,ed=range[i].second; // 新维护区间
    }
    else ed=max(range[i].second,ed); // 更新维护区间
}
//对最后一个区间的操作
//……

用PII数组代替vector效率要高些对于可合并的情况不必写else if(ed<ed<range[i].second) 直接用max维护

trie树

给定一个字符串每个字符作为一个结点它的后续结点必定是26字母里的其中一个那么根据串的基本知识把26字母映射成0~25的数字就可以用下标存储所以抽象成树树中每个结点有0~25个子孩子

//如果非混在一起映射
// 将字符映射到0-36的索引
int charToIndex(char c) {
    if (isdigit(c)) return 26 + (c - '0'); // 数字映射到26-35
    if (c == '.') return 36; // 点映射到36
    return c - 'a'; // 字母映射到0-25
}

//一般情况 就是单一的字符种类
void insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';//大写-'A' 数字-'0' 混合调用int u = charToIndex(ch);
        if(!son[p][u])
            son[p][u]=++idx;//注意 若某串能作为已存在串的子串 插入它时一定不会新开结点
        p=son[p][u];
        //特殊需求
        //可记录途径该点的次数
        //way[p]++;
        //可判断是否包含某个子串
        //if(cnt[p])
    }
    cnt[p]++;//以该点结尾的
}

int query(char str[])
{
    int p=0;
    int res=0;//其实一般都是算某串的前面有多少子串 或者再拓展加上后面（它作为子串）
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u])
              return res;//return 0;//再或者纯粹些直接返回false return false;
        p=son[p][u];
        res+=cnt[p];
    }
    return res;//return cnt[p];//return true;
}

其他数学

除法问题

做除法的时候一定要double c=(double)a/b; 或者 a*1.0/b 另外尽可能把除法转变为乘法在同一个精度之下做除法并不会影响两个值的判断因为两个数都丢失了一样的东西（只有极少数可能让两个不一样的数反而判断成相等）但是如果要用这个除完后的数去进行新的计算就会因为之前丢失的精度而无法进行准确的计算所以面对涉及除法的判断问题时都尽可能的转变成乘法

等差与等比

等差数列公式：\(a_n = a_1 + (n-1)d\) 前 n 项和：\(S_n = (n/2)(a_1 + a_n)\) 或者 \(S_n = (n/2)(2a_1 + (n-1)d)\) 求和公式推导：\(S_n = (n/2)(a_1 + a_n) = (n/2)(2a_1 + (n-1)d) = na_1 + \frac{n(n-1)}{2}d\)

常用技巧：

若已知前 n 项和 \(S_n\)和公差 d，则可通过 \(S_n = (n/2)*(2a_1 + (n-1)d)\)解方程得到 \(a_1\)。
若已知前 n 项和 \(S_n\) 和项数 n，可通过 \(S_n = (n/2)*(a_1 + a_n)\) 解方程得到 \(a_n\)。

等比数列公式：\(a_n = a_1 * r^{(n-1)}\) 前 n 项和：\(S_n = \frac{a_1(1 - r^n)}{1 - r} （r != 1）\) 求和公式推导：

\(S_n = a_1 + a_2 + \dots + a_n\)
\(r \cdot S_n = a_2 + a_3 + \dots + a_{n+1}\)
\(S_n - r \cdot S_n = a_1 - a_{n+1}\)
\((1 - r) \cdot S_n = a_1(1 - r^n)\)

常用技巧：

若已知前 n 项和 \(S_n\) 和公比 r，则可通过 \(S_n = \frac{a_1(1 - r^n)}{1 - r}\) 解方程得到 \(a_1\)
若已知前 n 项和 \(S_n\) 和项数 n，可通过 \(S_n = \frac{a_1(1 - r^n)}{1 - r}\) 解方程得到 r

计算几何

两点间距离：\(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

线段中点：\(M(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2})\)

直线方程：

点斜式：\(y - y_1 = k(x - x_1)\)，其中 k 为斜率
截距式：\(y = kx + b\)，其中 b 为 y 轴截距

不要用除法求出来的k去算b 把k的公式带入消掉变成\(b=(x2y1-x1y2)/(x2-x1)\)

求两直线交点：解两直线方程组得到交点坐标。\(x=(b_2-b_1)/(k_1-k_2) y=k_1x+b_1\)

算这几个公式的时候一定要记得把右边转化成double类型！！！用*1.0也行！！！

double k=(double)(y2-y1)/(x2-x1); double b=(double)y1-k*x1; double x = (double)(b2 - b1) / (k1 - k2);

三角形面积：海伦公式 \(A = \\sqrt{s(s-a)(s-b)(s-c)}\)，其中 s 为半周长，a,b,c为三边长

库函数

四舍五入round round函数用于四舍五入浮点数到最接近的整数如果参数的小数部分是.5，则这个函数会将数值四舍五入到最近的偶数整数。这是为了遵守IEEE浮点数的标准，减少四舍五入操作的累积误差。

语法：double round(double x);
例子：round(2.3) 返回 2.0, round(3.5) 返回 4.0, round(4.5) 返回 4.0

向下取整floor floor函数将浮点数向下取整到最接近的整数，但不大于原数。无论原数的小数部分是多少，都会被丢弃，仅保留整数部分。

语法：double floor(double x);
例子：floor(2.3) 返回 2.0, floor(-3.8) 返回-4.0。

向上取整ceil

ceil函数将浮点数向上取整到最近的整数，但不小于原数。这意味着它会舍弃原数的小数部分，并在有小数的情况下将整数部分加一。

语法：double ceil(double x);
例子：ceil(2.3) 返回 3.0, ceil(-3.8) 返回 -3.0。

幂运算pow 用于计算一个数的指数幂。 cout<<pow(2,2);

平方根sqrt 应用场景：计算直角三角形的斜边长度，给定两条直角边的长度。

#include <cmath>
#include <iostream>
using namespace std;
int main() {
    double a = 3.0, b = 4.0;
    double c = sqrt(pow(a, 2) + pow(b, 2)); // 根据勾股定理计算斜边长度
    cout << "Hypotenuse: " << c << endl;
    return 0;
}

对数log2 和 log10

计算二进制表示所需的位数

log2 函数计算以2为底的对数，这在需要处理与二进制相关的问题时非常有用。比如，计算一个正整数在二进制表示中需要多少位。这对于算法竞赛中的位操作题目，比如求解一个数的二进制中1的数量，或者需要用位掩码表示某些状态时，非常实用。

#include <cmath>
#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    int bitsNeeded = log2(n) + 1; // 加1因为log2(n)计算的是索引，而位数从1开始计数

    cout << "Bits needed for binary representation of " << n << ": " << bitsNeeded << endl;
    return 0;
}

这个例子假设n是一个正整数。log2(n)计算了n在二进制表示下的最高位的位置（从0开始计数），因此需要加1来得到总位数。

计算十进制数中的位数 log10函数计算以10为底的对数，它可以用来快速确定一个数在十进制表示中的位数。这在处理需要数位操作的算法问题时特别有用，比如数字反转、数位和计算等。

#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    int digits = log10(n) + 1; // 加1因为log10(n)计算的是最高位的索引

    cout << "Digits in the decimal representation of " << n << ": " << digits << endl;
    return 0;
}

这个例子演示了如何快速计算出一个正整数在十进制表示中的位数。类似于log2的用法，这里log10(n)计算的是n的最高位的位置索引，在十进制中，这个位置索引加1就是该数的总位数。

其他

modf - 分解浮点数应用场景：如果要将一个浮点数的小时表示转换为小时和分钟（例如，将3.75小时转换为3小时45分钟），可以使用modf。

#include <cmath>
#include <iostream>
using namespace std;

int main() {
    double hours;
    cin >> hours;
    double intpart, fracpart;
    fracpart = modf(hours, &intpart);
    int minutes = round(fracpart * 60);
    cout << intpart << " hours and " << minutes << " minutes" << endl;
    return 0;
}

fmod - 浮点数除法的余数应用场景：计算一个飞轮每分钟转动7.5圈，经过98分钟后，它总共转了多少圈，并计算其相对于整圈的余数（即最后停留的位置）。

#include <cmath>
#include <iostream>
using namespace std;

int main() {
    double rotationsPerMinute = 7.5;
    double timeInMinutes = 98;
    double totalRotations = rotationsPerMinute * timeInMinutes;
    double remainder = fmod(totalRotations, 1); // 计算相对于整圈的余数

    cout << "Remainder: " << remainder << " of a rotation" << endl;
    return 0;
}

输入输出

优化模版

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    return 0;
}

输入

getline 用法：getline(cin, stringVar); 目的：读取一整行文本，直到遇到换行符\n。getline会丢弃换行符，但会读取并保留行中的其他所有字符，包括空格。场景：当你需要读取包含空格的一行文本或者确保一次读取直到行末尾时，getline是最佳选择。注意：在getline之前使用cin或scanf读取其他数据，并且期望紧接着用getline读取下一行时，需要注意消耗掉留在输入缓冲区中的换行符

cin>>n;
getline(cin,s);
for(int i=0;i<n;i++){
    getline(cin,s);
    m[i]=s.size();
    for(int j=0;j<m[i];j++){
        if(isalpha(s[j])){
            g[i][j]=1;
        }
        else{
            g[i][j]=0;
        }
    }
}

cin

用法：cin >> variable; 目的：读取数据，使用空格、制表符或换行符作为分隔符 cin会自动忽略任何前导空白字符场景：适用于读取分隔开的单个数据项，如整数、浮点数、字符串（不含空格）优点：使用方便，支持连锁调用（如cin >> a >> b;）缺点：不能读取含有空格的字符串。

scanf 用法：scanf("%format_specifier", &variable); 目的：根据指定的格式读取数据。scanf提供了格式化输入的能力，可以按照特定的格式读取数据。场景：当输入数据遵循固定格式，且需要精确控制输入格式时使用。它对于读取复杂格式化的输入非常有效。优点：读取速度快，可以精确地控制输入数据的格式。缺点：使用不当容易出错，如忽略返回值可能会导致未定义行为。对于字符串的处理不如cin和getline直观。常用格式控制

整数

%d：读取一个十进制整数。
%ld和%lld：分别用于读取long和long long类型的十进制整数。
%u：读取一个无符号十进制整数。
%x或%X：读取一个十六进制整数。
%o：读取一个八进制整数。

浮点数

%f：读取一个浮点数（float或double）。
%lf：读取一个double类型的浮点数。虽然%f在printf中用于double，但在scanf中%f是用于float的，%lf用于double。

字符和字符串

%c：读取一个字符。
%s：读取一个字符串，直到遇到空白字符（空格、制表符或换行符）为止。读取的字符串自动以空字符\0结尾。

其他

%p：读取一个指针。
%%：读取一个%字符。

读取多个值 scanf可以在一个调用中读取多个值，格式说明符之间的空格将被忽略，输入中的空格、制表符和换行符可以在任何格式说明符之间进行匹配。

int a, b;
scanf("%d %d", &a, &b);
char ch;
scanf(" %c", &ch); // 注意前面的空格，用于跳过前面的空白字符
double d;
scanf("%lf", &d);
char str[100];
scanf("%s", str); // 不需要&，因为数组名本身就是地址

注意事项

当使用%s读取字符串时，确保目标数组足够大，以避免缓冲区溢出。
使用%c读取字符时，如果想要忽略前面的空白字符（包括空格、制表符和换行符），可以在%c之前加一个空格，如scanf(" %c", &ch);
对于scanf来说，必须提供变量的地址作为参数（使用&运算符），除了字符串数组因为数组名已经是地址。
使用scanf时要特别注意返回值，它返回成功读取的项目数。这个返回值可以用来检测输入是否按照预期进行。

getchar 用法：int c = getchar(); 目的：从标准输入读取下一个字符，并返回它。如果遇到文件结束符（EOF），则返回EOF。场景：适用于需要逐字符读取输入时，如处理输入流中的空格、换行符等特殊字符。

总结在算法竞赛中，选择哪种输入方法取决于具体任务的需求：如果你需要读取整行数据，特别是包含空格的字符串，使用getline。

对于分隔的数据项，特别是不包含空格的字符串或数字，cin是一个方便的选项。
当输入格式非常具体，或者在性能极其关键的情况下，scanf可能是最好的选择，尽管它需要更多的注意来避免错误。
读取单个字符，逐字符处理，使用getchar：

输出

cout 用法：cout << value << ...; 目的：输出数据到标准输出。cout是C++中的标准输出流对象。场景：适用于大多数输出需求，特别是当需要输出字符串、数字或是其他复合数据结构时。cout由于是类型安全的，因此在处理类似于字符串和数字混合输出时非常方便。优点：

类型安全，自动类型推断。
支持连锁调用，易于使用。
可以与C++标准库中的其他流对象一起使用，如文件流。缺点：
相比于printf，在处理格式化输出时可能不那么灵活。
在某些情况下，可能比printf慢，尤其是没有优化I/O性能时。使用ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);进行优化

printf 用法：printf("format specifier", value1, value2, ...); 目的：根据指定的格式输出数据。printf是C语言中的标准输出函数，但在C++中仍然可用。场景：当需要精确控制输出格式，比如指定浮点数的精度，或者输出的宽度时。优点：

高度格式化的输出。
在某些情况下，性能优于cout。缺点：
不是类型安全的，错误的格式说明符可能导致运行时错误常用格式控制 printf非常强大，支持多种格式控制符，可以精确地控制输出格式。
%d：输出十进制整数。
%u：输出无符号十进制整数。
%f：输出浮点数，默认情况下保留小数点后六位。
%.2f：输出浮点数，小数点后保留两位。
%s：输出字符串。
%c：输出单个字符。
%x或%X：输出十六进制数，x产生小写字母，X产生大写字母。
%p：输出指针地址。
%%：输出%字符。高级用法
指定宽度：%5d表示输出的整数至少占5个字符宽度，如果数字位数不够，前面补空格。
左对齐：%-5d表示输出的整数左对齐，至少占5个字符宽度。
指定浮点数精度：%.3f表示输出的浮点数保留三位小数。
动态宽度和精度：%*.*f允许动态指定宽度和精度，这两个值由额外的参数提供。

printf("%5d\n", 123);  // "  123"
printf("%-5d\n", 123); // "123  "
printf("%.3f\n", 3.1415926); // "3.142"

puts和putchar puts：

用法：puts(const char* s);
目的：输出字符串s到标准输出，并自动在末尾添加换行符。
优点：简单易用，自动添加换行符，适合快速输出一行字符串。
缺点：只能输出字符串，不能格式化输出其他类型的数据。 putchar：
用法：putchar(int char);
目的：输出单个字符到标准输出。
优点：非常简单，用于输出单个字符。
缺点：每次只能输出一个字符，不适用于复杂的输出需求。

总结根据需要输出的数据类型和格式化要求来决定。 cout适合大部分场景且易于使用； printf在需要特定格式时更为强大；而puts和putchar适用于简单的输出需求，特别是当性能要求较高时。