断断续续看了2周，终于把第一章给结束了
接下来写写我自己的心得吧
感觉这本书还不错，因此打算长期学下去。
第一章的应用面很广，要好好打基础
接下来可能每干完一章都会写一下这样的学习笔记（flag）
不过每次学完都不是全懂，我只写下自己理解了的地方
等日后回头看可能有新的心得了再更新
接下来是正文

——————————————————————————————————————————————————————
1.位运算

1.1基本运算
与 &
或 |
非 ~
异或 ^
主要是有一些运算规律可以总结，假设x是某一个二进制位，即x=1 or x=0
那么有：

x&1==x,x&0==0;
x|1==1,x|0==x;
x^1==!x,x^0==x;
-x==~x+1;

1.2移位运算
有>>和<<两种，分别表示二进制下的数字右移和左移
利用这个可以遍历某个数字二进制的各位
应用一：快速幂（也是一个模板）
AcWing89https://www.acwing.com/problem/content/91/
直接上代码

#include <bits/stdc++.h>
using namespace std;
int power(int a,int b,int p){
    int ans=1%p;//防止p为1的特判
    for(;b;b>>=1){
        if(b&1)ans=(long long)ans*a%p;//开long long 防止爆int
        a=(long long)a*a%p;
    }
    return ans;
}
int main(){
    int a,b,p; cin>>a>>b>>p;
    cout<<power(a,b,p);
    return 0;
}

应用二：大整数乘法
AcWing90https://www.acwing.com/problem/content/92/
这里只列举书上的时间复杂度O（1）的做法，类似快速幂也可以的

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull mul(ull a,ull b,ull p){
    a%=p; b%=p;
    ull c=(long double)a*b/p;//我们需要的是高的有效数字
    ull x=a*b,y=c*p;
    ull ans=x-y;
    if(ans<0)ans+=p;//x<y的特判
    return ans;
}
int main(){
    ull a,b,p;
    cin>>a>>b>>p;
    cout<<mul(a,b,p);
    return 0;
}

应用三：二进制状态压缩
讲真，我还没搞太明白，尤其是状态压缩DP那里（我好菜）
等后续我看懂了再来更新吧

2.递推与递归

2.1三个组合的枚举
1）AcWing 92https://www.acwing.com/problem/content/94/

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>v;
void solve(int x){
    if(x==n+1){
        for(int i=0;i<n;i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
        return;
    }
    v.push_back(x);//选择x
    solve(x+1);
    v.pop_back();//还原现场
    solve(x+1);
}
int main(){
    cin>>n;
    solve(1);
    return 0;
}

2）AcWing93https://www.acwing.com/problem/content/95/

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int>v;
void solve(int x){
    if(v.size()>m || n+1-x+v.size()<m)return;//加一句特判就行
    if(x==n+1){
        for(int i=0;i<n;i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
        return;
    }
    v.push_back(x);//选择x
    solve(x+1);
    v.pop_back();//还原现场
    solve(x+1);
}
int main(){
    cin>>n>>m;
    solve(1);
    return 0;
}

3）AcWing94https://www.acwing.com/problem/content/96/
也可以用next_permutation

#include <bits/stdc++.h>
using namespace std;
int n;
int a[10];
bool b[10];
void solve(int x){//这里x的含义是遍历到第几个数字了
    if(x==n+1){
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(b[i])continue;
        a[x]=i;
        b[i]=true;//表示我要i这个数字
        solve(x+1);
        b[i]=false;//还原现场
    }
}
int main(){
    cin>>n;
    solve(1);
    return 0;
}

2.2汉诺塔问题
AcWing96https://www.acwing.com/problem/content/98/

#include<bits/stdc++.h>
using namespace std;
int main(){
    int d[15],f[15];
    d[1]=1;
    for(int i=2;i<=12;i++)d[i]=1+2*d[i-1];//这是只有三塔的汉诺塔
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=12;i++){
        for(int j=0;j<i;j++){
            f[i]=min(f[i],2*f[j]+d[i-j]);
        }
    }
    for(int i=1;i<=12;i++)cout<<f[i]<<endl;
    return 0;
}

还有分治和分形，整不太明白，指书上的题目，后续再补吧

3.前缀和与差分

3.1前缀和
这个东西老好用了，自从学了这个感觉好多题目迎刃而解
看一道经典的二维前缀和
AcWing89https://www.acwing.com/problem/content/101/

#include<bits/stdc++.h>
using namespace std;
int a[5005][5005];
int main(){
    int n,r; cin>>n>>r;
    int p=r,q=r;
    for(int i=0,x,y,v;i<n;i++){
        cin>>x>>y>>v;
        x++, y++;//计算前缀和需要前导0
        p=max(p,x), q=max(q,y);//计算目标最远到哪里了
        a[x][y]+=v;
    }
    for(int i=1;i<=p;i++)
        for(int j=1;j<=q;j++)
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//计算二维前缀和
    int ans=0;
    for(int i=r;i<=p;i++)
        for(int j=r;j<=q;j++)
            ans=max(ans,a[i][j]-a[i-r][j]-a[i][j-r]+a[i-r][j-r]);
    cout<<ans;
    return 0;
}

3.2差分
这个就是前缀和的逆运算
如果对于一个区间的操作可以使用差分来转化为对两个点的操作，继而提高效率
A从Wing100https://www.acwing.com/problem/content/102/
反正知道之后这题就是找规律的问题了

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int b[100010];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    b[1]=a[1];
    for(int i=2;i<=n;i++){
        b[i]=a[i]-a[i-1];
    }
    b[n+1]=0;
    long long sum1=0,sum2=0;
    for(int i=2;i<=n;i++){
        if(b[i]>0)sum1+=b[i];
        else if(b[i]<0)sum2+=abs(b[i]);
    }
    cout<<max(sum1,sum2)<<endl<<abs(sum1-sum2)+1;
    return 0;
}

4.二分

这个就没啥模板的了，如果对于一道题目，他的答案单调，并且判定难度小，找答案难度高，不如试试二分答案
除了有一些小技巧，这里我写下我自己学到的

//对于二分，有两种二分法
//1
int mid=(L+R)>>1;
if()L=mid+1;
else R=mid;
//2
int mid=(L+R+1)>>1;
if()L=mid;
else R=mid-1;

对于前者，因为取不到R，因此要L=mid+1，否则最后会忽略R这个答案
对于后者，因为取不到L，因此要R=mid-1，否则最后会忽略L这个答案

5.排序

5.1离散化
这也是很重要的一个思想，对于压缩空间和时间有一个重要应用，具体给一道题体会下
AcWing121https://www.acwing.com/problem/content/123/

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int sum[1010][1010];
int c,n;
vector<int>numbers;
vector<PII>points;
int get_point(int x){
    return lower_bound(numbers.begin(),numbers.end(),x)-numbers.begin();//返回x离散后的下标对应多少
}
bool check(int x){
    for(int x1=1,x2=1;x2<numbers.size();x2++){
        while(numbers[x2]-numbers[x1]+1>x)x1++;//找目前满足正方形的最小边长，下面那个也是
        for(int y1=1,y2=1;y2<numbers.size();y2++){
            while(numbers[y2]-numbers[y1]+1>x)y1++;
            if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]>=c)return true;//找到了满足不小于c的情况
        }
    }
    return false;
}
int main(){
    cin>>c>>n;
    numbers.push_back(0);
    for(int i=0,x,y;i<n;i++){
        cin>>x>>y;
        numbers.push_back(x);
        numbers.push_back(y);
        points.push_back({x,y});
    }
    sort(numbers.begin(),numbers.end());//同时离散化x,y坐标后排序
    numbers.erase(unique(numbers.begin(),numbers.end()),numbers.end());//离散化（其实就是去除重复元素）
    for(int i=0;i<n;i++){
        int x=get_point(points[i].first),y=get_point(points[i].second);
        sum[x][y]++;//计算离散后的sum
    }
    for(int i=1;i<numbers.size();i++){
        for(int j=1;j<numbers.size();j++){
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    int l=1,r=10000;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}

这题其实把离散化，前缀和，二分一起考了，主要是离散化的问题，为什么x,y坐标可以放在一起呢。
因为x的坐标离散化后在number里只有一个可以对应，这个有点绕，理解下就行。

5.2中位数
主要学一下一个对顶堆动态维护中位数的思想
其实就是在中位数前是大（小）顶堆，后是小（大）顶堆，然后模拟就行
AcWing106https://www.acwing.com/problem/content/108/

#include <bits/stdc++.h>
using namespace std;
vector<int>ans;
priority_queue<int>que1;//大顶堆
priority_queue<int,vector<int>,greater<int> >que2;//小顶堆
int main(){
    int p; cin>>p;
    while(p--){
        ans.clear();
        while(!que1.empty())que1.pop();
        while(!que2.empty())que2.pop();
        int cnt,n; cin>>cnt>>n;
        int mid;
        for(int i=1,x;i<=n;i++){
            cin>>x;
            if(i==1){
                ans.push_back(x);
                que2.push(x);
                mid=x;
                continue;
            }
            if(x<mid)que1.push(x);
            else que2.push(x);
            if(i%2==1){
                while(que2.size()-que1.size()!=1){
                    que2.push(que1.top());
                    que1.pop();
                }
                ans.push_back(que2.top());
            }else{
                while(que1.size()!=que2.size()){
                    if(que1.size()<que2.size()){
                        que1.push(que2.top());
                        que2.pop();
                    }else{
                        que2.push(que1.top());
                        que1.pop();
                    }
                }
            }
            mid=que2.top();
        }
        cout<<cnt<<" "<<ans.size()<<endl;
        for(int i=0;i<ans.size();i++){
            cout<<ans[i];
            if((i+1)%10==0 && i!=ans.size()-1)cout<<endl;
            if((i+1)%10!=0 && i!=ans.size()-1)cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

5.3第k大数
这个代码之后补上
5.4逆序对
主要给一个归并排序的模板，顺便计算下逆序对个数

#include<bits/stdc++.h>
using namespace std;
const int p=5e5+10;
int arr[p],b[p];
long long cnt=0;
void merge(int l,int mid,int r){
    int i=l,j=mid+1,k=0;
    while(i<=mid && j<=r){
        if(arr[i]<=arr[j])b[k++]=arr[i++];
        else b[k++]=arr[j++],cnt+=mid-i+1;
    }
    while(i<=mid)b[k++]=arr[i++];
    while(j<=r)b[k++]=arr[j++];
    for(i=l,j=0;i<=r;j++,i++)arr[i]=b[j];
}
void merge_sort(int l,int r){
    if(l==r)return;
    int mid=(l+r)/2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    merge(l,mid,r);
}
int main(){
    int n;
    while(cin>>n && n){
        cnt=0;
        for(int i=0;i<n;i++)cin>>arr[i];
        merge_sort(0,n-1);
        cout<<cnt<<endl;
    }
    return 0;
}

6.倍增

目前我就只会一个RMQ模板

//RMQ模板/st表
#include<bits/stdc++.h>
using namespace std;
const int p=100010;
int f[p][19];
void st(){
      for(int j=1;j<=19;j++){
            for(int i=0;i+(1<<j)-1<n;i++){
		f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
            }
      }
}
int Q(int l,int r){
      int len=log2(r-l+1);
      return max(f[i][len],f[r-(1<<len)+1][len]);
}
int main(){
      int n,m; //n个数，m次询问
      for(int i=0;i<n;i++)cin>>f[i][0];
      st();
      while(m--){
            int l,r; cin>>l>>r;
            l--; r--;
            cout<<Q(l,r)<<endl;
      }
      return 0;
}

7.贪心

这个很难总结知识点啊，直接看题目吧
如果是难的贪心还需要严谨的数学证明
这题是国王游戏问题，贪心的方法是按照左手乘右手大小贪心
哦对了，这题是贪心加上高精度（高精度乘除低精度）
AcWing114https://www.acwing.com/problem/content/116/

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
PII p[N];
vector<int> mul(vector<int> a,int b){//高精度*低精度
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size();i++){
        t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    while(t)c.push_back(t%10),t/=10;
    return c;
}
vector<int> div(vector<int> a,int b){//高精度/低精度
    vector<int> c;
    int is_first=false;
    for(int i=a.size()-1,t=0;i>=0;i--){
        t=t*10+a[i];
        int x=t/b;
        if(x || is_first){
            is_first=true;
            c.push_back(x);
        }
        t%=b;
    }
    return vector<int>(c.rbegin(),c.rend());
}
vector<int>manx(vector<int> a,vector<int> b){//高精度比大小（比字典序）
    if(a.size()>b.size())return a;
    if(a.size()<b.size())return b;
    if(vector<int>(a.rbegin(),a.rend())>vector<int>(b.rbegin(),b.rend()))return a;
    return b;
}
int main(){
    int n; cin>>n;
    for(int i=0,x,y;i<=n;i++){
        cin>>x>>y;
        p[i]={x*y,x};
    }
    sort(p+1,p+1+n);
    vector<int> product(1,1);
    vector<int> ans(1,0);
    for(int i=0;i<=n;i++){
        if(i)ans=manx(ans,div(product,p[i].first/p[i].second));
        product=mul(product,p[i].second);
    }
    for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
    cout<<endl;
    return 0;
}

或者这里有一题国王游戏的低配版
二分+贪心+前缀和
AcWing125https://www.acwing.com/problem/content/127/

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
PII p[50050];
int sum[50050];
int n;
bool check(int x){
    for(int i=1;i<n+1;i++){
        if(sum[i-1]-p[i].first+p[i].second>x)return false;
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=1,w,s;i<=n;i++){
        cin>>w>>s;
        p[i]={w+s,w};
    }
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+p[i].second;
    int l=-1e9,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}

大概就先这么多吧，如果遇到有启发的题目也尽量更新一下