---
title: "01-根据时间复杂度选择算法"
created: 2026-01-09
tags:
  - 博客

---
# 根据时间复杂度选择算法

![[Pasted image 20260907191939.png]]
## 总览

1. n≤30 → 指数级别

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

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

   floyd，dp
3. n≤1000 → O(n^2)，O(n^2log\_n)

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

   块状链表，分块，莫队
5. n≤100000 → O(nlog\_n)

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

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

   常数较小的 O(nlog\_n)：sort，树状数组，heap，dijkstra，spfa
7. n≤10000000 → O(n)

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

   判断质数
9. n≤10^{18} → O(log\_n)

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

    高精度加减乘除
11. n≤ 10^{100000} → O(log*n \* loglog*n)

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

## N<=30

### dfs bfs

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

```cpp
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);
```

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

```cpp
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 不同顺序算同一种 组合型枚举

```cpp
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);
```

图

拓展

```cpp
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回溯路径

```cpp
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; 看要的是左边还是方向
}
```

合法

```cpp
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]; 染色
}
```

读图

```cpp
每行无空格
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

```cpp
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

```cpp
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把所有它能拓展到的点都标记 一共被标记几次就有几个连通块

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

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

```cpp
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处染色 可区分两部分

主要在于读图

```cpp
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);
```

棋盘：

```text
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

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

```cpp
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

```cpp
#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层转移而来 使用滚动数组的话 需要从大到小枚举体积

```cpp
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层转移来 从小到大枚举体积

```cpp
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背包的一个物品

```cpp
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背包求解 完全背包另做一种情况

```cpp
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[][][]
循环时 和枚举体积一样 多枚举一个东西即可 注意状态转移 右边集合
上一个状态的这一维也要减去

```cpp
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];
```

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

```cpp
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

```cpp
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

```cpp
//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

```cpp
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 在没有物品可选的情况下 不可能恰好填满非零体积的背包

```cpp
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 在没有物品可选的情况下 不能恰好填满非零体积的背包

```cpp
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的情况外 其他所有体积的最大价值都是不可达的

```cpp
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 还没有开始选择物品 在初始状态下它们不可达的

```cpp
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在顶部

```cpp
    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];
```

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

求最大

```cpp
 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;
```

求最小

```cpp
  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]处为右下角 答案`

```cpp
    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]结尾的上升子序列的最大长度 或最大权和

长度

```cpp
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;
```

权和

```cpp
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;
```

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

```cpp
    从左往右的上升子序列
    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);
            }
        }
    }
```

关于答案

```cpp
若答案只需要最大(不管方向 全局最大)
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]`

```cpp
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范围内
状态转移 左价值加右价值加该步价值

```cpp
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个石头

```cpp
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

```cpp
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
考虑二分
思路 答案能不能套出来？具不具有二段性？即随便套了一个答案 发现小了 能不能往大的找

两个模版

```cpp
---- |----  找最小(最左边)
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

正权边最短路 贪心思想

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

```cpp
#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

最小生成树

```cpp
#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思想

```cpp
#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
到了这个数据范围确实没什么可写了就想一下贪心能不能行
后面几题的话 想不出来写法其实就可以直接蒙贪心 反正不亏

主要熟悉排序的自定义

```cpp
单关键字
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);
```

```cpp
多关键字
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);
```

```cpp
优先队列
//升序队列 小顶堆 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;
```

```cpp
//默认都是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

```cpp
最短路
#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;
}
```

```cpp
判负环
#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指针使得答案包含在内

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

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

```cpp
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） 对撞指针
利用单调性 用俩指针（一个最大一个最小）去找到某个值（和） 根据值的情况调动指针 可以用在一个区间也可以用在两个区间里面 本质一样

```cpp
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](与二分功能相似）

```cpp
/*
    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];`
`}`
递归的过程中 让直接存上祖宗结点

```cpp
#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使得真实下标和映射下标得到了对应
只有对应了 离散化才具有意义
用法大概是 找原区间里某个数的映射出的新下标
在这个新下标处干一些事情 把每一步的意义记清楚 不然容易晕头转向的

```cpp
#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

```cpp
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预处理出来

```cpp
#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

```cpp
下标从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

### 筛法

```cpp
埃氏筛
从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

### 约数

```cpp
试除法判断约数
从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[]记录每个数在这堆数中的约数数量 它的约数一定会它的倍数约 所以它的约数数量可以同步累加进它的倍数的约数数量里面去
把每个数当成被约的数 从它入手 同步更新所有倍数的数量
而不是累加完后 把每个数当成约其他数的数 再去遍历判断可约的数的数量
从按列算转变成按行算 大大提高速度
1. 初始化一个数组来记录每个数的约数计数。
2. 遍历每个数，对于每个数，遍历它的所有倍数，并将当前数的出现次数累加到这些倍数的约数计数上。
3. 一旦所有数都被处理过，每个数的约数计数就可以从数组中获得。

```cpp
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的越界危险
```cpp
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=2*2*3中 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 的质因子，如果有，输出（如果有 只会有一个）

```cpp
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)

```cpp
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 就是两数最大公约数
```cpp
    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)

```cpp
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;`

```cpp
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^{几百位}\) 这样的数

```cpp
#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的该位（如果存在）
那么用一个数去记录这个和 个位其实就是当前位的值 十位（如果存在）其实就是对下一位的进位

```cpp
#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
当然为避免负值 采用先判断大小 让计算始终是大的减小的 如果要求是小的减大的 则计算大的减小的 把结果加个负号

```cpp
#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
```cpp
#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
```cpp
#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开始
```cpp
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];
```

二维前缀和
```cpp
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;
```

一维差分
```cpp
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]<<" ";
}
```

二维差分
```cpp
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;
}
```

### 日期问题

组合拳
```cpp
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遍历

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

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

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

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

从1~n遍历

序列应该是单调递减

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

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

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

从n~1遍历

序列应该是单调递增

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

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

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

从n~1遍历

序列应该是单调递减

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

```cpp
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找到

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

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

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

```cpp
#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)左边 最远的 小于它的数**

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

```cpp
#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即可

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

```cpp
#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 最小 若该数为最小 直接加入 否则 二分找

```cpp
#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)的时间内找到这个最值

一般也就两个场景

找窗口的最小值

```cpp
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]];
    }
}
```

找窗口的最大值

```cpp
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]];
    }
}
```

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

```cpp
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版

```cpp
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

```cpp
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个子孩子

```cpp
//如果非混在一起映射
// 将字符映射到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 + {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 = {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 = {a\_1(1 - r^n)} / {1 - r}\) 解方程得到 \(a\_1\)
- 若已知前 n 项和 \(S\_n\) 和项数 n，可通过   \(S\_n = {a\_1(1 - r^n)} / {1 - r}\) 解方程得到 r

#### 计算几何

两点间距离：\(d = sqrt{(x\_2 - x\_1)^2 + (y\_2 - y\_1)^2}\)

线段中点：\(M({x\_1 + x\_2}/{2}, {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
应用场景：计算直角三角形的斜边长度，给定两条直角边的长度。

```cpp
#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的数量，或者需要用位掩码表示某些状态时，非常实用。
```cpp
#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为底的对数，它可以用来快速确定一个数在十进制表示中的位数。
这在处理需要数位操作的算法问题时特别有用，比如数字反转、数位和计算等。
```cpp
#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`。
```cpp
#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分钟后，它总共转了多少圈，并计算其相对于整圈的余数（即最后停留的位置）。
```cpp
#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;
}
```

### 输入输出

优化模版
```cpp
#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读取下一行时，需要注意消耗掉留在输入缓冲区中的换行符
```cpp
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`可以在一个调用中读取多个值，格式说明符之间的空格将被忽略，输入中的空格、制表符和换行符可以在任何格式说明符之间进行匹配。

```cpp
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允许动态指定宽度和精度，这两个值由额外的参数提供。

```cpp
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`适用于简单的输出需求，特别是当性能要求较高时。