ST表
P3865
#include<iostream>#include<cstdio>#include<cmath>using namespace std;int Max[100100][21],Log2[100100];int readd(){ int ret=0; char ch=getchar(); while('0'<=ch&&'9'>=ch){ ret*=10; ret+=(ch-'0'); ch=getchar(); } return ret;}int main(){ ios::sync_with_stdio(false); int n,q,sj; n=readd();q=readd(); sj=int(log2(n)); for(int i=1;i<=n;i++) Max[i][0]=readd(); for(int i=1;i<=n;i++) Log2[i]=(int)log2(i); for(int i=1;i<=sj;i++){ for(int j=1;j+(1<<i)<=n+1;j++){ Max[j][i]=max(Max[j][i-1],Max[j+(1<<(i-1))][i-1]); //cout<<Max[j][i]<<' '; } //cout<<endl; } int l,r; for(int i=0;i<q;i++){ l=readd(); r=readd(); printf("%d\n",max(Max[l][Log2[r-l+1]],Max[r-(1<<Log2[r-l+1])+1][Log2[r-l+1]])); } return 0;}线性求逆元
3805
#include<iostream>#include<cstring>#include<cstdio>using namespace std;char y[52000100],a[102000100];int b[52000100];int main(){ int ans=0; scanf("%s",y); int olen=strlen(y),len; a[0]='#';a[1]='#'; for(register int i=0;i<olen;i++){ a[(i<<1)+2]=y[i]; a[(i<<1)+3]='#'; } len=strlen(a); int maxr=0,mid=0;b[0]=1; for(register int i=1;i<=len;i++){ if(i<maxr) b[i]=min(b[(mid<<1)-i],b[mid]+mid-i); else b[i]=1; for(;a[i-b[i]]==a[i+b[i]];b[i]++); if(b[i]+i>maxr){ maxr=i+b[i]; mid=i; } ans=max(b[i],ans); } cout<<ans-1; return 0;}3811
#include<iostream>#include<cstdio>using namespace std;long long a[3000005];int main(){ int n,p; cin>>n>>p; a[1]=1; if(n>=1)printf("1\n"); for(register int i=2;i<=n;i++){ a[i]=(-((p/i)*(a[p%i]))%p+p)%p; printf("%lld\n",a[i]); } return 0;}线段树
3372
#include<iostream>using namespace std;#define ll long longll data[100005];struct point{ ll sum; ll lazy_tag;} a[400005];inline int ls(int x){return x<<1;}inline int rs(int x){return x<<1|1;}void build(int u,int l,int r){ a[u].lazy_tag=0; if(l==r){ a[u].sum=data[l]; //cout<<u<<' '<<l<<' '<<r<<' '<<a[u].sum<<endl; return; } int mid=(l+r)>>1; build(ls(u),l,mid); build(rs(u),mid+1,r); a[u].sum=a[ls(u)].sum+a[rs(u)].sum; //cout<<u<<' '<<l<<' '<<r<<' '<<a[u].sum<<endl;}void push_down(int u,int l,int r){ if(a[u].lazy_tag==0) return; a[ls(u)].lazy_tag+=a[u].lazy_tag; a[rs(u)].lazy_tag+=a[u].lazy_tag; int mid=(l+r)>>1; a[ls(u)].sum+=(a[u].lazy_tag*(mid-l+1)); a[rs(u)].sum+=(a[u].lazy_tag*(r-mid)); a[u].lazy_tag=0;}void add(int u,int al,int ar,int l,int r,int k){//l&r 所在区间 if(al<=l&&ar>=r){ a[u].lazy_tag+=k; a[u].sum+=(k*(r-l+1)); return; } int mid=(l+r)>>1; if(mid>=al){ push_down(u,l,r); add(ls(u),al,ar,l,mid,k); } if(mid<ar){ push_down(u,l,r); add(rs(u),al,ar,mid+1,r,k); } a[u].sum=a[ls(u)].sum+a[rs(u)].sum;}long long query(int u,int al,int ar,int l,int r){//和 //cout<<u<<' '<<al<<' '<<ar<<' '<<l<<' '<<r<<' '<<endl; if(al>r||ar<l) return 0ll; if(al<=l&&ar>=r){ //cout<<u<<" get:"<<a[u].sum<<endl; return a[u].sum; } long long ret=0; int mid=(l+r)>>1; if(mid>=al){ push_down(u,l,r); ret+=query(ls(u),al,ar,l,mid); } if(mid<ar){ push_down(u,l,r); ret+=query(rs(u),al,ar,mid+1,r); } //cout<<u<<" get:"<<ret<<endl; return ret;}int main(){ ios::sync_with_stdio(false); int n,m,opt,x,y,z; cin>>n>>m; for(int i=1;i<=n;i++) cin>>data[i]; build(1,1,n); for(int i=0;i<m;i++){ cin>>opt; if(opt==1){ cin>>x>>y>>z; add(1,x,y,1,n,z); } else{ cin>>x>>y; cout<<query(1,x,y,1,n)<<endl; } } return 0;}3373
#include<iostream>using namespace std;#define ll long longll mod;ll data[100005];struct point{ ll sum; ll addtag; ll multag;} a[400005];inline int ls(int x){return x<<1;}inline int rs(int x){return (x<<1)+1;}void up(int root){ a[root].sum=(a[ls(root)].sum+a[rs(root)].sum)%mod;}void build(int root,int l,int r){ a[root].addtag=0; a[root].multag=1; if(l==r) a[root].sum=data[l]; else{ int mid=(l+r)>>1; build(ls(root),l,mid); build(rs(root),mid+1,r); up(root); }}void pd(int root,int l,int r){ int mid=(r+l)>>1; a[ls(root)].addtag*=a[root].multag; a[rs(root)].addtag*=a[root].multag; a[ls(root)].addtag+=a[root].addtag; a[rs(root)].addtag+=a[root].addtag; a[ls(root)].addtag%=mod; a[rs(root)].addtag%=mod; a[ls(root)].multag*=a[root].multag; a[rs(root)].multag*=a[root].multag; a[ls(root)].multag%=mod; a[rs(root)].multag%=mod; a[ls(root)].sum=a[ls(root)].sum*a[root].multag+a[root].addtag*(mid-l+1); a[rs(root)].sum=a[rs(root)].sum*a[root].multag+a[root].addtag*(r-mid); a[ls(root)].sum%=mod; a[rs(root)].sum%=mod; a[root].addtag=0; a[root].multag=1;}void add(int root,int l,int r,int ql,int qr,ll x){ if(ql<=l&&qr>=r){ a[root].addtag+=x; a[root].addtag%=mod; a[root].sum+=(r-l+1)*x; a[root].sum%=mod; return; } if(r<ql||l>qr) return; int mid=(l+r)>>1; pd(root,l,r); if(ql<=mid)add(ls(root),l,mid,ql,qr,x); if(qr>mid)add(rs(root),mid+1,r,ql,qr,x); up(root); return;}void mul(int root,int l,int r,int ql,int qr,ll x){ if(ql<=l&&qr>=r){ a[root].addtag*=x; a[root].addtag%=mod; a[root].multag*=x; a[root].multag%=mod; a[root].sum*=x; a[root].sum%=mod; return; } if(r<ql||l>qr) return; int mid=(l+r)>>1; pd(root,l,r); if(ql<=mid)mul(ls(root),l,mid,ql,qr,x); if(qr>mid)mul(rs(root),mid+1,r,ql,qr,x); up(root); return;}ll query(int root,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r) return a[root].sum%mod; if(r<ql||l>qr) return 0; int mid=(l+r)>>1; ll ret=0; pd(root,l,r); if(ql<=mid)ret+=query(ls(root),l,mid,ql,qr); if(qr>mid)ret+=query(rs(root),mid+1,r,ql,qr); return ret%mod;}int main(){ ios::sync_with_stdio(false); ll n,m,opt,x,y,z; cin>>n>>m>>mod; for(int i=1;i<=n;i++)cin>>data[i]; build(1,1,n); for(int i=0;i<m;i++){cin>>opt; if(opt==1){cin>>x>>y>>z;mul(1,1,n,x,y,z);} if(opt==2){cin>>x>>y>>z;add(1,1,n,x,y,z);} if(opt==3){cin>>x>>y;cout<<query(1,1,n,x,y)<<endl;} } return 0;}树链剖分
#include<iostream>#define ll long long#define MAXN 100005using namespace std;ll p;int cnt=0;struct edge{ int v,next;} g[2*MAXN];int head[MAXN],ov[MAXN],val[MAXN],depth[MAXN],fa[MAXN],siz[MAXN];int son[MAXN],id[MAXN],top[MAXN];using namespace std;struct point{ ll sum,tag;} a[400005];ll data[100005];int ls(int root){return root<<1;}int rs(int root){return (root<<1)+1;}void up(int root){ a[root].sum=a[ls(root)].sum+a[rs(root)].sum;}void build(int root,int l,int r){ a[root].tag=0; if(l==r)a[root].sum=val[l]; else{ int mid=(l+r)>>1; build(ls(root),l,mid); build(rs(root),mid+1,r); up(root); }}void pd(int root,int l,int r){ a[ls(root)].tag+=a[root].tag; a[ls(root)].tag%=p; a[rs(root)].tag+=a[root].tag; a[rs(root)].tag%=p; int mid=(l+r)>>1; a[ls(root)].sum+=a[root].tag*(mid-l+1); a[ls(root)].sum%=p; a[rs(root)].sum+=a[root].tag*(r-mid); a[rs(root)].sum%=p; a[root].tag=0;}void add(int root,int l,int r,int ql,int qr,ll k){ if(ql>qr)swap(ql,qr); k%=p; if(ql<=l&&qr>=r){ a[root].tag+=k;a[root].sum+=k*(r-l+1); return; } pd(root,l,r); int mid=(l+r)>>1; if(mid>=ql)add(ls(root),l,mid,ql,qr,k); if(qr>mid) add(rs(root),mid+1,r,ql,qr,k); up(root);}ll query(int root,int l,int r,int ql,int qr){ if(ql>qr)swap(ql,qr); if(ql<=l&&qr>=r){ return a[root].sum; } pd(root,l,r); int mid=(l+r)>>1; ll ret=0; if(mid>=ql)ret+=query(ls(root),l,mid,ql,qr); if(qr>mid) ret+=query(rs(root),mid+1,r,ql,qr); up(root); return ret%p;}void addedge(int u,int v){ cnt++; g[cnt].v=v; g[cnt].next=head[u]; head[u]=cnt;}void dfs1(int n,int f,int deep){ depth[n]=deep; fa[n]=f; siz[n]=1; if(g[head[n]].v==f&&g[head[n]].next==0){ son[n]=n; return; } int maxx=0; for(int i=head[n];i;i=g[i].next){ if(g[i].v==f)continue; dfs1(g[i].v,n,deep+1); siz[n]+=siz[g[i].v]; maxx=(siz[g[i].v]>siz[maxx])?g[i].v:maxx; } son[n]=maxx;}void dfs2(int n,int htop){ cnt++; id[n]=cnt; val[cnt]=ov[n]; top[n]=htop; if(g[head[n]].v==fa[n]&&g[head[n]].next==0)return; dfs2(son[n],htop); for(int i=head[n];i;i=g[i].next){ if(g[i].v==fa[n]||g[i].v==son[n])continue; dfs2(g[i].v,g[i].v); }}ll querychain(int x,int y,int n){ ll ans=0; while(top[x]!=top[y]){ if(depth[top[x]]<depth[top[y]])swap(x,y); ans+=query(1,1,n,id[x],id[top[x]]); ans%=p; x=fa[top[x]]; } ans+=query(1,1,n,id[x],id[y]); ans%=p; return ans;}void addchain(int x,int y,int n,ll k){ k%=p; while(top[x]!=top[y]){ if(depth[top[x]]<depth[top[y]])swap(x,y); add(1,1,n,id[x],id[top[x]],k); x=fa[top[x]]; } if(depth[top[x]]<depth[top[y]])swap(x,y); add(1,1,n,id[x],id[y],k);}ll querytree(int x,int n){ return query(1,1,n,id[x],id[x]+siz[x]-1);}void addtree(int x,int n,ll k){ add(1,1,n,id[x],id[x]+siz[x]-1,k);}int main(){ ios::sync_with_stdio(false); int n,m,r,u,v; cin>>n>>m>>r>>p; for(int i=1;i<=n;i++)cin>>ov[i]; for(int i=1;i<n;i++){ cin>>u>>v; addedge(u,v); addedge(v,u); } dfs1(r,0,1); cnt=0; dfs2(r,r); build(1,1,n); int opt,x,y,z; for(int i=0;i<m;i++){ cin>>opt; if(opt==1){ cin>>x>>y>>z; addchain(x,y,n,z); } else if(opt==2){ cin>>x>>y; cout<<querychain(x,y,n)<<endl; } else if(opt==3){ cin>>x>>y; addtree(x,n,y); } else if(opt==4){ cin>>x; cout<<querytree(x,n)<<endl; } } return 0;}树状数组
#include<iostream>using namespace std;typedef long long ll;ll b[500005],c[500005];int n;inline ll lowbit(ll x){return x&(-x);}void add(int t,ll x){ while(t<=n){ c[t]+=x; t+=lowbit(t); }}ll sum(ll t){ ll ret=0; while(t>0){ ret+=c[t]; t-=lowbit(t); } return ret;}int main(){ ios::sync_with_stdio(false); int m,x,y,k,opt; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>c[i]; b[i]=c[i]-c[i-1]; } for(int i=1;i<=n;i++)c[i]=0; for(int i=1;i<=n;i++)add(i,b[i]); for(int i=0;i<m;i++){ cin>>opt; if(opt==1){ cin>>x>>y>>k; add(x,k); add(y+1,-k); } else{ cin>>x; cout<<sum(x)<<endl; } } return 0;}3374
#include<iostream>#define ll long longusing namespace std;ll n;ll c[500005];inline ll lowbit(ll x){ return x&(-x);}void add(ll t,ll x){ while(t<=n){ c[t]+=x; t+=lowbit(t); }}ll sum(ll t){ ll ret=0; while(t>0){ ret+=c[t]; t-=lowbit(t); } return ret;}ll search(ll l,ll r){ return sum(r)-sum(l-1);}int main(){ ios::sync_with_stdio(false); ll m,x,y,z; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>x; add(i,x); } for(int i=0;i<m;i++){ cin>>x>>y>>z; if(x==1) add(y,z); else cout<<search(y,z)<<endl; } return 0;}网络流
#include<iostream>#include<cstdio>#include<cstdlib>#define MAXN 100005using namespace std;struct fhq_treap{ int val[MAXN],son[MAXN][2],rnd[MAXN],siz[MAXN],rt,cnt; void pushup(int root){ siz[root]=siz[son[root][0]]+siz[son[root][1]]+1; } int newnode(int v){ val[++cnt]=v; rnd[cnt]=rand(); siz[cnt]=1; return cnt; } int merge(int x,int y){ if(!x||!y)return x+y; if(rnd[x]<rnd[y]){ son[x][1]=merge(son[x][1],y); pushup(x); return x; } else{ son[y][0]=merge(x,son[y][0]); pushup(y); return y; } } void split(int root,int pos,int &x,int &y){ if(!root)x=y=0; else{ if(val[root]<=pos){ x=root; split(son[root][1],pos,son[root][1],y); } else{ y=root; split(son[root][0],pos,x,son[root][0]); } pushup(root); } } void insert(int v){ int x,y; split(rt,v,x,y); rt=merge(merge(x,newnode(v)),y); } void del(int v){ int x,y,z; split(rt,v,x,z); split(x,v-1,x,y); y=merge(son[y][0],son[y][1]); rt=merge(merge(x,y),z); } int get_rank(int v){ int x,y,ret; split(rt,v-1,x,y); ret=siz[x]+1; rt=merge(x,y); return ret; } int get_kth(int root,int k){ while(1){ if(k<=siz[son[root][0]]) root=son[root][0]; else if(k==siz[son[root][0]]+1) return val[root]; else{ k-=(siz[son[root][0]]+1); root=son[root][1]; } } } int pre(int v){ int x,y,ret; split(rt,v-1,x,y); ret=get_kth(x,siz[x]); rt=merge(x,y); return ret; } int suf(int v){ int x,y,ret; split(rt,v,x,y); ret=get_kth(y,1); rt=merge(x,y); return ret; }}T;int main(){ int n,x,opt; cin>>n; for(int i=0;i<n;i++){ cin>>opt>>x; if(opt==1)T.insert(x); else if(opt==2)T.del(x); else if(opt==3)cout<<T.get_rank(x)<<endl; else if(opt==4)cout<<T.get_kth(T.rt,x)<<endl; else if(opt==5)cout<<T.pre(x)<<endl; else if(opt==6)cout<<T.suf(x)<<endl; } return 0;}当前弧优化3376
#include<iostream>#include<cstring>#define inf 2147483647using namespace std;struct edge{ int val,to,next;}a[200005];int head[10005],q[10005],floor[10005],cnt=0;bool vis[10005];void add_edge(int u,int v,int val){ cnt++;a[cnt].to=v;a[cnt].val=val;a[cnt].next=head[u];head[u]=cnt;}bool bfs(int s,int t){ memset(vis,0,sizeof(vis)); memset(floor,0,sizeof(floor)); int h=0,ta=1,x; q[0]=s;floor[s]=1;vis[s]=1; while(h<ta){ x=q[h]; for(int i=head[x];i;i=a[i].next){ if(!vis[a[i].to]&&a[i].val){ q[ta++]=a[i].to; floor[a[i].to]=floor[x]+1; vis[a[i].to]=1; } } h++; } return vis[t];}int dfs(int u,int limit,int t){ if(u==t)return limit; int temp,ans=0; for(int i=head[u];i&&limit;i=a[i].next){ if(a[i].val&&floor[u]+1==floor[a[i].to]){ temp=dfs(a[i].to,min(limit,a[i].val),t); if(temp!=-1){ ans+=temp; a[i].val-=temp; a[(i^1)+2].val+=temp; limit-=temp; } } } return ans;}int main(){ ios::sync_with_stdio(false); int n,m,u,v,w,s,t,ans=0; cin>>n>>m>>s>>t; for(int i=0;i<m;i++){ cin>>u>>v>>w; add_edge(u,v,w);add_edge(v,u,0);} while(bfs(s,t)){ ans+=dfs(s,inf,t); } cout<<ans; return 0;}最小生成树 ：
p3366
#include<iostream>#include<queue>#include<algorithm>using namespace std;int bcj[200005];int fa(int x){ if(bcj[x]==0) return x; else{ int temp=fa(bcj[x]); bcj[x]=temp; return temp; }}void merge(int x,int y){ int fx=fa(x),fy=fa(y); if(fx!=fy) bcj[fy]=fx;}bool find(int x,int y){ int fx=fa(x),fy=fa(y); if(fx==fy) return true; return false;}struct edge{ int val; int l,r;} a[200005];bool operator<(edge a,edge b){ return a.val<b.val;}int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; for(int i=0;i<m;i++) cin>>a[i].l>>a[i].r>>a[i].val; sort(a,a+m); int cnt=0,ans=0; for(int i=0;cnt<n-1;i++){ if(!find(a[i].l,a[i].r)){ ans+=a[i].val; cnt++; merge(a[i].l,a[i].r); } if(i==m-1&&cnt<n-1){ cout<<"orz"; return 0; } } cout<<ans; return 0;}匈牙利算法
3386
#include<iostream>#include<cstring>using namespace std;bool map[1005][1005],used[1005];int book[1005];int n;bool dfs(int x){ for(int i=1;i<=n;i++){ if(map[x][i]==1&&used[i]==false){ used[i]=1; if(book[i]==0||dfs(book[i])){ book[i]=x; return true; } } } return false;}int main(){ int m,e,x,y,ans=0; cin>>n>>m>>e; for(int i=0;i<e;i++){ cin>>x>>y; if(x<=n&&y<=m) map[x][y]=1; } for(int i=1;i<=m;i++){ memset(used,0,sizeof(used)); if(dfs(i)) ans++; } cout<<ans; return 0;}fhqtreap实现的区间翻转
3391
#include<iostream>#include<cstdlib>#define MAXN 100005using namespace std;struct fhqtreap{ int rnd[MAXN],siz[MAXN],ch[MAXN][2],val[MAXN],root,cnt; bool rev[MAXN]; void pushup(int rt){ siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1; } int newnode(int v){ siz[++cnt]=1; rnd[cnt]=rand(); val[cnt]=v; return cnt; } void pushdown(int rt){ if(rev[rt]){ swap(ch[rt][0],ch[rt][1]); if(ch[rt][0])rev[ch[rt][0]]^=1; if(ch[rt][1])rev[ch[rt][1]]^=1; rev[rt]=0; } } int merge(int x,int y){ if(!x||!y)return x+y; if(rnd[x]<rnd[y]){ pushdown(x); ch[x][1]=merge(ch[x][1],y); pushup(x); return x; } else{ pushdown(y); ch[y][0]=merge(x,ch[y][0]); pushup(y); return y; } } void split(int rt,int pos,int &x,int &y){ if(!rt)x=y=0; else{ pushdown(rt); if(pos<=siz[ch[rt][0]]){ //cout<<"进入左子树,pos="<<pos<<endl; y=rt; split(ch[rt][0],pos,x,ch[rt][0]); } else{ //cout<<"进入右子树,pos="<<pos-siz[ch[rt][0]]-1<<endl; x=rt; split(ch[rt][1],pos-siz[ch[rt][0]]-1,ch[rt][1],y); } pushup(rt); } } void reverse(int l,int r){ int x,y,z; //cout<<"开始split,pos="<<l-1<<endl; split(root,l-1,x,y); //cout<<"开始split,pos="<<r-l+1<<endl; split(y,r-l+1,y,z); rev[y]^=1; root=merge(x,merge(y,z)); } void putout(int rt){ if(!rt)return; pushdown(rt); putout(ch[rt][0]); cout<<rt<<' '; putout(ch[rt][1]); }}T;int main(){ int n,m,l,r; cin>>n>>m; for(int i=1;i<=n;i++) T.root=T.merge(T.root,T.newnode(i)); for(int i=0;i<m;i++){ cin>>l>>r; T.reverse(l,r); } T.putout(T.root); cout<<endl; return 0;}KMP 3375
#include<iostream>#include<cstring>using namespace std;int kmp[1000005];char a[1000005],b[1000005];int main(){ int lena,lenb,x=0; cin>>a+1>>b+1; lena=strlen(a+1); lenb=strlen(b+1); for(int i=2;i<=lenb;i++){ while(x&&b[i]!=b[x+1]) x=kmp[x]; if(b[i]==b[x+1])kmp[i]=++x; }x=0; for(int i=1;i<=lena;i++){ //cout<<x<<' '<<i<<endl; while(x&&a[i]!=b[x+1]) x=kmp[x]; if(a[i]==b[x+1])x++; if(x==lenb){ cout<<i-lenb+1<<endl; x=kmp[x]; } } for(int i=1;i<=lenb;i++)cout<<kmp[i]<<" "; return 0;}LCA
#include<iostream>#include<cstdio>using namespace std;struct edge{ int v;int next;} a[1000010];int head[500005],depth[500005],lg[500005],fa[500005][30],cnt=0;inline int read(){ int x=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x;}inline void add_edge(int u,int v){ a[++cnt].v=v; a[cnt].next=head[u]; head[u]=cnt;}void dfs(int n,int father){ depth[n]=depth[father]+1; //cout<<"father="<<father<<endl; fa[n][0]=father; for(int i=1;i<lg[depth[n]];i++){ fa[n][i]=fa[fa[n][i-1]][i-1]; //cout<<"fa["<<n<<"]["<<i<<"]="<<fa[n][i]<<" "; } for(int i=head[n];i;i=a[i].next) if(a[i].v!=father) dfs(a[i].v,n); return;}inline int lca(int x,int y){ if(depth[x]<depth[y])swap(x,y); while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1]; if(x==y)return x; for(int i=lg[depth[x]]-1;i>=0;i--){ if(fa[x][i]==fa[y][i]) continue; else x=fa[x][i],y=fa[y][i]; if(fa[x][0]==fa[y][0]) return fa[x][0]; }}int main(){ int n,m,root,u,v; scanf("%d%d%d",&n,&m,&root); for(register int i=1;i<n;i++){ u=read();v=read(); add_edge(u,v); add_edge(v,u); } for(register int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); dfs(root,0); //for(int i=1;i<=n;i++)cout<<depth[i]<<' ';cout<<endl; for(register int i=0;i<m;i++){ u=read();v=read(); printf("%d\n",lca(u,v)); } return 0;}凸包极角序
#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>using namespace std;struct point{ double x,y;} a[300005],LTL,b[300005];int top=0;bool toleft(point p,point q,point r){ return (0<(p.x*q.y-q.x*p.y+q.x*r.y-r.x*q.y+r.x*p.y-p.x*r.y));}bool operator<(point a,point b){ return toleft(LTL,a,b);}double dis(point a,point b){ return sqrt(abs(a.x-b.x)*abs(a.x-b.x)+abs(a.y-b.y)*abs(a.y-b.y));}int main(){ /*point t,tt,ttt; t.x=-1;t.y=-2; tt.x=tt.y=4; ttt.x=0;ttt.y=1; cout<<toleft(t,tt,ttt);*/ int n; cin>>n; LTL.x=LTL.y=1000000007; for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y; for(int i=1;i<=n;i++) if(LTL.y>a[i].y||(LTL.y==a[i].y&<L.x>a[i].x)) LTL=a[i]; bool bj=0; for(int i=1;i<=n;i++){ if(a[i].x==LTL.x&&a[i].y==LTL.y)bj=1; if(bj==1&&i<n)a[i]=a[i+1]; } sort(a+1,a+n); //for(int i=1;i<n;i++)cout<<a[i].x<<' '<<a[i].y<<endl; b[top++]=LTL; for(int i=1;i<n;i++){ //cout<<"\n--------\n"; if(top<=1){ b[top++]=a[i]; continue; } while(top>1){ //cout<<"\n----\n"; //for(int i=0;i<top;i++)cout<<b[i].x<<' '<<b[i].y<<endl; if(!toleft(b[top-2],b[top-1],a[i])) top--; else break; } b[top++]=a[i]; } double sum=0; //cout<<"\n----ans----\n"; for(int i=1;i<top;i++){ sum+=dis(b[i],b[i-1]); //cout<<b[i].x<<' '<<b[i].y<<endl; } sum+=dis(b[top-1],b[0]); printf("%.2lf",sum); return 0;}/*90 40 10 01 02 1-2 2-1 -24 -14 4*/Dijkstra
4779
#include<iostream>#include<utility>#include<queue>#include<cstring>using namespace std;struct point{ int diss; int u;};point mk(int x,int y){ point xx; xx.diss=x; xx.u=y; return xx;}bool operator<(point a,point b){ return a.diss>b.diss;}priority_queue<point> pq;vector<pair<int,int> > a[100005];int dis[100005];bool book[100005];void dijkstra(int s){ while(!pq.empty()){ s=pq.top().u; pq.pop(); if(book[s])continue; book[s]=1; //cout<<s<<endl; for(int i=0;i<a[s].size();i++){ if(a[s][i].second+dis[s]<dis[a[s][i].first]&&book[a[s][i].first]==0){ //cout<<a[s][i].first<<'#'<<endl; dis[a[s][i].first]=a[s][i].second+dis[s]; pq.push(mk(dis[a[s][i].first],a[s][i].first)); } } }}int main(){ ios::sync_with_stdio(false); memset(dis,0x3f,sizeof(dis)); int n,m,s,x,y,c; cin>>n>>m>>s; for(int i=0;i<m;i++){ cin>>x>>y>>c; a[x].push_back(make_pair(y,c)); } dis[s]=0; pq.push(mk(0,s)); dijkstra(s); for(int i=1;i<=n;i++)cout<<dis[i]<<' '; return 0;}/*6 8 31 3 31 5 31 6 32 5 12 6 13 4 33 5 35 6 3*/