1.筛\(phi\)
\(logn\)求少数\(phi\)
inline int phi(R int x){
R int res=x,tmp=x;
for(R int i=2;i*i<=x;i++){
if(tmp%i==0)res=res*(i-1)/i;
while(tmp%i==0)tmp/=i;
}
if(tmp>1)res=res*(tmp-1)/tmp;
return res;
}
线性求\(phi\)
inline void getphi(R int n){
vis[1]=0;
for(R int i=2;i<=n;i++){
if(!vis[i]){
prime[++tot]=i;
phi[i]=i-1;
}
for(R int j=1;j<=tot&&i*prime[j]<=n;j++){
vis[prime[j]*i]=1;
if(i%prime[j]==0){
phi[prime[j]*i]=phi[i]*prime[j];break;
}
else phi[prime[j]*i]=phi[i]*(priem[j]-1);
}
}
}
线性筛约数个数和约数和
//num[i] 表示i的最小质因子出现次数
inline void get_d(){
d[1]=1;num[1]=1;
for(R int i=2;i<=n;i++){
if(!vis[i]){
prime[++tot]=i;
d[i]=2;num[i]=1;
}
for(R int j=1;j<=tot&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
num[i*prime[j]]=num[i]+1;
d[i*prime[j]]=d[i]/num[i*prime[j]]*(num[i*prime[j]]+1);
break;
}
d[prime[j]*i]=d[i]*(1+1);
num[prime[j]*i]=1;
}
}
}
//sp[i] 表示i的(1+p[1]+p[1]^1+...+p[1]^a[1])
inline void get_sd(){
sd[1]=1;sp[1]=1;
for(R int i=2;i<=n;i++){
if(!vis[i]){
prime[++tot]=i;
sd[i]=i+1;
sp[i]=i+1;
}
for(R int j=1;j<=tot&&prime[j]*i<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
sp[i*prime[j]]=sp[i]*prime[j]+1;
sd[i*prime[j]]=sd[i]/sp[i]*sp[i*prime[j]];
break;
}
sd[i*prime[j]]=sd[i]*sd[prime[j]];
sp[i*prime[j]]=prime[j]+1;
}
}
}
2.ST表
inline void pre(){
mn[0]=-1;
for(R int i=1;i<=n;i++){
mn[i]=((i&(i-1))==0)? mn[i-1]+1:mn[i-1];
stmax[i][0]=a[i];
}
for(R int j=1;j<=mn[n];j++)
for(R int i=1;i+(1<<j)-1<=n;i++)
stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
}
inline int getmax(R int l,R int r){
R int k=mn[r-l+1];
return max(stmax[l][k],stmax[r-(1<<k)+1][k]);
}
int main(){
read(n);read(m);
for(R int i=1;i<=n;i++)read(a[i]);
pre();
for(R int i=1;i<=m;i++){
read(l);read(r);
printf("%d\n",getmax(l,r));
}
return 0;
}
3.高斯消元
read(n);
for(R int i=1;i<=n;i++)
for(R int j=1;j<=n+1;j++)
scanf("%lf",&mp[i][j]);
for(R int i=1;i<=n;i++){
R int mx=i;
for(R int j=i+1;j<=n;j++)
if(fabss(mp[mx][i])<fabss(mp[j][i]))mx=i;
if(mx!=i)swap(mp[mx],mp[i]);
if(fabss(mp[i][i])>eps){
R double div=mp[i][i];
for(R int j=i;j<=n+1;j++)
mp[i][j]/=div;
for(R int j=1;j<=n;j++){
if(i==j)continue;
div=mp[j][i];
for(R int k=i;k<=n+1;k++)
mp[j][k]-=div*mp[i][k];
}
}
}
for(R int i=1;i<=n;i++){
R int cnt=1;
while(fabss(mp[i][cnt])<eps&&cnt<=n+1)cnt++;
if(cnt==n+1)pd_nojie=1;
if(cnt>n+1)pd_wuqiong=1;
}
if(pd_nojie||pd_wuqiong){
printf("No Solution\n");
return 0;
}
ans[n]=mp[n][n+1];
for(R int i=n-1;i>=1;i--){
ans[i]=mp[i][n+1];
for(R int j=i+1;j<=n;j++)
ans[i]-=mp[i][j]*ans[j];
}
for(R int i=1;i<=n;i++)
printf("%.2lf\n",ans[i]);
4.悬线法
for(R int i=1;i<=n;i++){
for(R int j=1;j<=m;j++){
read(mp[i][j]);
up[i][j]=1;
l[i][j]=r[i][j]=j;
}
}
for(R int i=1;i<=n;i++)
for(R int j=2;j<=m;j++)
if(mp[i][j]!=mp[i][j-1])
l[i][j]=l[i][j-1];
for(R int i=1;i<=n;i++)
for(R int j=m-1;j>=1;j--)
if(mp[i][j]!=mp[i][j+1])
r[i][j]=r[i][j+1];
for(R int i=1;i<=n;i++){
for(R int j=1;j<=m;j++){
if(i>1&&mp[i][j]!=mp[i-1][j]){
l[i][j]=max(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
up[i][j]=up[i-1][j]+1;
}
R int a=r[i][j]-l[i][j]+1;
R int b=min(a,up[i][j]);
ans1=max(ans1,b*b);
ans2=max(ans2,a*up[i][j]);
}
}
5.nim游戏
tmp=0;
read(n);
for(R int i=1;i<=n;i++)
read(x),tmp^=x;
if(tmp)printf("Yes\n");
else printf("No\n");
6.线段树双lazy
#define ls(o) o<<1
#define rs(o) o<<1|1
#define up(o) t[o]=(t[ls(o)]+t[rs(o)])%mod
inline void build(R int o,R int l,R int r){
mul[o]=1;add[o]=0;
if(l==r){
t[o]=a[l]%mod;
return;
}
R int mid=(l+r)>>1;
build(ls(o),l,mid);
build(rs(o),mid+1,r);
up(o);
}
inline void push_down(R int o,R int l,R int r){
if(mul[o]!=1){
t[ls(o)]=(mul[o]*t[ls(o)])%mod;
t[rs(o)]=(mul[o]*t[rs(o)])%mod;
add[ls(o)]=(add[ls(o)]*mul[o])%mod;
add[rs(o)]=(add[rs(o)]*mul[o])%mod;
mul[ls(o)]=(mul[o]*mul[ls(o)])%mod;
mul[rs(o)]=(mul[o]*mul[rs(o)])%mod;
mul[o]=1;
}
R int mid=(l+r)>>1;
if(add[o]){
t[ls(o)]=(t[ls(o)]+add[o]*(mid-l+1))%mod;
t[rs(o)]=(t[rs(o)]+add[o]*(r-mid))%mod;
add[ls(o)]=(add[ls(o)]+add[o])%mod;
add[rs(o)]=(add[rs(o)]+add[o])%mod;
add[o]=0;
}
}
inline void update_add(R int o,R int nl,R int nr,R int l,R int r,R ll k){
if(nl<=l&&nr>=r){
t[o]=(t[o]+(r-l+1)*k)%mod;
add[o]=(add[o]+k)%mod;
return;
}
push_down(o,l,r);
R int mid=(l+r)>>1;
if(nl<=mid)update_add(ls(o),nl,nr,l,mid,k);
if(nr>mid)update_add(rs(o),nl,nr,mid+1,r,k);
up(o);
}
inline void update_mul(R int o,R int nl,R int nr,R int l,R int r,R ll k){
if(nl<=l&&nr>=r){
t[o]=t[o]*k%mod;
add[o]=add[o]*k%mod;
mul[o]=mul[o]*k%mod;
return;
}
push_down(o,l,r);
R int mid=(l+r)>>1;
if(nl<=mid)update_mul(ls(o),nl,nr,l,mid,k);
if(nr>mid)update_mul(rs(o),nl,nr,mid+1,r,k);
up(o);
}
最大子段和
struct node{
int lm,rm,sm,sum;
void init(int x){
lm=rm=sm=sum=x;
}
friend node operator + (node a,node b){
node ans;
ans.sum=a.sum+b.sum;
ans.sm=max(max(a.sm,b.sm),a.rm+b.lm);
ans.lm=max(a.lm,a.sum+b.lm);
ans.rm=max(b.rm,b.sum+a.rm);
return ans;
}
}t[N];
7.有理数取余（附加快速幂）
char A[N],B[N];
ll a,b;
inline ll ksm(R ll x,R ll y){
ll res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int main(){
scanf("%s%s",A+1,B+1);
R int n=strlen(A+1);
R int m=strlen(B+1);
for(R int i=1;i<=n;i++)
a=(a*10+A[i]-'0')%mod;
for(R int i=1;i<=m;i++)
b=(b*10+B[i]-'0')%mod;
if(!b)printf("Angry!\n");
else printf("%lld\n",a*ksm(b,mod-2)%mod);
return 0;
}
8.割点（割顶）
inline void tarjan(R int x){
R int rd=0;
dfn[x]=low[x]=++num;
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(!dfn[xx]){
fa[xx]=fa[x];
tarjan(xx);
low[x]=min(low[x],low[xx]);
if(low[xx]>=dfn[x]&&x!=fa[x])cut[x]=1;
if(x==fa[x])rd++;
}
low[x]=min(low[x],dfn[xx]);
}
if(x==fa[x]&&rd>=2)cut[x]=1;
}
int main(){
read(n);read(m);
for(R int i=1,u,v;i<=m;i++)
read(u),read(v),add(u,v),add(v,u);
for(R int i=1;i<=n;i++)fa[i]=i;
for(R int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
R int now=0;
for(R int i=1;i<=n;i++)
if(cut[i])ans[++now]=i;
printf("%d\n",now);
for(R int i=1;i<=now;i++)printf("%d ",ans[i]);
return 0;
}
9.缩点
inline void tarjan(R int x){
vis[x]=1;
sta[++top]=x;
dfn[x]=low[x]=++num;
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(!dfn[xx]){
tarjan(xx);
low[x]=min(low[x],low[xx]);
}
else if(vis[xx])low[x]=min(low[x],dfn[xx]);
}
if(dfn[x]==low[x]){
cnt++;
R int now=-1;
while(now!=x){
now=sta[top];
top--;
col[now]=cnt;
sum[cnt]+=val[now];
vis[now]=0;
}
}
}
10.裴蜀定理
scanf("%d",&n);
scanf("%d",&ans);
ans=abs(ans);
for(R int i=2;i<=n;i++){
scanf("%d",&x);
ans=gcd(ans,abs(x));
}
printf("%d",ans);
11.负环
inline bool spfa(R int s){
queue<int> q;
for(R int i=1;i<=n;i++)dist[i]=INF,vis[i]=0;
q.push(s);vis[s]=1;dist[s]=0;cnt[s]++;
while(!q.empty()){
R int x=q.front();q.pop();vis[x]=0;
cnt[x]++;
if(cnt[x]>=n)return 1;
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(dist[xx]>dist[x]+edge[i].dis){
dist[xx]=dist[x]+edge[i].dis;
if(!vis[xx]){
vis[xx]=1;
q.push(xx);
}
}
}
}
return 0;
}
11+.最短路计数
while(!q.empty()){
int x=q.front();q.pop();vis[x]=0;
for(int i=h[x];i;i=edge[i].nex){
int xx=edge[i].to;
if(dist[xx]==dist[x]+edge[i].dis){
ans[xx]+=ans[x];ans[xx]%=mod;
if(!vis[xx]){
vis[xx]=1;
q.push(xx);
}
}
if(dist[xx]>dist[x]+edge[i].dis){
dist[xx]=dist[x]+edge[i].dis;
ans[xx]=ans[x]%mod;
if(!vis[xx]){
vis[xx]=1;
q.push(xx);
}
}
}
12.Dij堆优化
struct HeapNode{
int u;ll d;
friend bool operator < (const HeapNode &a,const HeapNode &b){
return a.d>b.d;
}
};
priority_queue<HeapNode> q;
inline void Dij(R int s){
for(R int i=1;i<=n;i++)dist[i]=INF,vis[i]=0;
q.push((HeapNode){s,0});dist[s]=0;
while(!q.empty()){
R int x=q.top().u;q.pop();
if(vis[x])continue;vis[x]=1;
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(dist[xx]>dist[x]+edge[i].dis){
dist[xx]=dist[x]+edge[i].dis;
q.push((HeapNode){xx,dist[xx]});
}
}
}
}
13.manacher
scanf("%s",a);
n=strlen(a);
for(R int i=0;i<n;i++)s[i*2]='#',s[i*2+1]=a[i];
n=2*n+1;s[n-1]='#';
rl[0]=1;
for(R int i=0;i<n;i++){
if(i<=maxright)rl[i]=min(rl[center*2-i],maxright-i);
else rl[i]=1;
while(s[i+rl[i]]==s[i-rl[i]]&&i+rl[i]<n&&i-rl[i]>=0)rl[i]++;
if(i+rl[i]-1>maxright)maxright=i+rl[i]-1,center=i;
}
for(R int i=0;i<n;i++)ans=max(ans,rl[i]-1);
14.KMP
scanf("%s%s",s1+1,s2+1);
l1=strlen(s1+1);
l2=strlen(s2+1);
R int j=0;
nex[1]=0;
for(R int i=2;i<=l2;i++){
while(j&&s2[i]!=s2[j+1])j=nex[j];
if(s2[i]==s2[j+1])j++;
nex[i]=j;
}
j=0;
for(R int i=1;i<=l1;i++){
while(j&&s1[i]!=s2[j+1])j=nex[j];
if(s1[i]==s2[j+1])j++;
if(j==l2){
printf("%d\n",i-l2+1);
j=nex[j];
}
}
15.线性求逆元
read(n);read(mod);
a[1]=1;
for(R int i=2;i<=n;i++)
a[i]=(((-mod/i)*a[mod%i])%mod+mod)%mod;
for(R int i=1;i<=n;i++)printf("%lld\n",a[i]);
阶乘及阶乘逆元
fac[0]=fac[1]=1;
for(R int i=2;i<=n;i++)fac[i]=(fac[i-1]*i)%mod;
inv[n]=ksm(fac[n],mod-2);
for(R int i=n-1;i>=0;i--)inv[i]=((i+1)*inv[i+1])%mod;
16.prim堆优化
struct node{
int v,w;
friend bool operator < (const node &a,const node &b){
return a.w>b.w;
}
};
vector<node> t[N];
bool vis[N];
ll ans;
inline void prim(){
priority_queue<node> q;
while(!q.empty())q.pop();
ans=0;
for(R int i=1;i<=n;i++)vis[i]=0;
for(R int i=0;i<(int)t[1].size();i++)
q.push(t[1][i]);
vis[1]=1;
R int bian=n-1;
R node x;
while(bian--){
x=q.top();q.pop();
if(vis[x.v])
while(vis[x.v])
x=q.top(),q.pop();
ans=ans+x.w;
vis[x.v]=1;
for(R int i=0;i<t[x.v].size();i++)
if(!vis[t[x.v][i].v])
q.push(t[x.v][i]);
}
}
int main(){
read(n);read(m);node x;
for(R int i=1,u,v,w;i<=m;i++){
read(u);read(v);read(w);
x.v=v;x.w=w;
t[u].push_back(x);
x.v=u;
t[v].push_back(x);
}
prim();
printf("%lld\n",ans);
return 0;
}
17.树上差分
inline void dfs(R int x,R int f){
dep[x]=dep[f]+1;fa[x][0]=f;
for(R int i=1;(1<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(xx==f)continue;
dfs(xx,x);
}
}
inline int lca(R int x,R int y){
if(dep[x]>dep[y])swap(x,y);
for(R int i=20;i>=0;i--)
if(dep[x]<=dep[y]-(1<<i))y=fa[y][i];
if(x==y)return x;
for(R int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline void search(R int x){
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(xx==fa[x][0])continue;
search(xx);
cnt[x]+=cnt[xx];
}
}
//边差分
cnt[x]++;cnt[y]++;
cnt[LCA]-=2;
//点差分
cnt[x]++;cnt[y]++;
cnt[LCA]--;cnt[fa[LCA][0]]--;
18.并查集
inline int find(R int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}
inline void merge(R int x,R int y){fa[find(x)]=find(y);}
19.左偏堆
inline int merge(R int x,R int y){
if(x==0||y==0)return x+y;
if(val[x]>val[y]||(val[x]==val[y]&&x>y))swap(x,y);
ch[x][1]=merge(ch[x][1],y);
fa[ch[x][1]]=x;
if(dep[ch[x][0]]<dep[ch[x][1]])swap(ch[x][0],ch[x][1]);
dep[x]=dep[ch[x][1]]+1;
return x;
}
inline int find(R int x){
while(fa[x])x=fa[x];
return x;
}
inline void pop(R int x){
val[x]=-1;
fa[ch[x][0]]=fa[ch[x][1]]=0;
merge(ch[x][0],ch[x][1]);
}
int main(){
read(n);read(m);
dep[0]=-1;
for(R int i=1;i<=n;i++)read(val[i]);
while(m--){
R int opt,x,y,xx,yy;
read(opt);
if(opt==1){
read(x);read(y);
if(val[x]==-1||val[y]==-1)continue;
if(x==y)continue;
xx=find(x),yy=find(y);
merge(xx,yy);
}
else{
read(x);
if(val[x]==-1)puts("-1");
else{
y=find(x);
printf("%d\n",val[y]);
pop(y);
}
}
}
return 0;
}
20.最小瓶颈路
struct MST{
int u,v,w;
friend bool operator < (const MST &a,const MST &b){
return a.w<b.w;
}
}t[N];
inline void ins(R int u,R int v,R int w){
t[++num].u=u;
t[num].v=v;
t[num].w=w;
}
struct node{
int nex,to,dis;
}edge[N<<1];
inline void add(R int u,R int v,R int w){
edge[++tot].nex=h[u];
edge[tot].to=v;
edge[tot].dis=w;
h[u]=tot;
}
inline int find(R int x){return fat[x]==x?fat[x]:fat[x]=find(fat[x]);}
inline void dfs(R int x,R int f,R int g){
dep[x]=dep[f]+1;
fa[x][0]=f;
mx[x][0]=g;
for(R int i=1;(1<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1],
mx[x][i]=max(mx[x][i-1],mx[fa[x][i-1]][i-1]);
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(xx==f)continue;
dfs(xx,x,edge[i].dis);
}
}
inline int get_ans(R int x,R int y){
R int res=0;
if(dep[x]>dep[y])swap(x,y);
for(R int i=20;i>=0;i--)
if(dep[x]<=dep[y]-(1<<i))
res=max(res,mx[y][i]),y=fa[y][i];
if(x==y)return res;
for(R int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i])
res=max(res,max(mx[x][i],mx[y][i])),
x=fa[x][i],y=fa[y][i];
res=max(res,max(mx[x][0],mx[y][0]));
return res;
}
int main(){
read(n);read(m);
for(R int i=1;i<=n;i++)fat[i]=i;
for(R int i=1,u,v,w;i<=m;i++)
read(u),read(v),read(w),ins(u,v,w);
sort(t+1,t+1+m);
for(R int i=1;i<=m;i++){
R int x=find(t[i].u);
R int y=find(t[i].v);
if(x!=y){
fat[x]=y;
add(x,y,t[i].w);
add(y,x,t[i].w);
}
}
dfs(1,0,0);
read(q);
while(q--){
R int x,y;
read(x);read(y);
if(find(x)!=find(y))puts("impossible");
else printf("%d\n",get_ans(x,y));
}
return 0;
}
21.矩阵乘法(Fib)
struct Mar{
ll a[10][10];
Mar(){memset(a,0,sizeof(a));}
};
Mar cheng(Mar a,Mar b){
Mar c;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
return c;
}
Mar ksm(Mar x,ll y){
Mar res=e;
while(y){
if(y&1)res=cheng(res,x);
x=cheng(x,x);
y>>=1;
}
return res;
}
22.中国剩余定理
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;y=0;return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
ll msc(ll x,ll y,ll mod){
ll ans=0;
while(y){
if(y&1)ans=(ans+x)%mod;
x=x*2%mod;
y>>=1;
}
return ans;
}
void China(){
for(int i=1;i<=n;i++)N*=b[i];
ll x,y;//所求的X是N/b[i]*y
for(int i=1;i<=n;i++){
ll m=N/b[i];
exgcd(b[i],m,x,y);
y=(y+b[i])%b[i];
X=(X+msc(msc(a[i],m,N),y,N))%N;
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
China();
printf("%lld",(X+N)%N);
return 0;
}
23数列分块（余数求和）
int main(){
read(n);read(k);
ans=n*k;
for(R ll l=1,r;l<=n;l=r+1){
ll s=k/l;
if(s!=0)r=min(k/s,n);
else r=n;
ans-=s*(r-l+1)*(l+r)/2;
}
printf("%lld",ans);
return 0;
}
24.线性基
void insert(long long x){
for(int i=63;i>=0;i--){
if(x&(1LL<<i)){
if(!p[i]){
p[i]=x;break;
}
else x^=p[i];
}
}
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
insert(a[i]);
}
for(int i=63;i>=0;i--){
if((ans^p[i])>ans)ans^=p[i];
}
printf("%lld\n",ans);
return 0;
}
25.逆序对
inline void msort(R int l,R int r){
if(l==r)return;
R int mid=(l+r)>>1;
msort(l,mid);msort(mid+1,r);
R int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
if(a[i]<=a[j])
b[k]=a[i],k++,i++;
else
b[k]=a[j],k++,j++,ans+=(mid-i+1);
while(i<=mid)
b[k]=a[i],i++,k++;
while(j<=r)
b[k]=a[j],j++,k++;
for(R int i=l;i<=r;i++)
a[i]=b[i];
}
26.高精
struct big{
int a[N];
}x,y,ed,one;
big operator + (big a,big b){
big c;
memset(c.a,0,sizeof(c.a));
int len=max(a.a[0],b.a[0]);
for(int i=1;i<=len;i++)c.a[i]=a.a[i]+b.a[i];
for(int i=1;i<=len;i++)
if(c.a[i]>=10){
c.a[i+1]+=c.a[i]/10;
c.a[i]%=10;
}
if(c.a[len+1])len++;
c.a[0]=len;
return c;
}
big operator - (big a,big b){
big c;
memset(c.a,0,sizeof(c.a));
int len=max(a.a[0],b.a[0]);
for(R int i=1;i<=len;i++)c.a[i]=a.a[i]-b.a[i];
for(R int i=1;i<=len;i++){
if(c.a[i]<0){
c.a[i+1]--;
c.a[i]+=10;
}
}
while(!c.a[len])len--;
c.a[0]=len;
return c;
}
big operator / (big a,int x){
big c;
memset(c.a,0,sizeof(c.a));
int len=0,tmp=0;
for(R int i=a.a[0];i>=1;i--){
tmp=tmp*10+a.a[i];
if(tmp>=x){
c.a[++len]=tmp/x;
tmp%=x;
}
else c.a[++len]=0;
}
for(R int i=1;i<=len;i++)w[i]=c.a[len-i+1];
for(R int i=1;i<=len;i++)c.a[i]=w[i];
c.a[0]=len;
return c;
}
inline void print(big x){
if(x.a[0]==0)printf("0");
for(int i=x.a[0];i>=1;i--)
printf("%d",x.a[i]);
}
27.二分图
inline int find(R int x){
for(R int i=1;i<=n;i++){
if(!vis[i]&&mp[x][i]){
vis[i]=1;
if(!to[i]||find(to[i])){
to[i]=x;
return 1;
}
}
}
return 0;
}
for(R int i=1;i<=m;i++){
memset(vis,0,sizeof(vis));
if(find(i))ans++;
}
28.模拟退火
void SA(){
double T = 2333.0;
double xx = x,yy = y;
while(T > 1e-16）{
double vx = xx + T * (rand() * 2 - RAND_MAX),vy = yy + T * (rand() * 2 - RAND_MAX);
double res = calc(vx,vy) - calc(xx,yy);
if(res < 0){
x = xx = vx,y = yy = vy;
}
else if(exp(-res/ T) * RAND_MAX > rand())xx = x,yy = y;
T = T * 0.9982;
}
}
29.Trie树
void insert(char *s,int rt){
for(int i=0;s[i];i++){
int v=s[i]-'a';
if(!trie[rt][v]) trie[rt][v]=++tot;
rt=trie[rt][v];
}
}
int find(char *s,int rt){
for(int i=0;s[i];i++){
int v=s[i]-'a';
if(!trie[rt][v])return 0;
rt=trie[rt][v];
}
sum[rt]++;
return sum[rt];
}
01 Trie树
inline void insert(R int x,R int rt){
for(R int i=1<<30;i;i>>=1){
bool c=x&i;
if(!trie[rt][c])trie[rt][c]=++num;
rt=trie[rt][c];
}
}
inline int query(R int x,R int rt){
R int ans=0;
for(R int i=1<<30;i;i>>=1){
bool c=x&i;
if(trie[rt][c^1])ans+=i,rt=trie[rt][c^1];
else rt=trie[rt][c];
}
return ans;
}
30.LCS && LIS
//LCS
for(R int i=1;i<=n;i++)
for(R int j=1;j<=m;j++)
dp[i][j]=max(dp[i-1][j],max(dp[i][j-1],dp[i-1][j-1]+(a[i]==b[j])));
printf("%d\n",dp[n][m]);
//LIS
read(n);read(k);
for(R int i=1;i<=n;i++)read(b[i]);
for(R int i=1;i<=k-1;i++)
if(b[i]<b[k])a[++tot]=b[i];
a[++tot]=b[k];
for(R int i=k+1;i<=n;i++)
if(b[i]>b[k])a[++tot]=b[i];
low[1]=a[1];ans=1;
for(R int i=2;i<=tot;i++){
if(a[i]>=low[ans])low[++ans]=a[i];
else low[lower_bound(low+1,low+1+ans,a[i])-low]=a[i];
}
printf("%d\n",ans);
//统计方案数
for(R int i=1;i<=n;i++){
dp[i]=1;
for(R int j=1;j<i;j++)
if(a[j]>a[i])dp[i]=max(dp[i],dp[j]+1);
ans=max(ans,dp[i]);
}
for(R int i=1;i<=n;i++){
if(dp[i]==1)cnt[i]=1;
for(R int j=1;j<i;j++){
if(a[j]==a[i]&&dp[i]==dp[j])cnt[j]=0;
if(a[j]>a[i]&&dp[i]==dp[j]+1)cnt[i]+=cnt[j];
}
}
for(R int i=1;i<=n;i++)pos+=cnt[i]*(dp[i]==ans);
printf("%d %d\n",ans,pos);
31.对顶堆
priority_queue<int> q1;
priority_queue<int,vector<int>,greater<int> > q2;
inline void ins(R int x){
if(x>q1.top())q2.push(x);
else q1.push(x);
}
inline void query(){
int pos=q1.size()+q2.size();
while(abss(q1.size()-q2.size())>1){
if(q1.size()>q2.size())q2.push(q1.top()),q1.pop();
else q1.push(q2.top()),q2.pop();
}
if(pos&1){
if(q1.size()>q2.size())printf("%d\n",q1.top());
else printf("%d\n",q2.top());
}
else {
printf("%d\n",min(q1.top(),q2.top()));
}
}
32.康拓展开
inline ll contor(ll c[]){
ll ans=0;
for(R int i=1;i<=n;i++){
ll sum=0;
for(R int j=i+1;j<=n;j++)
if(c[i]>c[j])sum++;
ans+=sum*fac[n-i];
}
return ans+1;
}
inline ll revcontor(ll x){
memset(vis,0,sizeof(vis));
x--;ll j;
for(R int i=1;i<=n;i++){
ll t=x/fac[n-i];
for(j=1;j<=n;j++){
if(!vis[j]){
if(!t)break;
t--;
}
}
printf("%lld ",j);
vis[j]=1;
x%=fac[n-i];
}
printf("\n");
}
33.树链剖分
//---------------------线段树---------------------------
void build(int o,int l,int r){
if(l==r){
t[o]=a[tid[l]]; //guo
tag[o]=0;
return;
}
int mid=(l+r)>>1;
build(ls(o),l,mid);
build(rs(o),mid+1,r);
up(o);
}
void chuan(int o,int l,int r,int k){
tag[o]+=k;
t[o]+=k*(r-l+1);
t[o]%=mod;
}
void push_down(int o,int l,int r){
int mid=(l+r)>>1;
chuan(ls(o),l,mid,tag[o]);
chuan(rs(o),mid+1,r,tag[o]);
tag[o]=0;
up(o);
}
void change(int o,int nl,int nr,int l,int r,int k){
if(nl<=l&&nr>=r){
t[o]+=k*(r-l+1);
t[o]%=mod;
tag[o]+=k;
tag[o]%=mod;
return;
}
push_down(o,l,r);
int mid=(l+r)>>1;
if(nl<=mid)change(ls(o),nl,nr,l,mid,k);
if(nr>mid)change(rs(o),nl,nr,mid+1,r,k);
up(o);
}
int query(int o,int nl,int nr,int l,int r){
int ans=0;
if(nl<=l&&nr>=r)return t[o]%mod;
int mid=(l+r)>>1;
push_down(o,l,r);
if(nl<=mid)ans=(ans+query(ls(o),nl,nr,l,mid))%mod;
if(nr>mid) ans=(ans+query(rs(o),nl,nr,mid+1,r))%mod;
return ans%mod;
}
//---------------------线段树---------------------------
struct node{
int nex,to;
}edge[N<<1];
void add(int u,int v){
edge[++tot].nex=h[u];
edge[tot].to=v;
h[u]=tot;
}
//求 fa,dep,size,son(重儿子)
void dfs1(int x,int f,int depth){
fa[x]=f;dep[x]=depth;siz[x]=1;
for(int i=h[x];i;i=edge[i].nex){
int xx=edge[i].to;
if(dep[xx])continue;
dfs1(xx,x,depth+1);
siz[x]+=siz[xx];
if(son[x]==-1||siz[xx]>siz[son[x]])son[x]=xx;
}
}
//求 dfn,tid,top;
void dfs2(int x,int tp){
dfn[x]=++num;tid[num]=x;top[x]=tp;
if(son[x]==-1)return;
dfs2(son[x],tp);
for(int i=h[x];i;i=edge[i].nex){
int xx=edge[i].to;
if(dfn[xx])continue;
dfs2(xx,xx);
}
}
int ask_path(int x,int y){
int ans=0;
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]>dep[fy]){
ans+=query(1,dfn[fx],dfn[x],1,n);
ans%=mod;
x=fa[fx];
}
else {
ans+=query(1,dfn[fy],dfn[y],1,n);
ans%=mod;
y=fa[fy];
}
fx=top[x];fy=top[y];
}
if(dfn[x]>dfn[y])swap(x,y);
ans+=query(1,dfn[x],dfn[y],1,n);
ans%=mod;
return ans%mod;
}
void update(int x,int y,int z){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]>dep[fy]){
change(1,dfn[fx],dfn[x],1,n,z);
x=fa[fx];
}
else {
change(1,dfn[fy],dfn[y],1,n,z);
y=fa[fy];
}
fx=top[x];fy=top[y];
}
if(dfn[x]>dfn[y])swap(x,y);
change(1,dfn[x],dfn[y],1,n,z);
}
//query(1,dfn[x],dfn[x]+siz[x]-1,1,n)子树操作
34.倍增Floyed
struct Mar{
ll a[N][N];
Mar(){memset(a,0x3f,sizeof(a));}
};
Mar e,ans;
Mar cheng(R Mar a,R Mar b){
Mar c;
for(R int k=1;k<=tot;k++)
for(R int i=1;i<=tot;i++)
for(R int j=1;j<=tot;j++)
c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);
return c;
}
Mar ksm(R Mar x,ll y){
ans=x;
while(y){
if(y&1)ans=cheng(ans,x);
x=cheng(x,x);
y>>=1;
}
}
int main(){
read(n);read(m);read(s);read(t);
for(R int i=1,w,u,v;i<=m;i++){
read(w);read(u);read(v);
if(!vis[u])vis[u]=++tot;
if(!vis[v])vis[v]=++tot;
e.a[vis[u]][vis[v]]=e.a[vis[v]][vis[u]]=w;
}
ksm(e,n-1);
printf("%lld\n",ans.a[vis[s]][vis[t]]);
return 0;
}
35.A*（K短路）
int n,m,s,t,k,tot,ans;
int h1[M],h2[M];
struct bian{
int nex,to,val;
}edge[M],E[M];
struct node{
int f;//f=g+dist 估价函数
int g;//到当前点的路径长度
int from;
bool operator < (node a)const {
if(a.f==f)return g>a.g;
return f>a.f;
}
};
void add(int u,int v,int w){
edge[++tot].nex=h1[u];
edge[tot].to=v;
edge[tot].val=w;
h1[u]=tot;
E[tot].nex=h2[v];
E[tot].to=u;
E[tot].val=w;
h2[v]=tot;
}
struct HeapNode{
int u,d;
bool operator < (const HeapNode & b) const {return d>b.d;}
};
int dist[M];
bool vis[M];
priority_queue<HeapNode> Q;
void dij(int s){
for(int i=1;i<=n;i++)dist[i]=INF;
dist[s]=0; Q.push((HeapNode){s,0});
while(Q.size()){
int x=Q.top().u;Q.pop();
if(vis[x])continue; vis[x]=1;
for(int i=h2[x];i;i=E[i].nex){
int xx=E[i].to;
if(dist[xx]>dist[x]+E[i].val){
dist[xx]=dist[x]+E[i].val;
Q.push( (HeapNode){xx,dist[xx]});
}
}
}
}
int A_star(int s,int t,int k){
if(s==t) return 0; //起点即为终点
if(dist[s]==INF)return -1; //起点无联通
priority_queue<node> q; //优先队列搜索
int cnt=0; //记录第X短路
node tmp={0,0,0},to={0,0,0};
tmp.from=s;
tmp.f=tmp.g+dist[tmp.from];//估价函数
q.push(tmp);
while(!q.empty()){
tmp=q.top();
q.pop();
if(tmp.from==t) cnt++; //到达终点
if(cnt==k)return tmp.g;//现在已经是第K短路
for(int i=h1[tmp.from];i;i=edge[i].nex){
to.from=edge[i].to;
to.g=tmp.g+edge[i].val;
to.f=to.g+dist[to.from];
q.push(to);
}
}
return -1;
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++){
int u,v,w;
u=read();v=read();w=read();
add(u,v,w);
}
s=read();t=read();k=read();
dij(t); //反向边跑最短路
ans=A_star(s,t,k);
printf("%d",ans);
return 0;
}
end.对拍
@echo off
:loop
echo noip2018 rp++
data.exe>data.txt
a.exe<data.txt>a.txt
b.exe<data.txt>b.txt
fc a.txt b.txt
if not errorlevel 1 goto loop
pause
goto loop
ex
next_permutation(a+1,a+1+n);