树链剖分-不带修改的树上路径权值[A,B]的和询问-离线树状数组
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long LL; const int maxn=1e5+5; int n,m,start,end,cnt,k,index,opt; int fa[maxn],st[maxn],dep[maxn]; int top[maxn],son[maxn],size[maxn],id[maxn]; LL T[maxn],ans[maxn]; int a,b,x,y,z; struct node { int ed,nxt; }v[maxn*2]; struct Lv { int d,id; }w[maxn]; struct Quiry { int u,v,val,id,ty; }Q[maxn*2]; inline bool cmp(const Lv&A,const Lv&B) { return A.d<B.d; } inline bool cmp2(const Quiry&A,const Quiry&B) { return A.val<B.val; } inline void add(int x,int y) { v[cnt]=(node){y,st[x]}; st[x]=cnt++; } inline void dfs(int u,int f) { fa[u]=f; son[u]=0;size[u]=1;dep[u]=dep[f]+1; int ma=0; for(int x=st[u];~x;x=v[x].nxt) { int y=v[x].ed; if(y!=f) { dfs(y,u); size[u]+=size[y]; if(size[y]>ma)son[u]=y; } } } inline void DFS(int u,int tp) { top[u]=tp; id[u]=++index; if(son[u])DFS(son[u],tp); for(int x=st[u];~x;x=v[x].nxt) { int y=v[x].ed; if(y!=fa[u]&&y!=son[u])DFS(y,y); } } inline void update(int x,LL val) { for(;x<=n;x+=x&-x)T[x]+=val; } inline LL get(int x) { LL res=0; for(;x;x-=x&-x)res+=T[x]; return res; } inline LL quiry(int u,int v) { int x=top[u],y=top[v]; LL ans=0; while(x!=y) { if(dep[x]<dep[y])swap(x,y),swap(u,v); ans+=get(id[u])-get(id[x]-1); u=fa[x]; x=top[u]; } if(u==v)return ans+get(id[u])-get(id[u]-1); if(dep[u]<dep[v])swap(u,v); ans+=get(id[u])-get(id[v]-1); return ans; } int main() { while(~scanf("%d%d",&n,&m)) { memset(st,-1,sizeof(st)); cnt=0; for(int i=1;i<=n;++i) { scanf("%d",&w[i].d); w[i].id=i; } sort(w+1,w+1+n,cmp); for(int i=1;i<n;++i) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1,0); index=0; DFS(1,1); cnt=0; for(int i=1;i<=m;++i) { scanf("%d%d%d%d",&x,&y,&a,&b); Q[++cnt]=(Quiry){x,y,a-1,i,-1}; Q[++cnt]=(Quiry){x,y,b,i,1}; } sort(Q+1,Q+1+cnt,cmp2); memset(T,0,sizeof(T)); memset(ans,0,sizeof(ans)); int L=1; for(int i=1;i<=cnt;++i) { while(L<=n&&w[L].d<=Q[i].val) { update(id[w[L].id],w[L].d); L++; } ans[Q[i].id]+=(LL)Q[i].ty*quiry(Q[i].u,Q[i].v); } for(int i=1;i<m;++i)printf("%lld ",ans[i]); printf("%lld\n",ans[m]); } return 0; } 倍增LCA-树上权值和 #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N =100010; struct Edge { int x,w; Edge(int x,int w):x(x),w(w){} }; vector<Edge> g[N]; vector<int> vec[N]; int fa[N][20],dep[N],h[N]; int n,Q; void dfs(int x,int p) { h[x]=h[p]+1; fa[x][0]=p; for(int i=1;i<20;++i) fa[x][i]=fa[fa[x][i-1]][i-1]; int y; for(int i=0;i<g[x].size();++i) { y=g[x][i].x; if(y==p) continue; dep[y]=dep[x]+g[x][i].w; dfs(y,x); } } int lca(int x,int y) { if(h[x]<h[y]) swap(x,y); int d=h[x]-h[y]; for(int i=0;i<20;++i) if((d>>i)&1) x=fa[x][i]; if(x==y) return x; for(int i=19;i>=0;--i) if(fa[x][i]!=fa[y][i]) { x=fa[x][i];y=fa[y][i]; } return fa[x][0]; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&Q); for(int i=1;i<=n;++i) g[i].clear(); int x,y,w; for(int i=1;i<n;++i) { scanf("%d%d%d",&x,&y,&w); g[x].push_back(Edge(y,w)); g[y].push_back(Edge(x,w)); } dfs(1,0); int u,v,ans; while(Q--) { scanf("%d%d",&u,&v); ans=dep[u]+dep[v]-2*dep[lca(u,v)]; printf("%d\n",ans); } } return 0; } 高斯消元 #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cstring> using namespace std; const double eps=1e-8; const int MAXN=1e3; typedef double Matrix[MAXN][MAXN]; Matrix a;//m行n+1列，从0开始 //增广矩阵，即a[i][n]是方程右边的常数 //结束后a[i][n]是第i个未知数的值 int dcmp(double x)//浮点数比较 { if(fabs(x)<eps) return 0; return x<0?-1:1; } void Gauss(Matrix &a,int m,int n) { //变成行阶梯形矩阵 for(int i=0;i<m;++i) { //列选主元 int r=i; for(int j=i+1;j<m;++j) { if(fabs(a[j][i])>fabs(a[r][i])) r=j; } if(r!=i) for(int j=0;j<=n;++j) swap(a[r][j],a[i][j]); //与第i+1~m-1行进行消元 for(int k=i+1;k<m;++k) { double f=a[k][i]/a[i][i]; for(int j=i;j<=n;++j) a[k][j]-=f*a[i][j]; } } } //n元线性方程组 int solve(Matrix &a,int m,int n) { Gauss(a,m,n); int r1=0;//系数矩阵的秩 int r2=0;//增广矩阵的秩 for(int i=0;i<m;++i) { bool zero=true; for(int j=0;j<=n;j++) { if(dcmp(a[i][j])) { if(j<n) r1++; r2++; zero=false; break; } } if(zero||r1<r2) break; } if(r1<r2) return -1;//无解 else if(r1==r2&&r1<n) return 0;//有无穷多解 else { //回代 for(int i=n-1;i>=0;--i) { for(int j=i+1;j<n;++j) { a[i][n]-=a[j][n]*a[i][j]; } a[i][n]/=a[i][i]; } return 1;//有唯一解 } } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<m;++i) { for(int j=0;j<=n;++j) { scanf("%lf",&a[i][j]); } } int ans=solve(a,m,n); if(ans<0) printf("No solutions\n"); else if(ans==0) printf("Many solutions\n"); else { for(int i=0;i<n;++i) { printf("%d\n",(int)(a[i][n]+0.5)); } } } return 0; } RMQ const int maxn=1e5+5; int a[maxn],T[4*maxn],n,res[maxn],L,R,leaf[maxn]; //Segment Tree inline void update(int k) { T[k]=T[k<<1]+T[k<<1|1]; } inline void build(int l,int r,int k) { if(l==r) { T[k]=a[l]; leaf[l]=k; return; } int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); update(k); } inline int ask(int l,int r,int k) { if(L<=l&&r<=R)return T[k]; int mid=(l+r)>>1; int res=0; if(L<=mid)res+=ask(l,mid,k<<1); if(R>mid)res+=ask(mid+1,r,k<<1|1); return res; } inline void modify(int x) { int k=leaf[x]; T[k]=a[x]; k>>=1; for(;k;k>>=1)update(k); } //ST table void rmq_init() { for(int i=1; i<=n; i++) f[i][0] = a[i]; int k=floor(log((double)n)/log(2.0)); for(int j=1; j<=k; j++) for(int i=n; i>=1; i--) { if(i+(1<<(j-1))<=n) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } int rmq(int i,int j) { int k = floor(log((double)(j-i+1))/log(2.0)); return max(f[i][k],f[j-(1<<k)+1][k]); } 匈牙利算法-矩阵 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100+5; int G[maxn][maxn],a[maxn*maxn],b[maxn*maxn],obj[maxn]; bool used[maxn]; int n,m,k,kase; inline bool DFS(int u) { for(int i=1;i<=m;++i) if(G[u][i]&&used[i]==0) { used[i]=1; if(obj[i]==0||DFS(obj[i])) { obj[i]=u; return 1; } } return 0; } inline int Hungarian() { int res=0; memset(obj,0,sizeof(obj)); for(int i=1;i<=n;++i) { memset(used,0,sizeof(used)); if(DFS(i))res++; } return res; } int main() { while(~scanf("%d%d%d",&n,&m,&k)) { memset(G,0,sizeof(G)); for(int i=1;i<=k;++i) { scanf("%d%d",a+i,b+i); G[a[i]][b[i]]=1; } int MAX=Hungarian(),ans=0; for(int i=1;i<=k;++i) { G[a[i]][b[i]]=0; int res=Hungarian(); G[a[i]][b[i]]=1; if(res<MAX)ans++; } printf("Board %d have %d important blanks for %d chessmen.\n",++kase,ans,MAX); } return 0; } 匈牙利算法-邻接表 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100+5,maxm=maxn*maxn; int st[maxn],obj[maxn]; bool used[maxn]; int n,m,k,x,y,z,cnt; struct node { int ed,nxt; }v[maxm]; inline void add(int x,int y) { ++cnt; v[cnt]=(node){y,st[x]}; st[x]=cnt; } inline bool DFS(int u) { for(int x=st[u];x;x=v[x].nxt) { int y=v[x].ed; if(used[y]==0) { used[y]=1; if(obj[y]==-1||DFS(obj[y])) { obj[y]=u; return 1; } } } return 0; } inline int Hungarian() { int res=0; memset(obj,-1,sizeof(obj)); for(int i=1;i<n;++i) { memset(used,0,sizeof(used)); if(DFS(i))res++; } return res; } int main() { while(~scanf("%d%d%d",&n,&m,&k)&&n) { memset(st,0,sizeof(st)); cnt=0; for(int i=1;i<=k;++i) { scanf("%d%d%d",&z,&x,&y); if(x==0||y==0)continue; add(x,y); } int MAX=Hungarian(); printf("%d\n",MAX); } return 0; } 带权二分图最大匹配KM #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<queue> using namespace std; typedef long long LL; const int maxn=200+5,maxm=maxn*maxn,INF=1<<28; typedef pair<int,int> pai; char s[maxn]; int n,m,cnt,pos,ed; int lx[maxn],ly[maxn],slack[maxn],w[maxn],obj[maxn]; bool visx[maxn],visy[maxn]; vector<pai>M,H; int st[maxn]; struct node { int v,nxt,w; }v[maxm]; inline void add(int x,int y,int c,int z) { v[cnt]=(node){y,st[x],z}; st[x]=cnt++; } inline bool DFS(int u) { visx[u]=1; for(int x=st[u];~x;x=v[x].nxt) { int y=v[x].v; if(visy[y])continue; if(lx[u]+ly[y]==v[x].w) { visy[y]=1; if(obj[y]==-1||DFS(obj[y])) { obj[y]=u; w[y]=v[x].w; return 1; } }else slack[y]=min(slack[y],lx[u]+ly[y]-v[x].w); } return 0; } inline void KM() { for(int i=1;i<=M.size();++i)lx[i]=-INF,ly[i]=0; for(int i=1;i<=M.size();++i) for(int x=st[i];~x;x=v[x].nxt) lx[i]=max(lx[i],v[x].w);//min for(int i=1;i<=M.size();++i) { for(int j=1;j<=H.size();++j)slack[j]=INF; while(1) { memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(DFS(i))break; int d=INF; for(int j=1;j<=H.size();++j) if(!visy[j])d=min(d,slack[j]); for(int j=1;j<=H.size();++j) { if(visx[j])lx[j]-=d; if(visy[j])ly[j]+=d; else slack[j]-=d; } } } } int main() { while(~scanf("%d%d",&n,&m)) { if(!n&&!m)break; memset(st,-1,sizeof(st)); memset(obj,-1,sizeof(obj)); memset(w,0,sizeof(w)); cnt=0; H.clear();M.clear(); for(int i=0;i<n;++i) { scanf("%s",s); for(int j=0;j<m;++j) if(s[j]=='H')H.push_back(pai(i,j)); else if(s[j]=='m')M.push_back(pai(i,j)); } for(int i=0;i<M.size();++i) { pos=i+1; for(int j=0;j<H.size();++j) { int ed=j+1; int cost=abs(M[i].first-H[j].first)+abs(M[i].second-H[j].second); add(pos,ed,1,-cost); } } KM(); int ans=0; for(int i=1;i<=H.size();++i)ans-=w[i]; printf("%d\n",ans); } return 0; } 最大流 #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> using namespace std; typedef long long LL; const int maxn=500+5,maxm=maxn*maxn,INF=1<<30; int n,src,des,x,y,z,m; int st[maxn],stp[maxn],cnt; struct node { int v,w,nxt; }v[maxm]; inline void add(int x,int y,int z) { v[cnt]=(node){y,z,st[x]}; st[x]=cnt++; } queue<int>Q; inline bool bfs() { memset(stp,-1,sizeof(stp)); while(!Q.empty())Q.pop(); stp[src]=0; Q.push(src); while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int x=st[u];~x;x=v[x].nxt) { int y=v[x].v; if(v[x].w>0&&stp[y]==-1) { stp[y]=stp[u]+1; Q.push(y); } } } return stp[des]!=-1; } inline int dfs(int u,int f) { if(u==des)return f; int res; for(int x=st[u];~x;x=v[x].nxt) { int y=v[x].v; if(v[x].w>0&&stp[y]==stp[u]+1) { res=dfs(y,min(f,v[x].w)); if(res>0) { v[x].w-=res; v[x^1].w+=res; return res; } } } stp[u]=-1; return 0; } inline int Dinic() { int ans=0,res; while(bfs()) { while(res=dfs(src,INF)) { ans+=res; } } return ans; } int main() { while(~scanf("%d%d",&n,&m)) { cnt=0; memset(st,-1,sizeof(st)); src=1;des=m; for(int i=1;i<=n;++i) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,-z); } int res=Dinic(); printf("%d\n",res); } return 0; } 最小费用最大流MCMF #include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f typedef long long LL; const int M=2010; const int N=510; struct edge { int to; int next; int cap; int cost; } e[11000]; int head[N],tot; int d[N], pre[N], path[N]; bool vis[N]; void init() { memset(head,-1,sizeof(head)); tot = 0; } void addedge(int s, int t, int cap, int cost) { e[tot].to=t; e[tot].cap=cap; e[tot].cost=cost; e[tot].next=head[s]; head[s] = tot++; e[tot].to=s; e[tot].cap=0; e[tot].cost=-cost; e[tot].next=head[t]; head[t] = tot++; } int spfa(int s, int t) { memset(d,-INF,sizeof(d)); memset(pre,-1,sizeof(pre)); memset(path,-1,sizeof(path)); memset(vis,false,sizeof(vis)); int res = d[0]; d[s] = 0; vis[s] = true; queue<int>q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if (d[v] < d[u] + e[i].cost && e[i].cap > 0) { d[v] = d[u] + e[i].cost; pre[v] = u; path[v] = i; if (!vis[v]) { vis[v] = true; q.push(v); } } } } return d[t] != res; } int MinCostMaxFlow(int s, int t,int &cost) { int flow; flow=cost=0; while (spfa(s, t)) { int minn = INF; for (int i = t; i != s && ~i; i = pre[i]) minn = min(minn, e[path[i]].cap); for (int i = t; i != s && ~i; i = pre[i]) { e[path[i]].cap -= minn; e[path[i] ^ 1].cap += minn; } if (d[t] < 0) break; flow += minn; cost += minn * d[t]; } return flow; } int main(void) { int n,m; while (cin>>n>>m) { init(); int s=0,t=n+1,cost; for (int i=1; i<=n; i++) { int a,b,c,d; cin>>a>>b>>c>>d; addedge(s,i,b,-a); addedge(i,t,d,c); } while (m--) { int u,v,k; cin>>u>>v>>k; addedge(u,v,INF,-k); addedge(v,u,INF,-k); } MinCostMaxFlow(s,t,cost); cout<<cost<<endl; } return 0; } //http://blog.csdn.net/qq_28954601/article/details/77149389 Dj+Heap struct Heap { int dis,u; bool operator <(const Heap&B) const { return dis>B.dis; } }; priority_queue<Heap> Q; inline void Dj(int s) { memset(inq,0,sizeof(inq)); memset(dis,127,sizeof(dis)); while(!Q.empty())Q.pop(); dis[s]=0; Q.push((Heap){0,s}); while(!Q.empty()) { Heap New=Q.top(); Q.pop(); if(inq[New.u])continue; int k=New.u; inq[k]=1; for(int x=st[k];x;x=a[x].next) { int y=a[x].ed; if(!vis[y]&&dis[y]>dis[k]+a[x].w) { dis[y]=dis[k]+a[x].w; Q.push((Heap){dis[y],y}); } } } } Dj次短路 #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; typedef long long LL; const int MAXN=1e5+5; const LL INF=1ll<<60; struct edge { int to; LL cost; edge(LL tv = 0, LL tc = 0):to(tv), cost(tc){} }; typedef pair<LL ,LL> P; int N, M, A, B, D; vector<edge> graph[MAXN]; priority_queue<P, vector<P>, greater<P> > Q; LL dist[MAXN]; LL dist2[MAXN]; void solve(){ //fill(dist, dist+N, INF); //fill(dist2, dist2+N, INF); for(int i = 1; i <= N;++i)dist[i]=dist2[i]=INF; while(!Q.empty())Q.pop(); dist[1] = 0; Q.push(P(0, 1)); while(!Q.empty()) { P p = Q.top(); Q.pop(); LL v = p.second, d = p.first; if(dist2[v] < d) continue; for(LL i = 0; i < graph[v].size(); i++) { edge e = graph[v][i]; LL d2 = d + e.cost; if(dist[e.to] > d2) { swap(dist[e.to], d2); Q.push(P(dist[e.to], e.to)); } if(dist2[e.to] > d2 && dist[v] < d2) { dist2[e.to] = d2; Q.push(P(dist2[e.to], e.to)); } } } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d", &N, &M); int MIN=1<<30; for(LL i = 1; i <= N;++i)graph[i].clear(); for(LL i = 0; i < M; i++) { scanf("%d%d%d", &A, &B, &D); graph[A].push_back(edge(B, D)); graph[B].push_back(edge(A, D)); if(A==N||B==N)MIN=min(D,MIN); } solve(); LL ans=min(dist[N]+(LL)MIN*2,dist2[N]); printf("%lld\n",ans); } return 0; } SPFA inline void SPFA(int s) { memset(dis,127,sizeof(dis)); memset(inq,0,sizeof(inq)); int l=0,r=0; q[++r]=s; inq[s]=1; dis[s]=0; while(l<r) { int k=q[++l]; inq[k]=0; for(int x=st[k];x;x=a[x].next) { int y=a[x].ed; if(dis[y]>dis[k]+a[x].val) { dis[y]=dis[k]+a[x].val; if(!inq[y]) { inq[y]=1; q[++r]=y; } } } } } 哈夫曼编码 #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int maxn=1e6+5; //typedef pair<int,int> pai; typedef long long LL; struct pai { LL cnt,len; bool operator <(const pai &B)const { return (cnt>B.cnt)||(cnt==B.cnt&&len>B.len); } }; LL n,k,sum,ans,w[maxn]; priority_queue<pai>Q; int main() { while(~scanf("%lld%lld",&n,&k)) { while(!Q.empty())Q.pop(); for(int i=1;i<=n;++i)scanf("%lld",w+i); while(k!=2&&n%(k-1)!=1)w[++n]=0; for(int i=1;i<=n;++i)Q.push((pai){w[i],0}); ans=0; while(Q.size()!=1) { LL sum=0,L=0; pai now={0,0}; for(int i=1;i<=k;++i) { now=Q.top(); Q.pop(); sum+=now.cnt; L=max(now.len,L); } now.cnt=sum; now.len=L+1; Q.push(now); ans+=sum; } pai now=Q.top(); printf("%lld\n%lld\n",ans,now.len); } return 0; } Lucas定理 const int MAXN = 1010; const int mod = 1e9 + 7; LL inv[MAXN + 10], fac[MAXN + 10]; void init() { inv[0] = fac[0] = inv[1] = fac[1] = 1; for(int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % mod; for(int i = 2; i < MAXN; i++) inv[i] = (mod - (mod / i)) * inv[mod % i] % mod;//lucas定理求逆元 for(int i = 1; i < MAXN; i++) inv[i] = inv[i - 1] * inv[i] % mod; } inline LL C(int n, int m)//求组合数 C n,m { if(n<m)return 0; return (fac[n] * inv[m] % mod) * inv[n - m] %mod; } 欧拉线性筛->莫比乌斯函数+欧拉函数 int n,m,T,kase,mobius[maxn],cnt[maxn],L,R; LL ans; bool vis[maxn]; int prime[maxn],phi[maxn]; inline void get_mobius() { int L=0; mobius[1]=1; phi[1]=1; for(int i=2;i<maxn;++i) { if(!vis[i])mobius[i]=-1,prime[++L]=i,phi[i]=i-1; for(int j=1;i*prime[j]<maxn&&j<=L;++j) { mobius[i*prime[j]]-=mobius[i]; phi[i*prime[j]]=phi[i]*phi[prime[j]]; vis[i*prime[j]]=1; if(i%prime[j]==0) { mobius[i*prime[j]]=0; phi[i*prime[j]]=phi[i]*prime[j]; break; } } } } 莫比乌斯反演+区间差分线段覆盖 #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int maxn=1e6,mod=1e9+7; int n,m; LL F[maxn+5],f[maxn+5]; bool vis[maxn+5]; int prime[maxn+5],mobius[maxn+5]; inline void get() { int L=0; mobius[1]=1; for(int i=2;i<=maxn;++i) { if(!vis[i])prime[++L]=i,mobius[i]=-1; for(int j=1;i*prime[j]<=maxn&&j<=L;++j) { vis[i*prime[j]]=1; mobius[i*prime[j]]-=mobius[i]; if(i%prime[j]==0) { mobius[i*prime[j]]=0; break; } } } } int main() { get(); for(int i=1;i<=maxn;++i) { F[i]++; for(int j=i+1;j<=maxn;j+=i) F[j]++; } for(int i=1;i<=maxn;++i)F[i]=(F[i-1]+F[i])%mod; for(int i=1;i<=maxn;++i) if(mobius[i]) { for(int j=i;j<=maxn;j+=i)f[j]=(f[j]+mobius[i]*F[j/i])%mod; } for(int i=1;i<=maxn;++i)f[i]=(f[i]+f[i-1])%mod; while(~scanf("%d",&n)) { printf("%lld\n",(f[n]+mod)%mod); } return 0; } 扩展欧几里得算法EXGCD /* 本程序仅用于求整数解，即当C满足模gcd(a,b)为0时可应用*/ #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> using namespace std; int a,b,c,x,y,t,x0,y0; inline int exgcd(int a,int b) { if (b==0) { x=1; y=0; return a; } // ax+by=gcd(a,b)->b=0,ax=gcd(a,0)=a->x=1,y=0 int T=exgcd(b,a%b),t=x; x=y; y=t-(a/b)*x; return T; /* 因为gcd(a,b)=gcd(b,a%b) 根据定理:ax+by=gcd(a,b) ax+by=bx1+(a%b)y1 -> ax+by=bx1+(a-(a/b)*b)y1[c++中 /相当于div ] ax+by=ay1+b(x1-(a/b)*y1) 所以x=y1,y=x1-(a/b)*y1 */ } int main() { freopen("exgcd.in","r",stdin); freopen("exgcd.out","w",stdout); scanf("%d%d%d",&a,&b,&c); t=exgcd(a,b); x0=x*(c/t); y0=y*(c/t); //对于c不是gcd(a,b)的情况。 printf("%d %d",x0,y0); return 0; } /* 本程序求出的是一个基础解,由基础解可求出其他整数解: 对于ax+by=gcd(a,b): X=x+b/gcd(a,b)*t,Y=y-a/gcd(a,b)*t, 对于ax+by=c： X=x0+b/gcd(a,b)*t,Y=y0-a/gcd(a,b)*t, 其中t为任意整数 */ Prim&Kruskal #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=500+5,INF=1<<28; int v[maxn][maxn],n,m,ans,dis[maxn]; bool inque[maxn]; inline void prim() { memset(inque,0,sizeof(inque)); for(int i=1;i<=n;++i)dis[i]=v[1][i]; inque[1]=1; ans=0; for(int i=2;i<=n;++i) { int mini=INF,k=-1; for(int j=1;j<=n;++j) if(!inque[j]&&dis[j]<mini) { mini=dis[j]; k=j; } ans=max(ans,mini); inque[k]=1; for(int j=1;j<=n;++j) if(!inque[j]&&dis[j]>v[k][j])dis[j]=v[k][j]; } } //const int maxn=3000+5,maxm=100000+5; struct nod { int u,v,w; }a[maxn]; int fa[maxn]; inline bool cmp(const nod&A,const nod&B) { return A.w<B.w; } inline int get(int u) { if(fa[u]==u)return u; return fa[u]=get(fa[u]); } inline void kruskal() { for(int i=1;i<=m;++i)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); for(int i=1;i<=n;++i)fa[i]=i; int size=n; sort(a+1,a+1+m,cmp); for(int i=1;i<=m;++i) { int fx=get(a[i].u),fy=get(a[i].v); if(fx!=fy) { fa[fx]=fy; size--; } } } int main() { return 0; } 数位DP typedef long long ll; int a[20]; ll dp[20][state];//不同题目状态不同 ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零 { //递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了 if(pos==-1) return 1;/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */ //第二个就是记忆化(在此前可能不同题目还能有一些剪枝) if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state]; /*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/ int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了 ll ans=0; //开始计数 for(int i=0;i<=up;i++)//枚举，然后把不同情况的个数加到ans就可以了 { if() ...s else if()... ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的 /*这里还算比较灵活，不过做几个题就觉得这里也是套路了 大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论 去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目 要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类， 前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/ } //计算完，记录状态 if(!limit && !lead) dp[pos][state]=ans; /*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/ return ans; } ll solve(ll x) { int pos=0; while(x)//把数位都分解出来 { a[pos++]=x;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来，反正注意数位边界就行 x/=10; } return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛 } int main() { ll le,ri; while(~scanf("%lld%lld",&le,&ri)) { //初始化dp数组为-1,这里还有更加优美的优化,后面讲 printf("%lld\n",solve(ri)-solve(le-1)); } } //http://blog.csdn.net/wust_zzwh/article/details/52100392 矩阵快速幂 #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long LL; const int N=4; LL n , MOD; struct Matrix { LL mat[N][N]; void init() { memset(mat,0,sizeof(mat)); mat[0][0]=mat[0][2]=mat[0][3]=1; mat[1][0]=mat[2][1]=mat[3][2]=1; } void clear() { memset(mat,0,sizeof(mat)); for(int i = 0 ; i < N ; i++)mat[i][i]=1; } Matrix operator*(const Matrix& m)const { Matrix tmp; for(int i = 0 ; i < N ; i++) { for(int j = 0 ; j < N ; j++) { tmp.mat[i][j] = 0; for(int k = 0 ; k < N ; k++) { tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD; tmp.mat[i][j] %= MOD; } } } return tmp; } }a; LL Pow(Matrix &a,LL b) { if(b <= 3)return (2*n)%MOD; if(b == 4)return 9%MOD; b -= 4; Matrix ans; ans.clear(); while(b){ if(b&1)ans=ans*a; b>>=1; a=a*a; } LL sum = 0; sum += ans.mat[0][0]*9%MOD; sum += ans.mat[0][1]*6%MOD; sum += ans.mat[0][2]*4%MOD; sum += ans.mat[0][3]*2%MOD; return sum%MOD; } int main() { while(~scanf("%lld%lld",&n,&MOD)) { a.init(); printf("%lld\n",Pow(a,n)); } return 0; } 不相交线段转换+连续代价小于x的最大覆盖数 #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxn=1000010; int n,m; struct node { int a,b; }x[maxn]; int l[maxn],r[maxn]; inline bool cmp(node x1, node x2){return x1.a<x2.a||(x1.a==x2.a&&x1.b < x2.b);} int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1; i<=n; i++)scanf("%d%d",&x[i].a,&x[i].b); sort(x+1, x+n+1, cmp); int cnt=1; l[1]=x[1].a;r[1]=x[1].b; for(int i=2; i<=n; i++) { if(x[i].a<=r[cnt])r[cnt]=max(r[cnt],x[i].b); else ++cnt,l[cnt]=x[i].a,r[cnt]=x[i].b; } int ans=r[1]-l[1]+1+m,L=1,res=0; for(int i=2;i<=cnt;++i) { res+=l[i]-r[i-1]-1; while(res>m) { res-=l[L+1]-r[L]-1; L++; } ans=max(ans,r[i]-l[L]+1+m-res); } printf("%d\n",ans); } return 0; } 归并排序求逆序对 LL ans; int a[maxn],n,b[maxn]; inline void merge(int l,int r) { if(l>=r)return; int mid=(l+r)>>1; merge(l,mid); merge(mid+1,r); int L=l,R=mid+1; int cnt=l; while(L<=mid||R<=r) { if(L>mid||(a[R]<a[L]&&R<=r)) { b[cnt++]=a[R++]; ans+=mid-L+1; } else b[cnt++]=a[L++]; } for(int i=l;i<=r;++i)a[i]=b[i]; } Splay-数组实现 #include<cstdio> #define N 2000100 using namespace std; struct node { int l,r,d,size,fa; void reset() { l=r=d=size=fa=0; } }T[N]; int cnt,i,j,m,n,k,root=1,now; inline void updata(int u)//update { T[u].size=T[T[u].l].size+T[T[u].r].size+1; } inline void zag(int s)//left_rotate { int x=T[s].fa,y=T[x].fa,z=T[s].l; if(T[y].l==x)T[y].l=s;else T[y].r=s; T[s].fa=y; T[x].r=z;T[z].fa=x; T[s].l=x;T[x].fa=s; updata(x); updata(s); } inline void zig(int s)//right_rotate { int x=T[s].fa,y=T[x].fa,z=T[s].r; if(T[y].l==x)T[y].l=s;else T[y].r=s; T[s].fa=y; T[x].l=z;T[z].fa=x; T[s].r=x;T[x].fa=s; updata(x); updata(s); } inline void splay(int s) { while(T[s].fa) { int x=T[s].fa,y=T[x].fa; if(y) { if(T[y].l==x) { if(T[x].l==s)zig(x),zig(s); else zag(s),zig(s); } else { if(T[x].l==s)zig(s),zag(s); else zag(x),zag(s); } } else if(T[x].l==s)zig(s);else zag(s); } root=s; } inline int findkth(int x)//寻找第k大返回指针 { int s=root; while(1) { if(x==T[T[s].l].size+1)return s; if(x<=T[T[s].l].size)s=T[s].l; else x=x-T[T[s].l].size-1,s=T[s].r; } } inline int getkth(int x)//寻找x是第k大返回k { int s=root; int sum=0; while(1&&s) { if(x==T[s].d)return sum+T[T[s].l].size+1; else if(x<T[s].d)s=T[s].l; else sum+=T[T[s].l].size+1,s=T[s].r; } return sum; } inline void insert(int x)//插入x { int s=root; if(!cnt){T[++cnt].reset();T[cnt].d=x;T[cnt].size=1;return;} while(1) { if(!T[s].d){T[s].d=x;T[s].size=1;return;} if(x<T[s].d) { if(!T[s].l){T[s].l=++cnt;T[cnt].fa=s;} T[s].size++; s=T[s].l; } else { if(!T[s].r){T[s].r=++cnt;T[cnt].fa=s;} T[s].size++; s=T[s].r; } } } inline void del(int x) { int y=findkth(x); splay(y); if(T[y].l==0&&T[y].r==0) { cnt=0;return; } if(T[y].l==0) { T[T[y].r].fa=0; root=T[y].r; return; } if(T[y].r==0) { T[T[y].l].fa=0; root=T[y].l; return; } int d=getkth(x); int z=findkth(d-1); T[z].r=T[y].r; T[T[y].r].fa=z; root=T[y].l; T[root].fa=0; splay(z); } int main() { scanf("%d",&n); cnt=0; for(i=1;i<=n;++i) { scanf("%d",&now); insert(now); //if(i&1)printf("%d\n",find((i>>1)+1,root)); //if(!(i%7))splay(root); } return 0; } Splay序列修改-指针 #include <cstdio> #include <cstring> using namespace std; struct node { char val; int size; node *lch, *rch, *pa; node(int s = 0, node *p = 0, char v = 0, node *l = 0, node *r = 0) : size(s), pa(p), val(v), lch(l), rch(r) { } }*top; struct pair { node *first, *second; pair(node *fir = 0, node *sec = 0) { first = fir, second = sec; } }; char s[100005]; int size(node *p) { if (!p) return 0; return p->size; } node *Build(char *s, int len, node *p = 0) { if (len == 0) return 0; if (len == 1) return new node(1, p, *s); node *res = new node; int mid = len >> 1; res->pa = p; res->val = s[mid]; res->lch = Build(s, mid, res); res->rch = Build(s + mid + 1, len - mid - 1, res); res->size = size(res->lch) + size(res->rch) + 1; return res; } void update(node *x) { if (x) x->size = size(x->lch) + size(x->rch) + 1; } node *rotate(node *x) { node *y = x ->pa; x->pa = y->pa, y->pa = x; if (x->pa) (x->pa->lch == y) ? x->pa->lch = x : x->pa->rch = x; if (y->lch == x) { y->lch = x->rch, x->rch = y; if (y->lch) y->lch->pa = y; }else { y->rch = x->lch, x->lch = y; if (y->rch) y->rch->pa = y; } update(y), update(x); return x; } node *splay(node *x) { node *y, *z; while (x->pa) { y = x->pa; if (!y->pa) rotate(x); else { z = y->pa; if (z->lch == y && y -> lch == x || z->rch == y && y->rch == x) rotate(x), rotate(x); else rotate(y), rotate(x); } } return x; } node *Find(node *t, int id) { int s; while (true) { s = size(t->lch); if (s >= id) t = t->lch; else if (s + 1 == id) break; else t = t->rch, id -= s + 1; } return t; } node *Merge(node *x, node *y) { if (!x) return y; x = Find(x, size(x)); splay(x); x->rch = y; if (y) y->pa = x; update(x); return x; } pair Split(node *x, int idx) { if (!idx) return pair(0, x); if (!(size(x) - idx)) return pair(x, 0); x = Find(x, idx), splay(x); node *y = x->rch; y->pa = x->rch = 0; update(x); return pair(x, y); } void Put_Front() { int X, Y; scanf("%d%d", &X, &Y), X ++, Y ++; pair a = Split(top, X - 1); pair b = Split(a.second, Y - X + 1); top = Merge(b.first, Merge(a.first, b.second)); } void Put_Back() { int X, Y; scanf("%d%d", &X, &Y), X ++, Y ++; pair a = Split(top, X - 1); pair b = Split(a.second, Y - X + 1); top = Merge(Merge(a.first, b.second), b.first); } char Query() { int idx; scanf("%d", &idx), idx ++; node *x = Find(top, idx); top = splay(x); return top->val; } int Q, opt; int main() { freopen("std.in", "r", stdin); freopen("Code.out", "w", stdout); scanf("%s", s); top = Build(s, strlen(s)); scanf("%d", &Q); while (Q --) { scanf("%d", &opt); if (opt == 1) Put_Front(); if (opt == 2) Put_Back(); if (opt == 3) printf("%c\n", Query()); } return 0; } 可持久化Treap-指针 /* Treap[Merge,Split] by Memphis */ #include<cstdio> #include<algorithm> #include<cstring> #include<ctime> using namespace std; #define maxn 2000005 #define rep(i,x,y) for(int i=x;i<=y;++i) #define dep(i,x,y) for(int i=x;i>=y;--i) struct Treap{ Treap *l,*r; int fix,key,size; Treap(int key_):fix(rand()),key(key_),l(NULL),r(NULL),size(1){} inline void updata(){ size=1+(l?l->size:0)+(r?r->size:0); } }*root; typedef pair<Treap*,Treap*> Droot;//用来Split返回两个根 inline int Size(Treap *x){return x?x->size:0;}//这样求size可以防止访问空指针 Treap *Merge(Treap *A,Treap *B){//合并操作 if(!A)return B; if(!B)return A; if(A->fix<B->fix){ A->r=Merge(A->r,B); A->updata(); return A; }else{ B->l=Merge(A,B->l); B->updata(); return B; } } Droot Split(Treap *x,int k){//拆分操作 if(!x)return Droot(NULL,NULL); Droot y; if(Size(x->l)>=k){ y=Split(x->l,k); x->l=y.second; x->updata(); y.second=x; }else{ y=Split(x->r,k-Size(x->l)-1); x->r=y.first; x->updata(); y.first=x; } return y; } Treap *Build(int *a){//建造操作 static Treap *stack[maxn],*x,*last; int p=0; rep(i,1,a[0]){ x=new Treap(a[i]); last=NULL; while(p && stack[p]->fix>x->fix){ stack[p]->updata(); last=stack[p]; stack[p--]=NULL; } if(p) stack[p]->r=x; x->l=last; stack[++p]=x; } while(p) stack[p--]->updata(); return stack[1]; } int Findkth(int k){//查找第K小 Droot x=Split(root,k-1); Droot y=Split(x.second,1); Treap *ans=y.first; root=Merge(Merge(x.first,ans),y.second); return ans->key; } int Getkth(Treap *x,int v){//询问一个数是第几大 if(!x)return 0; return v<x->key?Getkth(x->l,v):Getkth(x->r,v)+Size(x->l)+1; } void Insert(int v){//插入操作 int k=Getkth(root,v); Droot x=Split(root,k); Treap *n=new Treap(v); root=Merge(Merge(x.first,n),x.second); } void Delete(int k){//删除操作 Droot x=Split(root,k-1); Droot y=Split(x.second,1); root=Merge(x.first,y.second); } int a[maxn],M,x,y; int main(){ freopen("bst.in","r",stdin); freopen("bst.out","w",stdout); scanf("%d",a); rep(i,1,a[0]) scanf("%d",a+i); sort(a+1,a+1+a[0]); root=Build(a); scanf("%d",&M); while(M--){ char ch=getchar(); while(ch!='Q' && ch!='A' && ch!='D') ch=getchar(); scanf("%d",&x); if(ch=='Q') printf("%d\n",Findkth(x)); if(ch=='A') Insert(x); if(ch=='D') Delete(x); } } Treap //fan_hd #include <cstdio> #include <cstdlib> using namespace std; class Treap{ public: #define Max_N 1<<20 struct point{ int pri,val,father,left,right; point *left,*right; }p[Max_N]; int length; int rand_arr[Max_N]; void reset(int key){ srand(time(0)); for (int i=0;i!=key;rand_arr[i]=i++;) for (int i=0;i!=key;i++){ int a=rand()%key,b=rand()%key; rand_arr[a]^=rand_arr[b],rand_arr[b]^=rand_arr[a],rand_arr[a]^=rand_arr[b]; //swap } length=0; p[0].pri=-1; p[0].left=1; } inline void left_rotate(int now,int father){ int now_right=p[now].right; p[now].right=father,p[father].left=now_right; p[now].father^=p[father].father,p[father].father^=p[now].father,p[now].father^=p[father].father;//swap } inline void right_rotate(int now,int father){ int now_left=p[now].left; p[now].left=father,p[father].right=now_left; p[now].father^=p[father].father,p[father].father^=p[now].father,p[now].father^=p[father].father;//swap } void insert(int va,int pr){ p[++length]={pr,va,0,0,0}; if (length==1) return; for (int i=p[0].left,f;i;f=i,i=va>p[i].val?p[i].right:p[i].left); p[length].father=f; while (pr<p[p[length].father].pri){ if (p[p[length].father].left==length) left_rotate(length,p[length].father); else right_rotate(length,p[length].father); } } int find(int v){ for (int i=p[0].left;i;){ if (p[i].val==v) return i; else i=v>p[i].val?p[i].right:p[i].left; } return -1; } void del(int v){ int pos=find(v); if (pos+1==0) return; for(;;){ if (pos[i]) } } void print(){ } }; int main(){ return 0; } FWT #include<bits/stdc++.h> using namespace std; const int N=1e3+100,mod=1e9+7,rev=(mod+1)>>1; int a[N],ans[N]; void FWT(int *a,int n) { for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m) for(int j=0;j<d;j++) { int x=a[i+j],y=a[i+j+d]; a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod; //xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod; //and:a[i+j]=x+y; //or:a[i+j+d]=x+y; } } void UFWT(int *a,int n) { for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m) for(int j=0;j<d;j++) { int x=a[i+j],y=a[i+j+d]; a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod; //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2; //and:a[i+j]=x-y; //or:a[i+j+d]=y-x; } } void solve(int *a,int *b,int n) { FWT(a,n); FWT(b,n); for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod; UFWT(a,n); } FWT应用-CodeForces - 662C-FWTxor #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1e5+5,maxm=(1<<20)+5; LL a[maxn],b[maxm],f[maxm],n,m; char s[maxn]; void FWT(LL *a,LL n) { for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m) for(int j=0;j<d;j++) { LL x=a[i+j],y=a[i+j+d]; a[i+j]=(x+y),a[i+j+d]=(x-y); } } void UFWT(LL *a,LL n) { for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m) for(int j=0;j<d;j++) { LL x=a[i+j],y=a[i+j+d]; a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2; } } void solve(LL *a,LL *b,LL n) { FWT(a,n); FWT(b,n); for(int i=0;i<n;i++) a[i]=a[i]*b[i]; UFWT(a,n); } inline int calc(int x) { int res=0; for(;x;x-=x&-x)res++; return res; } int main() { scanf("%lld%lld",&n,&m); for(int i=0;i<n;++i) { scanf("%s",s); for(int j=0;j<m;++j)a[j]|=(s[j]=='1')<<i; } LL tot=(1<<n); for(int i=0;i<m;++i)b[a[i]]++; for(int i=0;i<tot;++i) { LL res=calc(i); f[i]=min(res,n-res); } solve(f,b,tot); LL ans=1e18; for(int i=0;i<tot;++i)ans=min(ans,f[i]); printf("%lld\n",ans); return 0; }