review（1）基础算法+基础数据结构+基础图论+简单dp
1.基础算法
1.排序。归并排序求逆序对。快排
2.前缀和 差分。前缀和，快速求出一段区间的和。差分，快速对一段区间修改。前缀和计算l-1，差分修改r+1。注意二维别写错
3.二分。注意如果是r=mid-1，，则mid要l+r+1>>1。
4.高精度
5.双指针算法。
6.位运算。lowbit
7.离散化
2.基础数据结构
1.单链表,h,e,ne,idx;
2.双链表：
//这里填你的代码^^
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int l[N],r[N],e[N],idx;
int m;void init()
{//0是左端点，1是右端点l[1]=0;r[0]=1;idx=2;
}
void insert(int k,int x)
{e[idx]=x;l[idx]=k;r[idx]=r[k];l[r[k]]=idx;r[k]=idx++;}void remove(int k)
{r[l[k]]=r[k];l[r[k]]=l[k];
}int main()
{init();cin>>m;while(m--){string op;int k,x;cin>>op;if(op=="L") cin>>x,insert(0,x);else if(op=="R") cin>>x,insert(l[1],x);else if(op=="D") cin>>k,remove(k+1);else if(op=="IR") cin>>k>>x,insert(k+1,x);else cin>>k>>x, insert(l[k+1],x);}for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~作者：yankai
链接：https://www.acwing.com/activity/content/code/content/3400144/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。3.栈
单调栈：求出第一个小于当前数、大于当前数的数。
4.队列
单调队列：维护滑动窗口最大值最小值。
5.KMP
6.Trie
7.并查集：
int find(int x)
{if(p[x]!=x) {int t=find(p[x]);d[x]+=d[p[x]];p[x]=t;}return p[x]
}8.堆
从最后一个非叶节点向下调整
9.hash
3.图论
1.拓扑序——dp
2.spfa求负环——到i点最短路经过大于n个点
//这里填你的代码^^
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;const int N =1000010;
int h[N],e[N],w[N],ne[N],idx;
int dist[N],cnt[N];//存每个点最短路长度
int n,m;
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()
{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]){st[j]=true;q.push(j);}}}}return false;}int main()
{cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);}if(spfa()) cout<<"Yes";else cout<<"No";return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~作者：yankai
链接：https://www.acwing.com/activity/content/code/content/3670027/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。3.最小生成树求法
4.匈牙利算法（st数组每轮更新）
//这里填你的代码^^
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N =510,M=100010;
int h[N],ne[M],e[M],idx;
bool st[N]; //表示本次循环右边该点是否被考虑过 每次不要重复搜一个点（因为一次循环内不需要再更改这个点的match）
int match[N]; //存储右边的点和左边的哪个点匹配int n1,n2,m;void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}bool find(int x)
{for(int i=h[x];i!=-1;i=ne[i]){int j=e[i];if(!st[j]) //本次循环内没有考虑过j{st[j]=true;if(match[j]==0||find(match[j])) //j没有匹配过，或者再find一次和j匹配的节点能匹配到新的//代表这个j可以和当前这个x匹配{match[j]=x;return true;}}}return false;
}int main()
{memset(h,-1,sizeof h);cin>>n1>>n2>>m;for(int i=0;i<m;i++){int a,b;cin>>a>>b;add(a,b);}int res=0;for(int i=1;i<=n1;i++){memset(st,false,sizeof st);if(find(i)) res++;//成功匹配}cout<<res;return 0;}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~作者：yankai
链接：https://www.acwing.com/activity/content/code/content/3682284/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。5.dp
01背包，完全背包
多重背包：二进制优化，单调队列优化
这里先给出二进制优化：
注意不够二级次幂的要加上
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N =25000,M=2010;int v[N],w[N];
int n,m;
int f[M];int main()
{cin>>n>>m;int cnt=0;for(int i=1;i<=n;i++){int a,b,s;cin>>a>>b>>s;int k=1;while(k<=s){cnt++;v[cnt]=a*k;w[cnt]=b*k;s-=k;k*=2;}if(s>0){v[++cnt]=s*a; w[cnt]=b*s;}}n=cnt;//n变为打包后的物品数量for(int i=1;i<=cnt;i++)for(int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[m];
}
分组背包：01背包+多一层遍历组内物品
//这里填你的代码^^
#include<iostream>
#include<algorithm>
using namespace std;const int N =110;
int v[N][N],w[N][N],s[N];
int f[N];
int n,m;int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=1;j<=s[i];j++)cin>>v[i][j]>>w[i][j];}for(int i=1;i<=n;i++)for(int j=m;j>=0;j--)for(int k=1;k<=s[i];k++)if(v[i][k]<=j)f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);cout<<f[m];return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~作者：yankai
链接：https://www.acwing.com/activity/content/code/content/3818429/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。最长上升子序列的nlogn解法
贪心+二分
状态表示：长度为i的最长上升子序列所有结尾中，结尾最小min的) 即长度为i的子序列末尾最小元素是什么。
当遇到一个新元素，二分一下找出结尾小于该数的，，长度最长的序列，然后更新长度+1（和已经求出的长度+1的方案比较）
当初看这个的时候感觉好难想啊，，现在看来思路是：找出结尾小于该数长度最长的方案 其实是很自然的。
//这里填你的代码^^
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//f[i]表示长度为i的最长上升子序列，末尾最小的数字。
//(长度为i的最长上升子序列所有结尾中，结尾最小min的) 即长度为i的子序列末尾最小元素是什么。
const int N =100010;int a[N];
int f[N];
int n;
int main()
{cin>>n;for(int i=0;i<n;i++) cin>>a[i];int len=0;f[0]=-2e9;for(int i=0;i<n;i++){int l=0,r=len;while(l<r){int mid=l+r+1>>1;if(f[mid]<a[i]) l=mid;else r=mid-1;}len=max(len,r+1);f[r+1]=a[i];}cout<<len;return 0;
}//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~作者：yankai
链接：https://www.acwing.com/activity/content/code/content/3899911/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
