前言
带权并查集
银河英雄传说
银河英雄传说
#include<iostream>using namespace std;const int N =3e4+10;int fa[N],d[N],cnt[N];//cnt[i]记录的是当前结点以及它的子节点一起的个数int T;int find(int x){if(fa[x]==x)return x;int t=find(fa[x]);d[x]=d[x]+d[fa[x]];return fa[x]=t;
}void un(int x,int y){//如果这个树一直吞并他人，那么这个树的祖先节点是不会改变,一直都是第一个int fx=find(x);int fy=find(y);if(fx!=fy){fa[fx]=fy;d[fx]=cnt[fy];//到fy的距离就是前面的飞机数cnt[fy]+=cnt[fx];}
}int issame(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy)return -1;else return abs(d[x]-d[y])-1;
}int main(){cin>>T;for(int i=1;i<=30000;i++){fa[i]=i;cnt[i]=1;}while(T--){char c;int i,j;cin>>c>>i>>j;if(c=='M'){un(i,j);}else{cout<<issame(i,j)<<endl;}}return 0;
}字符串哈希
【模板】字符串哈希
【模板】字符串哈希
#include<iostream>
#include<algorithm>
using namespace std;const int N=1e4+10;typedef unsigned long long ULL;int n;ULL a[N];const int P =131;ULL get_hash(string s){ULL ret =0;for(int i=1;i<=s.size();i++){ret=ret*P+s[i-1];}return ret;
}int main(){cin>>n;for(int i=1;i<=n;i++){string s;cin>>s;a[i]=get_hash(s);}sort(a+1,a+n+1);//左闭右开。。，，，algorithm,,[)int ret=1;for(int i=2;i<=n;i++){if(a[i]!=a[i-1])ret++;}cout<<ret;return 0;
}兔子与兔子
兔子与兔子
#include<iostream>using namespace std;typedef unsigned long long ULL;
const int P =13331;
const int N=1e6+10;
ULL f[N];//1~N的哈希值
ULL p[N];//p[i]=p^i;string s;int n;void init(){f[0]=0;p[0]=1;for(int i=1;i<=n;i++){p[i]=p[i-1]*P;f[i]=f[i-1]*P+s[i];}
}ULL get_hash(int l,int r){return f[r]-f[l-1]*p[r-l+1];
}int main(){cin>>s;n=s.size();s=" "+s;//可以从[1,n]了int m;cin>>m;init();while(m--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;if(get_hash(l1,r1)==get_hash(l2,r2)){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}return 0;
}字典树
【模板】字典树
【模板】字典树
#include<iostream>
#include<cstring>//使用memset
using namespace std;const int N = 3e6+10;//总共可能有多少个节点int tri[N][62];//tir[i][j]=k表示的意思是i经过j到k
int p[N];//每个节点经过的次数int inx;//记录已经创建的最大结点int n,q;int toNum(char c){if(c>='a'&&c<='z')return c-'a';else if(c>='A'&&c<='Z')return c-'A'+26;else return c-'0'+52;
}void insert(string& s){int cur=0;//记录当前遍历到的节点位置p[cur]++;for(auto c:s){int x=toNum(c);if(tri[cur][x]==0) tri[cur][x]=++inx;cur=tri[cur][x];p[cur]++;}
}int find_pre(string& s){//如果不引用的话，可能会超时int cur=0;//记录当前遍历到的节点位置for(auto c:s){int x=toNum(c);if(tri[cur][x]==0) return 0;cur=tri[cur][x];}return p[cur];
}int main(){int T;cin>>T;while(T--){cin>>n>>q;
// memset(tri,0,sizeof(tri));
// memset(p,0,sizeof(p));//这个会超时，因为全部都赋值为0，没有用到的也赋值为0for(int i=0;i<=inx;i++){for(int j=0;j<62;j++)tri[i][j]=0;}for(int i=0;i<=inx;i++)p[i]=0;inx=0;//全部全局变量都要初始化while(n--){string s;cin>>s;insert(s);}while(q--){string s;cin>>s;cout<<find_pre(s)<<endl;}}return 0;
}动态规划
[GESP样题 六级] 下楼梯
[GESP样题 六级] 下楼梯
#include<iostream>using namespace std;const int N=65;int n;typedef long long LL;LL fx[N];int main(){cin>>n;
// fx[1]=1;
// fx[2]=2;
// fx[3]=4;
// for(int i=4;i<=n;i++){
// fx[i]=fx[i-1]+fx[i-2]+fx[i-3];
// }
// cout<<fx[n];//空间优化LL a=1;LL b=2;LL c=4;for(int i=4;i<=n;i++){LL t=a+b+c;a=b;b=c;c=t;}if(n==0)cout<<1;if(n==1)cout<<1;if(n==2)cout<<2;if(n>=3)cout<<c;return 0;
}[IOI 1994] 数字三角形 Number Triangles
[IOI 1994] 数字三角形 Number Triangles
//#include<iostream>
//
//using namespace std;
//
//const int N = 1010;
//
//int n;
//
//int a[N][N];
//int fx[N][N];//fx[i][j]:表示顶点到fx[i][j]最大距离
//
//int main(){
// cin>>n;
// for(int i=1;i<=n;i++)
// for(int j=1;j<=i;j++){
// cin>>a[i][j];
// }
// for(int i=1;i<=n;i++)
// for(int j=1;j<=i;j++){
// fx[i][j]=max(fx[i-1][j-1],fx[i-1][j])+a[i][j];
// }
// int ret=0;
// for(int i=1;i<=n;i++){
// ret=max(ret,fx[n][i]);
// }
// cout<<ret;
// return 0;
//}#include<iostream>using namespace std;const int N = 1010;int n;int a[N][N];
int fx[N];//fx[i][j]:表示顶点到fx[i][j]最大距离int main(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++){cin>>a[i][j];}for(int i=1;i<=n;i++)for(int j=i;j>=1;j--){fx[j]=max(fx[j-1],fx[j])+a[i][j];}int ret=0;for(int i=1;i<=n;i++){ret=max(ret,fx[i]);}cout<<ret;return 0;
}
基础线性 dp
台阶问题
台阶问题
#include<iostream>using namespace std;int n,k;const int N=1e5+10;const int mod=1e5+3;int fx[N];int main(){cin>>n>>k;fx[0]=1;fx[1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=k&&i-j>=0;j++){fx[i]=(fx[i]+fx[i-j])%mod;}}cout<<fx[n];return 0;
}路径类 dp
矩阵的最小路径和
矩阵的最小路径和
#include<iostream>
#include<cstring>
using namespace std;const int N=510;int a[N][N];int fx[N][N];int n,m;int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];}memset(fx,0x3f,sizeof fx);fx[0][1]=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){fx[i][j]=min(fx[i-1][j],fx[i][j-1])+a[i][j];}cout<<fx[n][m]<<endl;return 0;
}「⽊」迷雾森林
「⽊」迷雾森林
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=3010;int a[N][N];
int f[N][N];int n,m;int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
// cin>>a[i][j];//这个会超时，这个读取太慢了scanf("%d",&a[i][j]);}
// memset(f,0,sizeof f);f[n][0]=1;for(int i=n;i>=1;i--)for(int j=1;j<=m;j++){if(a[i][j]==0)f[i][j]=(f[i+1][j]+f[i][j-1])%2333;}cout<<f[1][m];return 0;}经典线性 dp
最长上升子序列
最长上升子序列
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=5010;
int n;
int a[N];
int f[N];//f[i]表示以a[i]结尾的最长的子序列的长度，找出j<i，a[j]<a[i]然后最大的f[j]
int main(){cin>>n;int ret=0;for(int i=1;i<=n;i++){cin>>a[i];f[i]=1;//因为最小为1for(int j=1;j<i;j++){if(a[j]<a[i]){f[i]=max(f[i],f[j]+1);}}ret=max(ret,f[i]);}cout<<ret;return 0;
}【模板】最长上升子序列
【模板】最长上升子序列
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=1e6+10;int a[N];
int f[N];//f[i]表示的含义是当长度为i时的所有子序列的值，中最小的值，这个数组一定是单调递增的
//每次一个新的a[i]，如果大于f[i]的话，小于等于f[i+1],那么以a[i]结束的子序列的长度为i+1,
//也就是f[i+1]=a[i]
int len;//记录有效的f[i]的长度int n;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}//初始化一个f[1],不然启动不起来f[1]=a[1];len++;for(int i=2;i<=n;i++){//先考虑边界情况，如果a[i]比最大的f[len]还大，那么就没有a[i]<=f[l+1]了if(a[i]>f[len])f[++len]=a[i];//边界情况 else{ //找到一个f[l+1],a[i]>f[l],a[i]<=f[l+1],那么f[l+1]=a[i],怎么找呢，二分找int l=1;int r=len;while(l<r){int mid=(l+r)/2;if(f[mid]>=a[i]){r=mid;}else{l=mid+1;}//这样找出来的值，肯定是f[l]>=a[i]的，而且左边一个就是f[l-1]小于a[i]的}f[l]=a[i];//正常情况 }}cout<<len;return 0;
}牛可乐和最长公共子序列
牛可乐和最长公共子序列
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=5010;
string s,t;int f[N][N];//f[i][j]表示s的1~i,与t的1~j个字符中最长公共子序列的长度
//判断f[i][j]的值为多少的时候，如果s[i]==t[i],那么f[i][j]=f[i-1][j-1]+1
//如果s[i]!=t[i],f[i][j]=max(f[i-1][j],f[i][j-1]),因为f[i-1][j],f[i][j-1]这两个绝对比f[i-1][j-1]大int main(){while(cin>>s>>t){int n=s.size();int m=t.size();//提前记录个数s=" "+s;t=" "+t;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i]==t[j]){f[i][j]=f[i-1][j-1]+1;}else{f[i][j]=max(f[i-1][j],f[i][j-1]);}}}cout<<f[n][m]<<endl;}return 0;
}01 背包
01 背包
01 背包
//#include<iostream>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//
//const int N=1010;
//int f[N][N];
1.状态表示
f[i][j]表示1~i个物品中选择总体积不大于j的最大价值为f[i][j]
所以等价为在f[i-1][j]的基础上要不要选择物品i
不选的话，f[i][j]=f[i-1][j]
要选的话，且v[i]<=j,f[i][j]=w[i]+f[i-1][j-v[i]]
所以f[i][j]为上面两个之中的最大值
2.初始化，我们看到f[i][j]会利用第i-1行的j列及前面的数据
所以从f[1][1]开始遍历的时候，就要初始化好第0行的数据
第0行选择0个物品，总体积为j，所以总价值为0
3.遍历顺序，，，从上往下，从左往右
//
1.状态表示
f[i][j]表示1~i个物品中选择总体积必须为j的最大价值为f[i][j]，其余不变
2.初始化，我们看到f[i][j]会利用第i-1行的j列及前面的数据
所以从f[1][1]开始遍历的时候，就要初始化好第0行的数据
第0行选择0个物品,所以总价值为0,第0行选择体积为j的，因为选择第0个物品，所以这个是不满足题意的
所以f[0][0]=0;f[0][1~n]不满足题意
因为求最大值，所以我们可以把不满足题意的初始化为负无穷
而且后面的f[i][j]，只要使用到了前面的负无穷，说明它也是不满足题意的
3.遍历顺序，，，从上往下，从左往右，i从1开始，因为i=0已经初始化好了，j从0开始，因为体积为0的时候，f为0，这个方法要适用
//int n,V;
//
//int v[N];
//int w[N];
//int main(){
// cin>>n>>V;
// for(int i=1;i<=n;i++){
// cin>>v[i]>>w[i];
// }
// for(int i=1;i<=n;i++){
// for(int j=0;j<=V;j++){
// f[i][j]=f[i-1][j];
// if(v[i]<=j){
// f[i][j]=max(f[i][j],w[i]+f[i-1][j-v[i]]);
// }
// }
// }
// cout<<f[n][V]<<endl;
// memset(f,-0x3f,sizeof f);
// f[0][0]=0;
// for(int i=1;i<=n;i++){
// for(int j=0;j<=V;j++){
// f[i][j]=f[i-1][j];
// if(v[i]<=j){
// f[i][j]=max(f[i][j],w[i]+f[i-1][j-v[i]]);
// }
// }
// }
// if(f[n][V]<=0)cout<<0<<endl;
// else cout<<f[n][V];
// return 0;
//}
//
//#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=1010;
int f[N];
int n,V;
//所谓空间优化，就是把一维的去掉，然后看是不是要更改遍历顺序，因为每个f[i][j]都是依赖上一排前面的，所以从后往前遍历
int v[N];
int w[N];
int main(){cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){
// for(int j=0;j<=V;j++){
// for(int j=v[i];j<=V;j++){for(int j=V;j>=v[i];j--){
// f[j]=f[j];
// if(v[i]<=j){f[j]=max(f[j],w[i]+f[j-v[i]]);}}cout<<f[V]<<endl;memset(f,-0x3f,sizeof f);f[0]=0;for(int i=1;i<=n;i++){for(int j=V;j>=v[i];j--){
// f[j]=[j];
// if(v[i]<=j){f[j]=max(f[j],w[i]+f[j-v[i]]);}}if(f[V]<=0)cout<<0<<endl;else cout<<f[V];return 0;
}
小A点菜
小A点菜
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=110;
const int M=10010;
int n,m;int a[N];//每个多少钱
//1.
int f[N][M];//f[i][j]表示在1~i个菜中选择总价格为j的点菜个数
//不选i，f[i][j]=f[i-1][j],选i，f[i][j]=f[i-1][j-a[i]]
//f[i][j]=f[i-1][j]+f[i-1][j-a[i]]
//2.初始化,第一行全0，因为当没有菜的时候总价格为j元的方案为0，f[0][0]=1;没有菜的时候总价格为0元的方案为1.就是不选
//3.顺序：int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}
// memset(f,0,sizeof f);f[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=a[i]){f[i][j]=f[i][j]+f[i-1][j-a[i]];}}}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout<<f[i][j]<<" ";
// }
// cout<<endl;
// }cout<<f[n][m]<<endl;return 0;
}完全背包
【模板】完全背包
【模板】完全背包
//#include<iostream>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//
//const int N=1010;
//int f[N][N];//状态表示。f[i][j]表示选择1~i个物品中，总体积<=j的最大价值
不选择i，f[i][j]==f[i-1][j],选择i，f[i][j]=f[i][j-w[i]]+w[i]
遍历顺序，必须从上往下，从左往右
初始化：最左：0，最上0
//
第二问，初始化：f[0][0]=0;负无穷
//
//int v[N];
//int w[N];
//int n,m;
//int main(){
// cin>>n>>m;
// for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
// 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][j-v[i]]+w[i]);
// }
// }
// }
// cout<<f[n][m]<<endl;
// 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][j-v[i]]+w[i]);
// }
// }
// }
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
cout<<f[i][j]<<" ";
}
cout<<endl;
}
// if(f[n][m]<=0)cout<< 0<< endl;
// else cout<<f[n][m]<<endl;
// return 0;
//}#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//空间优化，必须从左往右
const int N=1010;
int f[N];
int v[N];
int w[N];
int n,m;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=v[i];j<=m;j++){
// f[j]=f[j];
// if(j>=v[i]){f[j]=max(f[j],f[j-v[i]]+w[i]);
// }}}cout<<f[m]<<endl;memset(f,-0x3f,sizeof f);f[0]=0;for(int i=1;i<=n;i++){for(int j=v[i];j<=m;j++){
// f[j]=f[j];
// if(j>=v[i]){f[j]=max(f[j],f[j-v[i]]+w[i]);}}if(f[m]<=0)cout<< 0<< endl;else cout<<f[m]<<endl;return 0;
}多重背包
多重背包
多重背包
//#include<iostream>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//
//const int N=110;
//int f[N][N];//f[i][j]表示表示从1~i个中选择重量小于等于j的最大价值
状态转移方程，要判断每个数量了
初始化0
//int n,m;
//int x[N],w[N],v[N];
//int main(){
// cin>>n>>m;
// for(int i=1;i<=n;i++)cin>>x[i]>>w[i]>>v[i];
// for(int i=1;i<=n;i++){
// for(int j=0;j<=m;j++){
// for(int k=0;k<=x[i]&&j>=k*w[i];k++){
// f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]+k*v[i]);//包含了f[i-1][j]
// }
// }
// }
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
cout<<f[i][j]<<" ";
}
cout<<endl;
}
// cout<<f[n][m]<<endl;
// return 0;
//}//#include<iostream>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//
//const int N=110;
//int f[N];//f[i][j]表示表示从1~i个中选择重量小于等于j的最大价值
状态转移方程，要判断每个数量了
初始化0
//int n,m;
//int x[N],w[N],v[N];
//int main(){
// cin>>n>>m;
// for(int i=1;i<=n;i++)cin>>x[i]>>w[i]>>v[i];
// for(int i=1;i<=n;i++){
// for(int j=m;j>=0;j--){
// for(int k=0;k<=x[i]&&j>=k*w[i];k++){
// f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);//包含了f[i-1][j]
// }
// }
// }
// cout<<f[m]<<endl;
// return 0;
//}//#include<iostream>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//
//
第二个办法就是把选择x[i]个i分成每个组，每个组的选择为0或1
比如9个i物品，每个物品重量y,价值z
那么可以选择0~9个i物品，就可以转化为,1,2,4,2个i物品，四个分组，比如四个物品的分组，重量4*y,价值4*z
选择0~9个物品，就可以变成对四个分组的0,1选择
//
数量最多为20,则1,2,4,8,5，那么每个物品最多五个分组，所以最多数量为110*5
//
//const int N=110*5;
//int f[N][N];//f[i][j]表示表示从1~i个中选择重量小于等于j的最大价值
状态转移方程
初始化0
//int n,m;
//int w[N],v[N];
//int main(){
// cin>>n>>m;
// int index=0;//表示第几个分组了,也可以代表有几个01物品，就是把大物品的概念等价为小物品
// for(int i=1;i<=n;i++){
// //一边输入一边分组了
// int x,y,z;//分别代表每个物品数量，重量，价值
// cin>>x>>y>>z;
// int j=1;
// //创建2的倍数的分组
// while(x>=j){
// x=x-j;
// index++;
// w[index]=j*y;
// v[index]=j*z;
// j*=2;
// }
// //剩余的，非2的倍数分组
// if(x>0){
// index++;
// w[index]=x*y;
// v[index]=x*z;
// }
// }
// for(int i=1;i<=index;i++){
// for(int j=0;j<=m;j++){
// f[i][j]=f[i-1][j];
// if(j>=w[i]){
// f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
// }
// }
// }
// cout<<f[index][m]<<endl;
// return 0;
//}#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;//第二个办法就是把选择x[i]个i分成每个组，每个组的选择为0或1
//比如9个i物品，每个物品重量y,价值z
//那么可以选择0~9个i物品，就可以转化为,1,2,4,2个i物品，四个分组，比如四个物品的分组，重量4*y,价值4*z
//选择0~9个物品，就可以变成对四个分组的0,1选择//数量最多为20,则1,2,4,8,5，那么每个物品最多五个分组，所以最多数量为110*5const int N=110*5;
int f[N];//f[i][j]表示表示从1~i个中选择重量小于等于j的最大价值
//状态转移方程
//初始化0
int n,m;
int w[N],v[N];
int main(){cin>>n>>m;int index=0;//表示第几个分组了,也可以代表有几个01物品，就是把大物品的概念等价为小物品for(int i=1;i<=n;i++){//一边输入一边分组了int x,y,z;//分别代表每个物品数量，重量，价值cin>>x>>y>>z;int j=1;//创建2的倍数的分组while(x>=j){x=x-j;index++;w[index]=j*y;v[index]=j*z;j*=2;}//剩余的，非2的倍数分组if(x>0){index++;w[index]=x*y;v[index]=x*z;}}for(int i=1;i<=index;i++){for(int j=m;j>=w[i];j--){f[j]=max(f[j],f[j-w[i]]+v[i]);}}cout<<f[m]<<endl;return 0;
}
//但是这个只能计算最大价值，不能计算总的方案个数，因为同一个物品的不同分组的选择，可以是一个方案，但是看成了不同方案，所以不行
 Jenkins共享库与k8s集成)
