線段樹1（真題）

#include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std; const int N=1e5+100; long long tr[N*4],flag[N*4],ans; void built(int i,int l,int r,int x,long long val) {if(l==r){tr[i]+=val; return;}int mid=(l+r)/2;if(x<=mid) built(i*2,l,mid,x,val); if(x>mid) built(i*2+1,mid+1,r,x,val); tr[i]=tr[i*2]+tr[i*2+1]; return; } void pushdown(int i,int l,int r) {int mid=(l+r)/2;tr[i*2]+=flag[i]*(mid-l+1);tr[i*2+1]+=flag[i]*(r-mid); flag[i*2]+=flag[i];flag[i*2+1]+=flag[i];flag[i]=0; return; } void update(int i,int l,int r,long long x,long long y,long long k) {if(l>=x&&r<=y){tr[i]+=k*(r-l+1);flag[i]+=k; return;}if(flag[i]>0) pushdown(i,l,r);int mid=(l+r)/2;if(mid>=x) update(i*2,l,mid,x,y,k); if(mid<y) update(i*2+1,mid+1,r,x,y,k);tr[i]=tr[i*2]+tr[i*2+1];return; } void query(int i,int l,int r,long long x,long long y) {if(l>=x&&r<=y){ans+=tr[i]; return;}if(flag[i]>0) pushdown(i,l,r); int mid=(l+r)/2;if(mid>=x) query(i*2,l,mid,x,y); if(mid<y) query(i*2+1,mid+1,r,x,y); } int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++){long long x;cin>>x;built(1,1,n,i,x);}while(m--){int op;cin>>op;if(op==1){long long x,y,k;cin>>x>>y>>k;update(1,1,n,x,y,k);}if(op==2){long long x,y;cin>>x>>y;ans=0;query(1,1,n,x,y);cout<<ans<<endl;}}return 0; }

線段樹2（真題）

#include<bits/stdc++.h> using namespace std; const int N = 1e5+100; int n,m; int a,b,c; long long sum[N*4],fa[N*4],fm[N*4],w,p,ans; bool mu[N*4]; int mid[N*4]; void build(int i,int l,int r) {fm[i]=1;if(l==r){cin>>sum[i];return;}mid[i]=(l+r)/2;build(i*2,l,mid[i]);build(i*2+1,mid[i]+1,r);sum[i]=(sum[i*2]+sum[i*2+1])%p; } void down(int i,int l,int mid,int r) {if(mu[i]){sum[i*2]=sum[i*2]*fm[i]%p;sum[i*2+1]=sum[i*2+1]*fm[i]%p;fa[i*2]=fa[i*2]*fm[i]%p;fa[i*2+1]=fa[i*2+1]*fm[i]%p;fm[i*2]=fm[i*2]*fm[i]%p;fm[i*2+1]=fm[i*2+1]*fm[i]%p;mu[i*2]=mu[i*2+1]=true;fm[i]=1;mu[i]=false; }if(fa[i]){sum[i*2]=(sum[i*2]+fa[i]*(mid-l+1)%p)%p;sum[i*2+1]=(sum[i*2+1]+fa[i]*(r-mid)%p)%p;fa[i*2]=(fa[i*2]+fa[i])%p;fa[i*2+1]=(fa[i*2+1]+fa[i])%p;fa[i]=0;} } void solve(int i,int l,int r) {if(l>=b && r<=c){if(a==1){sum[i]=sum[i]*w%p;fa[i]=fa[i]*w%p;fm[i]=fm[i]*w%p;mu[i]=true;}elseif(a==2){sum[i]=(sum[i]+w*(r-l+1)%p)%p;fa[i]+=w;}elseans=(ans+sum[i])%p;return;}if(mu[i] || fa[i]) down(i,l,mid[i],r);if(b<=mid[i]) solve(i*2,l,mid[i]);if(c>mid[i]) solve(i*2+1,mid[i]+1,r);sum[i]=(sum[i*2]+sum[i*2+1])%p; } int main() {cin>>n>>m>>p;build(1,1,n);while(m--){cin>>a;if(a==1 || a==2){cin>>b>>c>>w;solve(1,1,n);}else{ans=0;cin>>b>>c;solve(1,1,n);cout<<ans<<endl;}}return 0; }

ST表（真題）

#include<cstdio> #include<cmath> #include<algorithm> using namespace std; inline int read() {char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } int maxx[1000010][21]; int query(int l,int r) {int k=log2(r-l+1);return max(maxx[l][k],maxx[r-(1<<k)+1][k]); } int main() {int n=read(),m=read();for(int i=1; i<=n; i++)maxx[i][0]=read();for(int j=1; j<=21; j++)for(int i=1; i+(1<<j)-1<=n; i++)maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]);for(int i=1; i<=m; i++){int l=read(),r=read();printf("%d\n",query(l,r));}return 0; }

并查集（真題）

#include<bits/stdc++.h> using namespace std; int n,m; int x,y,z; int a[11000]; int find(int x) {if(x==a[x])return x;elsereturn a[x]=find(a[x]); } int main() {cin>>n>>m;while(n--)a[n]=n;while(m--){cin>>x>>y>>z;if(x&2){if(find(y)==find(z))cout<<"Y"<<endl;elsecout<<"N"<<endl;}elseif(find(y)!=find(z))a[find(y)]=find(z);}return 0; }

乘法逆元（真題）

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #define int long long using namespace std; int a[3000010]; int n,p; main() {cin>>n>>p;a[1]=1;cout<<1<<"\n";for(int i=2;i<=n;i++){a[i]=(p-p/i)*a[p%i]%p;cout<<a[i]<<"\n";}return 0; }

單源最短路（真題）

#include <bits/stdc++.h> #define re register using namespace std; inline int read() {int X=0,w=1; char c=getchar();while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();return X*w; } struct Edge { int v,w,nxt; }; Edge e[500010]; int head[100010],cnt=0; inline void addEdge(int u,int v,int w) {e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt; } int n,m,s; int dis[100010]; struct node { //堆節(jié)點int u,d;bool operator <(const node& rhs) const {return d>rhs.d;} }; inline void Dijkstra() {for (re int i=1;i<=n;i++) dis[i]=2147483647;dis[s]=0;priority_queue<node> Q; //堆Q.push((node){s,0});while (!Q.empty()) {node fr=Q.top(); Q.pop();int u=fr.u,d=fr.d;if (d!=dis[u]) continue;for (re int i=head[u];i;i=e[i].nxt) {int v=e[i].v,w=e[i].w;if (dis[u]+w<dis[v]) {dis[v]=dis[u]+w;Q.push((node){v,dis[v]});}}} } int main() {n=read(),m=read(),s=read();for (re int i=1;i<=m;i++) {int X=read(),Y=read(),Z=read();addEdge(X,Y,Z);}Dijkstra();for (re int i=1;i<=n;i++) printf("%d ",dis[i]);return 0; }

堆(真題)

#include<bits/stdc++.h> using namespace std; priority_queue< int,vector<int>,greater<int> >a; int n,m; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&m);if(m==1){scanf("%d",&m);a.push(m);}elseif(m==2){cout<<a.top()<<endl;}elsea.pop();}return 0; }

二分圖匹配（真題）

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; int map[1010][1010]; int pl[1000010]; bool mark[1000010]; int n,m,e,tot; inline int read() {int x=0,f=1;char ch=getchar();for(; !isdigit(ch); ch=getchar())if(ch=='-')f=-1;for(; isdigit(ch); ch=getchar())x=(x<<1)+(x<<3)+ch-'0';return x*f; } bool find(int x) {for(int i=1; i<=m; i++){if(map[x][i]==1&&mark[i]==0){mark[i]=1;if(pl[i]==0||find(pl[i])==1){pl[i]=x;return 1;}}}return 0; } int main() {n=read(),m=read(),e=read();for(int i=1; i<=e; i++){int x=read(),y=read();if(x<=n&&y<=m)map[x][y]=1;}for(int i=1; i<=n; i++){memset(mark,0,sizeof(mark));if(find(i)==1)tot++;}cout<<tot;return 0; }

負(fù)環(huán)（真題）

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std;typedef long long LL;inline int read() {char c=getchar();int num=0,f=1;for(;!isdigit(c);c=getchar())f=c=='-'?-1:f;for(;isdigit(c);c=getchar())num=num*10+c-'0';return num*f; }const int N=2e3+5; const int M=3e3+5;int T,n,m;int head[N],num_edge; struct Edge {int v,w,nxt; }edge[M<<1];inline void add_edge(int u,int v,int w) {edge[++num_edge].v=v;edge[num_edge].w=w;edge[num_edge].nxt=head[u];head[u]=num_edge; }int dis[N],cnt[N],vis[N],tim; queue<int> que; bool spfa() {++tim;memset(dis,0x3f,sizeof(dis));memset(cnt,0,sizeof(cnt));while(!que.empty()) que.pop();int u;dis[1]=0,cnt[1]=1;que.push(1);while(!que.empty()){u=que.front(),que.pop();vis[u]=0;for(int i=head[u],v;i;i=edge[i].nxt){v=edge[i].v;if(dis[v]>dis[u]+edge[i].w){dis[v]=dis[u]+edge[i].w;++cnt[v]/*=cnt[u]+1*/;if(cnt[v]>=n) return 1;if(vis[v]!=tim){vis[v]=tim;que.push(v);}}}}return 0; }int main() {T=read();while(T--){memset(head,0,sizeof(head));num_edge=0;n=read(),m=read();for(int i=1,a,b,c;i<=m;++i){a=read(),b=read(),c=read();add_edge(a,b,c);if(c>=0) add_edge(b,a,c);}if(spfa()) puts("YE5");else puts("N0");}return 0; }

矩陣快速冪（真題）

#include<iostream> #include<cstring> #define mod 1000000007 #define ll long long using namespace std; struct Mat{ll m[101][101]; }; Mat a,e; ll n,p; Mat Mul(Mat x,Mat y) {Mat c;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c.m[i][j]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++){c.m[i][j]=c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod;}return c; } Mat pow(Mat x,ll y) {Mat ans=e;while(y){if(y&1)ans=Mul(ans,x); x=Mul(x,x);y>>=1;}return ans; }int main() {cin>>n>>p;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a.m[i][j];for(int i=1;i<=n;i++)e.m[i][i]=1; Mat ans=pow(a,p);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<ans.m[i][j]%mod<<" ";cout<<endl;} return 0; }

縮點（真題）

#include<iostream> using namespace std; const int maxn = 10007; const int maxm = 100007; struct node {int x,y; }E[maxm],ne[maxm]; int n,m,tm = 0,top = 0,tot = 0; int W[maxn],dfn[maxn],low[maxn],Head[maxn],Next[maxm],S[maxn],V[maxn],sd[maxn];//w 點權(quán)...sd 縮點后 舊點所對應(yīng)的新點 int nh[maxn],nn[maxm],in[maxn],D[maxn];//newhead，newnext，index入度，D就是上面說的F啦 void tarjan(int x) {dfn[x] = low[x] = ++tm;S[++top] = x; V[x] = 1;for (int y,i = Head[x]; i; i = Next[i]){y = E[i].y;if (!dfn[y]){tarjan(y);low[x] = min(low[x],low[y]);}else if (V[y]){low[x] = min(low[x],low[y]);// low[x] = min(low[x],dfn[y]);兩種都行，老師講的注釋里的 求大佬解釋下到底哪種好}}if (dfn[x] == low[x]){int y;while (y = S[top--]){V[y] = 0;sd[y] = x;//縮點if (y==x) break;W[x] +=W[y];}}return; } int main() {cin>>n>>m;for (int i = 1; i<=n; i++){scanf("%d",&W[i]);}for (int i = 1; i<=m; i++){scanf("%d%d",&E[i].x,&E[i].y);Next[i] = Head[E[i].x];Head[E[i].x] = i;} for (int i = 1; i<=n; i++){if (!dfn[i]){tarjan(i);}}for (int x,y,i = 1; i<=m; i++){x = sd[E[i].x]; y = sd[E[i].y];if (x!=y)//不是一個強連通分量 說明需要建邊{ne[++tot].x = x; ne[tot].y = y;nn[tot] = nh[x];nh[x] = tot;in[y]++;}}top = 0;for (int i = 1; i<=n; i++){if (sd[i] == i && !in[i])//找那些入度為零的強連通分量根節(jié)點{S[++top] = i;D[i] = W[i];}}while (top){int x = S[top--];for (int y,i = nh[x]; i; i = nn[i]){y = ne[i].y;D[y] = max(D[y],D[x]+W[y]);if (--in[y] == 0){S[++top] = y;}}}int ans = 0;for (int i = 1; i<=n; i++){ans = max(ans,D[i]);}cout<<ans<<endl;return 0; }

線性篩素數(shù)（真題）

#include<bits/stdc++.h> using namespace std; int n,m,x; bool shai(int a) {if(a==1) return 0;if(a==2 || a==3) return 1;if(a%6!=1 && a%6!=5) return 0;for(int i=5;i<=sqrt(a);i+=6){if(a%i==0 || a%(i+2)==0)return 0;}return 1; } int main() {cin>>n>>m;for(int i=1;i<=m;i++){cin>>x;if(shai(x))cout<<"Yes"<<endl;elsecout<<"No"<<endl;x=0;}return 0; }

最近公共祖先(真題)

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,s,tot=0,cnt=0; int head[1000100],nxt[1000100],to[1000100]; int d[500100],f[30][1000100]; int read() {int x=0,flag=0;char ch=getchar();if(ch=='-') flag=1;while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar();if(flag) return -x;return x; } void addedge(int x,int y) {cnt++;nxt[cnt]=head[x];head[x]=cnt;to[cnt]=y; } void dfs(int u,int dep) {d[u]=dep;for(int i=head[u];i!=-1;i=nxt[i]){int v=to[i];if(!d[v]) dfs(v,dep+1),f[0][v]=u;} } int LCA(int x,int y) {int l=0;while((1<<l)<=n) l++;l--;if(d[x]<d[y]) swap(x, y);for(int i=20;i>=0;i--)if(d[y]<=d[x]-(1<<i)) x=f[i][x];if(x==y) return x;for(int i=20;i>=0;i--){if(f[i][x]!=f[i][y]){x=f[i][x];y=f[i][y];}}return f[0][x]; } int main() {memset(head,-1,sizeof(head));n=read(),m=read(),s=read();for(int i=1;i<n;i++){int x,y;x=read(),y=read();addedge(x,y);addedge(y,x);}f[0][s]=s;dfs(s,1);for(int i=1;(1<<i)<=n;i++)for(int j=1;j<=n;j++)f[i][j]=f[i-1][f[i-1][j]];for(int i=1;i<=m;i++){int l,r;l=read(),r=read();printf("%d\n",LCA(l,r));}return 0; }

最長公共子序列（真題）

#include<bits/stdc++.h> using namespace std; int a[110000],t[110000],A[110000],B[110000],f[110000]; bool cmp(int a,int b) {return a<b; } int solve(int l,int r,int x) {int mid=(l+r)/2;;if (l==r) return l;if (a[mid]>x) return solve(l,mid,x);if (a[mid]<=x) return solve(mid+1,r,x); } int main() {int n;scanf("%d",&n);for (int i=1; i<=n; i++) scanf("%d",&A[i]);for (int i=1; i<=n; i++) scanf("%d",&B[i]);for (int i=1; i<=n; i++) f[A[i]]=i;for (int i=1; i<=n; i++) t[i]=f[B[i]];memset(a,0,sizeof(a));for (int i=1; i<=n; i++){if ((i==0)||(t[i]>a[a[0]])) a[++a[0]]=t[i];else if (t[i]<a[a[0]]) a[solve(1,a[0],t[i])]=t[i];}printf("%d\n",a[0]);return 0; }

最小生成樹（真題）

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int M=200100; struct node {int x;int y;int w; } a[M],t; int n,e,dad[M],p=1,ans;bool cmp(node x,node y) {if(x.w<y.w)return 1;if(x.w==y.w)if(x.x>y.x)return 1;return 0; }void qsort(int l,int r) {int i=l,j=r;node mid=a[(i+j)/2];while(i<=j){while(cmp(a[i],mid))i++;while(cmp(mid,a[j]))j--;if(i<=j){t=a[i];a[i]=a[j];a[j]=t;i++;j--;}}if(i<r)qsort(i,r);if(l<j)qsort(l,j); } int findx(int x) {if(x==dad[x])return x;dad[x]=findx(dad[x]);return dad[x]; } void solve() {qsort(1,e);for(int i=1; i<=n; i++)dad[i]=i;for(int i=1; i<=e; i++){if(findx(a[i].x)!=findx(a[i].y)){ans+=a[i].w;dad[findx(a[i].x)]=a[i].y;p++;if(p==n)return ;}} } int main() {cin>>n>>e;for(int i=1; i<=e; i++)cin>>a[i].x>>a[i].y>>a[i].w;solve();cout<<ans;return 0; }

快讀

long long read() {long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; }

嚴(yán)格次小生成樹（真題）

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath>using namespace std; const int N = 1e5 + 10;#define gc getchar()int n, m, now = 1; struct Node {int u, v, w, is_in;bool operator <(const Node a)const{return w < a.w;} } E[N * 3]; struct Node_2 {int u, v, w, nxt; } G[(N * 3) << 1]; int fa[N][30], Max[N][30], Tmax[N][30], deep[N], head[N], father[N]; int Mi[30];#define LL long long LL Answer; int Min = 1e9;inline int read() {int x = 0;char c = gc;while(c < '0' || c > '9') c = gc;while(c >= '0' || c >= '9') x = x * 10 + c - '0', c = gc;return x; }void Add(int u, int v, int w) {G[now].v = v;G[now].w = w;G[now].nxt = head[u];head[u] = now ++; } int Getfa(int x) {return father[x] == x ? x : father[x] = Getfa(father[x]); }void Mst() {int js(0);for(int i = 1; js != n - 1; i ++){int u = E[i].u, v = E[i].v, fu = Getfa(u), fv = Getfa(v);if(fu != fv){father[fu] = fv;js ++;E[i].is_in = 1;Answer += (LL)E[i].w;Add(E[i].u, E[i].v, E[i].w);Add(E[i].v, E[i].u, E[i].w);}} }void Dfs(int x, int f_, int dep) {deep[x] = dep;for(int i = 1; ; i ++){if(deep[x] - Mi[i] < 0) break;fa[x][i] = fa[fa[x][i - 1]][i - 1];Max[x][i] = max(Max[x][i - 1], Max[fa[x][i - 1]][i - 1]);if(Max[x][i - 1] == Max[fa[x][i - 1]][i - 1])Tmax[x][i] = max(Tmax[x][i - 1], Tmax[fa[x][i - 1]][i - 1]);elseTmax[x][i] = max(min(Max[x][i - 1], Max[fa[x][i - 1]][i - 1]),max(Tmax[x][i - 1], Tmax[fa[x][i - 1]][i - 1]));}for(int i = head[x]; ~ i; i = G[i].nxt){int v = G[i].v;if(v != f_){fa[v][0] = x;Max[v][0] = G[i].w;Tmax[v][0] = -1;Dfs(v, x, dep + 1);}} }int Lca(int x, int y) {if(deep[x] < deep[y]) swap(x, y);int k = deep[x] - deep[y];for(int i = 0; i <= 17; i ++)if(k >> i & 1) x = fa[x][i];if(x == y) return x;for(int i = 17; i >= 0; i --)if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];return fa[x][0]; }void Work(int s, int t, int w_) {int m1 = 0, m2 = 0, k = deep[s] - deep[t];for(int i = 0; i <= 17; i ++){if(k >> i & 1){m2 = max(m2, Tmax[s][i]);if(Max[s][i] > m1){m2 = max(m2, m1);m1 = Max[s][i];}}}if(m1 == w_) Min = min(Min, w_ - m2);else Min = min(Min, w_ - m1); }int main() {n = read();m = read();for(int i = 1; i <= n; i ++) head[i] = -1, father[i] = i;Mi[0] = 1;for(int i = 1; i <= 17; i ++) Mi[i] = Mi[i - 1] * 2;for(int i = 1; i <= m; i ++){E[i].u = read(), E[i].v = read(), E[i].w = read();}sort(E + 1, E + m + 1);Mst();Dfs(1, 0, 1);for(int i = 1; i <= m; i ++){if(!E[i].is_in){int u = E[i].u, v = E[i].v;int L = Lca(u, v);Work(u, L, E[i].w);Work(v, L, E[i].w);}}cout << Answer + Min;return 0; }

最大子段和（真題）

#include <stdlib.h> #include<stdio.h> int main() {int count;int a[100];int b[100];int i;int max;scanf("%d",&count);for(i=0; i<count; i++){scanf("%d",&a[i]);}b[0]=a[0];max=b[0];for(i=1; i<count; i++){if(b[i-1]>0)b[i]=b[i-1]+a[i];elseb[i]=a[i];if(b[i]>max)max=b[i];}printf("%d\n",max);return 0; }

快速冪||取余運算（真題）

#include<iostream> #include<algorithm> #include<cmath> using namespace std; long long b,p,k,s,t; int main() {cin>>b>>p>>k;cout<<b<<"^"<<p<<" mod "<<k<<"=";s=b%k;t=1;for (int i=2;i<=p;i++){s=s*b%k;if (s==b%k) break;t++;}p=p%t;s=1;if (p==0) p=t;for (int i=1;i<=p;i++)s=s*b%k;cout<<s;return 0; }

快速冪

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; int ksm(int a,int b,int p) {int ans=1;while(b){if(b&1) //這一位是不是1 ans=ans*a%p;a=a*a%p;b=b>>1; //送過來新的一位 }return ans; } int main() {int a,b,p;cin>>a>>b>>p;cout<<ksm(a,b,p);return 0; }

卡特蘭數(shù)

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; int a[1000010]; int main() {int n;cin>>n;a[0]=1;a[1]=1;for(int i=2;i<=n;i++){a[i]=a[i-1]*(4*i-2)/(i+1);}cout<<a[n];return 0; }

歐拉篩法

#include <cstring> using namespace std; int prime[1100000],primesize,phi[11000000]; bool is[11000000]; void getlist(int listsize) {memset(is,1,sizeof(is));is[1]=false;for(int i=2; i<=listsize; i++){if(is[i])prime[++primesize]=i;for(int j=1; j<=primesize&&i*prime[j]<=listsize; j++){is[i*prime[j]]=false;if(i%prime[j]==0)break;}} }

Dijkstra

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<queue> using namespace std; struct edge {int u,v,x; } ed[1000010]; struct node {int x,y;bool operator <(const node & a)const{return y>a.y;} }; priority_queue<node>que; int head[1000010]; int dis[1000010]; int n,m,s,cnt; void add(int x,int y,int z) {cnt++;ed[cnt].u=head[x];ed[cnt].v=y;ed[cnt].x=z;head[x]=cnt; } void dij() {for(int i=1; i<=n; i++)dis[i]=2147483647;dis[s]=0;que.push((node){s,0});while(!que.empty()){node temp=que.top();que.pop();int x=temp.x,y=temp.y;if(y!=dis[x])continue;for(int i=head[x]; i; i=ed[i].u){if(dis[ed[i].v]>dis[x]+ed[i].x){dis[ed[i].v]=dis[x]+ed[i].x;que.push((node){ed[i].v,dis[ed[i].v]});}}} } int main() {cin>>n>>m>>s;for(int i=1; i<=m; i++){int x,y,z;cin>>x>>y>>z;add(x,y,z);}dij();for(int i=1; i<=n; i++)cout<<dis[i]<<" ";return 0; }

單調(diào)隊列

#include <cstdio> #include <algorithm> using namespace std;const int N = 100000; int n, m, head = 1, tail = 0, ans = 2147483647; int a[N + 1], f[N + 1], que[N + 1];int main() {freopen("beacon.in", "r", stdin);freopen("beacon.out", "w", stdout);scanf("%d%d", &n, &m);for (int i = 1;i <= n;i++)scanf("%d", &a[i]);for (int i = 1;i <= n;i++){while (head <= tail && f[i - 1] <= f[que[tail]]) tail--; //當(dāng)F[i-1]比隊尾值更優(yōu)時把隊尾值彈出que[++tail] = i - 1; //把F[i-1]插入，這里插入下標(biāo)而不插入值，便于從隊頭彈出while (head <= tail && que[head] < i - m) head++; //不屬于區(qū)間維護內(nèi)的數(shù)彈出f[i] = f[que[head]] + a[i]; //狀態(tài)轉(zhuǎn)移}for (int i = n;i > n - m;i--) //求出答案ans = min(ans, f[i]);printf("%d\n", ans);fclose(stdin);fclose(stdout);return 0; }

EXGCD

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; int exgcd(int a,int b,int &x,int &y) {if(b==0){x=1,y=0;return a;}int an=exgcd(b,a%b,x,y),temp=x;x=y,y=temp-a/b*y;return an; } int main() {int a,b,x,y;cin>>a>>b;int ans=exgcd(a,b,x,y);while(x<0)x+=(b/ans);cout<<x;return 0; }

KMP字符串匹配

#include<iostream> #include<cstring> #define MAXN 1000010 using namespace std; int kmp[MAXN]; int la,lb,j; char a[MAXN],b[MAXN]; int main() {cin>>a+1;cin>>b+1;la=strlen(a+1);lb=strlen(b+1);for (int i=2;i<=lb;i++){ while(j&&b[i]!=b[j+1])j=kmp[j]; if(b[j+1]==b[i])j++; kmp[i]=j;}j=0;for(int i=1;i<=la;i++){while(j>0&&b[j+1]!=a[i])j=kmp[j];if (b[j+1]==a[i]) j++;if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];}}for (int i=1;i<=lb;i++)cout<<kmp[i]<<" ";return 0; }

字符串哈希

#include<bits/stdc++.h> using namespace std; typedef unsigned long long hh; hh chang=131; hh a[11000]; char s[11000]; int n,ans=1; hh hashn(char s[]) {int len=strlen(s);hh ans=0;for(int i=0;i<len;i++)ans=ans*chang+(hh)s[i];return ans & 0x7fffffff; } int main() {cin>>n;for(int i=1;i<=n;i++){cin>>s;a[i]=hashn(s);}sort(a+1,a+n+1);for(int i=2;i<=n;i++)if(a[i]!=a[i-1])ans++;cout<<ans<<endl;return 0; }

縮點（真題）

#include<bits/stdc++.h> using namespace std; const int N = 110000; int dfn[N],low[N],head[N],color[N],sta[N],value[N]; int f[N],rd[N],dis[N],z[N],x[N],y[N]; int k=0,n,m,top=0,tim=0,ans=0,ct; bool vis[N]; struct node {int to,next,from; }e[N]; void add(int u,int v) {e[++k].to=v;e[k].from=u;e[k].next=head[u];head[u]=k; } void tarjan(int s) {dfn[s]=low[s]=++tim;sta[++top]=s;vis[s]=true;for(int i=head[s],v=e[i].to;i;i=e[i].next,v=e[i].to){if(!dfn[v])tarjan(v),low[s]=min(low[s],low[v]);else if(vis[v])low[s]=min(low[s],dfn[v]);}if(low[s]==dfn[s]){++ct;vis[s]=false;while(sta[top+1]!=s){color[sta[top]]=ct;z[ct]+=value[sta[top]];vis[sta[top]]=false;top--;}} } int dfs(int x) {if(f[x])return f[x];f[x]=z[x];int maxx=0;for(int i=head[x];i;i=e[i].next){int to=e[i].to;if(!f[to])dfs(to);if(maxx>f[to])maxx=maxx;elsemaxx=f[to];}f[x]+=maxx;return f[x]; } int main() {cin>>n>>m;for(int i=1;i<=n;i++) cin>>value[i];for(int i=1;i<=m;i++){int u,v;cin>>u>>v;x[i]=u,y[i]=v;add(u,v);}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);memset(vis,false,sizeof(vis));memset(head,0,sizeof(head));memset(e,0,sizeof(e));k=0;for(int i=1;i<=m;i++){if(color[x[i]]!=color[y[i]]){add(color[x[i]],color[y[i]]);}}for(int i=1;i<=ct;++i)if(!f[i]){dfs(i);if(ans>f[i])ans=ans;else ans=f[i];}cout<<ans; }

主席樹 （真題）

#include<bits/stdc++.h> using namespace std; const int MAXN = 210000; int n, m, root[MAXN], cut, a[MAXN], s[MAXN], t, x, y, z; struct Edge {int lc, rc, ans; } tree[MAXN * 20]; void add(int &now, int last, int l, int r, int x) {now = ++cut;tree[now].ans = tree[last].ans + 1;tree[now].lc = tree[last].lc, tree[now].rc = tree[last].rc;if(l == r) return ;int mid = (l + r) >> 1;if(x <= mid) add(tree[now].lc, tree[last].lc, l, mid, x);else add(tree[now].rc, tree[last].rc, mid + 1, r, x);return ; } int query(int L, int R, int l, int r, int x) {if(l == r) return l;int p = tree[tree[R].lc].ans - tree[tree[L].lc].ans;int mid = (l + r) >> 1;if(p >= x) return query(tree[L].lc, tree[R].lc, l, mid, x);else return query(tree[L].rc, tree[R].rc, mid + 1, r, x - p); } int main() {cin >> n >> m;for(int i = 1; i <= n; i++) cin >> s[i], a[i] = s[i];sort(s + 1, s + n + 1);for(int i = 1; i <= n; i++){int p = lower_bound(s + 1, s + n + 1, a[i]) - s;add(root[i], root[i - 1], 1, n, p);}while(m--){cin >> x >> y >> z;int p = query(root[x - 1], root[y], 1, n, z);printf("%d\n", s[p]);}return 0; }

行來春色三分雨，睡去巫山一片云

轉(zhuǎn)載于:https://www.cnblogs.com/xmex/p/10154800.html

總結(jié)

以上是生活随笔為你收集整理的整理各种模板（准备随时弃坑）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。