10
23
2017
0

仙人掌-圆方树

圆方树:

http://immortalco.blog.uoj.ac/blog/1955

仙人掌最大独立集

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<complex>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int INF=1e9+10;
int n,m,x,y,N;
namespace Tree{
	int nedge;
	int n;
	int nxt[500010],f[500010][2],g[500010][2],hed[500010],too[500010];
	void init(){
		memset(hed,0,sizeof(hed));
		nedge=1;
	}
	void ae(int x,int y){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
	}
	/*
	void prin(){
		FOR(x,1,n){
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (x<y) printf("%d %d\n",x,y);
			}
		}
	}
	*/
	void dfs(int x,int l){
		if (x<=N){
			f[x][0]=0,f[x][1]=1;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				dfs(y,x);
				f[x][0]+=max(f[y][0],f[y][1]);
				f[x][1]+=f[y][0];
			}
		}
		else{
			int son=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				dfs(y,x);
			}
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				g[++son][0]=f[y][0];
				g[son][1]=f[y][1];
			}
			FOR(i,2,son){
				g[i][0]+=max(g[i-1][0],g[i-1][1]);
				g[i][1]+=g[i-1][0];
			}
			f[x][1]=max(g[son][0],g[son][1]);
			son=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				g[++son][0]=f[y][0];
				g[son][1]=f[y][1];
			}
			g[1][1]=-INF;
			FOR(i,2,son){
				g[i][0]+=max(g[i-1][0],g[i-1][1]);
				g[i][1]+=g[i-1][0];
			}
			f[x][0]=g[son][0];
		}
	}
}
namespace Cactus{
	int nedge;
	int n,dfs_block=0;
	bool u[500010];
	int nxt[500010],dfn[500010],fa[500010],F[500010],hed[500010],too[500010];
	void init(){
		nedge=1;
		memset(dfn,0,sizeof(dfn));
		sizeof(hed,0,sizeof(hed));
		memset(fa,0,sizeof(fa));
		memset(F,0,sizeof(F));
		memset(u,0,sizeof(u));
	}
	void ae(int x,int y){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
	}
	void dfs(int x,int l){
		dfn[x]=++dfs_block;
		for (int i=hed[x];i;i=nxt[i]){
			int y=too[i];
			if (y==l) continue;
			if (!dfn[y]) fa[y]=x,F[y]=i,dfs(y,x);
			if (dfn[y]>dfn[x]) continue;
			int t=x;
			++Tree::n;
			u[i]=1;
			while (1){
				Tree::ae(t,Tree::n);
				Tree::ae(Tree::n,t);
				if (t==y) break;
				u[F[t]]=1;
				t=fa[t];
			}
		}
	}
	void work(){
		FOR(i,1,nedge) u[i]=0;
		dfs(1,0);
		FOR(i,1,n){
			for (int j=hed[i];j;j=nxt[j]){
				int y=too[j];
				if (u[j] || u[j^1]) continue;
				Tree::ae(i,y);
			}
		}
	}
};
int main(){
	Cactus::init();
	Tree::init();
	scanf("%d%d",&n,&m);
	N=n;
	Cactus::n=n;
	Tree::n=n;
	FOR(i,1,m){
		getint(x),getint(y);
		Cactus::ae(x,y);
		Cactus::ae(y,x);
	}
	Cactus::work();
	Tree::dfs(1,0);
//	Tree::prin();
	printf("%d\n",max(Tree::f[1][0],Tree::f[1][1]));
	return 0;
}

仙人掌直径

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<complex>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int INF=1e9+10;
int n,m,x,y,ans,N,k,stk[500010];
namespace Tree{
	int nedge;
	int n;
	int nxt[500010],Q[500010],f[500010],hed[500010],too[500010];
	void init(){
		memset(hed,0,sizeof(hed));
		nedge=1;
	}
	void ae(int x,int y){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
	}
	
	void prin(){
		FOR(x,1,n){
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (x<y) printf("%d %d\n",x,y);
			}
		}
	}
	void dfs(int x,int l){
		if (x<=N){
			int mx1=0,mx2=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				dfs(y,x);
				if (f[y]+1>=mx1) mx2=mx1,mx1=f[y]+1;
				else if (f[y]+1>=mx2) mx2=f[y]+1;
			}
			f[x]=mx1;
			ans=max(ans,mx1+mx2);
		}
		else{
			int top=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				dfs(y,x);
				++top;
			}
			int cnt=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (y==l) continue;
				++cnt;
				stk[cnt]=y;
				f[x]=max(f[x],f[y]+min(cnt-1,top-cnt));
			}
			/*
			FOR(i,1,top)
				FOR(j,i+1,top)
					ans=max(ans,f[stk[i]]+f[stk[j]]+min(j-i,i+top+1-j));
			*/
			stk[++top]=0;
			FOR(i,1,cnt) stk[++top]=stk[i];
			int l=1,r=0;
			FOR(i,1,(cnt+1)/2){
				while (l<=r && f[stk[i]]-i>=f[stk[Q[r]]]-Q[r]) --r;
				Q[++r]=i;
			}
			for (int p=1,q=(cnt+1)/2+1;p<=cnt;++p,++q){
				while (Q[l]<p) ++l;
				ans=max(ans,q-Q[l]+f[stk[q]]+f[stk[Q[l]]]);
				while (l<=r && f[stk[q]]-q>=f[stk[Q[r]]]-Q[r]) --r;
				Q[++r]=q;
			}
		}
	}
}
namespace Cactus{
	int nedge;
	int n,dfs_block=0;
	bool u[500010];
	int nxt[500010],dfn[500010],fa[500010],F[500010],hed[500010],too[500010];
	void init(){
		nedge=1;
		memset(dfn,0,sizeof(dfn));
		sizeof(hed,0,sizeof(hed));
		memset(fa,0,sizeof(fa));
		memset(F,0,sizeof(F));
		memset(u,0,sizeof(u));
	}
	void ae(int x,int y){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
	}
	void dfs(int x,int l){
		dfn[x]=++dfs_block;
		for (int i=hed[x];i;i=nxt[i]){
			int y=too[i];
			if (y==l) continue;
			if (!dfn[y]) fa[y]=x,F[y]=i,dfs(y,x);
			if (dfn[y]>dfn[x]) continue;
			int t=x;
			++Tree::n;
			u[i]=1;
			while (1){
				Tree::ae(t,Tree::n);
				Tree::ae(Tree::n,t);
				if (t==y) break;
				u[F[t]]=1;
				t=fa[t];
			}
		}
	}
	void work(){
		FOR(i,1,nedge) u[i]=0;
		dfs(1,0);
		FOR(i,1,n){
			for (int j=hed[i];j;j=nxt[j]){
				int y=too[j];
				if (u[j] || u[j^1]) continue;
				Tree::ae(i,y);
			}
		}
	}
};
int main(){
	Cactus::init();
	Tree::init();
	scanf("%d%d",&n,&m);
	N=n;
	Cactus::n=n;
	Tree::n=n;
	FOR(i,1,m){
		getint(k);
		FOR(j,1,k) getint(stk[j]);
		FOR(j,2,k) Cactus::ae(stk[j-1],stk[j]),Cactus::ae(stk[j],stk[j-1]);
	}
	Tree::f[0]=-INF;
	Cactus::work();
//	Tree::prin();
	Tree::dfs(1,0);
	cout<<ans<<endl;
	return 0;
}
Category: 板子 | Tags:
10
20
2017
0

卡特兰数

普及了一些卡特兰数的知识。

接下来尝试解决一个问题。

求有多少长度为2n的01串满足任何非空前缀0的数量都不等于1的数量。

首先考虑对于第一位,选0和选1方案数是一样的,最后再*2就可以了。

假设第一位是1,那么对于后面的2n-1位,只要满足任何前缀1的数量>=0的数量。

假设后面的2n-1位中有m个0(m<=2n-1-m,0<=m<=n-1),

那么根据上面得到的东西,方案数是C(2n-1,m)-C(2n-1,m-1)

所以总的是

sigma(C(2n-1,m)-C(2n-1,m-1)) (m=0..n-1)

然后相同的项都抵消了剩下

=C(2n-1,n-1)

最后乘2

C(2n-1,n-1)*2=C(2n-1,n-1)+C(2n-1,n)=C(2n,n)

Category: 板子 | Tags:
10
19
2017
0

树链求交

void ae(int x,int y){
    nxt[++nedge]=hed[x];
    hed[x]=nedge;
    too[nedge]=y;
}
void lca_init(){
    FOR(i,1,n) mx=max(mx,dep[i]);
    mx=log2(mx);
    FOR(j,1,mx)
        FOR(i,1,n)
            anc[i][j]=anc[anc[i][j-1]][j-1];
}
int lca(int x,int y){
    if (dep[x]>dep[y]) swap(x,y);
    FORD(i,mx,0)
        if (dep[y]-(1<<i)>=dep[x]) y=anc[y][i];
    if (x==y) return x;
    FORD(i,mx,0)
        if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return anc[x][0];
}
pa intersect(int x,int y,int p,int q){
    int s=lca(x,p),t=lca(y,q);
    if (dep[s]<dep[y] || dep[s]<dep[q]) return mp(0,0);
    return mp(s,y+q-t);
}
pa chainintersect(int x,int y,int p,int q){
    int z=lca(x,y),r=lca(p,q);
    pa chain[4],inter[2];
    chain[0]=intersect(x,z,p,r);
    chain[1]=intersect(x,z,q,r);
    chain[2]=intersect(y,z,p,r);
    chain[3]=intersect(y,z,q,r);
    int num=0;
    FOR(i,0,3)
        if (chain[i].fi!=chain[i].se) inter[num++]=chain[i];
    if (!num){
        FOR(i,0,3)
            if (chain[i].fi) return chain[i];
        return mp(0,0);
    }
    if (num==1) return inter[0];
    if (inter[0].fi==inter[1].fi) return mp(inter[0].se,inter[1].se);
    else if (inter[0].fi==inter[1].se) return mp(inter[0].se,inter[1].fi);
    else if (inter[0].se==inter[1].fi) return mp(inter[0].fi,inter[1].se);
    else return mp(inter[0].fi,inter[1].fi);
}
void mkt(int x,int l){
    dep[x]=dep[l]+1;
    anc[x][0]=l;
    for (int i=hed[x];i;i=nxt[i]){
        int y=too[i];
        if (y==l) continue;
        mkt(y,x);
    }
}

 

Category: 板子 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com