BZOJ3511:土地划分 网络流

思路:

直接套用二元关系最小割,对于这道题而言非常朴素,而且不用考虑某些变量为负数还需要构造二分图的情况,很容易就水过去了.

现在我们仅考虑二元关系:(我们将所有收益预先加到一起,那么现在仅是需要减去最小的损失)

考虑两个点\(x,y\)以及一条边\(E(x,y)\):

\(x\in{A},y\in{A},cost=C_1=E_B\)

\(x\in{A},y\in{B},cost=C_2=E_A+E_B+E_C\)

\(x\in{B},y\in{A},cost=C_3=E_A+E_B+E_C\)

\(x\in{A},y\in{B},cost=C_4=E_A\)

连边\((S,x,a),(S,y,b),(x,T,c),(y,T,d),(x,y,e),(y,x,f)\).

随后不难发现:

\(C_1=c+d,C_2=b+c+e,C_3=a+d+f,C_4=a+b\)

好辣!如果我们能够直接解出\(a,b,c,d,e,f\)不是就非常好了么.

注意到如果\(a,b,c,d\)是负数我们并不用在意,因为\(a,c\)中只能选择一个,\(b,d\)中也只能选择一个,所以我们可以将边权均增大一个值,最终再减去即可.

可是\(e,f\)并不可以这样草率处理.

当\(C_2+C_3-C_1-C_2>0\)时,\(e,f\)可以取大于0的数,而\(a,b,c,d\)随意选择,问题可以解决.

如果不是的话,我们就需要在一对二元关系中,将其中一个点的意义反向,当然这有一个条件,二元关系必须不能存在奇环.不过这都是后话了.

这道题我们显然不用构造二分图,直接列出式子见图就行了.为了避免实数网络流将边权扩大二倍.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int INF=0x3f3f3f3f;
 
struct MaxflowSolver{
    static const int V=10010;
    static const int E=600010;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],stk[V],d[V],top,cur[V];
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int res=0,u=S,ins,Min,i;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find)stk[top++]=cur[u]=ins,u=end[ins];
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}Stg;
 
int in[10010],out[10010];
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
     
    Stg.reset();
    int S=0,T=n+1;
    in[1]=out[n]=INF;
    int a,b,x,res=0;
    for(i=2;i<n;++i)scanf("%d",&x),res+=x<<1,in[i]+=x<<1;
    for(i=2;i<n;++i)scanf("%d",&x),res+=x<<1,out[i]+=x<<1;
     
    int Ea,Eb,Ec;
    while(m--){
        scanf("%d%d%d%d%d",&a,&b,&Ea,&Eb,&Ec),res+=2*Ea+2*Eb;
        in[a]+=Ea,in[b]+=Ea,out[a]+=Eb,out[b]+=Eb;
        Stg.make(a,b,Ea+Eb+2*Ec),Stg.make(b,a,Ea+Eb+2*Ec);
    }
     
    for(i=1;i<=n;++i){
        if(in[i])Stg.make(S,i,in[i]);
        if(out[i])Stg.make(i,T,out[i]);
    }
     
    printf("%d",(res-Stg.Maxflow(S,T,n+2))>>1);
     
    return 0;
}

BZOJ3774:最优选择 网络流

思路:

首先由于是一个二分图,我们分为左右两部分.

...然后具体的建模自己看代码吧,真的是好神奇的思路...

我居然连这都想不出来真是混不下去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int INF=0x3f3f3f3f;
struct MaxflowSolver{
    static const int V=5010;
    static const int E=80010;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V];
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline bool bfs(int S,int T){
        static int q[V];int fr=0,ta=0;
        memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
        }return d[T]!=-1;
    }
    inline int dinic(int p,int T,int Maxflow){
        if(p==T)return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[p]+1==d[end[j]]){
            int to=dinic(end[j],T,last>flow[j]?flow[j]:last);if(to)flow[j]-=to,flow[j^1]+=to,last-=to;
            if(!last)return Maxflow;
        }
        d[p]=-1;return Maxflow-last;
    }
    inline int Maxflow(int S,int T){
        int res=0;
        while(bfs(S,T))res+=dinic(S,T,INF);
        return res;
    }
}Stg;
 
int lab[51][51][2],a[51][51],b[51][51];
 
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j,k;int x,res=0;
     
    int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)lab[i][j][0]=++id,lab[i][j][1]=++id;
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&a[i][j]);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&b[i][j]),res+=b[i][j];
     
    int S=0,T=id+1;
     
    Stg.reset();
    for(i=1;i<=n;++i)for(j=1;j<=m;++j){
        if((i+j)&1)Stg.make(S,lab[i][j][0],a[i][j]),Stg.make(lab[i][j][0],lab[i][j][1],b[i][j]);
        else Stg.make(lab[i][j][1],lab[i][j][0],b[i][j]),Stg.make(lab[i][j][0],T,a[i][j]);
        for(k=0;k<4;++k){
            int nowx=i+dx[k],nowy=j+dy[k];
            if(nowx>=1&&nowx<=n&&nowy>=1&&nowy<=m){
                if((i+j)&1)Stg.make(lab[i][j][0],lab[nowx][nowy][1],INF);
                else Stg.make(lab[nowx][nowy][1],lab[i][j][0],INF);
            }
        }
    }
     
    printf("%d",res-Stg.Maxflow(S,T));
     
    return 0;
}

BZOJ3609:[Heoi2014]人人尽说江南好 找规律

思路:

好歹我也是做过一些博弈论的题,结果毫无思路.

因为不能分解成子游戏,所以SG函数直接废.

反正一切线索全部都指向一条唯一的道路--找规律!!(也许是构造?但我太弱)

然后有一个指数级的暴力打表:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

int seq[31],lim;

bool Solve(){
	int num=0;register int i,j;
	for(i=1;i<=30;++i)num+=seq[i];
	if(num==1)return 0;
	int tseq[31];memcpy(tseq,seq,sizeof seq);
	for(i=1;i<=30;++i)for(j=i;j<=30;++j){
		memcpy(seq,tseq,sizeof tseq);
		if(i==j){
			if(seq[i]<2||2*i>lim)continue;
			seq[i]-=2,seq[2*i]++;
			if(!Solve())return 1;
		}
		else{
			if(!seq[i]||!seq[j]||i+j>lim)continue;
			--seq[i],--seq[j],++seq[i+j];
			if(!Solve())return 1;
		}
	}
	return 0;
}
int main(){
	register int i,j,k;
	for(i=1;i<=7;++i){
		for(j=1;j<=26;++j){
			memset(seq,0,sizeof seq),seq[1]=j;lim=i;
			if(Solve()==1)printf("lim=%d n=%d %d\n",i,j,j%i);
		}puts("");
	}
}

然后好像发现了什么.

然后就是AC程序.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
int main(){
    int T;scanf("%d",&T);int n,lim;
    while(T--){
        scanf("%d%d",&n,&lim);
        if(lim==1)puts("1");
        else if(n==1)puts("1");
        else if(n<=lim){
            if(n&1)puts("1");else puts("0");
        }
        else if(lim==2){
            if(n%4==2||n%4==3)puts("0");else puts("1");
        }
        else{
            if(lim&1){
                if(n%lim!=0&&(n%lim)%2==0)puts("0");else puts("1");
            }
            else{
                int t=n%lim;
                if(t==0){
                    if((n/lim)&1)puts("0");else puts("1");
                }
                else if(t&1){
                    if(n%(2*lim)==lim+t)puts("0");else puts("1");
                }
                else{
                    if(n%(2*lim)==t)puts("0");else puts("1");
                }
            }
        }
    }
    return 0;
}

BZOJ3577:玩手机 最大流+二维ST表优化

思路:

首先最大流显然,朴素建模显然.

但是边数是\(O((a+b)n^2)\)会爆炸.

因此我们得考虑优化.

注意到题目中的一个条件,也就是说每一个区域都是正方形.

因此我们设\(f[i][j][k]\)表示左上角坐标为\((i,j)\),边长为\(2^k\)的正方形区域,那么我们就可以用\(O(1)\)个这种正方形区域来完全覆盖所求的区域.

这样就可以过了.具体见代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
 
#define INF 0x3f3f3f3f
struct MaxflowSolver{
    static const int V=100000;
    static const int E=1000010;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],d[V],stk[V],top,cur[V];
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int i,Min,ins,u=S,res=0;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find)cur[u]=stk[top++]=ins,u=end[ins];
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}Stg;
 
#define N 61
#define M 61
int in[N][M],out[N][M];
int left[N][M][6],right[N][M][6];
 
int len[61];
 
int main(){
    int n,m,a,b;scanf("%d%d%d%d",&n,&m,&a,&b);register int i,j,k;
    int cnt=0;
     
    Stg.reset();
    int S=++cnt,T=++cnt;
    int x;for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&x),Stg.make(in[i][j]=++cnt,out[i][j]=++cnt,x);
     
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)left[i][j][0]=++cnt,right[i][j][0]=++cnt;
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)Stg.make(left[i][j][0],in[i][j],INF);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)Stg.make(out[i][j],right[i][j][0],INF);
    for(k=1;(1<<k)<=n&&(1<<k)<=m;++k)for(i=1;i+(1<<k)-1<=n;++i)for(j=1;j+(1<<k)-1<=m;++j){
        left[i][j][k]=++cnt;
        Stg.make(left[i][j][k],left[i][j][k-1],INF);
        Stg.make(left[i][j][k],left[i+(1<<(k-1))][j][k-1],INF);
        Stg.make(left[i][j][k],left[i][j+(1<<(k-1))][k-1],INF);
        Stg.make(left[i][j][k],left[i+(1<<(k-1))][j+(1<<(k-1))][k-1],INF);
        right[i][j][k]=++cnt;
        Stg.make(right[i][j][k-1],right[i][j][k],INF);
        Stg.make(right[i+(1<<(k-1))][j][k-1],right[i][j][k],INF);
        Stg.make(right[i][j+(1<<(k-1))][k-1],right[i][j][k],INF);
        Stg.make(right[i+(1<<(k-1))][j+(1<<(k-1))][k-1],right[i][j][k],INF);
    }
     
    for(i=2;i<=60;++i)len[i]=len[i>>1]+1;
     
    int x1,y1,x2,y2,l;
    while(a--){
        scanf("%d%d%d%d%d",&x,&x1,&y1,&x2,&y2);l=len[x2-x1+1];
        Stg.make(S,++cnt,x);
        Stg.make(cnt,left[x1][y1][l],INF);
        Stg.make(cnt,left[x1][y2-(1<<l)+1][l],INF);
        Stg.make(cnt,left[x2-(1<<l)+1][y1][l],INF);
        Stg.make(cnt,left[x2-(1<<l)+1][y2-(1<<l)+1][l],INF);
    }
    while(b--){
        scanf("%d%d%d%d%d",&x,&x1,&y1,&x2,&y2);l=len[x2-x1+1];
        Stg.make(++cnt,T,x);
        Stg.make(right[x1][y1][l],cnt,INF);
        Stg.make(right[x1][y2-(1<<l)+1][l],cnt,INF);
        Stg.make(right[x2-(1<<l)+1][y1][l],cnt,INF);
        Stg.make(right[x2-(1<<l)+1][y2-(1<<l)+1][l],cnt,INF);
    }
     
    printf("%d",Stg.Maxflow(S,T,cnt));
     
    return 0;
}

BZOJ3628:[JLOI2014]天天酷跑 dp

思路:

绝对是逗逼题,今年四月份的时候我居然都不会做...果然是幼儿园水平无力啊...

枚举Maxh,以及Maxcombo(什么枚举?没错就是枚举)

用一个Hash表存一下状态,然后随便分层dp就过了.

具体的状态设计见代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
int n,m,c1,c2;
 
int w[100010][21];
int Maxh,Maxn;
int res,ansh,ansn;
 
int f[2][21][21][6];
struct State{
    int y,h,t;
    State(){}
    State(int _y,int _h,int _t):y(_y),h(_h),t(_t){}
};
struct HashSet{
    int s[21][21][6],cnt;
    State sav[21*21*6];
    inline void reset(){cnt=0,memset(s,0xc0,sizeof s);}
    inline int Max(){
        int res=-1<<30;
        for(int j=1;j<=cnt;++j)res=max(res,s[sav[j].y][sav[j].h][sav[j].t]);
        return res;
    }
    inline void insert(State x,int w){
        if(s[x.y][x.h][x.t]==0xc0c0c0c0)s[x.y][x.h][x.t]=w,sav[++cnt]=x;
        else if(w>s[x.y][x.h][x.t])s[x.y][x.h][x.t]=w;
    }
}S[2];
inline void relax(int lab,int x,int y,int h,int t,int lastw){
    if(w[x][y]==-1)return;
    S[lab].insert(State(y,h,t),lastw+w[x][y]);
}
inline void Solve(){
    int now=0,last=1,ans=0xc0c0c0c0;
    S[now].reset(),S[now].insert(State(1,0,Maxn),0);
    register int i,j;
    State p;int w;
    for(i=1;i<=n;++i){
        swap(now,last),S[now].reset();
        for(j=1;j<=S[last].cnt;++j){
            p=S[last].sav[j],w=S[last].s[p.y][p.h][p.t];
            if(p.y==1){
                relax(now,i,1,0,Maxn,w);
                relax(now,i,2,Maxh-1,Maxn-1,w);
            }
            else if(p.h==0){
                if(p.t)relax(now,i,p.y+1,Maxh-1,p.t-1,w);
                relax(now,i,p.y-1,0,p.t,w);
            }
            else relax(now,i,p.y+1,p.h-1,p.t,w);
        }
    }
    ans=max(ans,S[now].Max()-(Maxn-1)*c2-(Maxh-1)*c1);
    if(ans>res)res=ans,ansn=Maxn,ansh=Maxh;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&c1,&c2);register int i,j;
    for(j=1;j<=m;++j)for(i=1;i<=n;++i)scanf("%d",&w[i][j]);
     
    res=0xc0c0c0c0;
    for(Maxn=1;Maxn<=5;++Maxn)
        for(Maxh=1;Maxh*Maxn<m;++Maxh)
            Solve();
     
    if(res==0xc0c0c0c0)puts("mission failed");else printf("%d %d %d\n",res,ansn,ansh);
     
    return 0;
}

BZOJ3771:Triple FFT+容斥原理

思路:

首先第一次看的时候认为是神题.

再一次看的时候卧槽这不是FFT裸题么.

然后写的时候发现有点坑...

(FFT都告诉你了难道还不会么)

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
static const f2 pi=acos(-1.0);
 
struct Complex{
    f2 u,v;
    Complex(){}
    Complex(f2 _u,f2 _v):u(_u),v(_v){}
     
    Complex operator+(const Complex&B)const{return Complex(u+B.u,v+B.v);}
    Complex operator-(const Complex&B)const{return Complex(u-B.u,v-B.v);}
    Complex operator*(const Complex&B)const{return Complex(u*B.u-v*B.v,u*B.v+v*B.u);}
    Complex operator*(const f2&p)const{return Complex(p*u,p*v);}
    Complex operator/(const f2&p)const{return Complex(u/p,v/p);}
    inline void operator=(const f2&p){u=p,v=0;}
    inline void operator+=(const Complex&B){u+=B.u,v+=B.v;}
    inline void operator-=(const Complex&B){u-=B.u,v-=B.v;}
    inline void operator*=(const Complex&B){f2 uu=u*B.u-v*B.v,vv=u*B.v+v*B.u;u=uu,v=vv;}
    inline void operator*=(const f2&p){u*=p,v*=p;}
    inline void operator/=(const f2&p){u/=p,v/=p;}
};
 
inline int revbit(int x,int b){
    int res=0;for(int i=0;i<b;++i)if((x>>i)&1)res+=1<<(b-1-i);return res;
}
inline void fft(Complex A[],int n,int rev){
    register int i,j,k;
    int bit=0,tmp=n;for(;tmp^1;tmp>>=1)++bit;
    int ano;for(i=0;i<n;++i){ano=revbit(i,bit);if(i<ano)swap(A[i],A[ano]);}
    Complex wn,w,t;
    for(k=2;k<=n;k<<=1)
        for(wn=Complex(cos(2*pi/k),rev*sin(2*pi/k)),i=0;i<n;i+=k)
            for(w=1,j=0;j<k/2;++j,w*=wn)
                t=w*A[i+j+k/2],A[i+j+k/2]=A[i+j]-t,A[i+j]+=t;
    if(rev==-1)for(i=0;i<n;++i)A[i]/=n;
}
 
#define N 131072
 
inline void mul(Complex A[],Complex B[],Complex C[]){
    static Complex sa[N],sb[N];
    memcpy(sa,A,N*sizeof(Complex)),memcpy(sb,B,N*sizeof(Complex));
    fft(sa,N,1),fft(sb,N,1);
    for(int i=0;i<N;++i)C[i]=sa[i]*sb[i];
    fft(C,N,-1);
}
 
Complex A[N],A2[N],A3[N];
Complex mul2[N],mul3[N],mul3_2[N];
 
long long res[N];
 
long long up(const f2&p){
    return(long long)(p+.5);
}
 
int main(){
    int n;scanf("%d",&n);register int i,j;
    int x;while(n--)scanf("%d",&x),A[x]=1,A2[2*x]=1,A3[3*x]=1;
     
    mul(A,A,mul2);
    mul(mul2,A,mul3);
    mul(A,A2,mul3_2);
     
    for(int i=0;i<N;++i)mul2[i]-=A2[i],mul2[i]*=.5;
    for(int i=0;i<N;++i)mul3_2[i]-=A3[i];
    for(int i=0;i<N;++i)mul3[i]-=A3[i]+mul3_2[i]*3,mul3[i]/=6;
     
    for(int i=0;i<N;++i)res[i]+=up(A[i].u)+up(mul2[i].u)+up(mul3[i].u);
     
    for(int i=0;i<N;++i)if(res[i]!=0)printf("%d %lld\n",i,res[i]);
    return 0;
}

BZOJ2322:[BeiJing2011]梦想封印(&&BZOJ3793) 线性基

思路:

首先必定是离线处理了.

然后呢,根据WC2011的最大异或和路径这道题目的做法,我们显然应该分成拆分成路径和环进行处理.

由于题目规定的是,从1开始的任意路径,所以我们得处理出从1开始到所有点结束时的异或和.

 

如果只是单独求一次的话怎么搞呢?

把所有的从起点开始的简单路径的异或和拿出来.

然后再把所有的简单环的异或和拿出来,搞成一个线性基.令线性基中有\(k\)个元素.

考虑一种算法,我们把所有简单路径都放在线性基中处理一下得到\(2^k\)种方案,但是会有重复!

若两条简单路径的异或和在线性基中消元之后的结果相同,那么这两个\(2^k\)种方案必定存在一一映射.(这个暂时不太会证,不过好像显然?)

至于不能为0的限制,就简单处理一下就好了.

 

可是现在要支持动态加边.

考虑加入一条边的影响.假设现在已经有一个线性基,以及若干在当前线性基下消元后不同的的若干简单路径.

加入一条边可能拓展从起点开始的有根生成树,从而多出一些简单路径,我们要尝试加入简单路径中;也可能多出一些新的环,我们要用这个去更新线性基.

这就是大体思路.

关键是维护不同的简单路径以及生成树.参考的Kanari神犇的代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
 
typedef long long LL;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*fS=buf,*fT=buf;
        if(fS==fT){fT=(fS=buf)+fread(buf,1,L,stdin);if(fS==fT)return EOF;}
        return*fS++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[20010*20],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 5010
#define M 20010
#define Q 20010
int n,m,q;
struct Edge{
    int u,v;LL l;bool ban;
    Edge(){}
    Edge(int _u,int _v,LL _l):u(_u),v(_v),l(_l){}
}E[M];
 
int head[N],next[M<<1],end[M<<1],ban[M<<1];LL len[M<<1];
inline void addedge(int a,int b,LL c){static int q=1;end[q]=b,next[q]=head[a],head[a]=q,len[q++]=c;}
inline void make(int a,int b,LL c){addedge(a,b,c),addedge(b,a,c);}
 
int seq[Q];
 
LL ins[64];int nums;
LL calc(LL x){
    for(int i=63;i>=0;--i)if((x>>i)&1)x^=ins[i];return x;
}
void insert(LL x){
    for(int i=63;i>=0;--i)if((x>>i)&1){
        if(!ins[i]){ins[i]=x,++nums;break;}else x^=ins[i];
    }
}
 
bool vis[N];LL w[N];
 
map<LL,int>S;int stk[N],top,sstk[N],stop;
 
int sav[N],get;
inline void setinqueue(){
    S.clear();stop=0;
    for(int i=1;i<=top;++i){
        int tmp=calc(w[stk[i]]);
        if(S[tmp]==0)S[tmp]=1,sstk[++stop]=stk[i];
    }
    for(int i=1;i<=get;++i){
        int tmp=calc(w[sav[i]]);
        if(S[tmp]==0)S[tmp]=1,sstk[++stop]=sav[i];
    }
    top=stop,memcpy(stk+1,sstk+1,stop*sizeof(int));
}
 
void extend(int x){
    vis[x]=1;if(x==1)sav[++get]=1;
    for(int j=head[x];j;j=next[j]){
        if(!vis[end[j]]){
            w[end[j]]=w[x]^len[j];
            sav[++get]=end[j];
            extend(end[j]);
        }
        else insert(w[x]^w[end[j]]^len[j]);
    }
}
 
LL getans(){
    return(1LL<<nums)*(top-1)+(1LL<<nums)-1;
}
 
LL res[Q];
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    Fio::Get(n),Fio::Get(m),Fio::Get(q);register int i;
    for(i=1;i<=m;++i)Fio::Get(E[i].u),Fio::Get(E[i].v),Fio::Get(E[i].l);
     
    for(i=1;i<=q;++i)Fio::Get(seq[i]),E[seq[i]].ban=1;
    for(i=1;i<=m;++i)if(!E[i].ban)make(E[i].u,E[i].v,E[i].l);
     
    get=0;extend(1);setinqueue();
     
    for(i=q;i>=0;--i){
        res[i]=getans();
         
        if(i==0)break;
        make(E[seq[i]].u,E[seq[i]].v,E[seq[i]].l);
        get=0;
        if(vis[E[seq[i]].u]&&vis[E[seq[i]].v])insert(w[E[seq[i]].u]^w[E[seq[i]].v]^E[seq[i]].l);
        else if(vis[E[seq[i]].u])extend(E[seq[i]].u);
        else if(vis[E[seq[i]].v])extend(E[seq[i]].v);
        setinqueue();
    }
     
    for(i=0;i<=q;++i)Fio::print(res[i]);
     
    return Fio::final(),0;
}

BZOJ3569:DZY Loves Chinese II(&&BZOJ3563) 高斯消元+构造

思路:

首先构造出原无向图的一棵生成树,然后就有一些非树边以及一些树边了吧.

给非树边随机一个unsignde long long的权值,并令每个树边的权值等于覆盖这条树边的所有非树边权值的异或和.

考虑删去哪些边之后可以使得原图不连通.

如果只删掉非树边显然是没用的.

那么我们必须删掉一条树边,以及覆盖这条树边的所有非树边!注意到这些边权值的异或和正好为0,因此问题转化为存不存在一个异或和为0的子集.于是高斯消元水.

时间复杂度\(O(n+64kq)\).

 

另外I可以拿一个有趣的方法水过...详情见代码.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
typedef unsigned long long LLU;
 
inline LLU get(){
    LLU res=1;for(int i=1;i<=4;++i)res*=rand();return res;
}
 
#define N 100010
#define M 500010
int head[N],next[M<<1],end[M<<1];LLU f[M<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int pa[N];
LLU v[N];
inline void dfs(int x){
    for(int j=head[x];j;j=next[j])if(!pa[end[j]]&&end[j]!=1)pa[end[j]]=x,dfs(end[j]);
}
inline void dfs2(int x){
    for(int j=head[x];j;j=next[j])
        if(pa[end[j]]==x)
            dfs2(end[j]),v[x]^=v[end[j]];
    for(int j=head[x];j;j=next[j])
        if(pa[end[j]]==x)
            f[(j+1)/2*2-1]=f[(j+1)/2*2]=v[end[j]];
}
 
LLU ins[64];
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    int a,b;for(i=1;i<=m;++i)scanf("%d%d",&a,&b),make(a,b);
     
    dfs(1);
    LLU now;
    for(i=1;i<=n;++i)for(j=head[i];j;j=next[j])if(i!=pa[end[j]]&&pa[i]!=end[j]){
        now=get();f[(j+1)/2*2-1]^=now,f[(j+1)/2*2]^=now,v[i]^=now,v[end[j]]^=now;
    }
    dfs2(1);
     
    int lans=0,q,t,x;LLU tmp;scanf("%d",&q);
    while(q--){
        scanf("%d",&t);
        memset(ins,0,sizeof ins);
        bool ok=1;
        for(i=1;i<=t;++i){
            scanf("%d",&x),tmp=f[2*(x^=lans)];
            for(j=63;j>=0;--j)if((tmp>>j)&1){
                if(!ins[j]){ins[j]=tmp;break;}else tmp^=ins[j];
            }
            if(!tmp)ok=0;
        }
        if(ok)puts("Connected"),++lans;else puts("Disconnected");
    }
     
    return 0;
}
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
#define M 500010
int head[N],next[M<<1],end[M<<1],ban[M<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
char s[10010];
 
int stk[16<<1],top;
 
bool vis[N];
void dfs(int x){
    vis[x]=1;for(int j=head[x];j;j=next[j])if(!ban[j]&&!vis[end[j]])dfs(end[j]);
}
 
int sav[20],num;
inline bool digit(char c){
    return c>='0'&&c<='9';
}
void get(){
    gets(s);int len=strlen(s);
    num=0;
    int tmp,i,j;
    for(i=0;i<len;){
        if(digit(s[i])){
            tmp=s[i]-'0';
            for(j=i+1;j<len&&digit(s[j]);++j)tmp=10*tmp+s[j]-'0';
            sav[++num]=tmp,i=j;
        }else++i;
    }
}
 
int lans[50010];
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    int a,b;for(i=1;i<=m;++i)scanf("%d%d",&a,&b),make(a,b);
     
    int Q;scanf("%d",&Q);gets(s);
     
    for(i=1;i<=Q;++i){
        get();
        lans[i-1]=(num-1)^sav[1];
    }
     
    for(i=1;i<Q;++i)if(lans[i]>lans[i-1])puts("Connected");else puts("Disconnected");
     
    for(i=2;i<=num;++i)sav[i]^=lans[Q-1],ban[2*sav[i]-1]=ban[2*sav[i]]=1;
    int cnt=0;for(i=1;i<=n;++i)if(!vis[i])dfs(i),++cnt;
    if(cnt==1)puts("Connected");else puts("Disconnected");
     
    return 0;
}

BZOJ2338:[HNOI2011]数矩形 暴力+计算几何

思路:

首先搞出所有的线段,然后中点相同的放在一起,并且长度相同的放在一起.

那么,中点相同并且长度相同,这两个线段就能够构成一个矩形.

这样的线段不会超过\(O(n)\)条,所以我们可以直接暴力枚举.

(其实我觉得可以把所有的线段以中点为原点进行极角序排序,然后我们就是要找出两条线段使得它们之间的夹角尽可能接近90,这大概就可以线性扫描了.)

本代码完全避免了精度问题!速来点赞!

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y):x(_x),y(_y){}
 
    bool operator<(const Point&B)const{return(x!=B.x)?x<B.x:y<B.y;}
    bool operator!=(const Point&B)const{return(x!=B.x)||(y!=B.y);}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
};
LL Cross(const Point&a,const Point&b){return(LL)a.x*b.y-(LL)a.y*b.x;}
LL Getans(Point p1,Point p2,Point q1,Point q2){
    LL res=Cross(p1-q1,p1-q2);
    return res<0?-res:res;
}
 
int gcd(int a,int b){return(!b)?a:gcd(b,a%b);}
 
struct Double{
    int x,y;
    Double(){}
    Double(int _x,int _y):x(_x),y(_y){}
 
    bool operator<(const Double&B)const{return(LL)x*B.y<(LL)y*B.x;}
};
 
 
#define N 1510
struct Segment{
    Point P1,P2;LL dis;
    bool insequal(const Segment&B)const{
        if(P1.x+P2.x!=B.P1.x+B.P2.x)return 0;
        if(P1.y+P2.y!=B.P1.y+B.P2.y)return 0;
        return 1;
    }
    bool operator<(const Segment&B)const{
        if(P1.x+P2.x!=B.P1.x+B.P2.x)return P1.x+P2.x<B.P1.x+B.P2.x;
        if(P1.y+P2.y!=B.P1.y+B.P2.y)return P1.y+P2.y<B.P1.y+B.P2.y;
        return dis<B.dis;
    }
    bool operator==(const Segment&B)const{return insequal(B)&&dis==B.dis;}
}S[N*N>>1];int id;
 
int x[N],y[N],n;
 
inline LL sqr(int x){
    return(LL)x*x;
}
 
int main(){
    scanf("%d",&n);register int i,j,k,p;for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
 
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)++id,S[id].P1=Point(x[i],y[i]),S[id].P2=Point(x[j],y[j]),S[id].dis=sqr(x[i]-x[j])+sqr(y[i]-y[j]);
     
    sort(S+1,S+id+1);
 
    LL res=0;
    for(i=1;i<=id;i=j+1){
        for(j=i;j!=id&&S[j]==S[j+1];++j);
        for(k=i;k<=j;++k)for(p=k+1;p<=j;++p)res=max(res,Getans(S[k].P1,S[k].P2,S[p].P1,S[p].P2));
    }
 
    cout<<res<<endl;
 
    return 0;
}

BZOJ2957:楼房重建 分块

逗逼分块,写完题解结果被吞QoQ.直接贴代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
typedef long long LL;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*fS=buf,*fT=buf;
        if(fS==fT){fT=(fS=buf)+fread(buf,1,L,stdin);if(fS==fT)return EOF;}
        return*fS++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[600010],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 100010
int begin[510],end[510],bel[N];
 
double res[N];
 
struct Stack{
    int top;
    double s[510];
    Stack():top(0){}
    inline void upd(int l,int r){
        top=0;
        for(int i=l;i<=r;++i)if(!top||res[i]>s[top])s[++top]=res[i];
    }
    inline int getans(const f2&x){
        if(!top||s[top]<=x)return 0;
        int L=1,R=top,mid;
        while(L<R){
            mid=(L+R)>>1;
            if(s[mid]>x)R=mid;else L=mid+1;
        }return top-L+1;
    }
}S[510];
 
int main(){
    int n,m;Fio::Get(n),Fio::Get(m);register int i,j;
 
    int persize=sqrt(n),nums=0;
    for(i=1;i*persize<=n;++i)begin[++nums]=(i-1)*persize+1,end[nums]=i*persize;
    if(n%persize)++nums,begin[nums]=(nums-1)*persize+1,end[nums]=n;
    for(i=1;i<=nums;++i)for(j=begin[i];j<=end[i];++j)bel[j]=i;
 
    for(i=1;i<=n;++i)res[i]=0;
 
    int x,y,ret;f2 Max;
    while(m--){
        Fio::Get(x),Fio::Get(y);
        res[x]=(f2)y/x;
        S[bel[x]].upd(begin[bel[x]],end[bel[x]]);
        for(ret=0,Max=0,i=1;i<=nums;++i){
            ret+=S[i].getans(Max);
            if(S[i].top&&S[i].s[S[i].top]>Max)Max=S[i].s[S[i].top];
        }
        Fio::print(ret);
    }
 
    return Fio::final(),0;
}