[关闭]
@hhzhhzhhz 2024-12-21T18:24:10.000000Z 字数 6922 阅读 351

赛前总结

1.　模板

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.  freopen("a.in","r",stdin);
  5.  freopen("a.out","w",stdout);
  8.  fclose(stdin);
  9.  fclose(stdout);
  10.  retrun 0;
  11. }

2.　快读快写

写不对就不写
scanf printf 不香吗？

3.　二分

  1. while(l<r) {
  2.     mid=(l+r+1)>>1;
  3.     if(judge(mid)) l=mid;
  4.     r=mid-1;
  5. }
  1. while(l<r) {
  2.     mid=(l+r)>>1;
  3.     if(judge(mid)) r=mid;
  4.     l=mid+1;
  5. }

4.　并查集

  1. init(){//初始化
  2.     for(int i=1;i<=n;i++){
  3.         f[i]=i;
  4.     }
  5. }
  1. get(int a){//查
  2.     if(a==f[a]) return a;
  3.     else return f[a]=get(f[a]);//路径压缩 
  4. }
  1. merge(int a,int b){//并
  2.     int fa,fb;
  3.     fa=get(a);
  4.     fb=get(b);
  5.     f[fa]=fb; 
  6. }

5.　队列（STL）

  1. #include<queue> //用到写一下，加.后可以弹出索引
  2. //      FIFO(First In First Out)
  3. queue<int > q;//定义 q
  4. q.push(x);    //将x压入q(队尾）
  5. q.pop(x);     //弹出队首
  6. q.front();    //取队首
  7. q.back();     //取队尾
  8. q.size();     //元素数
  9. q.empty();    //队列是否为空

建筑抢修
工作调度

  1. #include<queue>
  2. priority_queue<int > q1;//定义一个大根堆
  3. priority_queue<int ,vector<int> ,greater<int> > q2;//定义一个小根堆
  4. q1.top();      //取堆顶
  5. q1.top();      //弹出堆顶
  6. q1.push(x);    //压入x
  7. q1.size();     //元素数
  • 优先队列->重载运算符实现结构体
  1. #include<bits/stdc++.h>
  2. #include<queue>
  3. using namespace std;
  4. struct nod {
  5.     int a,b;
  6.     friend bool operator <(const nod &x,const nod &y) {//重载运算符以b为参数的大根堆
  7.         return x.b<y.b;
  8.     }
  9. }
  10. priority_queue<nod> q;
  11. int main() {
  12.     int n;
  13.     int t;
  14.     scanf("%d",&n);
  15.     for(int i=1; i<=n; i++) {
  16.         scanf("%d %d %d",&p.a,&p.b,&t);
  17.         if(t)
  18.             q.push(p);
  19.         else {
  20.             cout<<q.top().a<<q.top().b;
  21.             q.pop();
  22.         }
  23.     }
  24.     return 0;
  25. }

6.　栈(STL)

  1. #include<stack>
  2. //LIFO Last In First Out
  3. stack<int > s;
  4. stack<int >s;
  5. s.size();   //元素数 
  6. s.top();    //取栈顶 
  7. s.pop();    //弹出栈顶 
  8. s.push(x);  //压入x 
  9. s.empty();  //判断是否为空

7.　map(键值对)(STL)

　->方便查询和处理字符串等。

  1. #include<map>
  2. map<string,int> m2;
  3. map<int,int> m1;
  4. m1[a]=b;//赋值
  5. m1.find(x)==m1.end()  //判断是否有x这个元素

8.　归并排序(求逆序对)

  1. ???????
  2. merge(int l1 , int r1,int l2,int r2) {
  3.     int cnt=0,p=0;
  4.     while(l1<=r1&& l2<=r2)
  5.         if(a[l1]<=a[l2])    t[++cnt]=a[l1++];
  6.         else {
  7. //          ans[++num][4]=a[l1];
  8. //          ans[num][5]=a[l2]; 存逆序对
  9.             t[++cnt]=a[l2++];
  10.         }
  11.     while(l1<=r1)       t[++cnt]=a[l1++];
  12.     while(l2<=r2)       t[++cnt]=a[l2++];
  13.     for(int i=l1; i<=r2; i++) {
  14.         a[i]=t[++p];
  15.     }
  16. }
  17. merge_sort(int l,int r) {
  18.     int mid=(l+r)>>1;
  19.     if(l<r) {
  20.         merge_sort(l,mid);
  21.         merge_sort(mid+1,r);
  22.         merge(l,mid,mid+1,r);
  23.     }
  24. }
  1. #include "stdio.h"
  2. int count=0;
  3. void Merge(int r[],int r1[],int s,int m,int t) {    // 合并子序列
  4.     int i=s,j=m+1,k=s;
  5.     int b;
  6.     while(i<=m && j<=t) {
  7.         if(r[i]<=r[j]) {      // 取较小者放入r1[k]中
  8.             r1[k++]=r[i++];
  9.         } else {
  10.             count+=m-i+1;   // 若左边数大于右边数，则左边数及其后边数都大于该右边数
  11.             b=i;
  12.             while(b<=m) {
  13.                 printf("[%d,%d]\n",r[b],r[j]);
  14.                 b++;
  15.             }
  16.             r1[k++]=r[j++];
  17.         }
  19.     }
  20.     while(i<=m)         // 若第一个子序列没处理完，则进行收尾处理;下同
  21.         r1[k++]=r[i++];
  22.     while(j<=t)
  23.         r1[k++]=r[j++];
  24. }
  25. void MergeSort(int r[],int s,int t) { // 对序列r[s]~r[t]进行归并排序
  26.     int m,r1[1000],i;
  27.     if(s==t)
  28.         return ;
  29.     else {
  30.         m=(s+t)/2;         // 划分
  31.         MergeSort(r,s,m);     // 子问题1
  32.         MergeSort(r,m+1,t);   // 子问题2
  33.         Merge(r,r1,s,m,t);    // 合并
  34.         for(i=s; i<=t; i++)
  35.             r[i]=r1[i];
  36.     }
  37. }
  38. int main() {
  39.     int r[]= {1,2,4,3,7,6,5,1},i;
  40.     MergeSort(r,0,7);       // 三个参数分别为待查数组、起始下标、截止下标
  41.     for(i=0; i<=7; i++)
  42.         printf("%d ",r[i]);
  43.     printf("\n一共 %d个逆序对\n",count);
  44. }

9.　动态规划

要先确定要求的再f[][]表示什么
再确定动态转移方程
　

  1. 01背包
    一个物品只能用一次
    eg:洛谷 采药
  1.      for(int i=1;i<=n;i++){
  2.          for(int j=v;j>=w[i];j++{
  3.             f[j]=max(f[j],f[j-w[i]]+v[i]);
  4.          }
  5.      }

2.　完全背包
　　物品可以用无限次
　　eg:洛谷 疯狂的采药

  1. 　for(int i=1;i<=n;i++){
  2. 　    for(int i=w[i];i<=v;i++){
  3. 　       f[j]=max(f[j],f[j-w[i]]+v[i]);
  4. 　    }
  5. 　}

3.　LIS Longest Increasing Subsequence
　　eg:洛谷 p1091 合唱队形

  1. void lis() {
  2.     for(int i=1; i<=n; i++) {
  3.         for(int j=0; j<i; j++) {
  4.            if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
  5.         }
  6.     }
  7. }
  1.  //该题用nologn 的方法求得 最长不上升子序列 和 最长上升子序列 板子有备无患 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int a[100010];
  5. int f1[100010],f2[100010],len1=1,len2=1;
  6. //f1求最长不上升子序列
  7. //f2求最长上升子序列  即 第二问的解 
  9. //bool cmp(int a,int b) {
  10. //  return a>b;
  11. //}
  12. int main() {
  13.     int n=0;
  14.     while(scanf("%d",&a[++n])!=EOF);
  15.     f1[1]=a[1];
  16.     f2[1]=a[1];
  17.     for(int i=2; i=a[i]) f1[++len1]=a[i];//满足条件接上 
  18.         else *upper_bound(f1+1,f1+1+len1,a[i],greater  ())=a[i]; 
  19. //主要目的是为了将最后一个的数值尽可能放到最大使之后能放入的个数增加 达到序列最长的目的  
  20. //      else *upper_bound(f1+1,f1+1+len1,a[i],cmp)=a[i];               
  22. // upper_bound 与 lower_bound  返回值为地址，加*直接修改地址所对应的值
  23. // 两个函数分别为求在一个右半开的升序序列中求在自左向右第一个大于(等于)x的值的地址 upper为大于  lower为大于等于 
  24. // 在此升序是对于比较器而言的升序，故可以更改比较器，写个cmp，或直接用 greater  () 改为在 降序序列中找到第一个小于(等于）x的值的地址 
  25.         if(f2[len2] < a[i]) f2[++len2]=a[i];
  26.         else *lower_bound(f2+1,f2+1+len2,a[i])=a[i];
  27.     }
  28.     cout << len1 << endl << len2;
  29.     return 0;
  30. }
  1. //核心代码
  2. void lcs() {
  3. //  f[i][j]表示在a第i位前和b第j位前的lcs 
  4.     for(int i=1; i<=n1; i++) {
  5.         for(int j=1; j<=n2; j++) {
  6.            if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
  7.            if(a[i]!=b[j]) f[i][j]=max(f[i-1][j],f[i][j-1]);
  8.         }
  9.     }
  10. }

10.　图论

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int ver[10010];//该边终点
  4. int nxt[10010];//下一条边
  5. int head[10010];//表头
  6. int va[10010];//该边权值
  7. int cnt;
  8. void add(int x,int y,int v) {//加边 
  9.     cnt++;
  10.     ver[cnt]=y;// 终点
  11.     nxt[cnt]=head[x]; //把下一条边指向x原来的第一条边
  12.     head[x]=cnt;//使x下的这条边成为第一条边
  13.     va[cnt]=v;//赋权值
  14. }
  15. int bl(int x) {
  16.     for(int i=head[x]/*第一条边*/;i; i=nxt[i]){//遍历 
  17. //        va[i]; //这边权值
  18. //        ver[i];//这条边指向的点 
  19.     }
  20. }
  21. int main() {
  22.     int n;
  23.     scanf("%d",&n);
  24.     int x,y,v;
  25.     for(int i=1; i<=n; i++) {
  26.         cin>>x>>y>>v;
  27.         add(x,y,v);
  28. //      add(y,x,v);无向图
  29.     }
  30.     bl(1);
  31. }
  1. #include<bits/stdc++.h>
  2. #include<queue>
  3. using namespace std;
  4. const int bn=10010,dn=10010;//最大边数、最大点数  
  5. int head[dn],v[2*bn],ver[2*bn],nxt[2*bn];
  6. int cnt;
  7. void add(int x,int y,int va) {
  8.     cnt++;
  9.     nxt[cnt]=head[x];
  10.     head[x]=cnt;
  11.     ver[cnt]=y;
  12.     v[cnt]=va;
  13. }
  14. int vis[10010];
  15. int dis[10010];
  16. void spfa(int s) {
  17.     memset(dis,0x3f,sizeof(dis));
  18.     queue<int > q;//存下一步要去的点
  19.     q.push(s);
  20.     dis[s]=0;
  21.     vis[s]=1;
  22.     while(!q.empty()) {
  23.         int x=q.front();
  24.         q.pop();
  25.         vis[x]=0;
  26.         for(int i=head[x]; i; i=nxt[i]) {//枚举边
  27.             int to=ver[i],va=v[i];//找到去的点，和路上的权值
  28.             if(dis[to]>dis[x]+va) {
  29.                 dis[to]=dis[x]+va;
  30.                 if(!vis[to]) {
  31.                     q.push(to);
  32.                     vis[to]=1;
  33.                 }
  34.             }
  35.         }
  36.     }
  37. }
  38. int main() {
  39.     int n;
  40.     scanf("%d",&n);//输入边数 
  41.     int x,y,v;
  42.     for(int i=1; i<=n; i++) {
  43.         scanf("%d %d %d",&x,&y,&v);
  44.         add(x,y,v);
  45.         add(y,x,v);
  46.     }
  47.     int s;
  48.     scanf("%d",&s);
  49.     spfa(s);
  50.     for(int i=1; i<=n; i++)
  51.         printf("%d\n",dis[i]);
  52.     return 0;
  53. }
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MN=510;
  4. int dis[MN][MN];
  5. int main() {
  6.     int n,m,q;
  7.     int x,y,z;
  8.     memset(dis,0x3f,sizeof(dis));
  9.     scanf("%d %d %d",&n,&m,&q);//边数 点数 询问次数；
  10.     for(int i=1;i<=m;i++){
  11.         dis[i][i]=0;
  12.     }
  13.     for(int i=1; i<=n; i++) {
  14.         scanf("%d %d %d",&x,&y,&z);
  15.         dis[x][y]=z;
  16.         dis[y][x]=z;
  17.     }
  18.     for(int k=1; k<=n; k++) {
  19.         for(int i=1; i<=n; i++) {
  20.             for(int j=1; j<=n; j++) {
  21.             dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
  22.             }
  23.         }
  24.     }
  25.     for(int i=1; i<=q; i++) {
  26.           scanf("%d %d",&x,&y);
  27.           printf("%d",dis[x][y]);
  28.     }
  29.     return 0;
  30. }
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,fa[5010],ans,cnt;
  4. struct nod {
  5.     int fr,to,v;
  6. } a[200010];
  7. inline int get(int x) {
  8.     if(x==fa[x]) return x;
  9.     return fa[x]=get(fa[x]);
  10. }
  11. inline int merge(int a,int b) {
  12.     int f_a=get(a),f_b=get(b);
  13.     fa[f_a]=f_b;
  14. }
  15. bool cmp(nod a,nod b) {
  16.     return a.v<b.v;
  17. }
  18. void kruskal() {
  19.     for(int i=1; i<=m; i++) {
  20.         int u=get(a[i].fr);
  21.         int v=get(a[i].to);
  22.         if(u==v) continue;//在并查集里-即已经有一条更短的路在树中
  23.         else {
  24.             fa[u]=v;
  25.             ans+=a[i].v;
  26.             cnt++;
  27.         }
  28.         if(cnt==n-1) return;//即已形成树 
  29.     }
  30. }
  31. int main() {
  32.     scanf("%d %d",&n,&m);
  33.     for(int i=1; i<=n; i++) fa[i]=i;
  34.     for(int i=1; i<=m; i++) {
  35.         scanf("%d %d %d",&a[i].fr,&a[i].to,&a[i].v);
  36.     }
  37.     sort(a+1,a+1+m,cmp);//按照边长升序排列 
  38.     kruskal();
  39.     printf("%d",ans);
  40.     return 0;
  41. }

11. st表(RMQ,区间最值)

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int f[200010][20];
  5. int main() {
  6.     scanf("%d",&n);
  7.     for(int i=1; i<=n; i++) {
  8.         scanf("%d",&f[i][0]);
  9.     }
  10.     int m,l,r;
  11.     int k=2;
  12.     for(int j=1; j<=19; j++) {
  13.         for(int i=1; i+k-1<=n; i++) {
  14.             f[i][j]=max(f[i][j-1],f[i+(k>>1)][j-1]);
  15.         }
  16.         k*=2;
  17.     }
  18.     scanf("%d",&m);
  19.     for(int i=1; i<=m; i++) {
  20.         scanf("%d%d",&l,&r);
  21.         int t=log(r-l+1)/log(2);//换底公式
  22.         int x=pow(2,t);
  23.         printf("%d\n",max(f[l][t],f[r-x+1][t]));//将没有表示过的【l，r】,变为已经表示过的两端
  24.     }
  25.     return 0;
  26. }

12.快速幂

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long poww(long long a,long long b) {
  4.     int res=1,x=a;
  5.     while(b>0) {
  6.         if(b&1) res=res*x;
  7.         x=x*x;
  8.         b>>=1;
  9.     }
  10.     return res;
  11. }
  12. int main() {
  13.     long long a,b;
  14.     scanf("%lld %lld",&a,&b);
  15.     printf("%lld",poww(a,b));
  16.     return 0;
  17. }

13.快排函数

  1. bool cmp(node a, node b){
  2.     if(a.x != b.x){ // 如果两个 x 不等则以 x 的大小排序
  3.         return a.x > b.x;
  4.     }
  5.     return a.y > b.y; // 否则以 y 的大小排序
  6. }
  7. sort(c + 1, c + 1001, cmp);
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注