1 前缀和 /// 给定一组数,求任意区间的总和 #include<bits/stdc++.h> using namespace std; const int N=100010; int n,a[N],s[N],m; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; } while(m--) { int l,r; cin>>l>>r; cout<<s[r]-s[l-1]<<endl; } return 0; } 1-2 矩阵的前缀和 思路://https://blog.csdn.net/m0_62881629/article/details/124762394?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168250250916800227440048%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=168250250916800227440048&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-5-124762394-null-null.142^v86^control,239^v2^insert_chatgpt&utm_term=P1387%20%E6%9C%80%E5%A4%A7%E6%AD%A3%E6%96%B9%E5%BD%A2&spm=1018.2226.3001.4187 题目链接://https://www.luogu.com.cn/problem/P1387 ///s[i] [j] = s[i-1][j] + s[i][j-1 ] + a[i] [j] - s[i-1][ j-1] #include<iostream> #include<cstdio> using namespace std; const int N=1010; int a[N][N],s[N][N]; int main() { int n,m,q; scanf("%d%d%d",&n,&m,&q); 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++) s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1]; while(q--) { int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]); } return 0; } 洛谷:P1387 #include <bits/stdc++.h> using namespace std; int n,m,ans,tot,cnt; int s[101][101],ma[101][101],sum[101][101]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>ma[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j]=ma[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//前缀和 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int p=i,q=j,tmp=1;//(p,q)为起点 逐步扩展,tmp相当于长度范围. if(ma[p][q]==1 && sum[p][q]-sum[i-1][q]-sum[p][j-1]+sum[i-1][j-1]==tmp*tmp && p<=n&&q<=m) { while(ma[p][q]==1&&sum[p][q]-sum[i-1][q]-sum[p][j-1]+sum[i-1][j-1]==tmp*tmp && p<=n&&q<=m) p++,q++,tmp++; ans=max(ans,tmp-1); } } printf("%d\n",ans); } 2-1 一维差分 ///在差分中,b数组是a[i]=b[1]+b[2]+...+b[i];这样的形式叫做差分数组 ///也就是a数组是b数组的前缀和; 给出一组数组,要求你在某个区间里加上一个数c,数据有多组 例如:1 2 3 4 在 1-2 区间+1,在2-3区间+2,在1-4区间+1; 最终结果是 3 6 6 5 代码实现: ///由于前缀和的存在,如果给b[l]+c,那么a数组从l到n都加上了c,那么如果给b[r+1]-c,这就实现了从l到r的加c形式; #include<bits/stdc++.h> using namespace std; const int N=100010; int a[N],b[N]; int n,m; void Insert(int l,int r,int c) { b[l]+=c; b[r+1]-=c; } int main() { cin>>n>>m;//n为数组的长度,m为加的次数 for(int i=1;i<=n;i++) { cin>>a[i]; Insert(i,i,a[i]);///从区间到区间末,加上c,这一步是创建差分数组b } while(m--) { int l,r,c; cin>>l>>r>>c; Insert(l,r,c);///进行操作; } for(int i=1;i<=n;i++) { b[i]+=b[i-1];///更新数组; cout<<b[i]<<" "; } return 0; } 2-2 差分矩阵(二维差分) 与一维差分差不多,和前缀和一样,只是多一个公式 #include<bits/stdc++.h> using namespace std; const int N=1010; int a[N][N],b[N][N]; int n,m,q;//nxm的矩阵,q次访问; 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; } int main() { cin>>n>>m>>q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>a[i][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]; cout<<b[i][j]<<" "; } cout<<endl; } return 0; } 3-1 双指针 求最长不重复序列 #include<bits/stdc++.h> using namespace std; const int N=100010; int n,res=0; int a[N],s[N];///s用来储存a[i]中的数字出现的次数 int main() { cin>>n; for(int i=0;i<n;i++ cin>>a[i]; for(int i=0;i<n;i++) { s[a[i]]++; while(s[a[i]]>1)///循环,直到j与i的区间内没有重复元素; { s[a[j]]--; j++; } res=max(res,i-j+1); } cout<<res; return 0; } 4-1 离散化 #include<bits/stdc++.h> using namespace std; const int N=300010; typedef pair<int,int>PII; int n,m; int a[N],s[N]; vector<int> alls; vector<PII>add,query; int find(int x) { int l=0,r=alls.size()-1; while(l<r) { int mid=l+r>>1; if(alls[mid]>x) r=mid-1; else l=mid+1; } return l; } int main() { cin>>n>>m; for(int i=0;i<n;i++) { int x,c; cin>>x>>c; add.push_back({x,c}); alls.push_back(x); } for(int i=0;i<m;i++) { int l,r; cin>>l>>r; query.push_back({l,r}); alls.push_back(l); alls.push_back(r); } sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()),alls.end()); for(auto i:add) { int x=find(i.first); a[x]+=i.second; } for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i]; for(auto i:query) { int l=find(i .first),r=find(i.second); cout<<s[r]-s[l-1]<<endl; } return 0; } 5-1 Trie树,快速存储字符串和询问字符串 #include<bits/stdc++.h> using namespace std; const int N=100010; int son[N][26],cnt[N],idx; void Insert(char str[])///插入操作 { int p=0; for(int i=0;str[i];i++) { int u=str[i]-'a'; if(!son[p][u]) son[p][u]=++idx;///如果没有子节点,要自己创建子节点 p=son[p][u]; } cnt[p]++; } int query(char str[])///询问操作 { int p=0; for(int i=0;str[i];i++) { int u=str[i]-'a'; if(!son[p][u]) return 0;///没有子节点,说明不是这个字符串,返回0; p=son[p][u]; } return cnt[p]; } int main() { int n; cin>>n; while(n--) { char x; cin>>x; char y[N]; cin>>y; if(x=='I') Insert(y); else { int res=0; res=query(y); cout<<res<<endl; } } } 6-1 并查集 ///find函数可能有点难理解,自己尝试画下图随便理解好吧 ///M是合并,Q是询问是否在一个树中 #include<bits/stdc++.h> using namespace std; const int N=10010; int n,m; int q[N]; int find(int x) { if(q[x]!=x) q[x]=find(q[x]));///如果x不是树的头结点,向上循环查找到头结点为止. ///可以自己画图理解一下; return q[x]; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) q[i]=i; while(m--) { char op[2]; int a,b; scanf("%s%d%d",&op,&a,&b); if(op[0]=='M') q[find(a)]=find(b); else { if(find(a)==find(b)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; } 6-2 查并集,但是可能输出长度 #include<bits/stdc++.h> using namespace std; const int N=100010; int n,m; int p[N],size[N]; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { p[i]=i; size[i]=1; } while(m--) { ///C为合并,Q1为 检查是否在同一区间,Q2检查长度; char op[2]; scanf("%s",&op); int a,b; if(op[0]=='C') { cin>>a>>b; if(find(a)==find(b)) continue;///特判 size[find(b)]+=size[find(a)]; p[find(a)]=find(b); } else if(op[1]=='1') { cin>>a>>b; if(find(a)==find(b)) cout<<"YES"<<endl; else cout<<"No"<<endl; } else if(op[1]=='2') { cin>>a; cout<<size[find(a)]<<endl; } } } 6-3 食物链 https://www.luogu.com.cn/problem/P2024 ///这题是真难,看视频加理解一共花了俩小时 #include<bits/stdc++.h> using namespace std; const int N=100010; int n,m,res=0; int p[N],d[N]; int find(int x) { if(p[x]!=x)///与以往不同,这里的d数组刚开始的作用是,x节点与父节点的距离,经过find函数递归之后 ///d数组变成了,x节点到头节点的距离,这样就可以来判断是不是同一类和接下来做题了 { int t=find(p[x]); d[x]+=d[p[x]];///因为要用到p[x],所以先储存; p[x]=t; } return p[x]; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) p[i]=i; while(m--) { int a,b,c; cin>>c>>a>>b; if(a>n||b>n) res++; else { if(c==1) { int pa=find (a),pb=find(b); if(pa==pb&&(d[a]-d[b])%3) res++;///3个一循环;如果A和B是同类,而且他俩已经在合并过了,那么两者的距离相减,如果余三不得0那么就是错的; else { p[pa]=pb; d[pa]=d[b]-d[a]; } } else { int pa=find(a),pb=find(b); if(pa==pb&&(d[a]-d[b]-1)%3) res++; else if(pa!=pb) { p[pa]=pb; d[pa]=d[b]+1-d[a]; } } } } cout<<res; return 0; } 6-4 自动程序检测装置 https://www.luogu.com.cn/problem/P1955 ///这个题是我得知有查并集这个算法的起初 ///查并集+离散化,题目i和j都开到10的九次方了,不用离散化等着爆吧 ///本题思路 #include<bits/stdc++.h> using namespace std; const int N=400010; int t,n; int a[2*N],p[N],d[2*N],b[N],c[N]; int find(int x)///典 { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) { cin>>a[2*i-1]>>a[2*i]>>c[i]; d[2*i-1]=a[2*i-1],d[2*i]=a[2*i]; } sort(d+1,d+2*n+1); int h=0; b[0]=-1; for(int i=1;i<=2*n;i++) if(b[h]!=d[i]) b[++h]=d[i];///离散化完成,用了两次这个离散化模板了,感觉yxc老师的那个离散化模板用不了一点 for(int i=1;i<=h;i++) p[i]=i;///更新爹节点 for(int i=1;i<=n;i++) { if(c[i]==0) continue; int x=lower_bound(b+1,b+h+1,a[2*i-1])-b; int y=lower_bound(b+1,b+h+1,a[2*i])-b; if(find(x)==find(y)) continue; else p[find(x)]=find(y);///将所有相等的元素,放进树里面;接下来的就是狠狠的查找有没有内鬼 } bool f=false; for(int i=1;i<=n;i++) { if(c[i]==1) continue; int x=lower_bound(b+1,b+h+1,a[2*i-1])-b; int y=lower_bound(b+1,b+h+1,a[2*i])-b; if(find(x)==find(y))///查找内鬼,如果有人在相等的树里面,就是内鬼! { cout<<"NO"<<endl; f=true; break; } } if(!f) cout<<"YES"<<endl; } return 0; } 7-0 利用动态二维数组创建无权邻接表 #include<bits/stdc++.h> using namespace std; const int N=100010; vector<int>g[N]; int n,m; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; g[x].push_back(y); g[y],push_back(x); } for(int i=1;i<=n;i++) { cout<<i<<":"<<" "<<endl; for(auto v:g[i]) cout<<v<<" "; cout<<endl; } } 7-1 创立有权邻接表 #include<bits/stdc++.h> using namespace std; const int N=100010; int n,m; struct node { int to; int val; }; vector<node>g[N]; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; node tmp; cin>>a>>b>>c; tmp.to=b; tmp.val=c; g[a].push_back(tmp); } for(int i=1;i<=n;i++) { cout<<i<<":"<<endl; for(auto v:g[i]) cout<<v.to<<" "<<v.val; cout<<endl; } return 0; }