秘制CSP模板
- 2019 年 10 月 20 日
- 筆記
不定期更细中。。。。。。
声明1：由于js的问题导致VIEW CODE按钮只能点“I”附近才能展开代码
声明2：为了排版的美观，所有的解释以及需要留意的地方我都放在代码中了
声明3：以下所有代码均是已经AC的，请各位放心食用
STL类
堆
#include<bits/stdc++.h> using namespace std; int n; priority_queue<int,vector<int>,greater<int> >dui; int main(){ cin>>n; for(register int i=1;i<=n;++i){ register int ty;cin>>ty; if(ty==1){ cin>>ty; dui.push(ty); } else if(ty==2){ cout<<dui.top()<<endl; }else{ dui.pop(); } } }图类
负环
#include<bits/stdc++.h> using namespace std; int tt,n,m,head[100005],ji,dis[100005],cnt[100005]; int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } struct node{ int next,yuan,w; }ed[1000005]; void add(int p,int q,int quan){ ed[++ji].next=head[p]; ed[ji].yuan=q; ed[ji].w=quan; head[p]=ji; } bool huan; queue<int>dui;//队列就行了 void spfa(){ while(dui.size())dui.pop(); dui.push(1); dis[1]=0;//0号节点到根节点的距离为0 while(dui.size()){ int x=dui.front();dui.pop(); for(int i=head[x];i;i=ed[i].next){ int y=ed[i].yuan,l=dis[x]+ed[i].w; if(dis[y]>l){ dis[y]=l; ++cnt[y]; dui.push(y); if(cnt[y]>=n){huan=1;return;}//>=n!!! } } } } int main(){ cin>>tt; while(tt--){ cin>>n>>m; memset(head,0,sizeof(head)); memset(ed,0,sizeof(ed)); memset(dis,127,sizeof(dis)); memset(cnt,0,sizeof(cnt)); ji=0,huan=0; for(int i=1;i<=m;i++){ register int cn=read(),cm=read(),cw=read(); if(cw<0)add(cn,cm,cw); else add(cm,cn,cw),add(cn,cm,cw); } spfa(); if(huan)cout<<"YE5"<<endl; else cout<<"N0"<<endl; } return 0; }Dij
#include<iostream> #include<cstdio> #include<queue> using namespace std; int m,n,s,ji,head[200005],dis[200005]; bool bo[200005]; struct node{ int w,next,yuan; }ed[200005]; void add(int p,int q,int quan) { ed[++ji].w=quan; ed[ji].yuan=q; ed[ji].next=head[p]; head[p]=ji; } priority_queue < pair < int , int > > dui;//注意怎么写 int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ int cm,cn,cs; scanf("%d%d%d",&cm,&cn,&cs); add(cm,cn,cs); } for(int i=1;i<=n;i++)dis[i]=0x7fffffff;//注意是只有初始化 dis[s]=0; dui.push(make_pair(0,s));//注意make_pair怎么写,内容是什么 while(!dui.empty()){//注意有括号 int x=dui.top().second;//括号 dui.pop(); if(bo[x])continue;//记得判断重复 bo[x]=1; for(int j=head[x];j;j=ed[j].next){ int y=ed[j].yuan,l=dis[x]+ed[j].w; if(dis[y]>l){ dis[y]=l; dui.push(make_pair(-dis[y],y));//是-dis[y] } } } for(int i=1;i<=n;i++)printf("%d ",dis[i]); return 0; }spfa
#include<bits/stdc++.h> using namespace std; int n,m,s; int read(){ int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } int head[200005],ji,dis[200005]; struct node{ int next,yuan,w; }ed[5000005]; void add(int p,int q,int quan){ ed[++ji].next=head[p]; ed[ji].yuan=q; ed[ji].w=quan; head[p]=ji; } bool bo[1000005]; queue<int>dui; void spfa(){ dui.push(s);bo[s]=1; for(int i=1;i<=n;i++)dis[i]=0x7fffffff;dis[s]=0; while(dui.size()){ int x=dui.front();dui.pop(); bo[x]=0; for(int i=head[x];i;i=ed[i].next){ int y=ed[i].yuan,l=ed[i].w+dis[x]; if(dis[y]>l){ dis[y]=l; if(!bo[y]){//注意注意spfa与dij最大的额就是bo的位置 //dij每个点只会更新一次spfa可能会多次更新 bo[y]=1; dui.push(y); } } } } } int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ int cn=read(),cm=read(),cw=read(); add(cn,cm,cw); } spfa(); for(int i=1;i<=n;i++)cout<<dis[i]<<" "; }tarjan
#include<bits/stdc++.h> using namespace std; int n,m,head[100005],ji,sum,ans,mem; struct node{ int next,yuan; }ed[100005]; void add(int p,int q){ ed[++ji].next=head[p]; ed[ji].yuan=q; head[p]=ji; } int dfn[100005],low[100005]; stack<int>dui;//必须用stack!!!队列是先进先出 bool bo[100005]; void tarjan(int k){ mem=0; low[k]=dfn[k]=++ji; dui.push(k);bo[k]=1; for(int i=head[k];i;i=ed[i].next){ int y=ed[i].yuan; if(!dfn[y]){ tarjan(y); low[k]=min(low[k],low[y]); }else { if(bo[y]){ low[k]=min(low[k],low[y]); } } } if(dfn[k]==low[k]){ bo[k]=0; int x=dui.top(); while(x!=k&&dui.size()){ bo[x]=0; dui.pop(); x=dui.top(); ++mem; } dui.pop(); if(mem>0)++ans;//因为题目说了构成联通块的牛的数量要>=2 mem=0; } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int cn,cm; cin>>cn>>cm; add(cn,cm); } ji=0; for(int i=1;i<=n;i++){ if(!dfn[i])tarjan(i); } cout<<ans; }SCC
#include<bits/stdc++.h> using namespace std; int n,m,dfn[1000005],low[1000005],col[1000005],sum,si[1000005],out[1000005]; struct node{ int next,yuan; }ed[1000005]; int head[10000105],ji; void add(int p,int q){ ed[++ji].next=head[p]; ed[ji].yuan=q; head[p]=ji; } bool bo[1000005]; stack<int>dui; void tarjan(int k){ low[k]=dfn[k]=++ji; dui.push(k); bo[k]=1; for(int i=head[k];i;i=ed[i].next){ int y=ed[i].yuan; if(!dfn[y]){ tarjan(y); low[k]=min(low[k],low[y]); }else { if(bo[y]){ low[k]=min(low[k],low[y]); } } } if(dfn[k]==low[k]){ si[++sum]=1; col[k]=sum; bo[k]=1; while(dui.top()!=k){ col[dui.top()]=sum; bo[dui.top()]=0; si[sum]++;//与正常tarjan相比就是这里和上面col不同，si是统计每个块里面有多少个元素 dui.pop(); } dui.pop(); } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int cn,cm;cin>>cn>>cm; add(cn,cm); }ji=0; for(int i=1;i<=n;i++){ if(!dfn[i]){ tarjan(i); } } //到这里强连通分量已经算完啦 //后面只是题目要求。。。 /* 具体解释参考 恨妹不成穹 的解释： 但如果有多个点出度为0，那么它们都当不了明星（它们没有受到对方的爱慕—>它们没有受到所有牛的爱慕） 得出结论: 1.缩点后，若只有一个出度为0的点，那么明星牛的个数即那个强连通分量包含的点的个数； 2.缩点后，若有多个出度为0的点或无出度为0的点，那么明星牛的个数即为0。 */ for(int i=1;i<=n;i++){ for(int j=head[i];j;j=ed[j].next){ int y=ed[j].yuan; if(col[i]!=col[y])++out[col[i]]; } } int cun=0,ans=0; for(int i=1;i<=sum;i++){ if(!out[i]){// ++cun; ans+=si[i]; } if(cun>=2){ cout<<"0"<<endl; return 0; } } cout<<ans; }LCA
#include<bits/stdc++.h> using namespace std; int n,m,root,f[500005][25]; struct node{ int next,yuan; }ed[5000005]; int head[500005],ji,de[500005]; inline int read(){ register int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } inline void add(int p,int q){ ed[++ji].next=head[p]; ed[ji].yuan=q; head[p]=ji; } inline void dfs(int k,int ste){ for(int j=1;j<=20;j++){//因为不一定编号小的就是编号大的 的祖先所以要在dfs时预处理f f[k][j]=f[f[k][j-1]][j-1]; //还有，f预处理必须放在dfs前面，因为后面的儿子会要用到这个f } for(register int i=head[k];i;i=ed[i].next){ register int y=ed[i].yuan; if(!de[y]){ de[y]=ste; f[y][0]=k; dfs(y,ste+1); } } } inline int lca(int p,int q){ if(de[p]>de[q])swap(p,q); for(register int i=20;i>=0;i--){ if(de[f[q][i]]>=de[p])q=f[q][i];//记得是>=!!! } if(p==q)return p; for(register int i=20;i>=0;i--){ if(f[p][i]!=f[q][i]){ p=f[p][i],q=f[q][i]; } } return f[p][0]; } int main(){ cin>>n>>m>>root; for(register int i=1;i<n;i++){ register int cn=read(),cm=read(); add(cn,cm);add(cm,cn); } de[root]=1; dfs(root,2); for(register int i=1;i<=m;i++){ register int cn=read(),cm=read(); printf("%dn",lca(cn,cm));//cout->printf 2.7s->1.7s } }数论类
线性基
#include<bits/stdc++.h> #define ll long long using namespace std; ll p[55],a,n,ans; void merge(ll k){ for(int i=55;i>=0;i--){//>=0!!!!!!!! if(!(k>>i))continue; if(!p[i]){p[i]=k;break;} k^=p[i];//消去最高位，后面的1不管，这也是为什么线性基不唯一——shuixirui } } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a; merge(a); } for(int i=55;i>=0;i--){ if((ans^p[i])>ans)ans^=p[i]; } cout<<ans; } //如果要查询某个数是否能被该线性基表出可以把该数转成二进制 //对于每一位如果为1就XORp[i]如果最后结果为0则可以被表出裴蜀定理
//裴蜀定理内容ax+by=c,x∈Z*,y∈Z*成立的充要条件是gcd(a,b)∣c,Z* 表示正整数集。 //扩展到求ax+by=c 的最小非负 c,显然 c 要满足 (a,b)|c,所以 c 取 (a,b)是最小的。 #include<bits/stdc++.h> using namespace std; int n,a,ans; int gcd(int a,int b){ if(!b)return a; return gcd(b,a%b); } int main(){ cin>>n; for(int i=1;i<=n;i++){cin>>a;a>0?(a*=1):(a*=(-1));ans=gcd(ans,a);} cout<<ans; }并查集
#include<bits/stdc++.h> using namespace std; int n,m,fa[200005]; int find(int k){ while(fa[k]!=k)k=fa[k]=fa[fa[k]];//循环版找爸爸 return k; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++){ int cn,cm,cz; cin>>cn>>cm>>cz; int a=find(cm),b=find(cz); if(cn==1){ if(a>b)fa[a]=b;//按序号大小合并 else fa[b]=a; }else{ if(a==b)cout<<"Y"<<endl; else cout<<"N"<<endl; } } }快速排序
#include<bits/stdc++.h> using namespace std; int n,a[100005]; int read(){ int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } void quick_sort(int l,int r){ if(l>=r)return ; int mid=a[(l+r)>>1],i=l,j=r; while(i<=j){ while(a[i]<mid)++i;//不能加‘=’不然会T while(a[j]>mid)--j; if(i<=j){//要特判 swap(a[i],a[j]); ++i,--j;//注意注意 } } if(l<j)quick_sort(l,j);//!!! if(r>i)quick_sort(i,r);//!!! } int main(){ cin>>n; for(int i=1;i<=n;i++){ a[i]=read(); } quick_sort(1,n); for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } }素数筛
#include<bits/stdc++.h> using namespace std; int n,m,prime[100000005],ji; bool bo[10000005]; int main(){ cin>>n>>m; for(int i=2;i<=n;i++){ if(!bo[i])prime[++ji]=i;//不能加括号！！！，每次都要更新！！！ for(int j=1;i*prime[j]<=n;j++){//记得是prime[j]*i,i和j换个位置 bo[i*prime[j]]=1; if(i%prime[j]==0)break;//期中有其他因子的时候就退出来 } } bo[1]=bo[0]=1; for(int i=1;i<=m;i++){ int cn;cin>>cn; if(bo[cn])cout<<"No"<<endl; else cout<<"Yes"<<endl; } } //当你n特别大比如1e12时我们可以这么求出这个数可以被分解成多少个质数： #include<bits/stdc++.h> using namespace std; long long read() { long long x=0,f=1; char c=getchar(); while((c<'0'||c>'9')&&c!='-')c=getchar(); if(c=='-')f=-1,c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return f*x; } long long T,n,ans; int main(){ T=read(); while(T--){ n=read(); ans=0; for(long long i=2;i*i<=n;++i) while(!(n%i)){ n/=i; ans++; } if(n>1)ans++; if(ans==2)printf("Bobn"); else printf("Alicen"); } return 0; }快速幂
#include<bits/stdc++.h> #define ll long long using namespace std; long long m,n,mod; ll quick(ll x,int y){//快速幂 ll res=1; while(y){ if(y&1)res=(ll)res*x%mod; x=(ll)x*x%mod; y>>=1; }return res; } int main(){ cin>>m>>n>>mod; cout<<m<<"^"<<n<<" mod "<<mod<<"="<<quick(m,n)%mod; } 或者你也可以这么写 下面是我早期写的版本 #include<iostream> using namespace std; long long b,p,k; long long mod(long long x) { if(x==0) return 1%k; long long y=x,s; bool bo=y%2; y/=2; s=mod(y); s*=s%k; if(bo==1) s*=b; return s%k; } int main(){ cin>>b>>p>>k; cout<<b<<"^"<<p<<" mod "<<k<<"="<<mod(p); }三分法
#include<bits/stdc++.h> #define eps 1e-6 using namespace std; int n; double l,r,a[20]; double f(double x){//秦九昭定理 double s=0; for(int i=1;i<=n+1;i++)s=s*x+a[i];//巧妙的操作 return s; } int main(){ cin>>n>>l>>r; for(int i=1;i<=n+1;i++)cin>>a[i];//特别注意有n+1个值 while(r-l>=eps){ double k=(r-l)/3.0; double mid1=l+k,mid2=r-k; if(f(mid1)>f(mid2))r=mid2; else l=mid1; } printf("%.5lf",l); }矩阵快速幂
#include <bits/stdc++.h> #define ll long long #define m 1000000007 using namespace std; inline ll gi(){ register char ch=getchar();register ll x=0; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } ll n,k; struct node { ll mat[100][100]; }add,a,ans,mu,e,qk; inline node mul(node x,node y){ node mem=qk; for(register int i=1;i<=n;i++){ for(register int j=1;j<=n;j++){ for(register int h=1;h<=n;h++){ mem.mat[i][j]=(mem.mat[i][j]+x.mat[i][h]*y.mat[h][j])%m;//记得加上原来的 } } } return mem; } inline void quick(ll k){ ans=e; while(k){ if(k&1)ans=mul(ans,mu); mu=mul(mu,mu); k>>=1; } } int main(){ cin>>n>>k; for(register int i=1;i<=n;i++){ for(register int j=1;j<=n;j++){ mu.mat[i][j]=a.mat[i][j]=gi(); } } for(ll i=1;i<=n;i++){ e.mat[i][i]=1; } quick(k); for(register int i=1;i<=n;i++){ for(register int j=1;j<=n;j++){ printf("%lld ",ans.mat[i][j]); } printf("n"); } return 0; }乘法逆元
//法1(递推法) #include<bits/stdc++.h> using namespace std; long long n,p,inv[3000001]; int main(){ cin>>n>>p; inv[1]=1; for(int i=2;i<=n;i++){ inv[i]=(p-p/i)*inv[p%i]%p; } for(int i=1;i<=n;i++)printf("%dn",inv[i]); } /* 递推求inv的解释： 设p=k*i+r; 则有k*i+r≡0(mod p) 为了把r^(-1)剥离出来两边同乘i^(-1)*r^(-1) 得到r^(-1)=-k*r^(-1); k=p/i,r^(-1)=inv[p%i]; 此时我们注意到这样乘起来是负数 所以我们用p减去他 */ //法2(扩展欧几里得法) #include<bits/stdc++.h> #define ll long long using namespace std; ll n,p,inv[3000001],x,y; void exgcd(ll a,ll b,ll &x,ll &y){ if(!b){x=1,y=0;return ;} exgcd(b,a%b,y,x); y-=a/b*x; } int main(){ cin>>n>>p; for(int i=1;i<=n;i++){ exgcd(i,p,x,y); x=(p+x%p)%p; cout<<x<<endl; } } /* a*x≡c(mod p) 令t=x^(-1) 我们要求的就是 x*t≡1(mod p) 于是我们有 x*t+p*y=1 求t即可 */ //法3(快速幂) //即x^(p-2); //由于这个方法只适用于x与p互质的情况，exgcd不仅比他快还适用所有情况 这里就不在赘述NIM游戏
#include<bits/stdc++.h> using namespace std; int t,n; int main(){ cin>>t; while(t--){ cin>>n; int ans=0; for(int i=1;i<=n;i++){ int ci; cin>>ci; ans^=ci; } if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl; } }中国剩余定理
#include<bits/stdc++.h> #define int long long using namespace std; int n,m,a[100005],b[100005]; void exgcd(int aa,int bb,int &x,int &y){ if(!bb){x=1,y=0;return ;} exgcd(bb,aa%bb,y,x); y-=aa/bb*x; } int ksc(int aa,int bb,int mod){ int re=0; while(bb){ if(bb&1)re=(re+aa)%mod; bb>>=1,aa=(aa+aa)%mod; } return re; } void crt(){ int ans=0; for(int i=1;i<=n;i++){ int mi=m/b[i],x,y; exgcd(mi,b[i],x,y);//求出mi的逆元 ans=(ans+ksc(ksc(x,mi,m)%m,a[i],m)%m)%m; } ans=(ans%m+m)%m; cout<<ans; } signed main(){ cin>>n;m=1; for(int i=1;i<=n;i++)cin>>a[i]; 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 crt(); } /* 对于sum{ai*mi*mi^(-1)}的解释 xi≡ai*mi*mi^(-1)(mod bi) xj≡aj*mj*mj^(-1)(mod bj) 当循环到j时由于mj=b1*b2*...*bj-1*bj+1*...*bn 故sum之后即为答案 */字符串类
manacher
//注意此算法求的是回文串，必须是连续的一段序列 //而回文序列则不必连续 #include<bits/stdc++.h> using namespace std; char s[31000005]; int r[31000005],len;//r是包括自己向右扩展的最大半径 int main(){ s[0]=s[1]='#';len=2; while(cin>>s[len]){ s[++len]='#';++len; } --len;//在每个字符之间插板子 r[0]=r[1]=1; int maxr=1,pos=0,ans=0; for(int i=1;i<=len;i++){//必须一个一个更新 因为可能答案是关于‘#’对称的。。。 if(i<maxr){ r[i]=min(r[(pos<<1)-i],maxr-i);//两种情况 }else r[i]=1; for(;s[i-r[i]]==s[i+r[i]];++r[i]);//左右拓展 if(maxr<i+r[i])pos=i,maxr=i+r[i]; ans=max(ans,r[i]); } cout<<ans-1;//半径减去‘#’的个数 }KMP
#include<bits/stdc++.h> using namespace std; int n,m,lena,lenb,nex[1000005]; char a[1000005],b[1000005]; int main(){ scanf("%s%s",a+1,b+1); lena=strlen(a+1); lenb=strlen(b+1); int j=0; for(int i=2;i<=lenb;i++){ while(j&&b[i]!=b[j+1])j=nex[j]; if(b[i]==b[j+1])++j; nex[i]=j; } j=0; for(int i=1;i<=lena;i++){ while(j&&b[j+1]!=a[i])j=nex[j]; if(b[j+1]==a[i])++j; if(j==lenb){cout<<i-lenb+1<<endl;j=nex[j];} } for(int i=1;i<=lenb;i++)cout<<nex[i]<<" "; return 0; }杂项
ST表
//交LG的话记得加快读~~~ #include<bits/stdc++.h> using namespace std; int n,m,f[5000005][20];//f[i][j]为从i开始(2^j)-1的最大值 int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>f[i][0]; } for(int k=1;k<=20;k++){ for(int i=1;i<=n-(1<<k)+1;i++){ 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] } }//如果是先枚举i那么在f[1][2]的时候会不知道f[2][1]的值 for(int i=1;i<=m;i++){ int le,ri;cin>>le>>ri; int t=log(ri-le+1)/log(2);//换底公式即log以2为ri-le+1的对数，找到最大的k printf("%dn",max(f[le][t],f[ri-(1<<t)+1][t]));//左右两半区间查询 //记得+1如1~5:log2(5)=2,f[1][2]为1~4的max而后半段要2~5，5-2^2=1所以要加1！！！ } }线段树1
#include<bits/stdc++.h> #include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,a[100005]; struct node{ ll sum,add; ll l,r; }t[1000005]; ll read(){ ll x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } void build(ll p,ll l,ll r){ t[p].l=l,t[p].r=r; if(l==r){t[p].sum=a[l];return ;} ll mid=(l+r)>>1; build(p*2,l,mid); build(p*2+1,mid+1,r); t[p].sum=t[p*2].sum+t[p*2+1].sum; } void spread(ll p){ if(t[p].add){ t[p*2].sum+=(ll)t[p].add*(t[p*2].r-t[p*2].l+1);//ll!!! t[p*2+1].sum+=(ll)t[p].add*(t[p*2+1].r-t[p*2+1].l+1); t[p*2].add+=t[p].add;//别忘了 t[p*2+1].add+=t[p].add; t[p].add=0; } } void add(ll p,ll l,ll r,ll k){ if(t[p].l>=l&&t[p].r<=r){ t[p].add+=k; t[p].sum+=(ll)k*(t[p].r-t[p].l+1);//不要忘了 return ; } spread(p); ll mid=(t[p].l+t[p].r)>>1;//记得是在这个节点记录的区间的中点 if(l<=mid)add(p*2,l,r,k);//注意是l<=mid否则当修改区间横跨了mid时就不会进行任何操作 if(r>mid)add(p*2+1,l,r,k); t[p].sum=t[p*2].sum+t[p*2+1].sum;//还要记得修改sum } ll ask(ll p,ll l,ll r){ if(t[p].l>=l&&t[p].r<=r){ return t[p].sum; } spread(p); t[p].sum=t[p*2].sum+t[p*2+1].sum; ll mid=(t[p].r+t[p].l)>>1; ll val=0; if(l<=mid)val+=ask(p*2,l,r); if(r>mid)val+=ask(p*2+1,l,r); return val; } int main(){ cin>>n>>m; for(ll i=1;i<=n;i++){ a[i]=read(); } build(1,1,n); for(ll i=1;i<=m;i++){ ll ty=read(); if(ty==1){ ll cn=read(),cm=read(),cw=read(); add(1,cn,cm,cw); } else { ll cn=read(),cm=read(); cout<<ask(1,cn,cm)<<endl; } } }线段树2
#include<bits/stdc++.h> #define ll long long using namespace std; int n,m,a[1000005],mod; struct node{ ll sum,l,r,mu,add; }t[1000005]; ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } void build(ll p,ll l,ll r){ t[p].l=l,t[p].r=r;t[p].mu=1; if(l==r){t[p].sum=a[l]%mod;return ;} ll mid=(l+r)>>1; build(p*2,l,mid); build(p*2+1,mid+1,r); t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod; } void spread(ll p){ 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; 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; t[p*2].mu=(ll)(t[p*2].mu*t[p].mu)%mod; t[p*2+1].mu=(ll)(t[p*2+1].mu*t[p].mu)%mod; t[p*2].add=(ll)(t[p*2].add*t[p].mu+t[p].add)%mod; t[p*2+1].add=(ll)(t[p*2+1].add*t[p].mu+t[p].add)%mod; t[p].mu=1,t[p].add=0; } void add(ll p,ll l,ll r,ll k){ if(t[p].l>=l&&t[p].r<=r){ t[p].add=(t[p].add+k)%mod; t[p].sum=(ll)(t[p].sum+k*(t[p].r-t[p].l+1))%mod;//只要加上增加的就好 return ; } spread(p); t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod; ll mid=(t[p].l+t[p].r)>>1; if(l<=mid)add(p*2,l,r,k); if(mid<r)add(p*2+1,l,r,k); t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod; } void mu(ll p,ll l,ll r,ll k){ if(t[p].l>=l&&t[p].r<=r){ t[p].add=(t[p].add*k)%mod;//比较重要的一步,add要在这里乘上k,因为后面可能要加其他的数而那些数其实是不用乘k的 t[p].mu=(t[p].mu*k)%mod; t[p].sum=(t[p].sum*k)%mod; return ; } spread(p); t[p].sum=t[p*2].sum+t[p*2+1].sum; ll mid=(t[p].l+t[p].r)>>1; if(l<=mid)mu(p*2,l,r,k); if(mid<r)mu(p*2+1,l,r,k); t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod; } ll ask(ll p,ll l,ll r){ if(t[p].l>=l&&t[p].r<=r){ return t[p].sum; } spread(p); ll val=0; ll mid=(t[p].l+t[p].r)>>1; if(l<=mid)val=(val+ask(p*2,l,r))%mod; if(mid<r)val=(val+ask(p*2+1,l,r))%mod; return val; } int main(){ cin>>n>>m>>mod; for(int i=1;i<=n;i++){ a[i]=read(); } build(1,1,n); for(int i=1;i<=m;i++){ int ty=read(); if(ty==1){ ll cn=read(),cm=read(),cw=read(); mu(1,cn,cm,cw); }else if(ty==2){ ll cn=read(),cm=read(),cw=read(); add(1,cn,cm,cw); }else { ll cn=read(),cm=read(); cout<<ask(1,cn,cm)<<endl; } } }悬线法
#include<bits/stdc++.h> using namespace std; int n,m,a[1005][1005],l[1005][1005],r[1005][1005],up[1005][1005]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ char ch;cin>>ch; if(ch=='F')a[i][j]=1; r[i][j]=l[i][j]=j,up[i][j]=1; } } for(int i=1;i<=n;i++){ for(int j=2;j<=m;j++){ if(a[i][j]==a[i][j-1]&&a[i][j]==1)l[i][j]=l[i][j-1]; } for(int j=m-1;j>=1;j--){ if(a[i][j]==a[i][j+1]&&a[i][j]==1)r[i][j]=r[i][j+1]; } } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(i>1&&a[i][j]==a[i-1][j]&&a[i][j]==1){//是>1才进去但是i=1时还是要做的 r[i][j]=min(r[i][j],r[i-1][j]); l[i][j]=max(l[i][j],l[i-1][j]); up[i][j]=up[i-1][j]+1; } ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]); } } cout<<ans; }哈夫曼树
#include<bits/stdc++.h> #define int long long using namespace std; int n,m; priority_queue<pair<int,int> >dui; signed main(){ cin>>n>>m;int w; for(int i=1;i<=n;i++){ cin>>w; dui.push(make_pair(-w,-1)); } while((dui.size()-1)%(m-1))dui.push(make_pair(-0,-1));//最后一次合并要满足=0 因为每次合并要减少k-1个节点要将n个节点合并成1个 //题解里的解释：因为每次都是将k个节点合并为1个（减少k-1个），一共要将n个节点合并为1个，如果（n-1）%（k-1）！=0 则最后一次合并时不足k个。也就表明了最靠近根节点的位置反而没有被排满，因此我们需要加入k-1-（n-1）%（k-1）个空节点使每次合并都够k个节点（也就是利用空节点将其余的节点挤到更优的位置上）。 int ans=0; while(dui.size()>=m){ int re=0,h=-0; for(int i=1;i<=m;i++){ int x=dui.top().first,y=dui.top().second;dui.pop(); re+=x; h=min(h,y); } ans+=re; dui.push(make_pair(re,h-1)); } cout<<-ans<<endl<<-dui.top().second-1; }LIS
#include<bits/stdc++.h> using namespace std; int n,a[100005],f[100005]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i];f[i]=0x7ffffff; } int len=0;f[0]=0; for(int i=1;i<=n;i++){ if(f[len]<a[i])f[++len]=a[i]; else { int l=1,r=len; while(l<r){ int mid=(l+r)>>1; if(a[i]<f[mid])r=mid;//因为要将a[i]插入到f中，且插入位置保证f[mid]>=a[i]，所以>a[i]也可能是答案 else l=mid+1; } f[l]=a[i]; } } cout<<len; }LCS
#include<bits/stdc++.h> using namespace std; int n,f[100001],a[100001],b[100001],ma[100001]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i];ma[a[i]]=i,f[i]=0x7fffffff; } for(int i=1;i<=n;i++)cin>>b[i]; f[0]=0; int len=0; for(int i=1;i<=n;i++){ if(f[len]<ma[b[i]])f[++len]=ma[b[i]];//比队尾还大 else { int l=1,r=len; while(l<r){ int mid=(l+r)>>1; if(f[mid]<ma[b[i]])l=mid+1; else r=mid; } f[l]=ma[b[i]]; } } cout<<len; } /*由于数据过大我们在时间和空间上都不能像下面那样做 那怎么办呢 我们发现既然是1到n的排列 那我们就可以把A离散化 这样我们就可以得到B在A序列中的编号 如果我们找到了一段编号序列的子序列，他是单调递增的，那么就表明对应元素在A和B中是从前往后排列的 这就是我们要的答案 差点忘了说 找这段单调递增的序列其实就是LIS哦 */ #include<bits/stdc++.h> using namespace std; int n,m,a[2005],b[2005],f[2005][2005]; inline int read(){ register int x=0;register char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } int main(){ freopen("lcis.in","r",stdin); freopen("lcis.out","w",stdout); cin>>n>>m; for(register int i=1;i<=n;++i){ a[i]=read(); } for(register int i=1;i<=m;++i){ b[i]=read(); } register int maxn=0; for(register int i=1;i<=n;++i){ for(register int j=1;j<=m;++j){ if(a[i]==b[j]){ for(register int k=1;k<j;++k){ f[i][j]=max(f[i][j],f[i][k]+1); } maxn=max(maxn,f[i][j]); }else f[i][j]=f[i-1][j]; } } cout<<maxn<<endl; } /* fij表示到ai和bj的位置且ai必选 */LCIS
#include<bits/stdc++.h> using namespace std; int n,m,a[505],b[505],g[505][505],f[505][505]; void path(int i,int j){ if(j==0)return ; path(g[i][j],j-1); if(g[i][j]!=i){ printf("%d ",a[i]); } } int main(){ cin>>n;for(int i=1;i<=n;i++)cin>>a[i]; cin>>m;for(int j=1;j<=m;j++)cin>>b[j]; int maxn=0,x=0,y=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i]==b[j]){ f[i][j]=1; for(int k=1;k<i;k++){ if(a[k]<a[i]){ if(f[i][j]<f[k][j-1]+1){//如果是f[k][j]由于a[1~i]与b[j]不匹配所以这样是错的 f[i][j]=f[k][j-1]+1; g[i][j]=k; } } } if(maxn<f[i][j]){maxn=f[i][j],x=i,y=j;} }else{ f[i][j]=f[i][j-1]; g[i][j]=i; } } } cout<<maxn<<endl; path(x,y); cout<<endl; } /* 输出的递归函数path应有两个参数(i,j),表示当前在数组A中位置是i,在数组B中位置是j. 我们沿着f[i][j]转移时的路径递归,也就是path(i-1,g[i][j]). 若g[i][j]==j,则说明这里是没有增加LCIS长度的转移, 应该沿着f[i][j]转移时的路径继续递归,但不输出.直到g[i][j]!=j就输出B[j]. */后序遍历
#include<bits/stdc++.h> using namespace std; char q[1000005],z[1000005]; int len; int find(char k){ for(int i=1;i<=len;i++)if(q[i]==k)return i; } void dfs(int l1,int r1,int l2,int r2){ int m=find(z[r2]); cout<<q[m]; if(m>l1)dfs(l1,m-1,l2,r2-r1+m-1);//有左子树 if(r1>m)dfs(m+1,r1,l2+m-l1,r2-1); } //r2-(r1-m+1) //r2-r1+m-1 //l2+(m-r1) //l2+m-r1 int main(){ scanf("%s",q+1);scanf("%s",z+1); len=strlen(q+1); dfs(1,len,1,len); }后缀表达式
#include<bits/stdc++.h> using namespace std; char a[1005]; int sum,k; stack <int> stk; int main() { gets(a); for(int i=0;a[i]!='@';i++) { if(a[i]=='.') { sum=0,k=1; for(int j=i-1;j>=0&&a[j]>='0'&&a[j]<='9';j--) sum=sum+(a[j]-48)*k,k*=10; stk.push(sum); continue; } if(a[i]>='0'&&a[i]<='9') continue; sum=stk.top(); stk.pop(); if(a[i]=='+') sum=stk.top()+sum; if(a[i]=='-') sum=stk.top()-sum; if(a[i]=='*') sum=stk.top()*sum; if(a[i]=='/') sum=stk.top()/sum; stk.pop(); stk.push(sum); } printf("%d",stk.top()); return 0; }中缀表达式转后缀表达式
#include<bits/stdc++.h> #define M 10007 using namespace std; int n; char ss[10000005]; stack<char>dui; int main(){ cin>>n; scanf("%s",ss +1); string s="."; for(int i=1;i<=n;i++){ if(ss[i]=='('||ss[i]=='*'){ dui.push(ss[i]); } if(ss[i]=='+'){ while(dui.size()&&dui.top()=='*'){//直到找到优先级更低的符号 s+=dui.top(); dui.pop(); } dui.push('+'); } if(ss[i]==')'){ while(dui.size()&&dui.top()!='('){ s+=dui.top(); dui.pop(); } dui.pop(); } if(ss[i]!='('&&ss[i]!=')'){ s+='.'; } } while(dui.size())s+=dui.top(),dui.pop(); cout<<s<<endl; } /* 8 +*+(*+)* 下面的话来自题解区： 转换过程需要用到栈，具体过程如下： 1）如果遇到操作数，我们就直接将其输出。 2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。 3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。 4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。 5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。 备注：本题中我们用一个"."来代表数字。扫描整个表达式（读入的字符串），如果当前位置不是括号（既不是左括号也不是右括号），就在后缀表达式里填一个"."表示这里应有一个数字。 */高精度
高精度加法
#include<iostream> #include<cstring> #include<cstdio> #define maxn 1000000 using namespace std; char d[maxn],e[maxn]; int a[maxn],b[maxn],c[maxn]; int main(){ scanf("%s%s",&d,&e); int lena=strlen(d),lenb=strlen(e),lenc=lena>lenb?lena:lenb,jin=0; for(int i=0;i<lena;i++){ a[lena-i]=d[i]-48; } for(int i=0;i<lenb;i++){ b[lenb-i]=e[i]-48; } for(int i=1;i<=lenc;i++){ c[i]=a[i]+b[i]+jin; jin=c[i]/10; c[i]%=10; } lenc++; c[lenc]=jin; while(!c[lenc]&&lenc>1){ lenc--; } for(int i=lenc;i>=1;i--)printf("%d ",c[i]); return 0; }高精度减法
#include<iostream> #include<cstring> #include<cstdio> #define maxn 1000000 using namespace std; char d[maxn],e[maxn]; int a[maxn],b[maxn],c[maxn],f[maxn]; int main(){ scanf("%s%s",&d,&e); if(strcmp(d,e)==0){ cout<<"0"; return 0; } int lena=strlen(d),lenb=strlen(e); for(int i=0;i<lena;i++){ a[lena-i]=d[i]-48; } while(!a[lena]){ lena--; } for(int i=0;i<lenb;i++){ b[lenb-i]=e[i]-48; } while(!b[lenb]){ lenb--; } int lenc=lena>lenb?lena:lenb; if(memcmp(a,b,lenc)<0&&lena==lenb||(lena<lenb)){ memcpy(f,a,sizeof(a)); memcpy(a,b,sizeof(b)); memcpy(b,f,sizeof(f)); cout<<"-"; int t=lena; lena=lenb; lenb=t; } lenc=lena>lenb?lena:lenb; for(int i=1;i<=lenc;i++){ if(a[i]-b[i]<0){ a[i]+=10; a[i+1]--; } c[i]=a[i]-b[i]; } lenc++; while(!c[lenc]&&lenc>1){ lenc--; } for(int i=lenc;i>=1;i--)printf("%d ",c[i]); return 0; }高精度乘法
#include<iostream> #include<cstring> using namespace std; int a[2005],b[2005],c[2005]; char a1[2005],b1[2005]; int main(){ scanf("%s%s",&a1,&b1); int lena=strlen(a1),lenb=strlen(b1); for(int i=0;i<lena;i++) a[lena-i]=a1[i]-'0'; for(int i=0;i<lenb;i++) b[lenb-i]=b1[i]-'0'; for(int i=1;i<=lenb;i++){ int jin=0; for(int j=1;j<=lena;j++){ c[i+j-1]=a[j]*b[i]+jin+c[i+j-1]; jin=c[i+j-1]/10; c[i+j-1]%=10; } c[lena+i]=jin; } int lenc=lena+lenb; while(!c[lenc]&&lenc>1)lenc--; for(int i=lenc;i>=1;i--)printf("%d ",c[i]); return 0; }高精除以低精（附带出输出余数）
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int a[2005],b,c[2005],jin; char a1[2005]; int main(){ scanf("%s",&a1); cin>>b; int lena=strlen(a1); for(int i=0;i<lena;i++) a[i+1]=a1[i]-'0';//记得是从前往后处理 for(int i=1;i<=lena;i++){ c[i]=(jin*10+a[i])/b; jin=(jin*10+a[i])%b; } int lenc=1; while(!c[lenc]&&lenc<lena)lenc++; for(int i=lenc;i<=lena;i++)printf("%d",c[i]); cout<<endl<<jin; return 0; } //jin取的是前面的余数，把前面的余数拼到后面一起除排序
选择排序
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int a[99999999],n; void swap(int &l,int &k){ int t=l; l=k; k=t; } int main(){ cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ int ji=i; for(int j=i+1;j<=n;j++){ if(a[j]<a[ji])ji=j; } if(ji!=i) // {//或者这样也行 // int t=a[i]; // a[i]=a[ji]; // a[ji]=t; // } swap(a[i],a[ji]);//要传址调用 } cout<<endl; for(int i=1;i<=n;i++) printf("%d ",a[i]); return 0; }正版冒泡
#include<iostream> #include<cstdio> using namespace std; int a[99999999],n; int main(){ cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=n-1;i>=1;i--){ for(int j=0;j<=i;j++){ if(a[j]>a[j+1]) swap(a[j],a[j+1]); } } for(int i=1;i<=n;i++)printf("%d ",a[i]); return 0; }盗版冒泡
#include<iostream> #include<cstdio> using namespace std; int a[99999999],n; int main(){ cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); // for(int i=1;i<=n;i++)cout<<a[i]<<" "; for(int i=1;i<=n;i++){ // int ji=0; for(int j=i+1;j<=n;j++){ if(a[i]>a[j]) swap(a[i],a[j]); } } for(int i=1;i<=n;i++)printf("%d ",a[i]); return 0; }插排
#include<iostream> #include<cstdio> using namespace std; int a[99999999],n,i,j; void yi(int p,int q) { for(int h=q;h>p;h--)a[h]=a[h-1]; } int main(){ cin>>n; for( i=1;i<=n;i++)scanf("%d",&a[i]); for( i=2;i<=n;i++){//a[i]为需要插入的数 for( j=i-1;j>=1;j--)//寻找插入点 if(a[j]<a[i])break; if(j!=i-1){//需要将a[i]插入a[j]后 int temp=a[i]; yi(j+1,i); a[j+1]=temp; } } cout<<endl; for(i=1;i<=n;i++)printf("%d ",a[i]); return 0; }桶排
#include<iostream> #include<cstdio> using namespace std; int a[99999999],n,ji; int main(){ cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&ji); a[ji]++; } for(int i=0;i<=n;i++){ while(a[i]){ printf("%d ",i); a[i]--; } } return 0; }三数取中+插排版 快排
#include<iostream> #include<cstdio> using namespace std; int a[99999999],n; void cha(int p,int q)//p<q { int f,g; for( f=p;f<=q;f++){ for( g=f-1;g>=p;g++)if(a[g]<a[f])break; if(g!=f-1){ int temp=a[f]; for(int s=f;s>g;s--)a[s]=a[s-1]; a[g+1]=temp; } } } void quick(int le,int ri) { if(le>=ri)return; if(ri-le>=10)cha(le,ri); int t=(le+ri)/2,mid,x=le,y=ri; if(a[le]<a[t]){ if(a[t]>a[ri]){ int w=a[t]; a[t]=a[ri]; a[ri]=w; } } if(a[le]>a[t]){ int w=a[t]; a[t]=a[le]; a[le]=w;//a[le]<a[t] if(a[t]>a[ri]){ int w=a[t]; a[t]=a[ri]; a[ri]=w; } } mid=a[t]; do{ while(a[x]<mid)x++; while(a[y]>mid)y--; if(x<=y){ int w=a[x]; a[x]=a[y]; a[y]=w; x++; y--; } }while(x<=y); if(le<y)quick(le,y); if(x<ri)quick(x,ri); } int main(){ cin>>n; for(int i=1;i<=n;i++)scanf("%d",&a[i]); quick(1,n); for(int i=1;i<=n;i++)printf("%d ",a[i]); } return 0；归并排序
#include<iostream> #include<cstdio> using namespace std; int a[99999999],b[99999999],n; void gui(int le,int ri) { if(le==ri)return; int mid=(le+ri)/2,x=le,y=mid+1,k=le; gui(le,mid); gui(mid+1,ri); while(x<=mid&&y<=ri){ if(a[x]<a[y]){ b[k++]=a[x++]; } else{ b[k++]=a[y++]; } } while(x<=mid){ b[k++]=a[x++]; } while(y<=ri){ b[k++]=a[y++]; } for(int g=le;g<=ri;g++)a[g]=b[g]; } int main(){ cin>>n; for(int i=1;i<=n;i++)scanf("%d",&a[i]); gui(1,n); for(int i=1;i<=n;i++)printf("%d ",a[i]); return 0; }测试数据生成器
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<ctime> using namespace std; int main(){ freopen("testdata.in","w",stdout); srand((unsigned)time(NULL)); for(int i=1;i<=10000;i++) printf("%d ",rand()); return 0； }
