高精度
struct bigint
{
int num[maxn],len;
bigint(string s="0")
{
memset(num,0,sizeof(num));
len=s.size();
for(int i=1;i<=len;i++) num[i]=s[len-i]-'0';
}
void output() const
{
for(int i=len;i>=1;i--) putchar(num[i]+'0');
}
bigint operator+(bigint a) const
{
bigint b;
b.len+=max(this->len,a.len);
for(int i=1;i<=b.len;i++)
{
b.num[i]=this->num[i]+a.num[i];
if(b.num[i]>9)
{
b.num[i+1]++;
b.num[i]-=10;
if(i==b.len) b.len++;
}
}
return b;
}
bigint operator-(const bigint &a) const
{
bigint b;
b.len=max(this->len,a.len);
for(int i=1;i<=b.len;i++)
{
b.num[i]+=this->num[i]-a.num[i];
if(b.num[i]<0)
{
b.num[i+1]--;
b.num[i]+=10;
}
}
while(!b.num[b.len]&&b.len>1) b.len--;
return b;
}
bigint operator*(const bigint &a) const
{
bigint b;
b.len=this->len+a.len;
for(int i=1;i<=this->len;i++)
for(int j=1;j<=a.len;j++)
{
b.num[i+j-1]+=this->num[i]*a.num[j];
if(b.num[i+j-1]>9)
{
b.num[i+j]+=b.num[i+j-1]/10;
b.num[i+j-1]%=10;
}
}
while(!b.num[b.len]&&b.len>1) b.len--;
return b;
}
bigint operator/(const int &a) const
{
bigint b;
b.len=this->len;
int r=0;
for(int i=b.len;i>=1;i--)
{
b.num[i]=(this->num[i]+r*10)/a;
r=(this->num[i]+r*10)%a;
}
while(!b.num[b.len]&&b.len>1) b.len--;
return b;
}
int operator%(const int &a) const
{
bigint b;
b.len=this->len;
int r=0;
for(int i=b.len;i>=1;i--)
{
b.num[i]=(this->num[i]+r*10)/a;
r=(this->num[i]+r*10)%a;
}
return r;
}
};
ST 表
#include<bits/stdc++.h>
#define maxn 2000005
using namespace std;
int f[maxn][25],logn[maxn]={0,0,1};
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&f[i][0]);
for(int i=3;i<=2000000;i++) logn[i]=logn[i/2]+1;
for(int j=1;j<=21;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",max(f[x][logn[y-x+1]],f[y-(1<<logn[y-x+1])+1][logn[y-x+1]]));
}
return 0;
}
并查集
#include<iostream>
using namespace std;
int fa[10005];
int father(int x)
{
if(fa[x]!=x) return fa[x]=father(fa[x]);
return x;
}
void unionn(int x,int y)
{
fa[father(x)]=father(y);
}
int main()
{
ios::sync_with_stdio(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
while(m--)
{
int z,x,y;
cin>>z>>x>>y;
if(z==1) unionn(x,y);
else
{
if(father(x)==father(y)) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
return 0;
}
线段树
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int s=0;char ch=getchar(),last=0;
while(ch<'0'||ch>'9') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return last=='-'?-s:s;
}
inline void write(int s)
{
int n=0,buf[15];
if(s<0) putchar('-'),s=-s;
do buf[n++]=s%10;while(s/=10);
while(n--) putchar(buf[n]+'0');
}
struct tree{int l,r,lc,rc,ans,lazy1,lazy2;}tr[2000005];
int a[1000005],tot,n,m,p;
inline int bt(int l,int r)
{
int pos=++tot;
tr[pos].l=l;tr[pos].r=r;
tr[pos].lazy1=1;tr[pos].lazy2=0;
if(l==r)
{
tr[pos].lc=tr[pos].rc=-1;
tr[pos].ans=a[l];
}
else
{
tr[pos].lc=bt(l,l+r>>1);
tr[pos].rc=bt((l+r>>1)+1,r);
tr[pos].ans=(tr[tr[pos].lc].ans+tr[tr[pos].rc].ans)%p;
}
return pos;
}
void times(int,int,int,int);
void add(int,int,int,int);
inline void update(int pos)
{
if(tr[pos].lazy1!=1)
{
times(tr[pos].lc,tr[tr[pos].lc].l,tr[tr[pos].lc].r,tr[pos].lazy1);
times(tr[pos].rc,tr[tr[pos].rc].l,tr[tr[pos].rc].r,tr[pos].lazy1);
tr[pos].lazy1=1;
}
if(tr[pos].lazy2)
{
add(tr[pos].lc,tr[tr[pos].lc].l,tr[tr[pos].lc].r,tr[pos].lazy2);
add(tr[pos].rc,tr[tr[pos].rc].l,tr[tr[pos].rc].r,tr[pos].lazy2);
tr[pos].lazy2=0;
}
tr[pos].ans=(tr[tr[pos].lc].ans+tr[tr[pos].rc].ans)%p;
}
inline void times(int pos,int l,int r,int x)
{
if(tr[pos].l==l&&tr[pos].r==r)
{
tr[pos].lazy1=tr[pos].lazy1*x%p;
tr[pos].lazy2=tr[pos].lazy2*x%p;
tr[pos].ans=tr[pos].ans*x%p;
return;
}
update(pos);
if(r<=tr[tr[pos].lc].r) times(tr[pos].lc,l,r,x);
else if(l>=tr[tr[pos].rc].l) times(tr[pos].rc,l,r,x);
else
{
times(tr[pos].lc,l,tr[tr[pos].lc].r,x);
times(tr[pos].rc,tr[tr[pos].rc].l,r,x);
}
tr[pos].ans=(tr[tr[pos].lc].ans+tr[tr[pos].rc].ans)%p;
}
inline void add(int pos,int l,int r,int x)
{
if(tr[pos].l==l&&tr[pos].r==r)
{
tr[pos].lazy2=(tr[pos].lazy2+x)%p;
tr[pos].ans=(tr[pos].ans+x*(r-l+1)%p)%p;
return;
}
update(pos);
if(r<=tr[tr[pos].lc].r) add(tr[pos].lc,l,r,x);
else if(l>=tr[tr[pos].rc].l) add(tr[pos].rc,l,r,x);
else
{
add(tr[pos].lc,l,tr[tr[pos].lc].r,x);
add(tr[pos].rc,tr[tr[pos].rc].l,r,x);
}
tr[pos].ans=(tr[tr[pos].lc].ans+tr[tr[pos].rc].ans)%p;
}
inline int query(int pos,int l,int r)
{
if(tr[pos].l==l&&r==tr[pos].r) return tr[pos].ans;
update(pos);
if(r<=tr[tr[pos].lc].r) return query(tr[pos].lc,l,r);
else if(l>=tr[tr[pos].rc].l) return query(tr[pos].rc,l,r);
else return (query(tr[pos].lc,l,tr[tr[pos].lc].r)+query(tr[pos].rc,tr[tr[pos].rc].l,r))%p;
}
signed main()
{
n=read(),m=read(),p=read();
for(int i=1;i<=n;i++) a[i]=read();
bt(1,n);
while(m--)
{
int op=read(),l=read(),r=read();
switch(op)
{
case 1:times(1,l,r,read());break;
case 2:add(1,l,r,read());break;
case 3:write(query(1,l,r)),putchar('\n');
}
}
return 0;
}
树状数组
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int s=0;char ch=getchar(),last='0';
while(ch<'0'||ch>'9') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return last=='-'?-s:s;
}
inline void write(int x)
{
int buf[20],n=0;
do buf[n++]=x%10;
while(x/=10);
while(n--) putchar(buf[n]+'0');
}
int tr[500005],n,m;
inline int lowbit(int x){return x&-x;}
inline void change(int x,int y)
{
while(x<=n)
{
tr[x]+=y;
x+=lowbit(x);
}
}
inline int query(int x)
{
int ans=0;
while(x>0)
{
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
int x=read();
change(i,x);
}
for(int i=1;i<=m;i++)
{
int id=read(),x=read(),y=read();
if(id==1) change(x,y);
else write(query(y)-query(x-1)),putchar('\n');
}
return 0;
}
普通平衡树
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
using namespace std;
using namespace __gnu_pbds;
tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> T;
int main()
{
ios::sync_with_stdio(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int oper;
ll x;
cin>>oper>>x;
if(oper==1) T.insert((x<<20)+i);
if(oper==2) T.erase(T.lower_bound(x<<20));
if(oper==3) cout<<T.order_of_key(x<<20)+1<<endl;
ll ans=-1e9;
if(oper==4) ans=*T.find_by_order(x-1);
if(oper==5) ans=*--T.upper_bound(x<<20);
if(oper==6) ans=*T.upper_bound((x+1)<<20);
if(ans!=-1e9) cout<<(ans>>20)<<endl;
}
return 0;
}
map in pbds
#include<ext/pb_ds/hash_policy.hpp>
gp_hash_table<int,int> h;
trie in pbds
#include<ext/pb_ds/trie_policy.hpp>
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> tr;
tr.insert(s);
tr.erase(s);
pair<tr::iterator,tr::iterator> range=base.prefix_range(x);
for(tr::iterator it=range.first;it!=range.second;it++) cout<<*it<<' '<<endl;
堆
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
__gnu_pbds::priority_queue<int,greater<int> > q;
int main()
{
ios::sync_with_stdio(0);
int n,op,x;
cin>>n;
while(n--)
{
cin>>op;
if(op==1)
{
cin>>x;
q.push(x);
}
else if(op==2) cout<<q.top()<<endl;
else q.pop();
}
return 0;
}
线性筛
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &s)
{
s=0;char ch=getchar(),last='0';
while(ch<'0'||ch>'9') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
if(last=='-') s=-s;
}
template<typename T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
int len=0,num[20];
do num[len++]=x%10;while(x/=10);
while(len--) putchar(num[len]+'0');
}
bool b[100000005];
int p[1000005];
int main()
{
memset(b,1,sizeof(b));
b[0]=b[1]=0;
int n,tot=0;
read(n);
for(int i=2;i<=n;i++)
{
if(b[i]) p[++tot]=i;
for(int j=1;j<=tot&&i*p[j]<=n;j++)
{
b[i*p[j]]=0;
if(i%p[j]==0) break;
}
}
int q;
read(q);
while(q--)
{
int k;
read(k);
write(p[k]);
putchar('\n');
}
return 0;
}
最小生成树
#include<bits/stdc++.h>
using namespace std;
struct edge{int f,t,v,nxt;}e[400005];
int last[5005],tot,fa[5005];
inline void add(int f,int t,int v)
{
e[++tot]={f,t,v,last[f]};
last[f]=tot;
}
inline bool cmp(const edge &a,const edge &b)
{
return a.v<b.v;
}
inline int father(int x)
{
if(fa[x]!=x) return fa[x]=father(fa[x]);
return x;
}
inline void unionn(int x,int y)
{
fa[father(x)]=father(y);
}
int main()
{
ios::sync_with_stdio(0);
int n,m,ans=0;
cin>>n>>m;
memset(last,-1,sizeof(last));
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
sort(e+1,e+m*2+1,cmp);
tot=0;
for(int i=1;i<=m*2&&tot<n-1;i++)
if(father(e[i].f)!=father(e[i].t))
{
unionn(e[i].f,e[i].t);
ans+=e[i].v;
tot++;
}
if(tot!=n-1) cout<<"orz"<<endl;
else cout<<ans<<endl;
return 0;
}
次小生成树
#include<bits/stdc++.h>
#define INF 2100000001
#define M 300003
#define N 100003
#define LL long long
using namespace std;
int read()
{
int f=1,x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
struct EDGE{
int x,y,z,flagg;
}w[M];
struct edgee{
int to,nextt,val;
}e[M];
int tot=0,m,n,minn=INF; LL ans=0;
int f[N][22],max1[N][22],g[N][22],fa[N],head[N],dep[N];
bool cmp(const EDGE &a,const EDGE &b)
{
return a.z<b.z;
}
int getfa(int x)
{
if(fa[x]==x) return x;
return fa[x]=getfa(fa[x]);
}
void add(int a,int b,int v)
{
tot++;
e[tot].to=b;
e[tot].nextt=head[a];
e[tot].val=v;
head[a]=tot;
}
void kruscal()
{
int q=1;
sort(w+1,w+m+1,cmp);
for(int i=1;i<=n;++i)
fa[i]=i;
for(int i=1;i<=m;++i)
{
int s1=getfa(w[i].x);
int s2=getfa(w[i].y);
if(s1!=s2)
{
ans+=w[i].z;w[i].flagg=1;
q++;
fa[s1]=s2;
add(w[i].x,w[i].y,w[i].z);
add(w[i].y,w[i].x,w[i].z);
}
if(q==n) break;
}
}
void dfs(int x)
{
for(int i=head[x];i;i=e[i].nextt)
{
int v=e[i].to;
if(v==f[x][0]) continue;
f[v][0]=x;
max1[v][0]=e[i].val;
dep[v]=dep[x]+1;
for(int j=1;j<=20;++j)
{
if(dep[v]<(1<<j))break;//注意：如果深度小于向上走的步数就可以break掉了
f[v][j]=f[f[v][j-1]][j-1];//f是向上走到达的点
max1[v][j]=max(max1[v][j-1],max1[f[v][j-1]][j-1]);//max1是最大边
if(max1[v][j-1]==max1[f[v][j-1]][j-1])
g[v][j]=max(g[v][j-1],g[f[v][j-1]][j-1]);//g是次大边
else
{
g[v][j]=min(max1[v][j-1],max1[f[v][j-1]][j-1]);
g[v][j]=max(g[v][j],g[f[v][j-1]][j-1]);
g[v][j]=max(g[v][j-1],g[v][j]);
}
}
dfs(v);
}
}
int LCA(int u,int x)
{
if(dep[u]<dep[x])swap(u,x);
for(int i=20;i>=0;--i)if(dep[f[u][i]]>=dep[x])u=f[u][i];
if(x==u) return x;
for(int i=20;i>=0;--i)if(f[x][i]!=f[u][i])x=f[x][i],u=f[u][i];
return f[x][0];
}
void change(int x,int lca,int val)
{
int maxx1=0,maxx2=0;
int d=dep[x]-dep[lca];
for(int i=0;i<=20;++i)
{
if(d<(1<<i))break;
if(d&(1<<i))
{
if(max1[x][i]>maxx1)
{
maxx2=max(maxx1,g[x][i]);
maxx1=max1[x][i];
}
x=f[x][i];
}
}
if(val!=maxx1) minn=min(minn,val-maxx1);
else minn=min(minn,val-maxx2);
}
void work()
{
for(int i=1;i<=m;++i)
{
if(!w[i].flagg)
{
int s1=w[i].x,s2=w[i].y;
int lca=LCA(s1,s2);
change(s1,lca,w[i].z);change(s2,lca,w[i].z);
}
}
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;++i)
{
w[i].x=read();w[i].y=read();w[i].z=read();
}
kruscal();
dfs(1);
work();
printf("%lld\n",ans+minn);
}
SPFA
#include<cstdio>
#include<cstring>
using namespace std;
struct node{int x,y,c,next;}a[1000005];
int d[1000005],last[1000005],q[1000005],len,n,m,s;
bool v[1000005];
void ins(int x,int y,int c)
{
len++;
a[len]={x,y,c,last[x]};
last[x]=len;
}
void spfa()
{
int st=1,ed=2;
memset(d,63,sizeof(d));
memset(v,false,sizeof(v));
d[s]=0;
v[s]=true;
q[st]=s;
while(st!=ed)
{
int x=q[st];
for(int i=last[x];i!=-1;i=a[i].next)
{
int y=a[i].y;
if(d[y]>d[x]+a[i].c)
{
d[y]=d[x]+a[i].c;
if(v[y]==false)
{
v[y]=true;
q[ed]=y;
ed++;
if(ed==n+1) ed=1;
}
}
}
v[x]=false;
st++;
if(st==n+1) st=1;
}
}
int main()
{
memset(last,-1,sizeof(last));
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);
}
spfa();
for(int i=1;i<=n;i++)
{
if(d[0]==d[i]) printf("2147483647 ");
else printf("%d ",d[i]);
}
return 0;
}
Dijkstra
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,head[100005],dis[100005];
struct edge{int v,w,nxt;}e[200005];
void addedge(int u,int v,int w)
{
static int cnt=0;
e[++cnt]=(edge){v,w,head[u]};
head[u]=cnt;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
void dijkstra(int s)
{
memset(dis,63,sizeof(dis));
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
int u=q.top().second,d=q.top().first;
q.pop();
if(d!=dis[u]) continue;
for(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(make_pair(dis[v],v));
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
}
dijkstra(s);
for(int i=1;i<=n;i++) printf("%d ",dis[i]);
return 0;
}
次短路
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
struct edge
{
int x,y,w;
}dd[maxn];
struct hh
{
int nex,to,dis;
}t[maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q1;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q2;//正反两次最短路，两个小根堆
int n,m,cnt=0,ans,mi;
int vis[maxn],d1[maxn],d2[maxn],head[maxn];
inline int read()
{
char kr=0;
char ls;
for(;ls>'9'||ls<'0';kr=ls,ls=getchar());
int xs=0;
for(;ls>='0'&&ls<='9';ls=getchar())
{
xs=xs*10+ls-48;
}
if(kr=='-') xs=0-xs;
return xs;
}
inline void add(int nex,int to,int w)
{
t[++cnt].nex=head[nex];
t[cnt].to=to;
t[cnt].dis=w;
head[nex]=cnt;
}
inline void dijkstra_first(int ww)
{
memset(d1,0x3f3f3f3f,sizeof(d1));
memset(vis,0,sizeof(vis));
q1.push(make_pair(0,ww));
d1[ww]=0;
while(!q1.empty())
{
int u=q1.top().second;
q1.pop();
if(vis[u]) continue;
vis[u]=1;
for(int v=head[u];v;v=t[v].nex)
{
if(d1[t[v].to]>d1[u]+t[v].dis&&!vis[t[v].to])
{
d1[t[v].to]=d1[u]+t[v].dis;
q1.push(make_pair(d1[t[v].to],t[v].to));
}
}
}
}
inline void dijkstra_second(int ww)
{
memset(d2,0x3f3f3f3f,sizeof(d2));
memset(vis,0,sizeof(vis));
q2.push(make_pair(0,ww));
d2[ww]=0;
while(!q2.empty())
{
int u=q2.top().second;
q2.pop();
if(vis[u]) continue;
vis[u]=1;
for(int v=head[u];v;v=t[v].nex)
{
if(d2[t[v].to]>d2[u]+t[v].dis&&!vis[t[v].to])
{
d2[t[v].to]=d2[u]+t[v].dis;
q2.push(make_pair(d2[t[v].to],t[v].to));
}
}
}
}//两次Dijkstra求正反最短路
int main()
{
n=read();m=read();
ans=999999;
mi=999999;
for(int i=1;i<=m;++i)
{
dd[i].x=read();dd[i].y=read();dd[i].w=read();
add(dd[i].x,dd[i].y,dd[i].w);
add(dd[i].y,dd[i].x,dd[i].w);
}
dijkstra_first(1);
dijkstra_second(n);
int minn=d1[n];
for(int i=1;i<=m;i++)
{
int x=dd[i].x,y=dd[i].y;
if(d1[x]+d2[y]>d1[y]+d2[x]) swap(x,y);
int s=d1[x]+d2[y];
if(s+dd[i].w==minn) continue;
ans=min(ans,s+dd[i].w);
}//第一点：不重走边
for(int i=1;i<=m;i++)
{
int x=dd[i].x,y=dd[i].y;
if(d1[x]+d2[y]>d1[y]+d2[x]) swap(x,y);
if(d1[x]+d2[y]+dd[i].w!=minn) continue;
mi=min(mi,dd[i].w);//找出最短路中最短的边
}//第二点：重走边
ans=min(ans,minn+mi*2);//取较小值
printf("%d\n",ans);
return 0;
}
KMP
#include<bits/stdc++.h>
using namespace std;
int kmp[1000005];
char a[1000005],b[1000005];
int main()
{
scanf("%s%s",a+1,b+1);
int la=strlen(a+1),lb=strlen(b+1),j;
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)
{
printf("%d\n",i-lb+1);
j=kmp[j];
}
}
for(int i=1;i<=lb;i++) printf("%d ",kmp[i]);
return 0;
}
欧拉路径
#include<bits/stdc++.h>
using namespace std;
vector<int> g[100005];
stack<int> st;
int in[100005],out[100005],del[100005];
void dfs(int now)
{
for(int i=del[now];i<g[now].size();i=del[now])
{
del[now]=i+1;
dfs(g[now][i]);
}
st.push(now);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].emplace_back(v);
in[v]++;out[u]++;
}
int s=1,c1=0,c2=0;
bool flag=1;
for(int i=1;i<=n;i++)
{
if(in[i]!=out[i]) flag=0;
if(out[i]-in[i]==1) c1++,s=i;
if(in[i]-out[i]==1) c2++;
}
if(!flag&&!(c1==1&&c2==1))
{
puts("No");
return 0;
}
for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
dfs(s);
while(!st.empty())
{
printf("%d ",st.top());
st.pop();
}
return 0;
}
LCA
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(),last='0';int s=0;
while(ch<'0'||ch>'9') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return last=='-'?-s:s;
}
inline void write(int x)
{
int n=0,buf[20];
do buf[n++]=x%10;while(x/=10);
while(n--) putchar(buf[n]+'0');
}
vector<int> graph[500005];
int lg[500005],fa[500005][20],dep[500005];
inline void dfs(int now,int father)
{
fa[now][0]=father;
dep[now]=dep[father]+1;
for(int i=1;i<=lg[dep[now]];i++) fa[now][i]=fa[fa[now][i-1]][i-1];
for(int i=0;i<graph[now].size();i++)
if(graph[now][i]!=father)
dfs(graph[now][i],now);
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
if(x==y) return x;
for(int k=lg[dep[x]]-1;k>=0;k--)
if(fa[x][k]!=fa[y][k])
{
x=fa[x][k];
y=fa[y][k];
}
return fa[x][0];
}
int main()
{
int n=read(),m=read(),s=read();
for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
for(int i=1;i<n;i++)
{
int x=read(),y=read();
graph[x].push_back(y);
graph[y].push_back(x);
}
dfs(s,0);
while(m--)
{
int x=read(),y=read();
write(lca(x,y));
putchar('\n');
}
return 0;
}
Tarjan+Kahn
#include<bits/stdc++.h>
using namespace std;
struct edge{int f,t,nex;}e[100005],ed[100005];
int n,m,dfn[10005],p[10005],dist[10005],head[10005],low[10005],in[10005],dfncnt,sum,s[10005],in_stack[10005],tp,scc[10005],sc,sz[10005],h[10005];
void insert(int x,int y)
{
e[++sum].nex=h[x];
e[sum].f=x;
e[sum].t=y;
h[x]=sum;
}
void tarjan(int u)
{
low[u]=dfn[u]=++dfncnt;
s[++tp]=u;
in_stack[u]=1;
for(int i=h[u];i;i=e[i].nex)
{
if(!dfn[e[i].t])
{
tarjan(e[i].t);
low[u]=min(low[u],low[e[i].t]);
}
else if(in_stack[e[i].t]) low[u]=min(low[u],low[e[i].t]);
}
if(dfn[u]==low[u])
{
int y;
while(y=s[tp--])
{
scc[y]=u;
in_stack[y]=0;
if(u==y) break;
p[u]+=p[y];
}
}
}
int kahn()
{
queue<int> q;
int tot=0;
for(int i=1;i<=n;i++)
if(scc[i]==i&&!in[i])
{
q.push(i);
dist[i]=p[i];
}
while (!q.empty())
{
int k=q.front();q.pop();
for (int i=head[k];i;i=ed[i].nex)
{
int v=ed[i].t;
dist[v]=max(dist[v],dist[k]+p[v]);
in[v]--;
if (in[v]==0) q.push(v);
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,dist[i]);
return ans;
}
int main()
{
int x,y,sh;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
insert(x,y);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(int i=1;i<=m;i++)
if (scc[e[i].f]!=scc[e[i].t])
{
ed[++sh].nex=head[scc[e[i].f]];
ed[sh].t=scc[e[i].t];
ed[sh].f=scc[e[i].f];
head[scc[e[i].f]]=sh;
in[scc[e[i].t]]++;
}
printf("%d",kahn());
return 0;
}
割点
#include<bits/stdc++.h>
using namespace std;
int n,m,num[100005],low[100005],inde,res;
bool vis[100005],flag[100005];
vector<int> edge[100005];
void tarjan(int u,int father)
{
vis[u]=1;
low[u]=num[u]=++inde;
int child=0;
for(int i=0;i<edge[u].size();i++)
{
int v=edge[u][i];
if(!vis[v])
{
child++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(father!=u&&low[v]>=num[u]&&!flag[u])
{
flag[u]=1;
res++;
}
}
else if(v!=father) low[u]=min(low[u],num[v]);
}
if(father==u&&child>=2&&!flag[u])
{
flag[u]=true;
res++;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edge[x].emplace_back(y);
edge[y].emplace_back(x);
}
for(int i=1;i<=n;i++)
if(!vis[i])
{
inde=0;
tarjan(i,i);
}
printf("%d\n",res);
for(int i=1;i<=n;i++)
if(flag[i])
printf("%d ",i);
return 0;
}
exgcd
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
char ch=getchar();int s=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
inline void write(int x)
{
int buf[20],n=0;
do buf[n++]=x%10;
while(x/=10);
while(n--) putchar(buf[n]+'0');
}
inline int exgcd(int a,int b,int &x,int &y)
{
int d=a;
if(!b) x=1,y=0;
else
{
d=exgcd(b,a%b,y,x);
y-=a/b*x;
}
return d;
}
signed main()
{
int T=read();
while(T--)
{
int a=read(),b=read(),c=read(),x,y,d=exgcd(a,b,x,y);
if(c%d) putchar('-'),putchar('1');
else
{
x*=c/d;y*=c/d;
int p=b/d,q=a/d,k;
if(x<0) k=ceil((1.0-x)/p),x+=p*k,y-=q*k;
else if(x>=0) k=(x-1)/p,x-=p*k,y+=q*k;
if(y>0)
{
write((y-1)/q+1),putchar(' ');
write(x),putchar(' ');
write((y-1)%q+1),putchar(' ');
write(x+(y-1)/q*p),putchar(' ');
write(y);
}
else
{
write(x),putchar(' ');
write(y+q*(int)ceil((1.0-y)/q));
}
}
putchar('\n');
}
return 0;
}
高斯消元
#include<bits/stdc++.h>
using namespace std;
double a[105][105];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)
scanf("%lf",&a[i][j]);
for(int i=1;i<=n;i++)
{
int maxx=i;
for(int j=i+1;j<=n;j++)
if(fabs(a[j][i])>fabs(a[maxx][i]))
maxx=j;
for(int j=1;j<=n+1;j++)
swap(a[i][j],a[maxx][j]);
if(!a[i][i])
{
puts("No Solution");
return 0;
}
for(int j=1;j<=n;j++)
if(j!=i)
{
double temp=a[j][i]/a[i][i];
for(int k=i+1;k<=n+1;k++)
a[j][k]-=a[i][k]*temp;
}
}
for(int i=1;i<=n;i++)
printf("%.2lf\n",a[i][n+1]/a[i][i]);
return 0;
}
树链剖分
#include <iostream>
#include <vector>
#define int long long
using namespace std;
vector<int> g[100005];
struct setment_tree {
int l, r, lc, rc, sum, lazy;
}tr[200005];
int a[100005], fa[100005], siz[100005], son[100005], top[100005], dep[100005], dfn[100005], rnk[100005];
int bt(int l, int r) {
static int trcnt = 0;
int pos = ++trcnt;
tr[pos].l = l;
tr[pos].r = r;
if (l == r) {
tr[pos].lc = tr[pos].rc = -1;
tr[pos].sum = a[rnk[l]];
} else {
tr[pos].lc = bt(l, l + r >> 1);
tr[pos].rc = bt((l + r >> 1) + 1, r);
tr[pos].sum = tr[tr[pos].lc].sum + tr[tr[pos].rc].sum;
}
tr[pos].lazy = 0;
return pos;
}
void add(int now, int l, int r, int x) {
tr[now].sum += x * (r - l + 1);
if (tr[now].l == l && tr[now].r == r) {
tr[now].lazy += x;
return;
}
add(tr[now].lc, tr[tr[now].lc].l, tr[tr[now].lc].r, tr[now].lazy);
add(tr[now].rc, tr[tr[now].rc].l, tr[tr[now].rc].r, tr[now].lazy);
tr[now].lazy = 0;
if (r <= tr[tr[now].lc].r)
add(tr[now].lc, l, r, x);
else if (l >= tr[tr[now].rc].l)
add(tr[now].rc, l, r, x);
else {
add(tr[now].lc, l, tr[tr[now].lc].r, x);
add(tr[now].rc, tr[tr[now].rc].l, r, x);
}
}
int query(int now, int l, int r) {
if (tr[now].l == l && tr[now].r == r)
return tr[now].sum;
add(tr[now].lc, tr[tr[now].lc].l, tr[tr[now].lc].r, tr[now].lazy);
add(tr[now].rc, tr[tr[now].rc].l, tr[tr[now].rc].r, tr[now].lazy);
tr[now].lazy = 0;
if (r <= tr[tr[now].lc].r)
return query(tr[now].lc, l, r);
else if (l >= tr[tr[now].rc].l)
return query(tr[now].rc, l, r);
else
return query(tr[now].lc, l, tr[tr[now].lc].r) + query(tr[now].rc, tr[tr[now].rc].l, r);
}
void dfs1(int now) {
son[now] = -1;
siz[now] = 1;
for (int i = 0; i < g[now].size(); i++) {
int &nxt = g[now][i];
if (nxt != fa[now]) {
fa[nxt] = now;
dep[nxt] = dep[now] + 1;
dfs1(nxt);
if (son[now] == -1 || siz[nxt] > siz[son[now]])
son[now] = nxt;
siz[now] += siz[nxt];
}
}
}
void dfs2(int now, int tp) {
static int dfncnt = 0;
top[now] = tp;
dfn[now] = ++dfncnt;
rnk[dfncnt] = now;
if (son[now] == -1)
return;
dfs2(son[now], tp);
for (int i = 0; i < g[now].size(); i++) {
int &nxt = g[now][i];
if (nxt != fa[now] && nxt != son[now])
dfs2(nxt, nxt);
}
}
void add_path(int x, int y, int z) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
add(1, dfn[top[x]], dfn[x], z);
x = fa[top[x]];
} else {
add(1, dfn[top[y]], dfn[y], z);
y = fa[top[y]];
}
}
if (dep[x] > dep[y])
add(1, dfn[y], dfn[x], z);
else
add(1, dfn[x], dfn[y], z);
}
int query_path(int x, int y) {
int sum = 0;
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
sum += query(1, dfn[top[x]], dfn[x]);
x = fa[top[x]];
} else {
sum += query(1, dfn[top[y]], dfn[y]);
y = fa[top[y]];
}
}
if (dep[x] > dep[y])
sum += query(1, dfn[y], dfn[x]);
else
sum += query(1, dfn[x], dfn[y]);
return sum;
}
void add_subtree(int x, int z) {
add(1, dfn[x], dfn[x] + siz[x] - 1, z);
}
int query_subtree(int x) {
return query(1, dfn[x], dfn[x] + siz[x] - 1);
}
signed main() {
int n, m, r, p;
cin >> n >> m >> r >> p;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
fa[r] = -1;
dfs1(r);
dfs2(r, r);
bt(1, n);
while (m--) {
int id, x, y, z;
cin >> id >> x;
if (id == 1) {
cin >> y >> z;
add_path(x, y, z);
} else if (id == 2) {
cin >> y;
cout << query_path(x, y) % p << endl;
} else if (id == 3) {
cin >> z;
add_subtree(x, z);
} else
cout << query_subtree(x) % p << endl;
}
return 0;
}
0 条评论
目前还没有评论...
