[关闭]
@lqhsr 2022-09-20T04:14:00.000000Z 字数 48564 阅读 812

NOIP初级模板大全（建议配套LGOJ食用）

PS:点击右上角三条横线可查看目录

杂项

快速读入（包括符号）

  1. long long read(){
  2.     long long x=0,f=1;
  3.     char c=getchar();
  4.     while((c<'0'||c>'9')&&c!='-')c=getchar();
  5.     if(c=='-')f=-1,c=getchar();
  6.     while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
  7.     return f*x;
  8. }

ST表

  1. //交LG的话记得加快读~~~
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int n,m,f[5000005][20];//f[i][j]为从i开始(2^j)-1的最大值 
  5. int main(){
  6.     cin>>n>>m;
  7.     for(int i=1;i<=n;i++){
  8.         cin>>f[i][0];
  9.     }
  10.     for(int k=1;k<=20;k++){
  11.         for(int i=1;i<=n-(1<<k)+1;i++){
  12.             f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);//将区间拆成两半[i,i+2^j-1]和[i+2^(j-1),j-1]
  13.         }
  14.     }//如果是先枚举i那么在f[1][2]的时候会不知道f[2][1]的值 
  15.     for(int i=1;i<=m;i++){
  16.         int le,ri;cin>>le>>ri;
  17.         int t=log(ri-le+1)/log(2);//换底公式即log以2为ri-le+1的对数，找到最大的k
  18.         printf("%d\n",max(f[le][t],f[ri-(1<<t)+1][t]));//左右两半区间查询
  19.         //记得+1如1~5:log2(5)=2,f[1][2]为1~4的max而后半段要2~5，5-2^2=1所以要加1！！！ 
  20.     }
  21. }

线段树1

  1. #include<bits/stdc++.h>
  2. #include<bits/stdc++.h>
  3. #define ll long long
  4. using namespace std;
  5. ll n,m,a[100005];
  6. struct node{
  7.     ll sum,add;
  8.     ll l,r;
  9. }t[1000005];
  10. ll read(){
  11.     ll x=0;char ch=getchar();
  12.     while(ch>'9'||ch<'0')ch=getchar();
  13.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  14.     return x;
  15. }
  16. void build(ll p,ll l,ll r){
  17.     t[p].l=l,t[p].r=r;
  18.     if(l==r){t[p].sum=a[l];return ;}
  19.     ll mid=(l+r)>>1;
  20.     build(p*2,l,mid);
  21.     build(p*2+1,mid+1,r);
  22.     t[p].sum=t[p*2].sum+t[p*2+1].sum;
  23. }
  26. void spread(ll p){
  27.     if(t[p].add){
  28.         t[p*2].sum+=(ll)t[p].add*(t[p*2].r-t[p*2].l+1);//ll!!!
  29.         t[p*2+1].sum+=(ll)t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
  30.         t[p*2].add+=t[p].add;//别忘了
  31.         t[p*2+1].add+=t[p].add;
  32.                 t[p].add=0;
  33.     }
  34. }
  35. void add(ll p,ll l,ll r,ll k){
  36.     if(t[p].l>=l&&t[p].r<=r){
  37.         t[p].add+=k;
  38.         t[p].sum+=(ll)k*(t[p].r-t[p].l+1);//不要忘了
  39.         return ;
  40.     }
  41.     spread(p);
  42.     ll mid=(t[p].l+t[p].r)>>1;//记得是在这个节点记录的区间的中点
  43.     if(l<=mid)add(p*2,l,r,k);//注意是l<=mid否则当修改区间横跨了mid时就不会进行任何操作
  44.     if(r>mid)add(p*2+1,l,r,k);
  45.     t[p].sum=t[p*2].sum+t[p*2+1].sum;//还要记得修改sum
  46. }
  47. ll ask(ll p,ll l,ll r){
  48.     if(t[p].l>=l&&t[p].r<=r){
  49.         return t[p].sum;
  50.     }
  51.     spread(p);
  52.     t[p].sum=t[p*2].sum+t[p*2+1].sum;//每次spread之后都要从新统计sum！
  53.     ll mid=(t[p].r+t[p].l)>>1;
  54.     ll val=0;
  55.     if(l<=mid)val+=ask(p*2,l,r);//如果这里修改为l~mid下面改成mid+1~r，则下一次进入ask函数的mid
  56.     //就会比这一次的r大了,因为mid是该节点的中间点,mid=(t[p].r+t[p].l)>>1
  57.     //后来我想改成mid=(l+r)>>1配套l~mid和mid+1~r,但这样会出现更严重的问题，
  58.     //假设询问的区间全部位于整棵树的左子树，这个时候会出现
  59.     //到整棵树的右子树中去求询问区间的右半边的情况，找了个寂寞！(感谢mrgg的提醒)
  60.     if(r>mid)val+=ask(p*2+1,l,r);
  61.     return val;
  62. }
  63. int main(){
  64.     cin>>n>>m;
  65.     for(ll i=1;i<=n;i++){
  66.         a[i]=read();
  67.     }
  68.     build(1,1,n);
  69.     for(ll i=1;i<=m;i++){
  70.         ll ty=read();
  71.         if(ty==1){
  72.             ll cn=read(),cm=read(),cw=read();
  73.             add(1,cn,cm,cw);
  74.         }
  75.         else {
  76.             ll cn=read(),cm=read();
  77.             cout<<ask(1,cn,cm)<<endl;
  78.         }
  79.     }
  80. }

线段树2

  1. #include<bits/stdc++.h>
  2. #define ll long long 
  3. using namespace std;
  4. int n,m,a[1000005],mod;
  5. struct node{
  6.     ll sum,l,r,mu,add;
  7. }t[1000005];
  8. ll read(){
  9.     ll x=0;char ch=getchar();
  10.     while(ch<'0'||ch>'9')ch=getchar();
  11.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  12.     return x;
  13. }
  14. void build(ll p,ll l,ll r){
  15.     t[p].l=l,t[p].r=r;t[p].mu=1;
  16.     if(l==r){t[p].sum=a[l]%mod;return ;}
  17.     ll mid=(l+r)>>1;
  18.     build(p*2,l,mid);
  19.     build(p*2+1,mid+1,r);
  20.     t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
  21. }
  22. void spread(ll p){
  25.     t[p*2].sum=(ll)(t[p].mu*t[p*2].sum+((t[p*2].r-t[p*2].l+1)*t[p].add)%mod)%mod;
  26.     t[p*2+1].sum=(ll)(t[p].mu*t[p*2+1].sum+(t[p].add*(t[p*2+1].r-t[p*2+1].l+1))%mod)%mod;
  28.     t[p*2].mu=(ll)(t[p*2].mu*t[p].mu)%mod;
  29.     t[p*2+1].mu=(ll)(t[p*2+1].mu*t[p].mu)%mod;
  31.     t[p*2].add=(ll)(t[p*2].add*t[p].mu+t[p].add)%mod;
  32.     t[p*2+1].add=(ll)(t[p*2+1].add*t[p].mu+t[p].add)%mod;
  34.     t[p].mu=1,t[p].add=0;
  35. }
  36. void add(ll p,ll l,ll r,ll k){
  37.     if(t[p].l>=l&&t[p].r<=r){
  38.         t[p].add=(t[p].add+k)%mod;
  39.         t[p].sum=(ll)(t[p].sum+k*(t[p].r-t[p].l+1))%mod;//只要加上增加的就好
  40.         return ;
  41.     }
  42.     spread(p);
  43.     t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
  44.     ll mid=(t[p].l+t[p].r)>>1;
  45.     if(l<=mid)add(p*2,l,r,k);
  46.     if(mid<r)add(p*2+1,l,r,k);
  47.     t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
  49. }
  50. void mu(ll p,ll l,ll r,ll k){
  51.     if(t[p].l>=l&&t[p].r<=r){
  52.         t[p].add=(t[p].add*k)%mod;//比较重要的一步,add要在这里乘上k,因为后面可能要加其他的数而那些数其实是不用乘k的
  53.         t[p].mu=(t[p].mu*k)%mod;
  54.         t[p].sum=(t[p].sum*k)%mod;
  55.         return ;
  56.     }
  57.     spread(p);
  58.     t[p].sum=t[p*2].sum+t[p*2+1].sum;
  59.     ll mid=(t[p].l+t[p].r)>>1;
  60.     if(l<=mid)mu(p*2,l,r,k);
  61.     if(mid<r)mu(p*2+1,l,r,k);
  62.     t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
  63. }
  64. ll ask(ll p,ll l,ll r){
  65.     if(t[p].l>=l&&t[p].r<=r){
  66.         return t[p].sum;
  67.     }
  68.     spread(p);
  69.     ll val=0;
  70.     ll mid=(t[p].l+t[p].r)>>1;
  71.     if(l<=mid)val=(val+ask(p*2,l,r))%mod;
  72.     if(mid<r)val=(val+ask(p*2+1,l,r))%mod;
  73.     return val;
  74. }
  75. int main(){
  76.     cin>>n>>m>>mod;
  77.     for(int i=1;i<=n;i++){
  78.         a[i]=read();
  79.     }
  80.     build(1,1,n);
  81.     for(int i=1;i<=m;i++){
  82.         int ty=read();
  83.         if(ty==1){
  84.             ll cn=read(),cm=read(),cw=read();
  85.             mu(1,cn,cm,cw);
  86.         }else if(ty==2){
  87.             ll cn=read(),cm=read(),cw=read();
  88.             add(1,cn,cm,cw);
  89.         }else {
  90.             ll cn=read(),cm=read();
  91.             cout<<ask(1,cn,cm)<<endl;
  92.         }
  93.     }
  94. }

悬线法

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,a[1005][1005],l[1005][1005],r[1005][1005],up[1005][1005];
  4. int main(){
  5.     cin>>n>>m;
  6.     for(int i=1;i<=n;i++){
  7.         for(int j=1;j<=m;j++){
  8.             char ch;cin>>ch;
  9.             if(ch=='F')a[i][j]=1;
  10.             r[i][j]=l[i][j]=j,up[i][j]=1;
  11.         }
  13.     }
  14.     for(int i=1;i<=n;i++){
  15.         for(int j=2;j<=m;j++){
  16.             if(a[i][j]==a[i][j-1]&&a[i][j]==1)l[i][j]=l[i][j-1];
  17.         }
  18.         for(int j=m-1;j>=1;j--){
  19.             if(a[i][j]==a[i][j+1]&&a[i][j]==1)r[i][j]=r[i][j+1];
  20.         }
  21.     }
  22.     int ans=0;
  23.     for(int i=1;i<=n;i++){
  24.         for(int j=1;j<=m;j++){
  25.             if(i>1&&a[i][j]==a[i-1][j]&&a[i][j]==1){//是>1才进去但是i=1时还是要做的
  26.                 r[i][j]=min(r[i][j],r[i-1][j]);
  27.                 l[i][j]=max(l[i][j],l[i-1][j]);
  28.                 up[i][j]=up[i-1][j]+1;
  29.             }
  30.             ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);
  31.         }
  32.     }
  33.     cout<<ans;
  34. }

哈夫曼树

  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,m;
  5. priority_queue<pair<int,int> >dui;
  6. signed main(){
  7.     cin>>n>>m;int w;
  8.     for(int i=1;i<=n;i++){
  9.         cin>>w;
  10.         dui.push(make_pair(-w,-1));
  11.     }
  12.     while((dui.size()-1)%(m-1))dui.push(make_pair(-0,-1));//最后一次合并要满足=0 因为每次合并要减少k-1个节点要将n个节点合并成1个
  13.     //题解里的解释：因为每次都是将k个节点合并为1个（减少k-1个），一共要将n个节点合并为1个，如果（n-1）%（k-1）！=0
  14.     //则最后一次合并时不足k个。也就表明了最靠近根节点的位置反而没有被排满，因此我们需要加入k-1-（n-1）%（k-1）个空节点
  15.     //使每次合并都够k个节点（也就是利用空节点将其余的节点挤到更优的位置上）。
  16.     int ans=0;
  17.     while(dui.size()>=m){
  18.         int re=0,h=-0;
  19.         for(int i=1;i<=m;i++){
  20.             int x=dui.top().first,y=dui.top().second;dui.pop();
  21.             re+=x;
  22.             h=min(h,y);
  23.         }
  24.         ans+=re;
  25.         dui.push(make_pair(re,h-1));
  26.     }
  27.     cout<<-ans<<endl<<-dui.top().second-1;
  28. }

后序遍历

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char q[1000005],z[1000005];
  4. int len;
  5. int find(char k){
  6.     for(int i=1;i<=len;i++)if(q[i]==k)return i;
  7. }
  8. void dfs(int l1,int r1,int l2,int r2){
  9.     int m=find(z[r2]);
  10.     cout<<q[m];
  11.     if(m>l1)dfs(l1,m-1,l2,r2-r1+m-1);//有左子树
  12.     if(r1>m)dfs(m+1,r1,l2+m-l1,r2-1);
  13. }
  14. //r2-(r1-m+1)
  15. //r2-r1+m-1
  16. //l2+(m-r1)
  17. //l2+m-r1
  18. int main(){
  19.     scanf("%s",q+1);scanf("%s",z+1);
  20.     len=strlen(q+1);
  21.     dfs(1,len,1,len);
  22. }

后缀表达式

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char a[1005];
  4. int sum,k;
  5. stack <int> stk;
  6. int main(){
  7.     gets(a);
  8.     for(int i=0;a[i]!='@';i++){
  9.         if(a[i]=='.'){
  10.             sum=0,k=1;
  11.             for(int j=i-1;j>=0&&a[j]>='0'&&a[j]<='9';j--) sum=sum+(a[j]-48)*k,k*=10; 
  12.             stk.push(sum);
  13.             continue;
  14.         }
  15.         if(a[i]>='0'&&a[i]<='9') continue;
  16.         sum=stk.top();
  17.         stk.pop(); 
  18.         if(a[i]=='+') sum=stk.top()+sum;
  19.         if(a[i]=='-') sum=stk.top()-sum;
  20.         if(a[i]=='*') sum=stk.top()*sum;
  21.         if(a[i]=='/') sum=stk.top()/sum;
  22.         stk.pop();
  23.         stk.push(sum);
  24.     }
  25.     printf("%d",stk.top());
  26.     return 0;
  27. }

中缀表达式转后缀表达式

  1. #include<bits/stdc++.h>
  2. #define M 10007
  3. using namespace std;
  4. int n;
  5. char ss[10000005];
  6. stack<char>dui;
  7. int main(){
  8.     cin>>n;
  9.     scanf("%s",ss   +1);
  10.     string s=".";
  11.     for(int i=1;i<=n;i++){
  12.         if(ss[i]=='('||ss[i]=='*'){
  13.             dui.push(ss[i]);
  14.         }
  15.         if(ss[i]=='+'){
  16.             while(dui.size()&&dui.top()=='*'){//直到找到优先级更低的符号
  17.                 s+=dui.top();
  18.                 dui.pop();
  19.             }
  20.             dui.push('+');
  21.         }
  22.         if(ss[i]==')'){
  23.             while(dui.size()&&dui.top()!='('){
  24.                 s+=dui.top();
  25.                 dui.pop();
  26.             }
  27.             dui.pop();
  28.         }
  29.         if(ss[i]!='('&&ss[i]!=')'){
  30.             s+='.';
  31.         }
  32.     }
  33.     while(dui.size())s+=dui.top(),dui.pop();
  34.     cout<<s<<endl;
  35. }
  36. /*    8
  37. +*+(*+)*
  38. 下面的话来自题解区：
  39. 转换过程需要用到栈，具体过程如下：
  40. 1）如果遇到操作数，我们就直接将其输出。
  41. 2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
  42. 3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
  43. 4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
  44. 5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
  45. 备注：本题中我们用一个"."来代表数字。扫描整个表达式（读入的字符串），如果当前位置不是括号（既不是左括号也不是右括号），就在后缀表达式里填一个"."表示这里应有一个数字。*/

科学的整数二分模板

  2. int l=0,r=1e6+1,mid;
  3. while(l<r){
  4.     mid=(l+r)>>1;
  5.     if(check(mid)) r=mid;
  6.     else l=mid+1;
  7. }
  8. return l;


(图片备用链接：https://cdn.luogu.com.cn/upload/image_hosting/jj8qtvuh.png)

小数二分

  1.     double l=1,r=2000;
  2.     while(r-l>1e-5){
  3.         double mid=(l+r)/2;
  4.         if(check(mid))l=mid;
  5.         else r=mid;
  6.     }
  7.     printf("%d\n",r);

逆序对

  1. #include<iostream>
  2. using namespace std;
  3. long long t[1000005],ans=0;
  4. long long n,a[1000005];
  5. void merge(int l,int r){//归并大法 
  6.     if(l==r)
  7.     return;
  8.     int mid=(l+r)/2;
  9.     merge(l,mid);//用分治的思想，先分离，再合并 
  10.     merge(mid+1,r);
  11.     int i=l,j=mid+1,p=l;
  12.     while(i<=mid&&j<=r){
  13.         if(a[i]>a[j]){
  14.             t[p++]=a[j++];
  15.             ans+=mid-i+1;//此时两边都是排好序了的，当前面的序列中有一个数大于后面的一个数时，前面序列中剩下的数都大于这个数，共mid-i+1个 
  16.         }
  17.         else
  18.         t[p++]=a[i++];
  19.     }
  20.     while(i<=mid)
  21.     t[p++]=a[i++];//把序列中剩下的数存入t 
  22.     while(j<=r)
  23.     t[p++]=a[j++];
  24.     for(i=l;i<=r;i++)
  25.     a[i]=t[i];//t中的数要回到a中
  26. }
  27. int main(){
  28.     cin>>n;
  29.     for(int i=1;i<=n;i++)
  30.     cin>>a[i];
  31.     merge(1,n);//调用merge 
  32.     cout<<ans<<endl;
  33.     return 0;
  34. }

树状数组1

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,a[5000005],sum[5000005];
  4. int read(){
  5.     int x=0;char ch=getchar();
  6.     while(ch>'9'||ch<'0')ch=getchar();
  7.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  8.     return x;
  9. }
  10. int lowbit(int x){return x&(-x);}
  11. void add(int x,int k){while(x<=n)sum[x]+=k,x+=lowbit(x);}
  12. int getsum(int x){
  13.     int re=0;
  14.     while(x!=0){
  15.         re+=sum[x];
  16.         x-=lowbit(x);
  17.     }
  18.     return re;
  19. }
  20. int main(){
  21.     n=read(),m=read();
  22.     for(int i=1;i<=n;i++)a[i]=read();
  23.     for(int i=1;i<=n;i++)add(i,a[i]);
  24.     int ty,x,y;
  25.     for(int i=1;i<=m;i++){
  26.         scanf("%d%d%d",&ty,&x,&y);
  27.         if(ty==1)add(x,y);
  28.         else cout<<getsum(y)-getsum(x-1)<<endl;
  29.     }
  30. }
  31. //单点修改区间查询

树状数组2

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,a[500005],sum[500005];
  4. int lowbit(int x){return x&(-x);}
  5. void add(int x,int k){while(x<=n)sum[x]+=k,x+=lowbit(x);}
  6. int getsum(int x){int re=0;while(x)re+=sum[x],x-=lowbit(x);return re;}
  7. int main(){
  8.     cin>>n>>m;
  9.     for(int i=1;i<=n;i++)cin>>a[i];
  10.     int ty,x,y,k;
  11.     for(int i=1;i<=m;i++){
  12.         cin>>ty;
  13.         if(ty==1){
  14.             cin>>x>>y>>k;
  15.             add(x,k);
  16.             add(y+1,-k);
  17.         }else {
  18.             cin>>x;
  19.             cout<<a[x]+getsum(x)<<endl;
  20.         }
  21.     }
  22. }
  23. //区间修改单点查询,我们不可能一个个去修改,于是考虑差分,想到这问题迎刃而解,区间修改时只需修改x和y+1即可,最后求个sum+a[x]即为答案

A*

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int lim,mp[10][10];
  4. const int n=5;
  5. const int dx[10]={0,1,1,-1,-1,2,2,-2,-2};
  6. const int dy[10]={0,2,-2,2,-2,1,-1,1,-1};
  7. const int st[7][7]={
  8.     {0,0,0,0,0,0},
  9.     {0,1,1,1,1,1},
  10.     {0,0,1,1,1,1},
  11.     {0,0,0,2,1,1},
  12.     {0,0,0,0,0,1},
  13.     {0,0,0,0,0,0}
  14. };
  15. int diff(){
  16.     int re(0);
  17.     for(int i=1;i<=n;i++){
  18.         for(int j=1;j<=n;j++){
  19.             if(mp[i][j]!=st[i][j])++re;
  20.         }
  21.     }
  22.     return re;
  23. }
  24. bool ans;
  25. bool pen(int x,int y){
  26.     if(x<1||x>n||y<1||y>n)return 0;
  27.     return 1;
  28. }
  29. void dfs(int dep,int x,int y){
  30.     if(ans)return ;
  31.     if(dep==lim){//必须是==,否则就成正常的搜索了......
  32.         if(!diff()){
  33.             ans=1;
  34.             printf("%d\n",lim);
  35.         }
  36.         return ;
  37.     }
  38.     for(int i=1;i<=8;i++){
  39.         int xx=x+dx[i],yy=y+dy[i];
  40.         if(pen(xx,yy)){
  41.             swap(mp[x][y],mp[xx][yy]);
  42.             int now=diff();
  43.             if(now+dep<=lim)dfs(dep+1,xx,yy);
  44.             swap(mp[x][y],mp[xx][yy]);
  45.         }
  46.     }
  47. }
  48. int main(){
  49.     int tt;
  50.     cin>>tt;
  51.     while(tt--){
  52.         int stax,stay;
  53.         char ch;
  54.         for(int i=1;i<=n;i++){
  55.             for(int j=1;j<=n;j++){
  56.                 cin>>ch;
  57.                 if(ch=='*')stax=i,stay=j,mp[i][j]=2;
  58.                 else mp[i][j]=ch-'0';
  59.             }
  60.         }
  61.         if(!diff()){printf("-1\n");continue;}
  62.         for(lim=1;lim<=15;lim++){
  63.             dfs(0,stax,stay);
  64.         }
  65.         if(!ans)printf("-1\n");
  66.         ans=0;
  67.     }
  68. }

DP

DD大牛的背包九讲（原版找不到了，将就一下）
https://blog.csdn.net/qq_41267618/article/details/89403294

01背包

不要求正好装满

  1. #include<iostream>
  2. using namespace std;
  3. int n,V,w[1000000],v[1000000],dp[1000000];
  4. int main(){
  5.     cin>>n>>V;
  6.     for(int i=1;i<=n;i++){
  7.         cin>>w[i]>>v[i];
  8.     }
  9.     for(int i=1;i<=n;i++){
  10.         for(int j=V;j>=w[i];j--){
  11.             dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
  12.         }
  13.     } 
  14.     cout<<dp[V]<<endl;
  15. }

要求正好装满

  1. //其实两种做法的区别仅仅是初始化的不同，当要求正好装满时，仅将dp[0]赋值为0，其它都是-INF
  2. //因为只有dp[0]合法（什么都不装相当于装了一个体积为0的物品）
  3. //比如现在有v[i]=3的一个物品，则dp[3]可以正好装下它
  4. //所以dp[3]此时不再是-INF，最后只要检查一下是否dp[V]>0即可
  5. //这个小技巧完全可以推广到其它类型的背包问题
  6. //下文未作说明默认不必放满
  7. #include<iostream>
  8. using namespace std;
  9. int n,V,w[1000000],v[1000000],dp[1000000];
  10. int main(){
  11.     cin>>n>>V;
  12.     for(int i=1;i<=n;i++){
  13.         cin>>w[i]>>v[i];
  14.     }
  15.     for(int i=1;i<=V;i++)dp[i]=-0x7fffffff
  16.     for(int i=1;i<=n;i++){
  17.         for(int j=V;j>=w[i];j--){
  18.             dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
  19.         }
  20.     } 
  21.     cout<<dp[V]<<endl;
  22. }

完全背包

  1. //完全背包与01背包的区别是完全背包的物品有无限个，但01背包仅有一个
  2. //考虑01背包的转移为什么是倒序，因为正序转移有可能造成同一个物品被考虑多次
  3. //这正是完全背包要求的，比如w[3]=3,dp[1]=5,则在dp[4]、dp[7]都会考虑一遍3号物品
  4. #include<iostream>
  5. using namespace std;
  6. int n,V,v[1000000],w[1000000],dp[1000000];
  7. int main(){
  8.     cin>>n>>V;
  9.     for(int i=1;i<=n;i++){
  10.         cin>>v[i]>>w[i];
  11.     }
  12.     for(int i=1;i<=n;i++){
  13.         for(int j=w[i];j<=V;j++){
  14.             dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
  15.         }
  16.     }
  17.     cout<<dp[V]<<endl;
  18. }

多重背包

  1. //多重背包在完全背包的基础上更近一步给出了物品的个数
  2. //多重背包可以将每件物品拆成单个的物品跑01背包，但数据上规模会TLE
  3. //这个时候考虑二进制优化，因为任何数都可以用二进制表示，如6件拆成2^0,2^1,3(surplus)
  4. #include<iostream>
  5. using namespace std;
  6. int n,V,w[1000000],v[1000000],cnt,dp[1000000];
  7. int main(){
  8.     cin>>n>>V;
  9.     int cv,cw,c,k;
  10.     for(int i=1;i<=n;i++){
  11.         cin>>cv>>cw>>c;
  12.         k=1;
  13.         while(k<=c){
  14.             w[++cnt]=cw*k;
  15.             v[cnt]=cv*k;
  16.             c-=k;
  17.             k=k<<1;//就是k*=2，进行二进制拆分 
  18.         }
  19.         if(c){
  20.             w[++cnt]=cw*c;
  21.             v[cnt]=cv*c;
  22.         }
  23.     }
  24.     for(int i=1;i<=cnt;i++){
  25.         for(int j=V;j>=w[i];j--){//倒序跑01背包 
  26.             dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
  27.         }
  28.     }
  29.     cout<<dp[V];
  30. }

二维费用背包

  1. #include<iostream>
  2. using namespace std;
  3. int n,V,M,v[1000000],m[1000000],w[1000000],dp[10000][10000];
  4. int main(){
  5.     cin>>n>>V>>M;
  6.     for(int i=1;i<=n;i++){
  7.         cin>>m[i]>>v[i]>>w[i];
  8.     }
  9.     for(int i=1;i<=n;i++){
  10.         for(int j=M;j>=m[i];j--){//可以与下面的for交换位置
  11.             for(int k=V;k>=v[i];j--){
  12.                 dp[j][k]=max(dp[j][k],dp[j-m[i]][k-v[i]]+w[i]);
  13. //二维费用背包有两个限制条件，只需增加一维即可,当发现题目是由熟悉的动态规划题目变形得来的时
  14. //在原来的状态中加一纬以满足新的限制是一种比较通用的方法
  15.             }
  16.         }
  17.     }
  18.     cout<<dp[V][M];
  19. }

分组背包

  1. //分组背包，通俗的讲就是，给你N组物品，然后每一组你至多选择一个物品(也可以不选),每个物品都有自己的体积和价值，现在给你一个容里为M的背包，让你用这个背包装物品，使得物品价值总和最大.(by鲜果维他命)
  2. #include<iostream>
  3. using namespace std;
  4. int n,V,m,dp[1000000];
  5. struct node{
  6.     int cnt,v[1000],w[1000];
  7. }bag[10000];
  8. int main(){
  9.     cin>>n>>m>>V;
  10.     for(int i=1;i<=m;i++){
  11.         cin>>bag[i].cnt;
  12.         for(int j=1;j<=bag[i].cnt;j++){
  13.             cin>>bag[i].v[j]>>bag[i].w[j];
  14.         }
  15.     }
  16.     for(int i=1;i<=m;i++){
  17.         for(int j=V;j>=1;j--){//显然是01背包～
  18.             for(int k=1;k<=bag[i].cnt;k++){//分组枚举（注意先枚举空间）
  19.                 if(j<bag[i].v[j])continue;
  20.                 dp[j]=max(dp[j],dp[j-bag[i].v[k]]+bag[i].w[k]);
  21.             }
  22.         }
  23.     }
  24.     cout<<dp[V]<<endl;
  25. }

有依赖的背包问题（树形DP）

  1. //（金明的预算方案）将主件视为根，将附件视为儿子，直接树形DP
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int n,m,v[100000],ji,head[100000],dp[1000][100000],w[100000];
  5. struct node{
  6.     int to,next; 
  7. }ed[100000];
  8. int add(int p,int q){
  9.     ed[++ji].to=q;
  10.     ed[ji].next=head[p];
  11.     head[p]=ji;
  12. }
  13. void tree_dp(int k,int le){
  14.     for(int i=head[k];i;i=ed[i].next){
  15.         int y=ed[i].to;
  16.         tree_dp(y,le-v[k]);
  17.         for(int j=le;j>=v[k];j--){
  18.             for(int t=j-v[k];t>=0;t--) 
  19.                 dp[k][j]=max(dp[k][j],dp[k][j-t]+dp[y][t]);//枚举花去金额t来寻找最大满意度 
  20.         }//dp[i][j]为主件为i时剩余金钱为j时的满意度（v*w）
  21.     }
  22.     for(int i=le;i>=v[k];i--)dp[k][i]+=w[k];//k为主件当然要算入k贡献的满意度
  23. }
  24. int main(){
  25.     cin>>m>>n;
  26.     m/=10;
  27.     int q;
  28.     for(int i=1;i<=n;i++){
  29.         cin>>v[i]>>w[i]>>q;//价格，重要程度，对应的主件
  30.         v[i]/=10;
  31.         w[i]*=v[i];//预处理w为买i所贡献的满意度
  32.         add(q,i);
  33.     }
  34.     tree_dp(0,m);
  35.     cout<<dp[0][m]*10<<endl;
  36. }

LIS（最长上升子序列）

  1. //维护一个单调上升的序列，如果当前的数比序列最后一个元素大则加入末尾
  2. //否则二分一个合适的位置替换掉那个元素，这种替换不会增加序列的长度，但是这一步的意义
  3. //在于记录最小序列，代表了一种“最可能性”。注意数组中的序列并不一定是正确的最长上升子序列
  4. //例(1,4,7,2,5,9,10,3) 序列：(1)->(1,4)->(1,4,7)->(1,2,7)->(1,2,5)->(1,2,5,9)->(1,2,5,9,10)->(1,2,3,9,10)
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. int n,a[100005],f[100005];
  8. int main(){
  9.     cin>>n;
  10.     for(int i=1;i<=n;i++){
  11.         cin>>a[i];f[i]=0x7ffffff;
  12.     }
  13.     int len=0;f[0]=0;
  14.     for(int i=1;i<=n;i++){
  15.         if(f[len]<a[i])f[++len]=a[i];
  16.         else {
  17.             int l=1,r=len;
  18.             while(l<r){
  19.                 int mid=(l+r)>>1;
  20.                 if(a[i]<f[mid])r=mid;
  21.     //因为要将a[i]插入到f中，且插入位置保证f[mid]>=a[i]，所以>a[i]也可能是答案
  22.                 else l=mid+1;
  23.             }
  24.             f[l]=a[i];
  25.         }
  26.     }
  27.     cout<<len;
  28. }
  29. //关于路径输出：如果当前加入f数组中的数仍存在于最终的f数组中则代表这个数属于LIS，因此，我们只需记录每个数存入f时的下标（每个数都会进入f），最后从n~1找按len到0的顺序输出即可，Talk is cheap, show you MR_xiao11's code.
  30. #include <bits/stdc++.h>
  31. using namespace std;
  32. const int N=100000+10;
  33. const int INF=0x3f3f3f3f;
  34. int n,f[N],a[N],st[N],res,tot,last[N],ans[N];
  35. int main(){
  36.     memset(st,-INF,sizeof(st));
  37.     cin>>n;
  38.     for(int i=1;i<=n;i++)
  39.         cin>>a[i];
  40.     for(int i=1;i<=n;i++){
  41.         f[i]=1;
  42.         if(st[tot]<=a[i]){
  43.             st[++tot]=a[i];
  44.             last[i]=tot;//输出标记 
  45.         }
  46.         else {
  47.             int k=upper_bound(st+1,st+1+tot,a[i])-st;//可相等 
  48.             //lower_bound(st+1,st+1+tot,a[i])-st; //严格上升序列 
  49.             st[k]=a[i];
  50.             last[i]=k;//输出标记 
  51.         }
  52.     }
  53.     cout<<"max="<<tot<<endl;
  54.     //输出标记 
  55.     int len=tot;
  56.     for(int i=n;i;i--){
  57.         if(last[i]==len)ans[len--]=a[i];
  58.         if(len==0)break;
  59.     }
  60.     for(int i=1;i<=tot;i++)
  61.         cout<<ans[i]<<" ";
  62.     cout<<endl;
  63.     return 0;
  64. }

LCS（最长公共子序列）

  1. /*由于数据过大我们在时间和空间上都不能像下面那样做，那怎么办呢
  2. 我们发现既然是1到n的排列，那就可以把A离散化，得到B在A序列中的编号，找到一段编号序列的子序列
  3. 他是单调递增的，那么就表明对应元素在A和B中是从前往后排列的
  4. 这就是我们要的答案，找这段单调递增的序列其实就是LIS哦*/
  5. //by 花姐
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. int dp[1001][1001],a1[2001],a2[2001],n,m;
  9. int main()
  10. {
  11.    //dp[i][j]表示两个串从头开始，直到第一个串的第i位 
  12.    //和第二个串的第j位最多有多少个公共子元素 
  13.    cin>>n>>m;
  14.    for(int i=1;i<=n;i++)scanf("%d",&a1[i]);
  15.    for(int i=1;i<=m;i++)scanf("%d",&a2[i]);
  16.    for(int i=1;i<=n;i++)
  17.     for(int j=1;j<=m;j++)
  18.      {
  19.         dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  20.         if(a1[i]==a2[j])
  21.         dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
  22.         //因为更新，所以++； 
  23.      }
  24.    cout<<dp[n][m];
  25. }
  26. //正解（仅适用于两个序列中都不出现重复元素的情况，如1232就不适用）
  27. #include<bits/stdc++.h>
  28. using namespace std;
  29. int n,f[100001],a[100001],b[100001],ma[100001];//ma为编号序列
  30. int main(){
  31.     cin>>n;
  32.     for(int i=1;i<=n;i++){
  33.         cin>>a[i];ma[a[i]]=i,f[i]=0x7fffffff;
  34.     }
  35.     for(int i=1;i<=n;i++)cin>>b[i];
  36.     f[0]=0;
  37.     int len=0;
  38.     for(int i=1;i<=n;i++){
  39.         if(f[len]<ma[b[i]])f[++len]=ma[b[i]];//比队尾还大
  40.         else {
  41.             int l=1,r=len;
  42.             while(l<r){
  43.                 int mid=(l+r)>>1;
  44.                 if(f[mid]<ma[b[i]])l=mid+1;
  45.                 else r=mid;
  46.             }
  47.             f[l]=ma[b[i]];
  48.         }
  49.     }
  50.     cout<<len;
  51. }

LCIS

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,a[505],b[505],g[505][505],f[505][505];
  4. void path(int i,int j){
  5.     if(j==0)return ;
  6.     path(g[i][j],j-1);
  7.     if(g[i][j]!=i){
  8.         printf("%d ",a[i]);
  9.     }
  10. }
  11. int main(){
  12.     cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
  13.     cin>>m;for(int j=1;j<=m;j++)cin>>b[j];
  14.     int maxn=0,x=0,y=0;
  15.     for(int i=1;i<=n;i++){
  16.         for(int j=1;j<=m;j++){
  17.             if(a[i]==b[j]){
  18.                 f[i][j]=1;
  19.                 for(int k=1;k<i;k++){
  20.                     if(a[k]<a[i]){
  21.                         if(f[i][j]<f[k][j-1]+1){
  22. //如果是f[k][j]由于a[1~i]与b[j]不匹配所以这样是错的
  23.                             f[i][j]=f[k][j-1]+1;
  24.                             g[i][j]=k;
  25.                         }
  26.                     }
  27.                 }
  28.                 if(maxn<f[i][j])maxn=f[i][j],x=i,y=j;
  29.             }else{
  30.                 f[i][j]=f[i][j-1];
  31.                 g[i][j]=i;
  32.             }
  33.         }
  34.     }
  35.     cout<<maxn<<endl;
  36.     path(x,y);
  37.     cout<<endl;
  38. }
  39. /*输出的递归函数path应有两个参数(i,j),表示当前在数组A中位置是i,在数组B中位置是j
  40. 我们沿着f[i][j]转移时的路径递归,也就是path(i-1,g[i][j])
  41. 若g[i][j]==j,则说明这里是没有增加LCIS长度的转移
  42. 应该沿着f[i][j]转移时的路径继续递归,但不输出.直到g[i][j]!=j就输出B[j]*/

数论类

O(1)快速乘

  1. int qmul(int x,int y,int mod){
  2.     return (x*y-(long long)((long double)x/mod*y)*mod+mod)%mod;
  3. }

gcd

  1. inline ll gcd(ll a,ll b){
  2.     if(a==0)return b;if(b==0)return a;
  3.     if(!(a&1)&&!(b&1))return 2*gcd(a>>1,b>>1);
  4.     else if(!(a&1))return gcd(a>>1,b);
  5.     else if(!(b&1))return gcd(a,b>>1);
  6.     else return gcd(abs(a-b),min(a,b));
  7. }//法一是二进制版本，法二三目版本如下
  8. int gcd(int a,int b){
  9. return b>0?gcd(b,a%b):a;
  10. //其实algorithm库里面有__gcd(a,b)函数

线性基

  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll p[55],a,n,ans;
  5. void merge(ll k){
  6.     for(int i=55;i>=0;i--){//>=0!!!!!!!!
  7.         if(!(k>>i))continue;
  8.         if(!p[i]){p[i]=k;break;}
  9.         k^=p[i];//消去最高位，后面的1不管，这也是为什么线性基不唯一——shuixirui 
  10.     }
  11. }
  12. int main(){
  13.     cin>>n;
  14.     for(int i=1;i<=n;i++){
  15.         cin>>a;
  16.         merge(a);
  17.     }
  18.     for(int i=55;i>=0;i--){
  19.         if((ans^p[i])>ans)ans^=p[i];
  20.     }
  21.     cout<<ans;  
  22. }
  23. //如果要查询某个数是否能被该线性基表出可以把该数转成二进制
  24. //对于每一位如果为1就XORp[i]如果最后结果为0则可以被表出

裴蜀定理

  1. //裴蜀定理内容ax+by=c,x∈Z*,y∈Z*成立的充要条件是gcd(a,b)∣c,Z* 表示正整数集。
  2. //扩展到求ax+by=c 的最小非负 c,显然 c 要满足 (a,b)|c,所以 c 取 (a,b)是最小的。
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. int n,a,ans;
  6. int gcd(int a,int b){
  7.     if(!b)return a;
  8.     return gcd(b,a%b);
  9. }
  10. int main(){
  11.     cin>>n;
  12.     for(int i=1;i<=n;i++){cin>>a;a>0?(a*=1):(a*=(-1));ans=gcd(ans,a);}
  13.     cout<<ans;
  14. }

线性素数筛

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,prime[100000005],ji;
  4. bool bo[10000005];
  5. int main(){
  6.     cin>>n>>m;
  7.     for(int i=2;i<=n;i++){
  8.         if(!bo[i])prime[++ji]=i;//不能加括号！！！，每次都要更新！！！
  9.         for(int j=1;i*prime[j]<=n;j++){//记得是prime[j]*i,i和j换个位置
  10.             bo[i*prime[j]]=1;
  11.             if(i%prime[j]==0)break;//期中有其他因子的时候就退出来
  12.         }
  13.     }
  14.     bo[1]=bo[0]=1;
  15.     for(int i=1;i<=m;i++){
  16.         int cn;cin>>cn;
  17.         if(bo[cn])cout<<"No"<<endl;
  18.         else cout<<"Yes"<<endl;
  19.     }
  20. }
  21. //当你n特别大比如1e12时我们可以这么求出这个数可以被分解成多少个质数：
  22. #include<bits/stdc++.h>
  23. using namespace std;
  24. long long read(){
  25.     long long x=0,f=1;
  26.     char c=getchar();
  27.     while((c<'0'||c>'9')&&c!='-')c=getchar();
  28.     if(c=='-')f=-1,c=getchar();
  29.     while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
  30.     return f*x;
  31. }
  32. long long T,n,ans;
  33. int main(){
  34.     T=read();
  35.     while(T--){
  36.         n=read();
  37.         ans=0;
  38.         for(long long i=2;i*i<=n;++i)
  39.             while(!(n%i)){
  40.                 n/=i;
  41.                 ans++;
  42.             }
  43.         if(n>1)ans++;
  44.         if(ans==2)printf("Bob\n");
  45.         else printf("Alice\n");
  46.     }
  47.     return 0;
  48. }

快速幂

  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. long long m,n,mod;
  5. ll quick(ll x,int y){//快速幂
  6.     ll res=1;
  7.     while(y){
  8.         if(y&1)res=(ll)res*x%mod;
  9.         x=(ll)x*x%mod; y>>=1;
  10.     }return res;
  11. }
  12. int main(){
  13.     cin>>m>>n>>mod;
  14.     cout<<m<<"^"<<n<<" mod "<<mod<<"="<<quick(m,n)%mod;
  15. }
  16. 或者你也可以这么写，下面是我早期写的版本
  17. #include<iostream>
  18. using namespace std;
  19. long long b,p,k;
  20. long long mod(long long x)
  21. {
  22.     if(x==0) return 1%k;
  23.     long long y=x,s;
  24.     bool bo=y%2;
  25.     y/=2; s=mod(y); s*=s%k;
  26.     if(bo==1) s*=b;
  27.     return s%k;
  28. }
  29. int main(){
  30.     cin>>b>>p>>k;
  31.     cout<<b<<"^"<<p<<" mod "<<k<<"="<<mod(p);
  32. }

三分法

  1. #include<bits/stdc++.h>
  2. #define eps 1e-6
  3. using namespace std;
  4. int n;
  5. double l,r,a[20];
  6. double f(double x){//秦九昭定理
  7.     double s=0;
  8.     for(int i=1;i<=n+1;i++)s=s*x+a[i];//巧妙的操作
  9.     return s;
  10. }
  11. int main(){
  12.     cin>>n>>l>>r;
  13.     for(int i=1;i<=n+1;i++)cin>>a[i];//特别注意有n+1个值
  14.     while(r-l>=eps){
  15.         double k=(r-l)/3.0;
  16.         double mid1=l+k,mid2=r-k;
  17.         if(f(mid1)>f(mid2))r=mid2;
  18.         else l=mid1;
  19.     }
  20.     printf("%.5lf",l);
  21. }

矩阵快速幂

  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define m 1000000007
  4. using namespace std;
  5. inline ll gi(){
  6.     register char ch=getchar();register ll x=0;
  7.     while(ch<'0'||ch>'9')ch=getchar();
  8.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  9.     return x;
  10. }
  11. ll n,k;
  12. struct node {
  13.     ll mat[100][100];
  14. }add,a,ans,mu,e,qk;
  15. inline node mul(node x,node y){
  16.     node mem=qk;
  17.     for(register int i=1;i<=n;i++){
  18.         for(register int j=1;j<=n;j++){
  19.             for(register int h=1;h<=n;h++){
  20.                 mem.mat[i][j]=(mem.mat[i][j]+x.mat[i][h]*y.mat[h][j])%m;//记得加上原来的
  21.             }
  22.         }
  23.     }
  24.     return mem;
  25. }
  26. inline void quick(ll k){
  27.     ans=e;
  28.     while(k){
  29.         if(k&1)ans=mul(ans,mu);
  30.         mu=mul(mu,mu);
  31.         k>>=1;
  32.     }
  33. }
  34. int main(){
  35.     cin>>n>>k;
  36.     for(register int i=1;i<=n;i++){
  37.         for(register int j=1;j<=n;j++){
  38.             mu.mat[i][j]=a.mat[i][j]=gi();
  39.         }
  40.     }
  41.     for(ll i=1;i<=n;i++){
  42.         e.mat[i][i]=1;
  43.     }
  44.     quick(k);
  45.     for(register int i=1;i<=n;i++){
  46.         for(register int j=1;j<=n;j++){
  47.             printf("%lld ",ans.mat[i][j]);
  48.         }
  49.         printf("\n");
  50.     }
  51.     return 0;
  52. }

乘法逆元1

  1. //法1(递推法)
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. long long n,p,inv[3000001];
  5. int main(){
  6.     cin>>n>>p;
  7.     inv[1]=1;
  8.     for(int i=2;i<=n;i++){
  9.         inv[i]=(p-p/i)*inv[p%i]%p;
  10.     }
  11.     for(int i=1;i<=n;i++)printf("%d\n",inv[i]);
  12. }
  13. /*递推求inv的解释：
  14. 设p=k*i+r;
  15. 则有k*i+r≡0(mod p)
  16. 为了把r^(-1)剥离出来两边同乘i^(-1)*r^(-1)
  17. 得到r^(-1)=-k*r^(-1);
  18. k=p/i,r^(-1)=inv[p%i];
  19. 此时我们注意到这样乘起来是负数
  20. 所以我们用p减去他*/
  21. //法2(扩展欧几里得法)
  22. #include<bits/stdc++.h>
  23. #define ll long long
  24. using namespace std;
  25. ll n,p,inv[3000001],x,y;
  26. void exgcd(ll a,ll b,ll &x,ll &y){
  27.     if(!b){x=1,y=0;return ;}
  28.     exgcd(b,a%b,y,x);
  29.     y-=a/b*x;
  30. }
  31. int main(){
  32.     cin>>n>>p;
  33.     for(int i=1;i<=n;i++){
  34.         exgcd(i,p,x,y);
  35.         x=(p+x%p)%p;
  36.         cout<<x<<endl;
  37.     }
  38. }
  39. /*a*x≡c(mod p)
  40. 令t=x^(-1)
  41. 我们要求的就是
  42. x*t≡1(mod p)
  43. 于是我们有
  44. x*t+p*y=1
  45. 求t即可*/
  46. //法3(快速幂)，即x^(p-2);
  47. //由于这个方法只适用于x与p互质的情况，exgcd不仅比他快还适用所有情况 这里就不在赘述

乘法逆元2

  1. //马上就考试了，这是题解，有时间补锅
  2. #include<cstdio>
  3. #include<cctype>
  4. typedef long long LL;
  5. int n,k,md,pre[5000005],suf[5000005],a[5000005];
  6. int readint(){
  7.     int x=0;char ch=getchar();
  8.     while(ch>'9'||ch<'0')ch=getchar();
  9.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  10.     return x;
  11. }
  12. inline int Inv(const int p){
  13.     if(p==1)return 1;
  14.     return((LL)(md-md/p)*Inv(md%p)%md);
  15. }
  16. int main(){
  17.     n=readint(),md=readint(),k=readint();
  18.     int ans=0;
  19.     for(register int i=*pre=suf[n+1]=1;i<=n;++i)
  20.     pre[i]=(LL)pre[i-1]*(a[i]=readint())%md;
  21.     for(register int i=n;i;--i)
  22.     suf[i]=(LL)suf[i+1]*a[i]%md;
  23.     for(register int i=1,j=k;i<=n;++i,j=(LL)j*k%md)
  24.     ans=(ans+(LL)j*pre[i-1]%md*suf[i+1])%md;
  25.     printf("%lld",ans*(LL)Inv(pre[n])%md);
  26.     return 0;
  27. }

NIM游戏

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int t,n;
  4. int main(){
  5.     cin>>t;
  6.     while(t--){
  7.         cin>>n;
  8.         int ans=0;
  9.         for(int i=1;i<=n;i++){
  10.             int ci;
  11.             cin>>ci;
  12.             ans^=ci;
  13.         }
  14.         if(ans)cout<<"Yes"<<endl;
  15.         else cout<<"No"<<endl;
  16.     }
  17. }

中国剩余定理

  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,m,a[100005],b[100005];
  5. void  exgcd(int aa,int bb,int &x,int &y){
  6.     if(!bb){x=1,y=0;return ;}
  7.     exgcd(bb,aa%bb,y,x);
  8.     y-=aa/bb*x;
  9. }
  10. int ksc(int aa,int bb,int mod){
  11.     int re=0;
  12.     while(bb){
  13.         if(bb&1)re=(re+aa)%mod;
  14.         bb>>=1,aa=(aa+aa)%mod;
  15.     }
  16.     return re;
  17. }
  18. void crt(){
  19.     int ans=0;
  20.     for(int i=1;i<=n;i++){
  21.         int mi=m/b[i],x,y;
  22.         exgcd(mi,b[i],x,y);//求出mi的逆元
  23.         ans=(ans+ksc(ksc(x,mi,m)%m,a[i],m)%m)%m;
  24.     }
  25.     ans=(ans%m+m)%m;
  26.     cout<<ans;
  27. }
  28. signed main(){
  29.     cin>>n;m=1;
  30.     for(int i=1;i<=n;i++)cin>>a[i];
  31.     for(int i=1;i<=n;i++){cin>>b[i];a[i]=(a[i]%b[i]+b[i])%b[i];m*=b[i];}//吧a转换成正数并计算m
  32.     crt();
  33. }
  34. /*
  35. 对于sum{ai*mi*mi^(-1)}的解释
  36. xi≡ai*mi*mi^(-1)(mod bi)
  37. xj≡aj*mj*mj^(-1)(mod bj)
  38. 当循环到j时由于mj=b1*b2*...*bj-1*bj+1*...*bn
  39. 故sum之后即为答案
  40. */

高斯消元

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. double f[4005][4005],ans[400];
  4. int n;
  5. int main(){
  6.     cin>>n;
  7.     for(int i=1;i<=n;i++){
  8.         for(int j=1;j<=n+1;j++){
  9.             cin>>f[i][j];
  10.         }
  11.     }
  12.     for(int i=1;i<=n;i++){
  13.         int r=0;
  14.     for(int j=i;j<=n;j++)
  15.             if(fabs(f[r][i])<fabs(f[j][i]))//fabs返回实数的绝对值
  16.                 r=j;
  17.         if(!r){
  18.             printf("No Solution");//找不到最大值即此列全为０
  19.             return 0;
  20.         }
  21.         swap(f[i],f[r]);//交换行骚操作～～～
  22.         double chu=f[i][i];//就是此列最大的那个关键元，那整列被放到第ｉ行
  23.         for(int j=i;j<=n+1;j++)f[i][j]/=chu;//是i~n+1!，第１～ｉ为０，本行除以这个关键元
  24.         for(int j=i+1;j<=n;j++){//枚举行数
  25.             chu=f[j][i];//当前行的关键元,要消去,且必须用中间变量（不然在后面的for里面值会被修改） 
  26.             for(int k=i;k<=n+1;k++){//枚举列数，是i~n+1
  27.                 f[j][k]-=f[i][k]*chu;//f[i][k]为这一列第一个，用关键元所在行对应列的来消此列其他值
  28.                 // if(f[j][k]==-0)f[j][k]=0;
  29.             }
  30.         }
  31.     }
  32.     ans[n]=f[n][n+1];//因为是阶梯型矩阵，最后一行的第n+1个数就是xn的值
  33.     for(int i=n;i>=1;i--){//倒着枚举！
  34.         ans[i]=f[i][n+1];//本行结果初始化为第n+1个数
  35.         for(int j=i+1;j<=n;j++){
  36.            ans[i]-=ans[j]*f[i][j];//ans[j]中已经存放了xj的答案，乘本行第ｊ个再减去就是xi的值
  37.         }
  38.     }
  39.     for(int i=1;i<=n;i++)
  40.         printf("%.2lf\n",ans[i]);
  41. }

康托展开

  1. //这是题解，有时间再补锅
  2. #include <iostream>
  3. #include <cstdio>
  4. #define MOD (998244353)
  5. using namespace std;
  6. int n,a[1000000];
  7. int c[1000001]={};
  8. inline int lowbit(int x){
  9.     return x&(-x);
  10. }
  11. inline void modify(int p){
  12.     while(p<=n){
  13.         ++c[p];
  14.         p+=lowbit(p);
  15.     }
  16.     return;
  17. }
  18. inline int ask(int p){
  19.     int s=0;
  20.     while(p){
  21.         s+=c[p];
  22.         p-=lowbit(p);
  23.     }
  24.     return s;
  25. }
  26. inline void readInt(int &x){
  27.     char c;
  28.     while((c=getchar())<'0' || c>'9');
  29.     x=(c^48);
  30.     while('0'<=(c=getchar()) && c<='9'){
  31.         x=x*10+(c^48);
  32.     }
  33.     return;
  34. }
  35. int fac[1000000]={1,1};
  36. int main(){
  37.     int i,s=0;
  38.     readInt(n);
  39.     for(i=0;i<n;++i){
  40.         readInt(a[i]);
  41.     }
  42.     for(i=2;i<1000000;++i){
  43.         fac[i]=(long long)fac[i-1]*i%MOD;
  44.     }
  45.     for(i=0;i<n;++i){
  46.         s=(s+(long long)fac[n-1-i]*(a[i]-1-ask(a[i]-1))%MOD)%MOD;
  47.         modify(a[i]);
  48.     }
  49.     printf("%d\n",(s+1)%MOD);
  50.     return 0;
  51. }

欧拉定理

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. using namespace std;
  6. int n,mod,phi,k;
  7. bool bo;
  8. int quick(int a,int b){
  9.     int res=a,ans=1;
  10.     while(b){
  11.         if(b&1)ans=(long long)ans*res%mod;//要加ll...
  12.         res=(long long)res*res%mod;
  13.         b>>=1;
  14.     }
  15.     return ans%mod;
  16. }
  17. int main(){
  18.     cin>>n>>mod;
  19.     n%=mod;
  20.     int x=phi=mod;//等于mod...
  21.     for(int i=2;i*i<=x;i++){
  22.         if(x%i==0){
  23.             phi=phi/i*(i-1);
  24.             while(x%i==0)x/=i;
  25.         }
  26.     }if(x>1){phi=phi/x*(x-1);}
  27.     char ch=getchar();
  28.     while(ch<'0'||ch>'9')ch=getchar();
  29.     while(ch>='0'&&ch<='9'){
  30.         k=(k<<1)+(k<<3)+(ch^48);
  31.         ch=getchar();
  32.         if(k>=phi)bo=1,k%=phi;//>=&&%phi...
  33.     }
  34.     if(k>=phi)bo=1,k%=phi;
  35.     if(bo)k+=phi;
  36.     printf("%d",quick(n,k));
  37. }

Pollard-Rho算法

  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll ans=1;
  5. inline ll quick(ll x,ll p,ll mod){
  6.     ll ans=1;
  7.     while(p){
  8.         if(p&1)ans=ans*x%mod;
  9.         x=x*x%mod; p>>=1;
  10.     }
  11.     return ans;
  12. }
  13. inline bool mr(ll x,ll p){
  14.     if(quick(x,p-1,p)!=1)return 0;
  15.     ll y=p-1,z;
  16.     while(!(y&1)){
  17.         y>>=1; z=quick(x,y,p);
  18.         if(z!=1&&z!=p-1)return 0;
  19.         return 1;
  20.     }return 1;
  21. }
  22. inline bool prime(ll p){ if(p<2)return 0;
  23.     if(p==2||p==3||p==5||p==11||p==101)return 1;
  24.     return mr(2,p)&&mr(3,p)&&mr(5,p)&&mr(11,p)&&mr(101,p);
  25. }
  26. inline ll Abs(ll x){return x<0?-x:x;}
  27. inline ll gcd (ll a,ll b){
  28.     register ll t;
  29.     while (b){
  30.         t=a%b;
  31.         a=b;
  32.         b=t;
  33.     }
  34.     return a;
  35. }
  36. inline ll rho(ll p){
  37.     ll x,y,z,c,g; int i,j;
  38.     while(1){
  39.         x=y=rand()%p; c=rand()%p;
  40.         z=1; i=0; j=1;
  41.         while(++i){
  42.             x=((__int128)x*x+c)%p;
  43.             z=(__int128)z*Abs(y-x)%p;
  44.             if(x==y)break;
  45.             if(z==0){
  46.                 g=gcd(Abs(y-x),p);
  47.                 if(g>1)return g;
  48.                 break;
  49.             }
  50.             if(!(i%127)||i==j){
  51.                 g=gcd(z,p);
  52.                 if(g>1)return g;
  53.                 if(i==j)y=x,j<<=2;
  54.             }
  55.         }
  56.     }
  57. }
  58. inline void find(ll x){
  59.     if(x<=ans)return ;
  60.     if(prime(x)){ans=x;return ;}
  61.     ll p=rho(x);
  62.     while(x%p==0)x/=p;
  63.     find(p); find(x);
  64. }
  65. int main(){
  66.     int t;cin>>t;
  67.     srand(time(0));
  68.     while(t--){
  69.         ll n; ans=1;
  70.         cin>>n; find(n);
  71.         if(ans==n){puts("Prime");continue;}
  72.         printf("%lld\n",ans);
  73.     }
  74. }

图类

Dijkstra


图片备用地址：https://cdn.luogu.com.cn/upload/image_hosting/qc4lnset.png

  1. //dij算法的复杂度十分优秀，甚至可以用于含有正环的图
  2. //但却对于含有负权边的图束手无策，因为每个点仅遍历一遍
  3. #include<iostream>
  4. #include<cstdio>
  5. #include<queue>
  6. using namespace std;
  7. int n,m,s,ji,head[1000000],dis[1000000];
  8. bool si[100000];
  9. priority_queue < pair < int , int > > dui;//使用堆优先更新权值最小的边，这样更有可能找到最短路
  10. struct node{
  11.     int to,w,next;
  12. }ed[1000000];
  13. void ad(int p,int q,int quan){
  14.     ed[++ji].w=quan;
  15.     ed[ji].to=q;//去往哪个点
  16.     ed[ji].next=head[p];//next记录p点（该边的起点）还有连有哪些边 
  17.     head[p]=ji;//head记录当前最后一条连着p点的边 
  18. }
  19. void dij(){
  20.     for(int i=1;i<=n;i++)dis[i]=0x7fffffff;
  21.     dui.push(make_pair(0,s));
  22.     dis[s]=0;
  23.     int now,su,ne;
  24.     while(dui.size()){
  25.         now=dui.top().second;
  26.         dui.pop();
  27.         if(si[now])continue;//这个点只需更新一次 
  28.         si[now]=1;
  29.         for(int i=head[now];i;i=ed[i].next){
  30.             ne=ed[i].to,su=dis[now]+ed[i].w;
  31.             if(dis[ne]>su){//更新最小值 
  32.                 dis[ne]=su;
  33.                 dui.push(make_pair(-su,ne));//stl的堆是最大堆 
  34.             }
  35.         }
  36.     }
  37. }
  38. int main(){
  39.     cin>>n>>m>>s;
  40.     int cu,cv,cw;
  41.     for(int i=1;i<=m;i++){
  42.         cin>>cu>>cv>>cw;
  43.         ad(cu,cv,cw);
  44.     }
  45.     dij();
  46.     for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
  47. }

spfa

  1. //spfa算法可以弥补dij不能应对负权边及负权回路的问题，但是在毒瘤数据面前复杂度会退化
  2. //spfa是队列优化版的Bellman-Ford，算法大致流程是用一个队列来进行维护。 
  3. //初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛
  4. //若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。
  5. #include<iostream>
  6. #include<cstdio>
  7. #include<queue>
  8. using namespace std;
  9. int n,m,s,ji,head[1000000],dis[1000000];
  10. bool si[100000];
  11. queue<int>dui;
  12. struct node{
  13.     int to,w,next;
  14. }ed[1000000];
  15. void ad(int p,int q,int quan){
  16.     ed[++ji].w=quan;
  17.     ed[ji].to=q;
  18.     ed[ji].next=head[p];
  19.     head[p]=ji;
  20. }
  21. void spfa(){
  22.     for(int i=1;i<=n;i++)dis[i]=0x7fffffff;
  23.     dui.push(s);si[s]=1;dis[s]=0;
  24.     //在spfa算法中，si标记数组的作用变成了标记该点是否存在于队列中 
  25.     int now,su,ne;
  26.     while(dui.size()){
  27.         now=dui.front();dui.pop();
  28.         si[now]=0;
  29.         for(int i=head[now];i;i=ed[i].next){
  30.             ne=ed[i].to,su=dis[now]+ed[i].w;
  31.             if(dis[ne]>su){
  32.                 dis[ne]=su;
  33.                 if(!si[ne]){
  34.                     si[ne]=1;
  35.                     dui.push(ne);
  36.                 }
  37.             }
  38.         }
  39.     }
  40. }
  41. int main(){
  42.     cin>>n>>m>>s;
  43.     int cu,cv,cw;
  44.     for(int i=1;i<=m;i++){
  45.         cin>>cu>>cv>>cw;
  46.         ad(cu,cv,cw);
  47.     }
  48.     spfa();
  49.     for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
  50. }

Floyd

  1. //Floyd算法最大的有点是面对稠密图比以上两种算法更优，而且它能求所有点互相的最短路，边权可正可负
  2. //但三重循环也限制了它只能用于小规模数据，且不能有负权回路
  3. #include<iostream>
  4. #include<cstdio>
  5. #include<queue>
  6. #include<cstring>
  7. using namespace std;
  8. int n,m,s,ji,dis[10000][10005];
  9. void floyd(){
  10.     for(int k=1;k<=n;k++){
  11.         for(int i=1;i<=n;i++){
  12.             for(int j=1;j<=n;j++){
  13.                 if(dis[i][k]==0x7fffffff||dis[k][j]==0x7fffffff)continue;//避免两数相加超过int范围
  14.                 if(dis[i][j]>dis[i][k]+dis[k][j])dis[i][j]=dis[i][k]+dis[k][j];
  15.             }
  16.         }
  17.     }
  18. }
  19. int main(){
  20.     cin>>n>>m>>s;
  21.     int cu,cv,cw;
  22.     for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=0x7fffffff;
  23.     for(int i=1;i<=n;i++)dis[i][i]=0;
  24.     for(int i=1;i<=m;i++){
  25.         cin>>cu>>cv>>cw;
  26.         dis[cu][cv]=min(dis[cu][cv],cw);
  27.     }
  28.     floyd();
  29.     for(int i=1;i<=n;i++)cout<<dis[s][i]<<" ";
  30. }

负环

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int tt,n,m,head[100005],ji,dis[100005],cnt[100005];
  4. int read(){
  5.   int x=0,f=1;char c=getchar();
  6.   while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
  7.   while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
  8.   return x*f;
  9. }
  10. struct node{
  11.     int next,yuan,w;
  12. }ed[1000005];
  13. void add(int p,int q,int quan){
  14.     ed[++ji].next=head[p];
  15.     ed[ji].yuan=q;
  16.     ed[ji].w=quan;
  17.     head[p]=ji;
  18. }
  19. bool huan;
  20. queue<int>dui;//队列就行了 
  21. void spfa(){
  22.     while(dui.size())dui.pop();
  23.     dui.push(1);
  24.     dis[1]=0;//0号节点到根节点的距离为0 
  25.     while(dui.size()){
  26.         int x=dui.front();dui.pop();
  27.         for(int i=head[x];i;i=ed[i].next){
  28.             int y=ed[i].yuan,l=dis[x]+ed[i].w;
  29.             if(dis[y]>l){
  30.                 dis[y]=l;
  31.                 ++cnt[y];
  32.                 dui.push(y);//无需判断是否已在队列中
  33.                 if(cnt[y]>=n){huan=1;return;}//>=n!!!
  34.             }
  35.         }
  36.     }
  37. }
  38. int main(){
  39.     cin>>tt;
  40.     while(tt--){
  41.         cin>>n>>m;
  42.         memset(head,0,sizeof(head));
  43.         memset(ed,0,sizeof(ed));
  44.         memset(dis,127,sizeof(dis));
  45.         memset(cnt,0,sizeof(cnt));
  46.         ji=0,huan=0;
  47.         for(int i=1;i<=m;i++){
  48.             register int cn=read(),cm=read(),cw=read();
  49.             if(cw<0)add(cn,cm,cw);
  50.             else add(cm,cn,cw),add(cn,cm,cw);
  51.         }
  52.         spfa();
  53.         if(huan)cout<<"YE5"<<endl;
  54.         else cout<<"N0"<<endl;
  55.     }
  56.     return 0;
  57. }

并查集

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,fa[200005];
  4. int find(int k){
  5.     while(fa[k]!=k)k=fa[k]=fa[fa[k]];//循环版找爸爸
  6.     return k;
  7. }
  8. int main(){
  9.     cin>>n>>m;
  10.     for(int i=1;i<=n;i++)fa[i]=i;
  11.     for(int i=1;i<=m;i++){
  12.         int cn,cm,cz;
  13.         cin>>cn>>cm>>cz;
  14.         int a=find(cm),b=find(cz);
  15.         if(cn==1){
  16.             if(a>b)fa[a]=b;//按序号大小合并
  17.             else fa[b]=a;
  18.         }else{
  19.             if(a==b)cout<<"Y"<<endl;
  20.             else cout<<"N"<<endl;
  21.         }
  22.     }
  23. }

Prime

  1. //两者区别：Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。（摘自某谷Nemlit大佬）
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int n,m,dis[2000000],head[2000000],ji,ans;
  6. bool si[2000000];
  7. struct node{
  8.     int to,next,w;
  9. }ed[2000000];
  10. void add(int p,int q,int quan){
  11.     ed[++ji].w=quan;
  12.     ed[ji].to=q;
  13.     ed[ji].next=head[p];
  14.     head[p]=ji;
  15. }
  16. void prime(){
  17.     for(int i=2;i<=n;i++)dis[i]=666666666;
  18.     for(int i=head[1];i;i=ed[i].next)dis[ed[i].to]=min(dis[ed[i].to],ed[i].w);//更新第一个点到周围点的距离 
  19.     int now=1,le=n-1,lo;
  20.     while(le--){//树的边数为点数减一 
  21.         si[now]=1;
  22.         lo=666666666;
  23.         for(int i=1;i<=n;i++)//找最小的边连上 
  24.             if(!si[i]&&lo>dis[i]){
  25.                 lo=min(lo,dis[i]);
  26.                 now=i;
  27.             }
  28.         ans+=lo;
  29.         for(int i=head[now];i;i=ed[i].next){//更新跟目前节点相连各点的距离 
  30.             if(!si[ed[i].to])dis[ed[i].to]=min(dis[ed[i].to],ed[i].w);
  31.         }
  32.     }
  33. }
  34. int main(){
  35.     cin>>n>>m;
  36.     int cn,cm,cw;
  37.     for(int i=1;i<=m;i++){
  38.         cin>>cn>>cm>>cw;
  39.         add(cn,cm,cw);//无向图则双向建边 
  40.         add(cm,cn,cw); 
  41.     }
  42.     prime();
  43.     if(ans<666666666)cout<<ans;
  44.     else cout<<"orz";
  45. }

Kruskal

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct tree{
  4.     int to,next,w;
  5. }ed[2000005],Ed[2000005];
  6. int m,ji,n,head[2000005],ans,fa[2000005];
  7. bool cmp(tree a,tree b){//比较函数
  8.     return a.w<b.w;
  9. }
  10. int find(int k){//循环版找爸爸
  11.     while(k!=fa[k])k=fa[k]=fa[fa[k]];
  12.     return k;
  13. }
  14. void kruskal(){
  15.     sort(ed+1,ed+m+1,cmp);
  16.     for(int i=1;i<=m;i++){
  17.         int x=find(ed[i].next),y=find(ed[i].to);
  18.         if(x==y)continue;
  19.         if(x>y){
  20.             fa[y]=x;
  21.         }
  22.         else 
  23.         fa[x]=y;
  24.         ans+=ed[i].w;
  25.         if(++ji==n-1)return ;
  26.     }
  27. }
  28. bool tong[2000005];//标记是否连通
  29. void dfs(int now){
  30.     tong[now]=1;
  31.     for(int i=head[now];i;i=Ed[i].next){
  32.         if(!tong[Ed[i].to])dfs(Ed[i].to);
  33.     }
  34. }
  35. void add(int p,int q,int quan){
  36.     Ed[++ji].w=quan;
  37.     Ed[ji].to=q;
  38.     Ed[ji].next=head[p];
  39.     head[p]=ji;
  40. }
  41. int main(){
  42.     cin>>n>>m;
  43.     int cn,cm,cw;
  44.     for(int i=1;i<=m;i++){
  45.         cin>>cn>>cm>>cw;
  46.         ed[i].next=cn,ed[i].to=cm,ed[i].w=cw;
  47.         add(cn,cm,cw);
  48.         add(cm,cn,cw);
  49.     }
  50.     dfs(1);
  51.     ji=0;
  52.     for(int i=1;i<=n;i++)if(!tong[i]){cout<<"orz";return 0;}//某谷最新数据要求判断是否连通
  53.     for(int i=1;i<=n;i++)fa[i]=i;
  54.     kruskal();
  55.     cout<<ans;
  56. }

tarjan

  1. //推荐 https://blog.csdn.net/qq_34374664/article/details/77488976
  2. //[USACO06JAN]The Cow Prom S
  3. #include<iostream>
  4. #include<stack>
  5. using namespace std;
  6. int n,m,ji,head[1000000],dfn[1000000],low[1000000],ans;
  7. bool bo[1000000];
  8. struct node{
  9.     int to,next;
  10. }ed[1000000];
  11. void add(int p,int q){
  12.     ed[++ji].to=q;
  13.     ed[ji].next=head[p];
  14.     head[p]=ji;
  15. }
  16. stack<int> dui;
  17. void tar(int k){
  18.     dfn[k]=low[k]=++ji;//我对dfn的理解是第几个被访问的
  19.                        //low就是这个强连通分量里最先被访问的节点的dfn 
  20.     bo[k]=1;//在栈里面 
  21.     dui.push(k);
  22.     for(int i=head[k];i;i=ed[i].next){
  23.         if(!dfn[ed[i].to]){//能拓展节点 
  24.             tar(ed[i].to);
  25.             low[k]=min(low[k],low[ed[i].to]);
  26.         }else if(bo[ed[i].to])//在栈里 
  27.                 low[k]=min(low[k],low[ed[i].to]);
  28.     }
  29.     if(low[k]==dfn[k]){
  30.         int mem=1;//k节点自身也是一个强连通分量 
  31.         while(dui.top()!=k&&dui.size()){
  32.             bo[dui.top()]=0;
  33.             dui.pop();
  34.             mem++;
  35.         }
  36.         dui.pop();
  37.         bo[k]=0;
  38.         if(mem>1)++ans;//题目要求数个数大于一的 
  39.     }
  40. }
  41. int main(){
  42.     cin>>n>>m;
  43.     int cn,cm;
  44.     for(int i=1;i<=m;i++){
  45.         cin>>cn>>cm;
  46.         add(cn,cm);
  47.     }
  48.     ji=0;
  49.     for(int i=1;i<=n;i++){
  50.         if(!dfn[i])tar(i);//防止有森林出现漏掉其他树 
  51.     }
  52.     cout<<ans;
  53. }

缩点

  1. //SCC是强连通分量
  2. #include<iostream>
  3. #include<stack>
  4. #include<queue>
  5. using namespace std;
  6. int n,m,ji,jied,head[1000000],headEd[1000000],w[1000000],dfn[1000000],low[1000000],sum[1000000],mem[1000000][3];
  7. int read(){
  8.     int x=0;char ch=getchar();
  9.     while(ch>'9'||ch<'0')ch=getchar();
  10.     while(ch<='9'&&ch>='0')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  11.     return x; 
  12. }
  13. struct node{
  14.     int to,next;
  15. }ed[1000000],Ed[1000000];
  16. void add(int p,int q){
  17.     ed[++ji].to=q;
  18.     ed[ji].next=head[p];
  19.     head[p]=ji;
  20. }
  21. bool bo[1000000];
  22. stack<int> sta; 
  23. queue<int>dui;
  24. int scc[1000000],col,in[1000000],dis[1000000];
  25. void tarjan(int k){
  26.     dfn[k]=low[k]=++ji;
  27.     bo[k]=1;sta.push(k); 
  28.     for(int i=head[k];i;i=ed[i].next){
  29.         if(!dfn[ed[i].to]){
  30.             tarjan(ed[i].to);
  31.             low[k]=min(low[k],low[ed[i].to]);
  32.         }else{
  33.             if(bo[ed[i].to])
  34.                 low[k]=min(low[k],low[ed[i].to]); 
  35.         }
  36.     }
  37.     if(dfn[k]==low[k]){
  38.         ++col;bo[k]=0;//打上颜色标记，表示在一个SCC内
  39.         while(sta.top()!=k&&sta.size()){
  40.             scc[sta.top()]=col;
  41.             sum[col]+=w[sta.top()];//sum记录SCC内的点权之和
  42.             bo[sta.top()]=0;
  43.             sta.pop();
  44.         }
  45.         sta.pop();
  46.         scc[k]=col,sum[col]+=w[k];
  47.     }
  48. }
  49. void addEd(int p,int q){
  50.     Ed[++ji].to=q;
  51.     Ed[ji].next=headEd[p];
  52.     headEd[p]=ji;
  53. }
  54. void topo(){
  55.     for(int i=1;i<=col;i++)dis[i]=sum[i];//这样赋值是防止孤立的SCC不被考虑 
  56.     while(dui.size()){
  57.         int x=dui.front();
  58.         dui.pop();
  59.         for(int i=headEd[x];i;i=Ed[i].next){//以每一个根为起点进行松弛
  60.             int y=Ed[i].to;
  61.             --in[y];
  62.             dis[y]=max(dis[y],dis[x]+sum[y]);
  63.             if(!in[y])dui.push(y);//????? 
  64.         }
  65.     } 
  66. }
  67. int main(){
  68.     n=read(),m=read();
  69.     int cn,cm; 
  70.     for(int i=1;i<=n;i++){
  71.         w[i]=read();
  72.     }
  73.     for(int i=1;i<=m;i++){
  74.         cn=read(),cm=read();
  75.         add(cn,cm);
  76.         mem[i][1]=cn,mem[i][2]=cm//记录每条有向边的起点和终点
  77.     }
  78.     ji=0;
  79.     for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
  80.     ji=0;
  81.     for(int i=1;i<=m;i++){
  82.         if(scc[mem[i][1]]!=scc[mem[i][2]]){
  83.             addEd(scc[mem[i][1]],scc[mem[i][2]]);//注意是以每个scc为点建边 
  84.             in[scc[mem[i][2]]]++;//记录每个点的入度 
  85.         }
  86.     }
  87.     //缩点到此结束，题目要求找一条最长路 
  88.     for(int i=1;i<=n;i++)if(!in[i])dui.push(i);//没有入度的点是孤立的点（森林） 
  89.     topo();
  90.     int ans=0;
  91.     for(int i=1;i<=n;i++){
  92.         ans=max(ans,dis[i]);
  93.     }
  94.     cout<<ans;
  95. }

LCA

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,root,f[500005][25];
  4. struct node{
  5.     int next,yuan;
  6. }ed[5000005];
  7. int head[500005],ji,de[500005];
  8. inline int read(){
  9.     register int x=0;char ch=getchar();
  10.     while(ch>'9'||ch<'0')ch=getchar();
  11.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  12.     return x;
  13. }
  14. inline void add(int p,int q){
  15.     ed[++ji].next=head[p];
  16.     ed[ji].yuan=q;
  17.     head[p]=ji;
  18. }
  19. inline void dfs(int k,int ste){
  20.     for(int j=1;j<=20;j++){//因为不一定编号小的就是编号大的 的祖先所以要在dfs时预处理f
  21.         f[k][j]=f[f[k][j-1]][j-1];  //还有，f预处理必须放在dfs前面，因为后面的儿子会要用到这个f
  22.     }
  23.     for(register int i=head[k];i;i=ed[i].next){
  24.         register int y=ed[i].yuan;
  25.         if(!de[y]){
  26.             de[y]=ste;
  27.             f[y][0]=k;
  28.             dfs(y,ste+1);
  29.         }
  30.     }
  32. }
  33. inline int lca(int p,int q){
  34.     if(de[p]>de[q])swap(p,q);
  35.     for(register int i=20;i>=0;i--){
  36.         if(de[f[q][i]]>=de[p])q=f[q][i];//记得是>=!!!
  37.     }
  38.     if(p==q)return p;
  39.     for(register int i=20;i>=0;i--){
  40.         if(f[p][i]!=f[q][i]){
  41.             p=f[p][i],q=f[q][i];
  42.         }
  43.     }
  44.     return f[p][0];
  45. }
  46. int main(){
  47.     cin>>n>>m>>root;
  48.     for(register int i=1;i<n;i++){
  49.         register int cn=read(),cm=read();
  50.         add(cn,cm);add(cm,cn);
  51.     }
  52.     de[root]=1;
  53.     dfs(root,2);
  54.     for(register int i=1;i<=m;i++){
  55.         register int cn=read(),cm=read();
  56.         printf("%d\n",lca(cn,cm));//cout->printf 2.7s->1.7s
  57.     }
  58. }

分层图

  1. //然而放的并不是分层图的做法，放的是Dij或spfa+DP的做法,貌似比正解还快???
  2. //首先是Dij版的
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. int n,m,k,f[100005][30];
  6. int read(){
  7.     int x=0;char ch=getchar();
  8.     while(ch>'9'||ch<'0')ch=getchar();
  9.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  10.     return x;
  11. }
  12. int head[1000005],ji;
  13. struct node{
  14.     int next,yuan,w;
  15. }ed[1000005];
  16. void add(int p,int q,int quan){
  17.     ed[++ji].next=head[p];
  18.     ed[ji].yuan=q;
  19.     ed[ji].w=quan;
  20.     head[p]=ji;
  21. }
  22. struct no{
  23.     int dis,x,now;
  24.     bool operator > (const no& bb)const{return dis<bb.dis;}
  25.     bool operator < (const no& bb)const{return dis>bb.dis;}//重中之重,重载运算符(直接变成小跟堆)
  26. };
  27. priority_queue< no >dui;
  28. bool bo[100005][30];
  29. void dij(){
  30.     memset(f,127,sizeof(f));
  31.     f[1][0]=0;
  32.     dui.push(no{0,1,0});
  33.     while(dui.size()){
  34.         int x=dui.top().x,now=dui.top().now;
  35.         dui.pop();
  36.         if(bo[x][now])continue;
  37.         bo[x][now]=1;
  38.         for(int i=head[x];i;i=ed[i].next){
  39.             int y=ed[i].yuan;
  40.             if((!bo[y][now])&&f[y][now]>f[x][now]+ed[i].w){
  41.                 f[y][now]=f[x][now]+ed[i].w;
  42.                     dui.push(no{f[y][now],y,now});
  43.             }
  44.             if((!bo[y][now+1])&&now<k&&f[y][now+1]>f[x][now]){
  45.                 f[y][now+1]=f[x][now];
  46.                 dui.push(no{f[y][now+1],y,now+1});
  47.             }
  48.         }
  49.     }
  50. }
  51. int main(){
  52.     n=read(),m=read(),k=read();
  53.     for(int i=1;i<=m;i++){
  54.         int cn=read(),cm=read(),cw=read();
  55.         add(cn,cm,cw);
  56.         add(cm,cn,cw);
  57.     }
  58.     dij();
  59.     cout<<f[n][k]<<endl;
  60.     return 0;
  61. }
  62. //法二，spfa版(当然比Dij慢多了)
  63. #include<bits/stdc++.h>
  64. using namespace std;
  65. int n,m,k,f[100005][30];
  66. int read(){
  67.     int x=0;char ch=getchar();
  68.     while(ch>'9'||ch<'0')ch=getchar();
  69.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  70.     return x;
  71. }
  72. int head[1000005],ji;
  73. struct node{
  74.     int next,yuan,w;
  75. }ed[1000005];
  76. void add(int p,int q,int quan){
  77.     ed[++ji].next=head[p];
  78.     ed[ji].yuan=q;
  79.     ed[ji].w=quan;
  80.     head[p]=ji;
  81. }
  82. queue<pair<int,int> >dui;
  83. bool bo[100005][30];
  84. void spfa(){
  85.     memset(f,127,sizeof(f));
  86.     dui.push(make_pair(1,0));
  87.     bo[1][0]=1,f[1][0]=0;
  88.     while(dui.size()){
  89.         int x=dui.front().first,now=dui.front().second;
  90.         dui.pop();
  91.         bo[x][now]=0;
  92.         for(int i=head[x];i;i=ed[i].next){
  93.             int y=ed[i].yuan;
  94.             if(f[y][now]>f[x][now]+ed[i].w){
  95.                 f[y][now]=f[x][now]+ed[i].w;
  96.                 if(!bo[y][now]){
  97.                     bo[y][now]=1;
  98.                     dui.push(make_pair(y,now));
  99.                 }
  100.             }
  101.             if(now<k&&f[y][now+1]>f[x][now]){
  102.                 f[y][now+1]=f[x][now];
  103.                 if(!bo[y][now+1]){
  104.                     bo[y][now+1]=1;
  105.                     dui.push(make_pair(y,now+1));
  106.                 }
  107.             }
  108.         }
  109.     }
  110. }
  111. int main(){
  112.     n=read(),m=read(),k=read();
  113.     for(int i=1;i<=m;i++){
  114.         int cn=read(),cm=read(),cw=read();
  115.         add(cn,cm,cw);
  116.         add(cm,cn,cw);
  117.     }
  118.     spfa();
  119.     int ans=0x7fffffff;
  120.     for(int i=0;i<=k;i++)ans=min(ans,f[n][i]);
  121.     cout<<ans<<endl;
  122.     return 0;
  123. }

哈夫曼树

  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. priority_queue<long long> dui;
  5. long long n;
  6. long long read() {
  7.     long long x=0; char ch = getchar();
  8.     while (ch > '9' || ch < '0')ch = getchar();
  9.     while (ch >= '0' && ch <= '9')x = (ch ^ 48) + (x << 1) + (x << 3), ch = getchar();
  10.     return x;
  11. }
  12. int main() {
  13.     n = read();
  14.     long long cn = 0;
  15.     for (int i = 1; i <= n; i++) {
  16.         cn = read();
  17.         dui.push(-cn);//用的大根堆
  18.     }
  19.     long long ans = 0,sum=0;
  20.     while (dui.size()>1) {
  21.         sum += dui.top();
  22.         dui.pop();
  23.         sum += dui.top();
  24.         dui.pop();
  25.         ans += sum;
  26.         dui.push(sum);
  27.         sum = 0;
  28.     }
  29.     cout << -ans << endl;
  30. }

STL类

堆

  1. //STL做法：
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int n;
  5. priority_queue<int,vector<int>,greater<int> >dui;
  6. int main(){
  7.     cin>>n;
  8.     for(register int i=1;i<=n;++i){
  9.         register int ty;cin>>ty;
  10.         if(ty==1){
  11.             cin>>ty;
  12.             dui.push(ty); 
  13.         }
  14.         else if(ty==2){
  15.             cout<<dui.top()<<endl;
  16.         }else{
  17.             dui.pop();
  18.         }
  19.     }
  20. }
  21. //手动实现：
  22. #include<iostream>
  23. using namespace std;
  24. int n, cnt;
  25. int t[1000006];
  26. void up(int x) {
  27.     while (x>1) {
  28.         if (t[x] < t[x / 2]) {
  29.             swap(t[x], t[x / 2]);
  30.             x /= 2;
  31.         }
  32.         else break;
  33.     }
  34. }
  35. void add(int x) {
  36.     t[++cnt]= x;
  37.     up(cnt);
  38. }
  39. void down(int x) {
  40.     int ne = x*2;
  41.     while (ne <= cnt) {//要比较的儿子节点必须有值
  42.         if (t[ne] > t[ne + 1] && ne < cnt)++ne;//要有左右儿子才考虑加一
  43.         if (t[x] > t[ne]) {
  44.             swap(t[x], t[ne]);
  45.             x = ne, ne *= 2;
  46.         }
  47.         else break;
  48.     }
  49. }
  50. void del() {
  51.     swap(t[1],t[cnt]);
  52.     cnt--;
  53.     down(1);
  54. }
  55. void rem(int x) {
  56.     swap(t[x], t[cnt]);
  57.     cnt--;
  58.     up(x);
  59.     down(x);
  60. }
  61. int main() {
  62.     cin >> n;
  63.     while (n--) {
  64.         int ty = 0, cm = 0;
  65.         cin >> ty;
  66.         if (ty == 1) {//添加
  67.             cin >> cm;
  68.             add(cm);
  69.         }
  70.         else if (ty == 2) {//输出堆顶
  71.             cout << t[1] << endl;
  72.         }
  73.         else if(ty == 3) {//删除堆顶
  74.             del();
  75.         }
  76.         else if (ty == 4) {//删除数组中对应下标的元素
  77.             cin >> cm;
  78.             rem(cm);
  79.         }
  80.     }
  81. }

字符串类

manacher

  1. //注意此算法求的是回文串，必须是连续的一段序列
  2. //而回文序列则不必连续
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. char s[31000005];
  6. int r[31000005],len;//r是包括自己向右扩展的最大半径
  7. int main(){
  8.     s[0]=s[1]='#';len=2;
  9.     while(cin>>s[len]){
  10.         s[++len]='#';++len;
  11.     }
  12.     --len;//在每个字符之间插板子
  13.     r[0]=r[1]=r[2]=1;
  14.     int maxr=2,pos=0,ans=0;
  15.     for(int i=3;i<=len;i++){//必须一个一个更新 因为可能答案是关于‘#’对称的。。。
  16.         if(i<maxr){
  17.             r[i]=min(r[(pos<<1)-i],maxr-i);//两种情况
  18.         }else r[i]=1;
  19.         for(;s[i-r[i]]==s[i+r[i]];++r[i]);//左右拓展
  20.         if(maxr<i+r[i])pos=i,maxr=i+r[i];
  21.         ans=max(ans,r[i]);
  22.     }
  23.     cout<<ans-1;//半径减去‘#’的个数
  24. }

KMP

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,lena,lenb,nex[1000005];
  4. char a[1000005],b[1000005];
  5. int main(){
  6.     scanf("%s%s",a+1,b+1);
  7.     lena=strlen(a+1);
  8.     lenb=strlen(b+1);
  9.     int j=0;
  10.     for(int i=2;i<=lenb;i++){
  11.         while(j&&b[i]!=b[j+1])j=nex[j];
  12.         if(b[i]==b[j+1])++j;
  13.         nex[i]=j;
  14.     }
  15.     j=0;
  16.     for(int i=1;i<=lena;i++){
  17.         while(j&&b[j+1]!=a[i])j=nex[j];
  18.         if(b[j+1]==a[i])++j;
  19.         if(j==lenb){cout<<i-lenb+1<<endl;j=nex[j];}
  20.     }
  21.     for(int i=1;i<=lenb;i++)cout<<nex[i]<<" ";
  22.     return 0;
  23. }

字符串hash

  1. #include<bits/stdc++.h>
  2. #define ull unsigned long long
  3. using namespace std;
  4. ull n,a[100005];
  5. char s[100005];
  6. ull mod=20190816170251;
  7. ull base=131;
  8. ull ha(int len){
  9.     ull ans=0;
  10.     for(int i=0;i<len;i++){
  11.         ans=(ans*base+(ull)s[i])%mod+19260817;//别问为什么是这个数,问就禁言
  12.     }
  13.     return ans;
  14. }
  15. int main(){
  16.     scanf("%lld",&n);
  17.     for(int i=1;i<=n;i++){
  18.         scanf("%s",s);
  19.         a[i]=ha(strlen(s));
  20.     }
  21.     int ans=1;
  22.     sort(a+1,a+n+1);
  23.     for(int i=1;i<n;i++){
  24.         if(a[i]!=a[i+1])
  25.         ans++;
  26.     }
  27.     printf("%d",ans);
  28. }
  29. /*字符串hash的原理:
  30. 比如abcde，则
  31. ha[1]=a，ha[2]=ab，ha[3]=abc，ha[4]=abcd，ha[5]=abcde
  32. 倒过来hash:
  33. ha[1]=e，ha[2]=ed，ha[3]=edc，ha[4]=edcb，ha[5]=edcba
  34. 所以如果要取出'cba'的子串
  35. 则要用ha[5]-ha[2]*(base^(5-2))  */

最小表示法

  1. #include<iostream>
  2. using namespace std;
  3. int n,a[600005];
  4. int main() {
  5.     cin >> n;
  6.     for (int i = 1; i <= n; i++) {
  7.         cin >> a[i];
  8.         a[i + n] = a[i];
  9.     }
  10.     int p = 1, q = 2;
  11.     int k = 0;
  12.     while (k < n&&p<=n&&q<=n) {
  13.         for (k = 0; k <= n; k++) {
  14.             if (a[p + k] < a[q + k]) {
  15.                 q = q + k + 1;//不可能指向最小表示序列的头的指针要往后移
  16.                 if (p == q)q++;
  17.                 break;
  18.             }
  19.             if (a[p + k] > a[q + k]) {
  20.                 p = p + k + 1;
  21.                 if (p == q)p++;
  22.                 break;
  23.             }
  24.         }
  25.     }
  26.     if (p > n) {
  27.         for (int i = q; i < q + n; i++)cout << a[i] << " ";
  28.     }
  29.     else {
  30.         for (int i = p; i < p + n; i++)cout << a[i] << " ";
  31.     }
  32. }

字典树

  1. //链表+vector写法：
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<vector>
  6. using namespace std;
  7. int n, m, c;
  8. char ss[3000006];
  9. struct node {
  10.     char s;
  11.     int cnt;
  12.     vector < node* > ne;
  13. }*head;
  14. vector< node* > emp;
  15. void insert(char s[]) {
  16.     int len = (int)strlen(s);
  17.     node* now = head;
  18.     for (int i = 0; i < len; i++) {
  19.         char ch = s[i];
  20.         bool fi = 0;
  21.         for (int j = 0; j < now->ne.size(); j++) {
  22.             if (now->ne[j]->s == ch) {
  23.                 now = now->ne[j];
  24.                 now->cnt++;
  25.                 fi = 1;
  26.                 break;
  27.             }
  28.         }
  29.         if (!fi) {
  30.             node* a = new node();
  31.             a->s = ch, a->cnt = 1;
  32.             now->ne.push_back(a);
  33.             now = a;
  34.         }
  35.     }
  36. }
  37. int ask(char s[]) {
  38.     int len = (int)strlen(s);
  39.     node* now = head;
  40.     for (int i = 0; i < len; i++) {
  41.         char ch = s[i];
  42.         bool fi = 0;
  43.         for (int j = 0; j < now->ne.size(); j++) {
  44.             if (now->ne[j]->s == ch) {
  45.                 now = now->ne[j];
  46.                 fi = 1;
  47.                 break;
  48.             }
  49.         }
  50.         if (!fi)return 0;
  51.     }
  52.     return now->cnt;
  53. }
  54. void era(node* now) {
  55.     if (now->cnt > 1) {
  56.         for (int i = 0; i < now->ne.size(); i++) {
  57.             era(now->ne[i]);
  58.         }
  59.     }
  60.     else {
  61.         free(now);
  62.     }
  63. }
  64. int main() {
  65.     cin >> c;
  66.     while (c--) {
  67.         head = new node();
  68.         cin >> n >> m;
  69.         for (int i = 1; i <= n; i++) {
  70.             scanf("%s", ss);
  71.             insert(ss);
  72.         }
  73.         for (int i = 1; i <= m; i++) {
  74.             scanf("%s", ss);
  75.             cout << ask(ss) << endl;
  76.         }
  77.         era(head);
  78.     }
  79. }
  81. //数组写法：
  82. #include<bits/stdc++.h>
  83. using namespace std;
  84. int T,q,n,t[3000005][65],cnt[3000005],idx;
  85. char s[3000005];
  86. int getnum(char x){
  87.     if(x>='A'&&x<='Z')
  88.         return x-'A';
  89.     else if(x>='a'&&x<='z')
  90.         return x-'a'+26;
  91.     else
  92.         return x-'0'+52;
  93. } 
  94. void insert(char str[]){
  95.     int p=0,len=strlen(str);
  96.     for(int i=0;i<len;i++){
  97.         int c=getnum(str[i]);
  98.         if(!t[p][c])
  99.             t[p][c]=++idx;
  100.         p=t[p][c];
  101.         cnt[p]++;
  102.     }
  103. }
  104. int find(char str[]){
  105.     int p=0,len=strlen(str);
  106.     for(int i=0;i<len;i++){
  107.         int c=getnum(str[i]);
  108.         if(!t[p][c])
  109.             return 0;
  110.         p=t[p][c];
  111.     }
  112.     return cnt[p];
  113. }
  114. int main(){
  115.     scanf("%d",&T);
  116.     while(T--){
  117.         for(int i=0;i<=idx;i++)
  118.             for(int j=0;j<=122;j++)
  119.                 t[i][j]=0;
  120.         for(int i=0;i<=idx;i++)
  121.             cnt[i]=0;
  122.         idx=0;
  123.         scanf("%d%d",&n,&q);
  124.         for(int i=1;i<=n;i++){
  125.             scanf("%s",s);
  126.             insert(s);
  127.         }
  128.         for(int i=1;i<=q;i++){
  129.             scanf("%s",s);
  130.             printf("%d\n",find(s));
  131.         }
  132.     }
  133.     return 0;
  134. }

高精度

高精度加法

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #define maxn 1000000
  5. using namespace std;
  6. char d[maxn],e[maxn];
  7. int a[maxn],b[maxn],c[maxn];
  8. int main(){
  9.     scanf("%s%s",&d,&e);
  10.     int lena=strlen(d),lenb=strlen(e),lenc=lena>lenb?lena:lenb,jin=0;
  11.     for(int i=0;i<lena;i++){
  12.         a[lena-i]=d[i]-48;
  13.     }
  14.     for(int i=0;i<lenb;i++){
  15.         b[lenb-i]=e[i]-48;
  16.     }
  17.     for(int i=1;i<=lenc;i++){
  18.         c[i]=a[i]+b[i]+jin;
  19.         jin=c[i]/10;
  20.         c[i]%=10;
  21.     }
  22.     lenc++;
  23.     c[lenc]=jin;
  24.     while(!c[lenc]&&lenc>1){
  25.         lenc--;
  26.     }
  27.     for(int i=lenc;i>=1;i--)printf("%d ",c[i]);
  28.     return 0;
  29. }

高精度减法

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstring>
  4. using namespace std;
  5. int a[1000000],b[1000000],c[1000000];
  6. char d[1000000],e[1000000];
  7. bool mi;
  8. int main(){
  9.     scanf("%s%s",&d,&e);
  10.     if(!strcmp(d,e)){cout<<"0";return 0;}//特判是否相同 
  11.     int lena=strlen(d),lenb=strlen(e);
  12.     for(int i=0;i<lena;i++)a[lena-i]=d[i]-48;
  13.     for(int i=0;i<lenb;i++)b[lenb-i]=e[i]-48;
  14.     while(!a[lena])lena--;//题目中说了有前导0（没有的请忽略） 
  15.     while(!b[lenb])lenb--;
  16.     int len=lena>lenb?lena:lenb;
  17.     if(((strcmp(d,e)<0)&&(lena==lenb))||(lena<lenb))
  18.         mi=1;//不用区交换数组了 
  19.     if(!mi)//记得分清谁减谁 
  20.         for(int i=1;i<=len;i++){
  21.             if(a[i]<b[i]){a[i]+=10;a[i+1]--;}
  22.             c[i]=a[i]-b[i];
  23.         }
  24.     else
  25.         for(int i=1;i<=len;i++){
  26.             if(b[i]<a[i]){b[i]+=10;b[i+1]--;}
  27.             c[i]=b[i]-a[i];
  28.         }
  29.     while(!c[len]&&len>1)--len;
  30.     if(mi)cout<<"-";
  31.     for(int i=len;i>=1;i--)cout<<c[i];
  32. }

高精度乘法

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. int a[2005],b[2005],c[2005];
  5. char a1[2005],b1[2005];
  6. int main(){
  7.     scanf("%s%s",&a1,&b1);
  8.     int lena=strlen(a1),lenb=strlen(b1);
  9.     for(int i=0;i<lena;i++) a[lena-i]=a1[i]-'0';
  10.     for(int i=0;i<lenb;i++) b[lenb-i]=b1[i]-'0';
  11.     for(int i=1;i<=lenb;i++){
  12.         int jin=0;
  13.         for(int j=1;j<=lena;j++){
  14.             c[i+j-1]=a[j]*b[i]+jin+c[i+j-1];
  15.             jin=c[i+j-1]/10;
  16.             c[i+j-1]%=10;
  17.         }
  18.         c[lena+i]=jin;
  19.     }
  20.     int lenc=lena+lenb;
  21.     while(!c[lenc]&&lenc>1)lenc--;
  22.     for(int i=lenc;i>=1;i--)printf("%d ",c[i]);
  23.     return 0;
  24. }

高精除以低精（附带出输出余数）

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. using namespace std;
  5. int a[2005],b,c[2005],jin;
  6. char a1[2005];
  7. int main(){
  8.     scanf("%s",&a1);
  9.     cin>>b;
  10.     int lena=strlen(a1);
  11.     for(int i=0;i<lena;i++) a[i+1]=a1[i]-'0';//记得是从前往后处理
  12.     for(int i=1;i<=lena;i++){
  13.         c[i]=(jin*10+a[i])/b;
  14.         jin=(jin*10+a[i])%b;
  15.     }
  16.     int lenc=1;
  17.     while(!c[lenc]&&lenc<lena)lenc++;
  18.     for(int i=lenc;i<=lena;i++)printf("%d",c[i]);
  19.     cout<<endl<<jin;
  20.     return 0;
  21. }
  22. //jin取的是前面的余数，把前面的余数拼到后面一起除

排序

安利 https://blog.csdn.net/songjiasheng1314/article/details/80663744

选择排序

  1. //选择排序的核心思想是找到一个最小的元素（第二层循环中ji就是最小元素在无序数组中的编号）然后把它放到最前面
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. using namespace std;
  6. int a[99999999],n;
  7. void swap(int &l,int &k){
  8.     int t=l;
  9.     l=k;
  10.     k=t;
  11. }
  12. int main(){
  13.     cin>>n;
  14.     for(int i=1;i<=n;i++)
  15.         scanf("%d",&a[i]);
  16.     for(int i=1;i<=n;i++){
  17.         int ji=i;
  18.         for(int j=i+1;j<=n;j++){
  19.             if(a[j]<a[ji])ji=j;
  20.         }
  21.         if(ji!=i)swap(a[i],a[ji]);//要传址调用 
  22.     }
  23.     cout<<endl;
  24.     for(int i=1;i<=n;i++)
  25.         printf("%d ",a[i]);
  26.     return 0;
  27. }

正版冒泡

  1. //冒泡排序的核心思想是一遍一遍地比较相邻两个数并交换顺序
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int a[99999999],n;
  6. int main(){
  7.     cin>>n;
  8.     for(int i=1;i<=n;i++)
  9.         scanf("%d",&a[i]);
  10.     for(int i=n-1;i>=1;i--){
  11.         for(int j=0;j<=i;j++){
  12.             if(a[j]>a[j+1]) swap(a[j],a[j+1]);
  13.         }
  14.     }
  15.     for(int i=1;i<=n;i++)printf("%d ",a[i]);
  16.     return 0;
  17. }

盗版冒泡

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int a[99999999],n;
  5. int main(){
  6.     cin>>n;
  7.     for(int i=1;i<=n;i++)
  8.         scanf("%d",&a[i]);
  9.     for(int i=1;i<=n;i++){
  10.         for(int j=i+1;j<=n;j++){
  11.             if(a[i]>a[j]) swap(a[i],a[j]);
  12.         }
  13.     }
  14.     for(int i=1;i<=n;i++)printf("%d ",a[i]);
  15.     return 0;
  16. }

插排

  1. //顾名思义
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int a[99999999],n,i,j;
  6. void yi(int p,int q){
  7.     for(int h=q;h>p;h--)a[h]=a[h-1];
  8. }
  9. int main(){
  10.     cin>>n;
  11.     for( i=1;i<=n;i++)scanf("%d",&a[i]);
  12.     for( i=2;i<=n;i++){//a[i]为需要插入的数 
  13.         for( j=i-1;j>=1;j--)//寻找插入点 
  14.             if(a[j]<a[i])break;
  15.             if(j!=i-1){//需要将a[i]插入a[j]后 
  16.                 int temp=a[i];
  17.                 yi(j+1,i);
  18.                 a[j+1]=temp;
  19.             }
  20.     }
  21.     for(i=1;i<=n;i++)printf("%d ",a[i]);
  22.     return 0;
  23. }

桶排

  1. //开一个数组记录所有数字出现了几次，最后按数组顺序输出
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int a[99999999],n,ji;
  6. int main(){
  7.     cin>>n;
  8.     for(int i=1;i<=n;i++){
  9.         scanf("%d",&ji);
  10.         a[ji]++;
  11.     }
  12.     for(int i=0;i<=n;i++){
  13.         while(a[i]){
  14.             printf("%d ",i);
  15.             a[i]--;
  16.         }
  17.     }
  18.     return 0;
  19. }

快速排序

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,a[100005];
  4. int read(){//快读优化
  5.     int x=0;char ch=getchar();
  6.     while(ch>'9'||ch<'0')ch=getchar();
  7.     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  8.     return x;
  9. }
  10. void quick_sort(int l,int r){
  11.     if(l>=r)return ;
  12.     int mid=a[(l+r)>>1],i=l,j=r;//我习惯用将基准数设为中间的那个数
  13.     while(i<=j){
  14.         while(a[i]<mid)++i;//不能加‘=’，否则当mid为整个数组中的最大数时会陷入死循环
  15.         while(a[j]>mid)--j; 
  16.         if(i<=j){//要特判，否则i>j了就是在帮倒忙了
  17.             swap(a[i],a[j]);
  18.             ++i,--j;//不在原地踏步
  19.         }
  20.     }
  21.     if(l<j)quick_sort(l,j);//！！！ 一遍快排之后i>j了所以~
  22.     if(r>i)quick_sort(i,r);
  23. }
  24. int main(){
  25.     cin>>n;
  26.     for(int i=1;i<=n;i++){
  27.         a[i]=read();
  28.     }
  29.     quick_sort(1,n);
  30.     for(int i=1;i<=n;i++){
  31.         cout<<a[i]<<" ";
  32.     }
  33. }

三数取中+插排版快排

  1. //
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int a[99999999],n;
  6. void cha(int p,int q){//p<q 
  7.     int ji=0,j;
  8.     for(int i=p+1;i<=q;i++){
  9.         for(j=p;j<i;j++)if(a[i]<a[j])break;
  10.         ji=a[i];
  11.         for(int k=i-1;k>=j;k--)a[k+1]=a[k];//千万记得是倒序赋值
  12.         a[j]=ji;
  13.     }
  14. }
  15. void quick(int le,int ri){
  16.     if(le>=ri)return;
  17.     if(ri-le<=10)cha(le,ri);
  18.     int t=(le+ri)/2,mid,x=le,y=ri;//在左端点右端点和中点位置的三个数中选取大小排中间的数，并将另外两数按大小分别赋给左右端点
  19.     if(a[le]<a[t]){
  20.         if(a[t]>a[ri]){
  21.             int w=a[t];
  22.             a[t]=a[ri];a[ri]=w;
  23.         }
  24.     }
  25.     if(a[le]>a[t]){
  26.         int w=a[t];
  27.         a[t]=a[le];
  28.         a[le]=w;//a[le]<a[t]
  29.         if(a[t]>a[ri]){
  30.             int w=a[t];
  31.             a[t]=a[ri];a[ri]=w;
  32.         }
  33.     }
  34.     mid=a[t];
  35.     while(x<=y){
  36.         while(a[x]<mid)x++;
  37.         while(a[y]>mid)y--;
  38.         if(x<=y){
  39.             int w=a[x];
  40.             a[x]=a[y];a[y]=w;
  41.             x++;y--;
  42.         }
  43.     }
  44.     if(le<y)quick(le,y);
  45.     if(x<ri)quick(x,ri);
  46. }
  47. int main(){
  48.     cin>>n;
  49.     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
  50.     quick(1,n);
  51.     for(int i=1;i<=n;i++)printf("%d ",a[i]);
  52.     return 0;
  53. }

归并排序

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int a[99999999],b[99999999],n;
  5. void gui(int le,int ri)
  6. {
  7.     if(le==ri)return;
  8.     int mid=(le+ri)/2,x=le,y=mid+1,k=le;
  9.     gui(le,mid);
  10.     gui(mid+1,ri);
  11.     while(x<=mid&&y<=ri)
  12.         if(a[x]<a[y])b[k++]=a[x++];
  13.         else b[k++]=a[y++];
  14.     while(x<=mid)b[k++]=a[x++];
  15.     while(y<=ri)b[k++]=a[y++];
  16.     for(int g=le;g<=ri;g++)a[g]=b[g];
  17. }
  18. int main(){
  19.     cin>>n;
  20.     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
  21.     gui(1,n);
  22.     for(int i=1;i<=n;i++)printf("%d ",a[i]);
  23.     return 0;
  24. }

基数排序

  1. 基数排序的核心思想是按顺序（从高往低或者从低往高）比较每个数字的个位十位百位等等，每次按当前数位上的数值大小将数组重新排列，然后将新数列按下一位上的数值大小比较并再次排序，以此类推即可得到答案
  2. #include<iostream>
  3. #define ll long long 
  4. using namespace std;
  5. ll ma,n,a[200000],tub[15][200000],bas[15]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000},k;
  6. int main(){
  7.     cin>>n;
  8.     for(ll i=1;i<=n;i++){
  9.         cin>>a[i];
  10.         ll t=1;
  11.         while(a[i]>=bas[t])++t;
  12.         ma=max(ma,t);//统计有多少位 
  13.     }
  14.     for(ll t=1;t<=ma;t++){
  15.         for(ll i=1;i<=n;i++){
  16.             k=(a[i]%(bas[t]))/bas[t-1];
  17.             tub[k][++tub[k][0]]=a[i];//按当前位大小放入桶子里 
  18.         }
  19.         ll now=1;
  20.         for(ll i=1;i<=n;i++)
  21.             for(k=0;k<=9;k++){
  22.                 for(ll ji=1;ji<=tub[k][0];ji++)
  23.                     a[now++]=tub[k][ji];//按桶子的顺序重新排序 
  24.                     tub[k][0]=0;//该元素记录桶子里有多少个数 
  25.             }
  26.     }
  27.     for(ll i=1;i<=n;i++)cout<<a[i]<<" ";
  28. }

测试数据生成器

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<ctime>
  6. using namespace std;
  7. int main(){
  8.     freopen("testdata.in","w",stdout);
  9.     srand((unsigned)time(NULL));
  10.     for(int i=1;i<=10000;i++)
  11.         printf("%d ",rand());
  12.     return 0；
  13. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注