模板复习计划

2016.04.13 14:57 Wed | 254次阅读 | 旧日oi | 固定链接 | 源码

date: 2016-04-23 13:03
status: public

title: 模板复习计划

Suffix_Array-倍增

uoj35

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n;
int a[N];
char s[N];
int sa[N<<1],rk[N<<1],h[N];
void get_sa(int lim)
{
    static int SA[N<<1],RK[N<<1];
    for(int i=1;i<=n;i++) h[a[i]]++;
    for(int i=1;i<=lim;i++) h[i]+=h[i-1];
    for(int i=1;i<=n;i++) sa[h[a[i]]--]=i;
    for(int i=1;i<=n;i++) rk[sa[i]]=rk[sa[i-1]]+(a[sa[i]]!=a[sa[i-1]]);
    for(int k=1;k<=n;k<<=1)
    {
        for(int i=1;i<=n;i++) h[rk[sa[i]]]=i;
        for(int i=n;i;i--) if(sa[i]>k) SA[h[rk[sa[i]-k]]--]=sa[i]-k;
        for(int i=n-k+1;i<=n;i++) SA[h[rk[i]]--]=i;
        for(int i=1;i<=n;i++) 
            RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
        memcpy(sa,SA,sizeof(SA));
        memcpy(rk,RK,sizeof(RK));
    }
    for(int k=0,j,i=1;i<=n;i++)
    {
        j=sa[rk[i]-1];
        while(a[j+k]==a[i+k]) k++;
        h[rk[i]]=k;if(k) k--;
    }
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1;
    get_sa(26);
    for(int i=1;i<=n;i++) printf("%d ",sa[i]);puts("");
    for(int i=2;i<=n;i++) printf("%d ",h[i]);puts("");
}

二分图最大匹配-匈牙利

uoj78

#include <bits/stdc++.h>
using namespace std;
#define N 100005
struct edge
{
    int to,next;
}e[250005];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;e[tp].next=h[u];h[u]=tp;
}
int nl,nr,m,ans;
bool vis[505];
int g[505],match[505];
bool dfs(int u)
{
    for(int v,i=h[u];i;i=e[i].next)
    if(!vis[v=e[i].to])
    {
        vis[v]=1;
        if(!match[v]||dfs(match[v]))
        {
            match[v]=u;
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin>>nl>>nr>>m;
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);
    }
    for(int i=1;i<=nl;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ans++;
    }
    printf("%d\n",ans);
    for(int i=1;i<=nr;i++) g[match[i]]=i;
    for(int i=1;i<=nl;i++) printf("%d ",g[i]);
}

一般图最大匹配-带花树

uoj80

#include <bits/stdc++.h>
using namespace std;
#define N 100005
struct edge
{
    int to,next;
}e[250005];
int h[N],tp=1;
void ae(int u,int v)
{
    e[++tp].to=v;e[tp].next=h[u];h[u]=tp;
}
int n,m,ans;
int match[N],link[N],fa[N],type[N];
int vis[N],tim;int q[N],f,t;
int get_lca(int u,int v)
{
    for(tim++;;swap(u,v))
    if(u)
    {
        if(vis[u]==tim) return u;
        vis[u]=tim;u=fa[link[match[u]]];
    }
}
void update(int u,int v,int tar)
{
    while(fa[u]!=tar)
    {
        link[u]=v;
        if(type[match[u]]==1) type[q[++t]=match[u]]=0;
        fa[u]=fa[match[u]]=tar;
        u=link[v=match[u]];
    }
}
bool bfs(int x)
{
    for(int i=1;i<=n;i++) type[fa[i]=i]=-1;
    type[q[t=1]=x]=0;
    for(int k=1;k<=t;k++)
    {
        int u=q[k];
        for(int v,i=h[u];i;i=e[i].next)
        {
            if(type[v=e[i].to]==-1)
            {
                type[v]=1;link[v]=u;
                int nu=match[v];
                if(!nu)
                {
                    while(v)
                    {
                        int nv=match[link[v]];
                        match[match[v]=link[v]]=v;
                        v=nv;
                    }
                    return 1;
                }
                type[q[++t]=nu]=0;
            }
            else if(type[v]==0&&fa[u]!=fa[v])
            {
                int lca=get_lca(u,v);
                update(u,v,lca);update(v,u,lca);
                for(int j=1;j<=n;j++) fa[j]=fa[fa[j]];
            }
        }
    }
    return 0;
}
int main()
{
    freopen("tt.in","r",stdin);
    cin>>n>>m;
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);
    }
    for(int i=1;i<=n;i++) 
    if(!match[i]&&bfs(i)) ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++) printf("%d ",match[i]);
}

二分图最小字典序匹配-匈牙利+贪心

poj3715

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct edge
{
    int to,next;
}e[100005];
int h[205],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
int T,n,m,ans;
int c[205],match[205];
bool vis[205],ban[205]; 
bool dfs(int u)
{
    for(int v,i=h[u];i;i=e[i].next)
    if(!vis[v=e[i].to]&&!ban[v])
    {
        vis[v]=1;
        if(match[v]==-1||dfs(match[v]))
        {
            match[v]=u;match[u]=v;
            return 1;
        }
    }
    return 0;
}
bool mp[205][205];
int main()
{
    freopen("tt.in","r",stdin);
    for(cin>>T;T--;)
    {
        scanf("%d%d",&n,&m);
        memset(match,-1,sizeof(match));
        memset(h,0,sizeof(h));tp=1;
        memset(mp,0,sizeof(mp));
        memset(ban,0,sizeof(ban));
        for(int i=0;i<n;i++) scanf("%d",c+i);
        for(int u,v,i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            if(c[u]==c[v]||mp[u][v]) continue;
            mp[u][v]=mp[v][u]=1;
            if(c[u]!=c[v]) ae(u,v),ae(v,u);
        }
        ans=0;
        for(int i=0;i<n;i++)
        if(match[i]==-1)
        {
            memset(vis,0,sizeof(vis));
            ans+=dfs(i);
        }
        printf("%d ",ans);
        for(int i=0;i<n;i++)
        {
            if(match[i]==-1) continue;
            int tmp=match[i];
            match[i]=match[tmp]=-1;
            ban[i]=1;
            memset(vis,0,sizeof(vis));
            if(dfs(tmp)) ban[i]=0;
            else printf("%d ",i);
        }
        puts("");
    }
}

广义后缀自动机+最长公共子串

BZOJ2806

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 2200010
int n,m;
char s[N<<1];
int mx[N<<1];
struct SAM
{
    int son[N][2],fa[N],len[N];
    int last,tot;
    void init()
    {
        last=tot=1;
    }
    void insert(int x)
    {
        int p=last;
        if(son[p][x])
        {
            p=son[p][x];
            if(len[p]==len[last]+1) last=p;
            else
            {
                int q=++tot;len[q]=len[last]+1;
                fa[q]=fa[p];fa[p]=q;
                memcpy(son[q],son[p],sizeof(son[q]));
                last=q;
            }
        }
        else
        {
            int np=++tot;len[np]=len[p]+1;last=np;
            for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
            if(!p) fa[np]=1;
            else
            {
                int q=son[p][x];
                if(len[q]==len[p]+1) fa[np]=q;
                else
                {
                    int nq=++tot;len[nq]=len[p]+1;
                    fa[nq]=fa[q];fa[q]=fa[np]=nq;
                    memcpy(son[nq],son[q],sizeof(son[q]));
                    for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
                }
            }
        }
    }
    void work(int l)
    {
        for(int p=1,lcs=0,i=1;i<=l;i++)
        {
            int now=s[i]-'0';
            if(son[p][now])
            {
                p=son[p][now];
                lcs++;
            }
            else
            {
                while(p&&!son[p][now]) p=fa[p];
                if(!p) lcs=0,p=1;
                else
                {
                    lcs=len[p]+1;
                    p=son[p][now];
                }
            }
            mx[i]=lcs;
        }
    }
}sam;
int dp[N],q[N],f,t,q2[N],f2,t2;
bool check(int len,int mid)
{

    q[f=t=1]=0;f2=1;t2=0;
    for(int i=1;i<=len;i++)
    {
        if(f2<=t2&&i-q2[f2]>=mid)
        {
            while(f<=t&&dp[q[t]]>=dp[q2[f2]]) t--;
            q[++t]=q2[f2];f2++;
        }
        while(f<=t&&q[f]<i-mx[i]) f++;
        dp[i]=dp[i-1]+1;
        if(f<=t&&i-q[f]>=mid) dp[i]=min(dp[i],dp[q[f]]);
        q2[++t2]=i;
    }
    return dp[len]*10<=len;
}
int main()
{
    cin>>n>>m;
    sam.init();
    for(int i=1;i<=m;i++)
    {
        sam.last=1;
        scanf("%s",s+1);
        int len=strlen(s+1);
        for(int j=1;j<=len;j++)
            sam.insert(s[j]-'0');
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        int len=strlen(s+1);
        sam.work(len);
        int l=0,r=len,mid,ans=0;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(check(len,mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
}

斯坦纳树

BZOJ4006

#include<bits/stdc++.h>
using namespace std; 
int n,m,p,top;
struct edge{
    int to,next,val;
}e[10005];
int h[2005],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;e[tp].next=h[u];e[tp].val=w;h[u]=tp;
}
struct node{
    int c,d,id;
    bool operator <(const node &a)const{
        return c<a.c;
    }
}a[15];
int x[15],num[15],g[1<<11],cnt;
int f[1001][1<<10];
#define inf 0x3f3f3f3f
int q[1000005],front,tail;
bool vis[2005];
void spfa(int k)
{
    while(front<=tail)
    {
        int u=q[front++];vis[u]=0;
        for(int v,i=h[u];i;i=e[i].next)
        if(f[v=e[i].to][k]>f[u][k]+e[i].val)
        {
            f[v][k]=f[u][k]+e[i].val;
            if(!vis[v]) {vis[v]=1;q[++tail]=v;} 
        }
    }
}
void stt()
{
    int i,j,k;
    for(i=1;i<=n;i++)
    for(j=0;j<(1<<top);j++)
        f[i][j]=inf;
    for(i=0;i<top;i++) f[x[i]][1<<i]=0;
    for(k=1;k<(1<<top);k++)
    {
        front=1;tail=0;
        for(i=1;i<=n;i++)
        {
            for(j=k&(k-1);j;j=(j-1)&k)
            f[i][k]=min(f[i][k],f[i][j]+f[i][k-j]);
            if(f[i][k]<inf) q[++tail]=i,vis[i]=1;
        }
        spfa(k);
    }
}
int id[15];
int main()
{
    cin>>n>>m>>p;
    int i,j,u,v,w;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);ae(v,u,w);
    }
    for(i=1;i<=p;i++) 
    {
        scanf("%d%d",&a[i].c,&a[i].d);
        a[i].c--;num[a[i].c]++;
    }
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=p;i++)
    if(num[a[i].c]>1) 
    {
        a[i].id=top;
        x[top++]=a[i].d;
    }
    stt();
    for(i=0;i<p;i++) 
    if(num[i]>1) id[i]=cnt++;
    for(i=0;i<(1<<cnt);i++)
    {
        w=0;
        for(j=1;j<=p;j++)
        if(num[a[j].c]>1&&(i&(1<<id[a[j].c]))) 
            w|=(1<<a[j].id);
        for(j=1;j<=p;j++)
        if(num[a[j].c]>1&&(i&(1<<id[a[j].c]))) 
            g[i]=min(g[i],f[a[j].d][w]);
        for(j=i&(i-1);j;(--j)&=i) g[i]=min(g[i],g[j]+g[i^j]);
    }
    cout<<g[(1<<cnt)-1]<<endl;
}

BSGS+原根+exgcd+快速幂

BZOJ2219

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x7fffffffffffffffll
#define mod 100007
int T;
ll A,B,K;
ll prime[1005];
int num;
int h[mod],tot;
ll val[100005];
int id[100005],nxt[100005];
ll qpow(ll x,ll k,ll p=inf)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=ret*x%p;
        k>>=1;x=x*x%p;
    }
    return ret;
}
bool check(int x,ll p,ll k)
{
    for(int i=1;i<=num;i++)
    if(qpow(x,k/prime[i],p)==1) return 0;
    return 1;
}
void div1(ll p)
{
    num=0;
    for(int i=2;i*i<=p;i++)
    if(p%i==0)
    {
        prime[++num]=i;
        while(p%i==0) p/=i;
    }
    if(p>1) prime[++num]=p;
}
ll get_root(ll p,ll x)
{
    div1(x);
    for(int i=2;;i++)
    if(check(i,p,x)) return i;
}
void exgcd(ll a,ll b,ll &x,ll &y,ll &d)
{
    if(!b){d=a;x=1;y=0;return;}
    exgcd(b,a%b,y,x,d);y-=a/b*x;
}
ll get_inv(ll a,ll b)
{
    ll x,y,d;exgcd(a,b,x,y,d);b/=d;
    return (x%b+b)%b;
}
int insert(ll tmp,int k)
{
    int t=tmp%mod;
    for(int i=h[t];i;i=nxt[i])
    if(val[i]==tmp) return id[i];
    if(k==-1) return -1;
    val[++tot]=tmp;id[tot]=k;nxt[tot]=h[t];h[t]=tot;
}
ll bsgs(ll a,ll g,ll p)
{
    memset(h,0,sizeof(h));tot=0;
    ll m=(int)sqrt(p)+1,tmp=1;
    for(int i=0;i<m;i++,tmp=tmp*g%p) insert(tmp,i);
    ll ni=get_inv(tmp,p);
    for(int k,i=0;i<m;i++,a=a*ni%p) 
    if((k=insert(a,-1))!=-1) return i*m+k;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll work(ll a,ll b,ll p,ll t)
{
    ll mo=qpow(p,t),ret=0,phi,g,ind,tmp;b%=mo;
    if(!b) return qpow(p,t-((t-1)/a+1));
    while(b%p==0) ret++,b/=p;
    if(ret%a) return 0;
    t-=ret;mo=qpow(p,t);
    phi=mo-mo/p;g=get_root(mo,phi);ind=bsgs(b,g,mo);tmp=gcd(a,phi);
    if(ind%tmp) return 0;
    return tmp*qpow(p,ret-ret/a);
}
int main()
{
    //freopen("tt.in","r",stdin);
    for(cin>>T;T--;)
    {
        scanf("%lld%lld%lld",&A,&B,&K);
        ll ans=1;K=K*2+1;
        for(ll i=2;i*i<=K&&ans;i++)
        if(K%i==0)
        {
            int ret=0;
            while(K%i==0) ret++,K/=i;
            ans*=work(A,B,i,ret);
        }
        if(K>1&&ans) ans=ans*work(A,B,K,1);
        printf("%lld\n",ans);
    }
}

平面图转对偶图+朱刘算法

BZOJ2960

#include <bits/stdc++.h>
using namespace std;
#define N 10005
struct Point
{
    int x,y;
    void read(){scanf("%d%d",&x,&y);}
    int operator *(const Point &a)const{
        return x*a.y-y*a.x;
    }
}p[N];
struct edge1
{
    int x,y;
    double alp;
    edge1(){}
    edge1(int a,int b):x(a),y(b){
        alp=atan2(p[b].x-p[a].x,p[b].y-p[a].y);
    }
}e[N];
struct edge2
{
    int x,y,v;
    edge2(){}
    edge2(int a,int b,int c):x(a),y(b),v(c){}
}ed[N];
int n,m,tp=1;
int belong[N],cnt;
int w[N];
struct Part1
{
    struct cmp
    {
        bool operator ()(int a,int b)
        {
            return e[a].alp<e[b].alp;
        }
    };
    set<int,cmp> g[N];
    set<int>::iterator k;
    bool del[N];
    int q[N];
    void insert(int x,int y){g[x].insert(y);}
    void work()
    {
        int i,j,t;
        for(i=2;i<=tp;i++)
        if(!del[i])
        {
            for(q[t=1]=j=i;;q[++t]=j=*k)
            {
                k=g[e[j].y].find(j^1);k++;
                if(k==g[e[j].y].end()) k=g[e[j].y].begin();
                if(*k==i) break;
            }
            int s=0;
            for(j=1;j<=t;j++) s+=p[e[q[j]].x]*p[e[q[j]].y];
            for(cnt++,j=1;j<=t;j++) del[q[j]]=1,belong[q[j]]=cnt;
        }
    } 
}part1;
struct Part2
{
    int pre[N],id[N],in[N],vis[N];
    int zhuliu(int root,int n,int m)
    {
        int tn,tm,ret=0;
        while(1)
        {
            for(int i=1;i<=n;i++) in[i]=0x3f3f3f3f,pre[i]=0;
            for(int i=1;i<=m;i++)
            if(ed[i].v<in[ed[i].y])
            {
                pre[ed[i].y]=ed[i].x;
                in[ed[i].y]=ed[i].v;
            }
            tn=tm=in[root]=0;
            for(int i=1;i<=n;i++) id[i]=vis[i]=0;
            for(int v,i=1;i<=n;i++)
            {
                ret+=in[v=i];
                while(vis[v]!=i&&!id[v]&&v!=root) vis[v]=i,v=pre[v];
                if(v!=root&&!id[v])
                {
                    id[v]=++tn;
                    for(int u=pre[v];u!=v;u=pre[u]) id[u]=tn;
                }
            }
            if(!tn) break;
            for(int i=1;i<=n;i++) if(!id[i]) id[i]=++tn;
            for(int i=1;i<=m;i++)
            if(id[ed[i].x]!=id[ed[i].y])
                ed[++tm]=edge2(id[ed[i].x],id[ed[i].y],ed[i].v-in[ed[i].y]);
            n=tn;m=tm;root=id[root];
        }
        return ret;
    }
    void work()
    {
        int n=cnt+1,root=cnt+1,m=0,sum=0;
        for(int i=2;i<=tp;i++) 
        if(belong[i]&&belong[i^1]&&w[i])
        {
            ed[++m]=edge2(belong[i],belong[i^1],w[i]);
            sum+=w[i];
        }
        for(int i=1;i<=cnt;i++) ed[++m]=edge2(root,i,sum);
        printf("%d\n",zhuliu(root,n,m)-sum);
    }
}part2;
int main()
{
    //freopen("2960.in","r",stdin);
    //freopen("2960.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i].read();
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&u,&v,&w[i*2],&w[i*2+1]);
        e[++tp]=edge1(u,v);part1.insert(u,tp);
        e[++tp]=edge1(v,u);part1.insert(v,tp);
    }
    part1.work();
    part2.work();
}

EXBSGS

模版

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int T;
ll a,b,c;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void exgcd(ll a,ll b,ll &x,ll &y,ll &d)
{
    if(!b){x=1;y=0;d=a;return;}
    exgcd(b,a%b,y,x,d);y-=a/b*x;
}
ll get_inv(ll a,ll b)
{
    ll x,y,d;
    exgcd(a,b,x,y,d);b/=d;
    return (x%b+b)%b;
}
#define mod 100007
int h[100007],nxt[1000005],id[1000005],tot;
ll val[1000005];
int insert(ll x,int k)
{
    int t=x%mod;
    for(int i=h[t];i;i=nxt[i])
    if(val[i]==x) return id[i];
    if(k==-1) return -1;
    val[++tot]=x;id[tot]=k;nxt[tot]=h[t];h[t]=tot;
}
ll bsgs(ll a,ll b,ll c)
{
    memset(h,0,sizeof(h));tot=0;
    ll blo=(ll)sqrt(c)+1,tmp=1;
    for(int i=0;i<blo;i++,tmp=tmp*a%c) insert(tmp,i);
    ll inv=get_inv(tmp,c);
    for(int k,i=0;i<blo;i++,b=b*inv%c) 
    if((k=insert(b,-1))!=-1) return i*blo+k;
    return -1; 
}
ll exbsgs(ll a,ll b,ll c)
{
    ll tmp=1,g,sum=0;b%=c;a%=c;
    for(int i=0;i<=50;i++,tmp=tmp*a%c) 
    if(tmp==b) return i;
    tmp=1;
    while((g=gcd(a,c))>1)
    {
        if(b%g) return -1;
        sum++;b/=g;c/=g;
        tmp=tmp*a/g%c;
    }
    b=b*get_inv(tmp,c)%c;
    tmp=bsgs(a,b,c);
    if(tmp==-1) return -1;
    return tmp+sum;
}
int main()
{
    //freopen("tt.in","r",stdin);
    for(cin>>T;T--;)
    {
        scanf("%lld%lld%lld",&a,&c,&b);
        if(c==1) puts(b?"-1":"0");
        else printf("%lld\n",exbsgs(a,b,c));
    }
}

KDtree

BZOJ4520

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,k,D,tot,root;
priority_queue<ll,vector<ll>,greater<ll> > q;
struct node
{
    ll x[2],mx[2],mn[2];
    int l,r;
    bool operator <(const node &a)const{
        return x[D]<a.x[D];
    }
}p[100005],t[100005];
void pushup(int x)
{
    for(int l=t[x].l,r=t[x].r,i=0;i<2;i++)
    {
        t[x].mn[i]=t[x].mx[i]=t[x].x[i];
        if(l) 
        {
            t[x].mn[i]=min(t[x].mn[i],t[l].mn[i]);
            t[x].mx[i]=max(t[x].mx[i],t[l].mx[i]);
        }
        if(r)
        {
            t[x].mn[i]=min(t[x].mn[i],t[r].mn[i]);
            t[x].mx[i]=max(t[x].mx[i],t[r].mx[i]);
        }
    }
}
#define sqr(x) (x)*(x)
ll pre(int rt,ll x,ll y)
{
    if(!rt) return 0;
    return max(sqr(x-t[rt].mn[0]),sqr(x-t[rt].mx[0]))+
            max(sqr(y-t[rt].mn[1]),sqr(y-t[rt].mx[1]));
}
void build(int &rt,int l,int r,int now)
{
    D=now;
    int mid=(l+r)>>1;
    nth_element(p+l,p+mid,p+r+1);
    t[rt=++tot]=p[mid];
    if(mid>l) build(t[rt].l,l,mid-1,now^1);
    if(mid<r) build(t[rt].r,mid+1,r,now^1);
    pushup(rt);
}
void query(int rt,int x,int y)
{
    if(q.top()<sqr(t[rt].x[0]-x)+sqr(t[rt].x[1]-y))
    {
        q.pop();
        q.push(sqr(t[rt].x[0]-x)+sqr(t[rt].x[1]-y));
    }
    ll tl=pre(t[rt].l,x,y),tr=pre(t[rt].r,x,y);
    if(tl>tr&&t[rt].l&&tl>q.top()) 
    {
        query(t[rt].l,x,y);
        if(t[rt].r&&q.top()<tr) query(t[rt].r,x,y);
    }
    else if(t[rt].r&&tr>q.top())
    {
        query(t[rt].r,x,y);
        if(t[rt].l&&q.top()<tl) query(t[rt].l,x,y);
    }
}
ll st[205];
char getc(){
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read(){
    static char ch;static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return D;
}
int main()
{
    n=read();k=read()<<1;
    for(int i=1;i<=n;i++) p[i].x[0]=read(),p[i].x[1]=read();
    build(root,1,n,0);
    for(int i=1;i<=k;i++) q.push(0); 
    for(int i=1;i<=n;i++) query(root,p[i].x[0],p[i].x[1]);
    printf("%lld\n",q.top());
}

数位dp

BZOJ4521

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll L,R,tmp;
ll dp[15][2][2][2][2][100];
int st[15],top;
//i位,是否在上界,是否有4,是否有8,是否连3个,上两位是k
bool check(int x,int y){return x%10==y&&(y==x/10%10);}
ll work(ll x)
{
    memset(dp,0,sizeof(dp));top=0;
    while(x) st[++top]=x%10,x/=10;
    for(int i=1;i<=st[top];i++) dp[top][i==st[top]][i==4][i==8][0][i]=1;
    for(int i=top;i>1;i--)
    {
        for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
        for(int t=0;t<2;t++)
        for(int p=0;p<100;p++)
        {
            if(tmp=dp[i][0][j][k][t][p])
            {
                for(int nxt=0;nxt<10;nxt++)
                    dp[i-1][0][j|(nxt==4)][k|(nxt==8)][t|check(p,nxt)][(p%10)*10+nxt]+=tmp;
            }
            if(tmp=dp[i][1][j][k][t][p])
            {
                for(int nxt=0;nxt<=st[i-1];nxt++)
                    dp[i-1][nxt==st[i-1]][j|(nxt==4)][k|(nxt==8)][t|check(p,nxt)][(p%10)*10+nxt]+=tmp;
            }
        }
    }
    ll ret=0;
    for(int i=0;i<100;i++) 
    {
        ret+=dp[1][0][0][1][1][i]+dp[1][1][0][1][1][i];
        ret+=dp[1][0][1][0][1][i]+dp[1][1][1][0][1][i];
        ret+=dp[1][0][0][0][1][i]+dp[1][1][0][0][1][i];
    }
    return ret;
}
int main()
{
    //freopen("tt.in","r",stdin);
    cin>>L>>R;
    if(L==10000000000) printf("%lld\n",work(R)-work(L)+1);
    else printf("%lld\n",work(R)-work(L-1));
}

最小割树

BZOJ4519

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int n,m,S,T;
struct edge
{
    int to,next,flow;
}e[2000005];
int h[1005],tp=1;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    h[u]=tp;
}
int val[1005],cnt;
int id[1005],_id[1005];
int dis[1005];
bool bfs()
{
    static int q[1005],f,t;
    memset(dis,0,sizeof(dis));dis[S]=1;
    q[f=t=1]=S;
    while(f<=t)
    {
        int u=q[f++];
        for(int v,i=h[u];i;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            q[++t]=v;
        }
    }
    return dis[T]>0;
}
int dfs(int u,int limit)
{
    if(u==T) return limit;
    int cost=0,tmp;
    for(int v,i=h[u];i;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(limit-cost,e[i].flow));
        if(tmp)
        {
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(cost==limit) break;
        }
        else dis[v]=-1;
    }
    return cost;
}
int dinic()
{
    int ret=0;
    while(bfs()) ret+=dfs(S,inf);
    return ret;
}
void work(int l,int r)
{
    if(l==r) return;
    for(int i=2;i<=tp;i+=2) 
        e[i].flow=e[i+1].flow=(e[i].flow+e[i+1].flow)/2;
    S=id[l],T=id[r];
    val[++cnt]=dinic();
    int tl=l,tr=r;
    for(int i=l;i<=r;i++)
    {
        if(dis[id[i]]) _id[tl++]=id[i];
        else _id[tr--]=id[i];
    }
    for(int i=l;i<=r;i++) id[i]=_id[i];
    work(l,tl-1);work(tr+1,r);
}
int main()
{
    cin>>n>>m;
    for(int u,v,w,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);ae(v,u,w);
    }
    for(int i=1;i<=n;i++) id[i]=i;
    work(1,n);
    sort(val+1,val+n);
    printf("%d\n",unique(val+1,val+n)-val-1);
}

Miller_Rabin+Pollard_rho

hdu4344

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll T,n;
ll st[100],top;
ll qmul(ll a,ll k,ll p)
{
    ll ret=0;
    while(k)
    {
        if(k&1) ret=(ret+a)%p;
        k>>=1;a=(a+a)%p;
    }
    return ret;
}
ll qpow(ll x,ll k,ll p)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=qmul(ret,x,p);
        k>>=1;x=qmul(x,x,p);
    }
    return ret;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
bool miller_rabin(ll n)
{
    ll m=n-1,cnt=0;
    while(~m&1) cnt++,m>>=1;
    for(int i=0;i<5;i++)
    {
        ll a=rand()%(n-1)+1,x=qpow(a,m,n),y;
        for(int j=0;j<cnt;j++)
        {
            y=qmul(x,x,n);
            if(y==1&&x!=1&&x!=n-1) return 0;
            x=y;
        }
        if(y!=1) return 0;
    }
    return 1;
}
ll rho_find(ll n,ll c)
{
    ll i=1,k=2,x=rand()%(n-1)+1,y=x,d;
    while(1)
    {
        x=(qmul(x,x,n)+c)%n;
        d=gcd((y-x+n)%n,n);
        if(1<d&&d<n) return d;
        if(y==x) return n;
        if((++i)==k) y=x,k<<=1;
    }
}
void pollard_rho(ll n)
{
    while(~n&1) st[++top]=2,n>>=1;
    if(n==1) return;
    if(miller_rabin(n)){st[++top]=n;return;}
    ll p=n;
    while(p==n) p=rho_find(n,rand()%(n-1)+1);
    pollard_rho(p);pollard_rho(n/p);
}
int main()
{
    //freopen("tt.in","r",stdin);
    for(cin>>T;T--;)
    {
        scanf("%lld\n",&n);
        top=0;
        pollard_rho(n);
        sort(st+1,st+top+1);
        ll last=st[1],cnt=0,ret=0;
        for(int i=2;i<=top+1;i++)
        {
            if(i==top+1||st[i]!=st[i-1])
            {
                cnt++;
                ret+=last;
                last=st[i];
            }
            else last*=st[i];
        }
        if(cnt==1) ret/=st[1];
        printf("%lld %lld\n",cnt,ret);
    }
}   

dancing links

poj2676

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 350
#define M 750
char s[15];
int id[N*M],cnt;
int num[N],pre[N];
int pos[10][10][10][4];
int X[N*M],Y[N*M],val[N*M];
int d[N*M],u[N*M],l[N*M],r[N*M];
int T,ans[10][10];
void add(int x,int &last,int &st,int a,int b,int v)
{
    num[x]++;id[++cnt]=x;
    X[cnt]=a;Y[cnt]=b;val[cnt]=v;
    d[u[cnt]=pre[x]]=cnt;
    d[u[x]=cnt]=x;pre[x]=cnt;
    if(!last) st=l[cnt]=r[cnt]=cnt;
    else l[r[last]=cnt]=last,r[l[st]=cnt]=st;
    last=cnt;
}
void del(int x)
{
    l[r[x]]=l[x];r[l[x]]=r[x];
    for(int i=d[x];i!=x;i=d[i])
    for(int j=r[i];j!=i;j=r[j])
        d[u[j]]=d[j],u[d[j]]=u[j],num[id[j]]--;
}
void back(int x)
{
    l[r[x]]=r[l[x]]=x;
    for(int i=u[x];i!=x;i=u[i])
    for(int j=l[i];j!=i;j=l[j])
        u[d[j]]=d[u[j]]=j,num[id[j]]++;
}
bool dlx()
{
    if(!r[0])
    {
        for(int i=1;i<=9;i++)
        {
            for(int j=1;j<=9;j++) 
                printf("%d",ans[i][j]);
            puts("");
        }
        puts("");
        return 1;
    }
    int p=0,s=M,i,j;
    for(i=r[0];i;i=r[i]) 
    if(num[i]&&num[i]<s) s=num[i],p=i;
    del(p);
    for(i=d[p];i!=p;i=d[i])
    {
        for(j=r[i];j!=i;j=r[j]) del(id[j]);
        ans[X[i]][Y[i]]=val[i];
        if(dlx()) return 1;
        for(j=l[i];j!=i;j=l[j]) back(id[j]);
    }
    back(p);
    return 0;
}
int main()
{
    //freopen("tt.in","r",stdin);
    for(int i=1;i<=9;i++)
    for(int j=1;j<=9;j++)
    for(int k=1;k<=9;k++)
    {
        pos[i][j][k][0]=(j-1)*9+i;
        pos[i][j][k][1]=(k-1)*9+81+i;
        pos[i][j][k][2]=162+i+((j-1)/3*3+(k-1)/3)*9;
        pos[i][j][k][3]=(j-1)*9+k+243;
    }
    for(cin>>T;T--;)
    {
        for(int i=0;i<=324;i++) l[i]=i-1,r[i]=i+1,pre[i]=d[i]=u[i]=i,num[i]=0;
        r[l[0]=cnt=324]=0;
        for(int i=1;i<=9;i++)
        {
            scanf("%s",s+1);
            for(int j=1;j<=9;j++)
            {
                if(s[j]!='0')
                {
                    for(int st=0,last=0,k=0;k<4;k++)
                        add(pos[s[j]-'0'][i][j][k],last,st,i,j,s[j]-'0');
                }
                else
                {
                    for(int k=1;k<=9;k++)
                    for(int st=0,last=0,t=0;t<4;t++)
                        add(pos[k][i][j][t],last,st,i,j,k);
                }
            }
        }
        dlx();
    }
}

可持久化可并堆+K短路

模板

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define ll long long
struct edge{
    int to,next,val;
}e[N];
int h[N],tp=1;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
int n,m,k;
queue<int> q;
vector<int> son[N];
int dis[N],fa[N],fr[N];
bool vis[N];
void build()
{
    memset(dis,0x3f,sizeof(dis));dis[n]=0;
    q.push(n);
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0;
        for(int v,i=h[u];e[i].to;i=e[i].next)
        if((i&1)&&dis[v=e[i].to]>dis[u]+e[i].val)
        {
            fa[v]=u;fr[v]=i;
            dis[v]=dis[u]+e[i].val;
            if(!vis[v])
            {
                vis[v]=1;
                q.push(v);
            }
        }
    }
    for(int i=1;i<=n;i++) son[fa[i]].push_back(i);
}
struct abcd
{
    int l,r,h,t;ll v;
}b[6000000];
struct node
{
    ll v;int x;
    bool operator <(const node &a)const{
        return v+b[x].v>a.v+b[a.x].v;
    }
}tmp,tmp2;
priority_queue<node> pq;
int cnt;
ll ans;
int g[N],H[N];
#define ls b[x].l
#define rs b[x].r
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(b[x].v>b[y].v) swap(x,y);
    rs=merge(rs,y);
    if(b[rs].h>b[ls].h) swap(ls,rs);
    b[x].h=b[rs].h+1;
    return x;
}
int Merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(b[x].v>b[y].v) swap(x,y);
    int ret=++cnt;b[ret]=b[x];x=ret;
    rs=Merge(rs,y);
    if(b[rs].h>b[ls].h) swap(ls,rs);
    b[x].h=b[rs].h+1;
    return x;
}
void dfs(int u,int f)
{
    g[u]=Merge(H[u],g[f]);
    for(int i=0;i<son[u].size();i++) dfs(son[u][i],u);
}
int main()
{
    //freopen("tt.in","r",stdin);
    cin>>n>>m>>k;
    for(int u,v,w,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);ae(v,u,w);
    }
    build();
    for(int i=1;i<=n;i++)
    for(int j=h[i];j;j=e[j].next)
    if((~j&1)&&fr[i]!=(j^1))
    {
        b[++cnt].v=e[j].val-(dis[i]-dis[e[j].to]);
        b[cnt].t=e[j].to;H[i]=merge(H[i],cnt);
    }
    dfs(n,0);
    tmp.x=g[1];
    pq.push(tmp);
    for(int i=1;i<k;i++)
    {
        tmp=pq.top();pq.pop();
        ans=tmp.v+b[tmp.x].v;
        tmp2.v=tmp.v+b[tmp.x].v;
        tmp2.x=g[b[tmp.x].t];
        pq.push(tmp2);
        tmp.x=Merge(b[tmp.x].l,b[tmp.x].r);
        if(tmp.x) pq.push(tmp);
    }
    printf("%lld\n",ans+dis[1]);
}

FWT

or

void fwt(int *a,int len,int type)
{
    for(int k=1;k<len;k<<=1)
    for(int i=0;i<len;i++)
    {
        if(i&k) continue;
        a[i+k]+=type*a[i];
    }
}

and

void fwt(long long *a,int len,int v)
{
  for(int k=0;(1<<k)<=len;k++)
  for(int i=0;i<len;i++)
  {
    if(i>>k&1) continue;
    a[i]+=v?a[i+(1<<k)]:-a[i+(1<<k)];
  }
}

xor

void fwt(ll a[])
{
    for(int k=1;k<(1<<n);k<<=1)
    for(int i=0;i<(1<<n);i++)
    {
        if(i&k) continue;
        ll t1=(a[i]+a[i+k])%mod;
        a[i+k]=(a[i]-a[i+k]+mod)%mod;
        a[i]=t1;
    }
}
void ifwt(ll a[])
{
    for(int k=1;k<(1<<n);k<<=1)
    for(int i=0;i<(1<<n);i++)
    {
        if(i&k) continue;
        ll t1=(a[i]+a[i+k])*Inv_2%mod;
        a[i+k]=(a[i]-a[i+k]+mod)*Inv_2%mod;
        a[i]=t1;
    }
}

Nim游戏积

模板

int get_sg(int x,int y)
{
    if(x<y) swap(x,y);
    if(y==0) return 0;
    if(x==1) return 1;
    int t=2;while(t*t<=x) t*=t;
    int t1=get_sg(x/t,y/t);
    int t2=get_sg(x%t,y/t)^get_sg(x/t,y%t);
    int t3=get_sg(x%t,y%t);
    return (t1^t2)*t^t3^get_sg(t1,t/2);
}

线性基

BZOJ3105

for(int i=n;i;i--)
    {
        for(int j=29;j>=0;j--)
        if(a[i]&(1<<j))
        {
            if(!vis[j])
            {
                vis[j]=i;
                for(int k=1;k<=top;k++)
                if(a[st[k]]&(1<<j)) a[st[k]]^=a[i];
                st[++top]=i;
                break;
            }   
            a[i]^=a[vis[j]];
        }
        if(a[i]) ans+=w[i];
    }

上下界最小流

BZOJ2502

#include <bits/stdc++.h>
using namespace std;
#define inf 1000000
struct edge
{
    int to,next,flow;
}e[2000005];
int h[205],tp=1;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    h[u]=tp;
}
void add(int u,int v,int w)
{
    ae(u,v,w);
    ae(v,u,0);
}
queue<int> q;
int dis[205];
int n,S,T,in[205];
bool bfs()
{
    memset(dis,0,sizeof(dis));dis[S]=1;
    while(!q.empty()) q.pop();
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];i;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==T) return 1;
            q.push(v);
        }
    }
    return 0;
}
int dfs(int u,int limit)
{
    if(u==T) return limit;
    int cost=0,tmp;
    for(int v,i=h[u];i;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(limit-cost,e[i].flow));
        if(tmp)
        {
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(cost==limit) break;
        }
        else dis[v]=-1;
    }
    return cost;
}
int dinic()
{
    int ret=0;
    while(bfs()) ret+=dfs(S,inf);
    return ret;
}
int main()
{
    //freopen("tt.in","r",stdin);
    cin>>n;
    S=n+2;T=n+3;
    for(int i=1;i<=n;i++)
    {
        add(0,i,inf);
        add(i,n+1,inf);
    }
    for(int m,i=1;i<=n;i++)
    {
        scanf("%d",&m);
        for(int x,j=1;j<=m;j++) 
        {
            scanf("%d",&x);
            in[i]--;in[x]++;
            add(i,x,inf);
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(in[i]>0) add(S,i,in[i]),sum+=in[i];
        else if(in[i]<0) add(i,T,-in[i]);
    }
    //dinic();
    //add(n+1,0,inf);
    //dinic();
    //printf("%d\n",e[tp].flow);

    printf("%d\n",sum-dinic());
}