题意:

有n(n<=300)只袋鼠，袋鼠i的体积为a_i，口袋大小为bi(a_i>b_i)。

把袋鼠i放入袋鼠j的口袋里。

要求此时袋鼠i和j的口袋里没有袋鼠，且袋鼠i,j不在其它袋鼠口袋里。

不断操作直到不能操作为止，有多少种不同的终止状态，对10⁹+7取模。

分析:

考虑一种合法的终止状态。

一定存在一只袋鼠，比它小的袋鼠都被装了，能装它的袋鼠都装了其它袋鼠。

先将a和b分别排序。

然后枚举这只倒霉的袋鼠i，dp算出方案数。

将a和b都按是否大于a_i分成左右两边。

用f[i][j]表示a中左边前i个与b中左边匹配j对的方案数。

用g[i][j]表示b中右边前i个与a中右边匹配j对的方案数。

枚举a中左边与b中右边匹配的对数k，则这k对有k!种匹配方法。

再乘上ab两边分别匹配的方案数，就是所有的方案数。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>inline void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)
#define dat(i,a,b) for(int i=a;i>b;--i)

const int MAXN=305;
const int Mod=1e9+7;

int n,ans;

int fac[MAXN];

int f[MAXN][MAXN],g[MAXN][MAXN];

int a[MAXN],b[MAXN];

inline void Init(){
	Scan(n);
	rep(i,1,n+1){
		Scan(a[i]),Scan(b[i]);
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	fac[0]=1;
	rep(i,1,n+1)
		fac[i]=1ll*fac[i-1]*i%Mod;
}

inline void Solve(){
	rep(wuke,1,n+1){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		int r=upper_bound(b+1,b+n+1,a[wuke])-b;
		f[0][0]=1;
		rep(i,1,r)
			rep(j,0,i+1){
				f[i][j]=f[i-1][j];
				int x=lower_bound(a+1,a+wuke,b[i])-a-1;
				if(j&&x-j+1>0){
					f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*(x-j+1)%Mod)%Mod;
				}
			}
		g[n+1][0]=1;
		dat(i,n,wuke)
			rep(j,0,n-i+2){
				g[i][j]=g[i+1][j];
				int x=n-(upper_bound(b+r,b+n+1,a[i])-b)+1;
				if(j&&x-j+1>0){
					g[i][j]=(g[i][j]+1ll*g[i+1][j-1]*(x-j+1)%Mod)%Mod;
				}
			}
		int s=min(wuke-1,n-r+1);
		rep(i,0,s+1){
			ans=(ans+1ll*f[r-1][wuke-1-i]*g[wuke+1][n-r+1-i]%Mod*fac[i]%Mod)%Mod;
		}
	}
	printf("%d\n",ans);
}

int main(){
	freopen("kangaroo.in","r",stdin);
	freopen("kangaroo.out","w",stdout);
	Init(); Solve(); return 0;
}

题意:

给出一棵以1为根的有向树，每个节点上有一个字符(只会是小写字母)。

多次询问，给出一个字符集合，要求统计树上合法的串的数量。

合法的串满足4个要求:

1.是树上某个点向根方向的走所形成的串

2.串中所有的字符来自给定的字符集合

3.给定的字符集合中的每一个字符都在串中出现过

4.没有被任意一个满足前三条条件的路径完全包含

树的节点数和询问次数均不超过10⁵

分析:

如果一个路径合法的串，当且仅当该路径向两端延伸1个位置都不能有在路径出现的字符。

我们记录每个节点向根方向的最近的出现某个字符的节点，显然合法的串只可能出现在这条路径上。

再记录每个节点所有儿子的字符集合，对于每个节点按深度枚举要走到的字符，判断是否合法。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>inline void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=50005;
const int Alpha=26;
typedef long long ll;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

char a[MAXN],b[MAXN];

int p[MAXN],dep[MAXN];

int last[MAXN][Alpha];

ll son[MAXN];

void dfs(int x){
	rep(i,0,Alpha)
		last[x][i]=last[p[x]][i];
	last[x][a[p[x]]-'a']=p[x];
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			p[y]=x;
			dep[y]=dep[x]+1;
			son[x]|=1ll<<(a[y]-'a');
			dfs(y);
		}
}

int n,m;

int ans[MAXN];

const int SIZE=(1<<18)-1;
struct hash{
	ll set[MAXN];
	int next[MAXN],id[MAXN];
	int head[SIZE+1],tot;
	inline void insert(ll s,int Id){
		int p=s&SIZE;
		set[++tot]=s,next[tot]=head[p];
		id[tot]=Id,head[p]=tot;
	}
	inline void update(ll s){
		int p=s&SIZE;
		for(int i=head[p];i;i=next[i])
			if(set[i]==s)++ans[id[i]];
	}
}set;

inline bool cmp(int a,int b){return dep[a]>dep[b];}

inline void deal(int x){
	static int q[Alpha+1];
	rep(i,0,Alpha)q[i]=last[x][i];
	sort(q,q+Alpha,cmp);
	ll S=1ll<<(a[x]-'a');
	rep(i,0,Alpha){
		if(S&son[x])break;
		if(!q[i])break;
		ll s=1ll<<(a[q[i]]-'a');
		if(!(S&s)){
			set.update(S);
		}
		S|=s;
	}
	if(S&son[x])return;
	set.update(S);
}

int main(){
	freopen("loneliness.in","r",stdin);
	freopen("loneliness.out","w",stdout);
	Scan(n),Scan(m);
	scanf("%s",a+1);
	rep(i,1,n){
		int u,v;
		Scan(u),Scan(v);
		AddEdge(u,v);
	}
	rep(i,1,m+1){
		ll S=0;
		scanf("%s",b);
		int l=strlen(b);
		rep(j,0,l){
			S|=1ll<<(b[j]-'a');
		}
		set.insert(S,i);
	}
	dep[1]=1,dfs(1);
	rep(i,1,n+1)deal(i);
	rep(i,1,m+1)printf("%d\n",ans[i]);
	return 0;
}

题意:

给出一个n*m(n<=10³,m<=10³)的黑白棋棋盘.

棋盘上有t(t<=10⁵)个位置坏掉了。

除了坏掉的位置之外，每个位置上有且只有1颗棋子，且初始时白面向上。

你可以进行k(k<=10⁹)次操作。

每次操作选择两颗棋子，将以它们为对角线的矩形内的所有棋子状态取反(不一定是主对角线).

问k次操作后，白面向上的棋子个数的期望值是多少。

分析:

由于期望具有线性性，我们可以分别计算每颗棋子的期望最后再求和。

假设某颗棋子在1次操作中被翻转的概率为p。

那么容易推出它k次操作后状态不变的概率为(1+(1-2*p)^k)/2.

现在问题就在于如何快速求出p.

由容斥得(x,y)被翻转的情况有:

|([1,x]×[1,y],[x,y]×[n,m])|+|([x,n]×[1,y],[1,x]×[y,m])|-|([x,x]×[1,y],[x,x]×[y,m])|-|([1,x]×[y,y],[x,n]×[y,y])|+1

用前缀和优化就好了。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=1005;

int n,m,k,t;

bool a[MAXN][MAXN];

int sum[MAXN][MAXN];

inline int Sum(int x1,int y1,int x2,int y2){
	int res=sum[x2][y2]-sum[x2][y1-1];
	return res-(sum[x1-1][y2]-sum[x1-1][y1-1]);
}

inline void Init(){
	Scan(n),Scan(m),Scan(k),Scan(t);
	rep(i,1,n+1)rep(j,1,m+1)sum[i][j]=a[i][j]=1;
	rep(i,1,t+1){
		int x,y;
		Scan(x),Scan(y);
		sum[x][y]=a[x][y]=0;
	}
	rep(i,1,n+1)rep(j,1,m+1)sum[i][j]+=sum[i][j-1];
	rep(i,1,n+1)rep(j,1,m+1)sum[i][j]+=sum[i-1][j];
}

typedef long double ld;
typedef long long ll;

inline ld qpow(ld x,int k){
	ld ans=1;
	for(;k;x=x*x,k>>=1)
		if(k&1)ans=ans*x;
	return ans;
}

ld ans;

inline void Solve(){
	ll q=1ll*sum[n][m]*sum[n][m];
	rep(i,1,n+1)rep(j,1,m+1){
		if(!a[i][j])continue;
		ll p=1ll*Sum(1,1,i,j)*Sum(i,j,n,m)+1ll*Sum(1,j,i,m)*Sum(i,1,n,j);
		p-=1ll*Sum(i,1,i,j)*Sum(i,j,i,m)+1ll*Sum(1,j,i,j)*Sum(i,j,n,j);
		p=p<<1|1;
		ld pr=(ld)p/q;
		ans+=(qpow(1.-pr*2.,k)+1.)/2.;
	}
	printf("%.20f\n",(double)ans);
}

int main(){
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
	Init(); Solve(); return 0;
}
 

题意:

给出一棵树，最开始只有1个节点。

每个时刻，这棵树会长出一个叶子。

树上每条边都有且只有1种颜色，并且同一种颜色的边都连通。

定义一个点到根的距离为该点到根的路径上的颜色种数。

求每个时刻树上最大距离的最小值。

分析:

考虑每次向上更新dp值，直到更新到根或者不能更新为止。

由树链剖分可知这样做的复杂度是O(nlogn)的。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN=1e6+5;

int n;

int dp[MAXN],p[MAXN];

int mx1[MAXN],mx2[MAXN];

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout); 
	scanf("%d",&n);
	puts("0");
	for(int i=2;i<=n;++i){
		scanf("%d",p+i);
		dp[i]=1;
		int cur=i;
		while(cur!=1){
			int par=p[cur];
			if(dp[cur]>mx1[par]){
				mx2[par]=mx1[par];
				mx1[par]=dp[cur];
			}
			else if(dp[cur]>mx2[par]){
				mx2[par]=dp[cur];
			}
			cur=par;
			int res=max(mx1[cur],mx2[cur]+1);
			if(res==dp[cur])break;
			dp[cur]=res;
		}
		printf("%d\n",mx1[1]);
	}
	return 0;
}

题意:

有n(n<=20000)个小球，最开始都未被染色。

进行m(m<=20000)次操作，操作分为2种类型。

0.回到第x次操作的状态

1.将小球x和y所在的集合合并

然后进行k(k<=20000)次染色操作。

第i次染色操作将时间ti时xi所在连通块中最多zi个小球染色。

如果一个小球被染色了，那么任意时刻它都被染色了。

求最多能将多少小球染色。

分析:

很容易想到网络流的做法，但是一般的建图方法的点数和边数都无法接受。

考虑用可持久化的思想优化网络流建图。

首先处理连通性时我们会用到用主席树实现的可持久化并查集。

注意，这时不能使用路径压缩，要按秩合并来优化。

然后可以发现可持久化并查集就可以来优化建图了。

我们只考虑叶子。

S向最初版本的每个叶子连容量1的边。

每次更新时将历史版本向当前版本连容量为+∞的边；

合并时，向集合代表元连容量为+∞的边。

每次染色时，找到ti版本xi所在集合的代表元，向T连容量为zi的边。

然后跑最大流就行了。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define S 1
#define T 2
#define inf 0x7f7f7f7f
#define gap(i) e[i].c-e[i].f
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=80005;

int Id=2;

typedef struct node*star;

struct node{
	int f,id,sz;
	star ch[2];
}pool[MAXN*20];
star tail=pool;

inline star query(star x,int l,int r,int pos){
	while(l<r){
		int mid=(l+r)>>1,d=pos>mid;
		if(d)l=mid+1; else r=mid;
		x=x->ch[d];
	}
	return x;
}

int n,m,k,Head[MAXN];

star rt[MAXN];

struct edge{
	int t,c,f,n;
	edge(int t=0,int c=0,int n=0):
		t(t),c(c),f(0),n(n){}
}e[MAXN<<2];
int head[MAXN],tot=1;
inline void AddEdge(int s,int t,int c=1){
	e[++tot]=edge(t,c,head[s]),head[s]=tot;
	e[++tot]=edge(s,0,head[t]),head[t]=tot;
}

void build(star&x,int l,int r){
	x=tail++;
	if(l==r){
		x->f=l,x->sz=1;
		AddEdge(S,x->id=++Id);
		return;
	}
	int mid=(l+r)>>1;
	build(x->ch[0],l,mid);
	build(x->ch[1],mid+1,r);
}

void update(star&y,star x,int l,int r,int t,int f,int v){
	y=++tail; *y=*x;
	if(l==r){
		y->f=f,y->sz+=v;		
		AddEdge(x->id,y->id=++Id,inf);		
		return;
	}
	int mid=(l+r)>>1,d=t>mid;
	if(d)l=mid+1; else r=mid;
	update(y->ch[d],x->ch[d],l,r,t,f,v);
}

star find(int idx,int x){
	star res=query(rt[idx],1,n,x);
	return res->f==x?res:find(idx,res->f);
}

inline void Init(){
	Scan(n),Scan(m),Scan(k);
	build(rt[0],1,n);
}

inline void Merge(int idx,int x,int y){
	star fx=find(idx,x);
	star fy=find(idx,y);
	if(fx->f==fy->f)return;
	if(fx->sz>fy->sz)swap(fx,fy);
	update(rt[idx],rt[idx],1,n,fx->f,fy->f,0);
	update(rt[idx],rt[idx],1,n,fy->f,fy->f,fx->sz);
	fx=query(rt[idx],1,n,fx->f);
	fy=query(rt[idx],1,n,fy->f);
	AddEdge(fx->id,fy->id,inf);
}

int d[MAXN],p[MAXN],q[MAXN];

int cur[MAXN],g[MAXN];

inline int isap(int s,int t,int n){
	rep(i,1,n+1)d[i]=n;
	int tail=1;
	q[1]=t; d[t]=0;
	rep(h,1,tail+1){
		int x=q[h];
		++g[d[x]],cur[x]=head[x];
		for(int i=head[x],y;i;i=e[i].n)	
			if(!e[i].c&&d[y=e[i].t]==n){
				d[y]=d[x]+1;
				q[++tail]=y;
			}
	}
	int flow=0,x=s,a,f;
	while(d[s]<n){
		if(x==t){
			a=inf;
			for(int i=t;i!=s;i=e[p[i]^1].t)
				a=min(a,gap(p[i]));
			for(int i=t;i!=s;i=e[p[i]^1].t)
				e[p[i]].f+=a,e[p[i]^1].f-=a;
			flow+=a;
			x=s;
		}
		f=1;
		for(int&i=cur[x];i;i=e[i].n)
			if(gap(i)&&d[x]==d[e[i].t]+1){
				f=0;
				p[x=e[i].t]=i;
				break;
			}
		if(f){
			if(!(--g[d[x]]))break;
			f=n-1;
			for(int i=head[x];i;i=e[i].n)
				if(gap(i))f=min(f,d[e[i].t]);
			++g[d[x]=f+1];
			cur[x]=head[x];
			if(x!=s)x=e[p[x]^1].t;
		}
	}
	return flow;
}

inline void Solve(){
	rep(i,1,m+1){
		rt[i]=rt[i-1];
		int t,x,y; 
		Scan(t),Scan(x);
		if(t)Scan(y),Merge(i,x,y);
		else rt[i]=rt[x];	
	}
	rep(i,0,k){
		int x,y,w;
		Scan(x),Scan(y),Scan(w);
		star f=find(x,y);
		AddEdge(f->id,T,w);
	}
	printf("%d\n",isap(S,T,Id));
}

int main(){
	freopen("link.in","r",stdin);
	freopen("link.out","w",stdout);
	Init(); Solve(); return 0;
} 

题意:

给出一张图(点数为n,边数为m)的一个生成树和一些非树边。

每条非树边有一个代价w，表示炸毁这条边需要付出的代价。

求炸毁一些非树边使得图中不存在偶环所付出的最小代价。

特别地，生成树上点的度数不超过10.

数据范围:n<=1000,m<=4000

分析:

首先如果一条非树边跨越了树上奇数条边，则这条边必须炸毁。

剩下的边，如果任意两条边所跨越的树上路径有公共边，则会存在偶环。

考虑到每个节点的儿子最多只有10个，我们可以考虑状压dp.

令f[x][s]表示以x为根的子树,只考虑集合s中儿子时能保留的边的最大权值。

令g[x][i]表示以x为根的子树,不考虑x的第i个儿子时能保留的边的最大权值。

每条非树边，只在它的端点的lca处考虑影响。

为了让路径不重复，则该非树边所覆盖的路径都不能被选。

暴力从一个端点到lca统计不考虑路径上的边时的最大权值。

再与该非树边没有覆盖的部分一起更新答案。

复杂度O(n*2¹⁰+n*m)

#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y 
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=1005;
const int MAXS=1<<10;

int n,m;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

int p[MAXN],dep[MAXN];

vector<int>ch[MAXN],qy[MAXN];

void dfs(int x){
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			p[y]=x;
			dep[y]=dep[x]+1;
			ch[x].pb(y);
			dfs(y);
		}
}

inline int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	while(dep[y]>dep[x])y=p[y];
	while(p[x]!=p[y])x=p[x],y=p[y];
	return x==y?x:p[x];
}

struct edge1{
	int u,v,w;
	inline void scan(){
		Scan(u),Scan(v),Scan(w);
	}
}tmp[MAXN*5];

int ans;

inline void Init(){
	Scan(n),Scan(m);
	rep(i,1,m+1){
		tmp[i].scan();
		ans+=tmp[i].w;
		if(!tmp[i].w){
			AddEdge(tmp[i].u,tmp[i].v);
		}
	}
	dfs(1);
	rep(i,1,m+1){
		if(!tmp[i].w)continue;
		int u=tmp[i].u,v=tmp[i].v;
		int Lca=lca(u,v);
		if((dep[u]+dep[v]-dep[Lca]*2)&1)continue;
		qy[Lca].pb(i);
	}
}

int dp[MAXN];

int f[MAXN][MAXS],g[MAXN][10];

inline int swim(int x,int par,int&res){
	int ban=-1;
	while(x!=par){
		if(~ban)res+=g[x][ban];
		else res+=dp[x];
		int s=ch[p[x]].size();
		rep(i,0,s)
			if(x==ch[p[x]][i]){
				ban=i; break;
			} 
		x=p[x];
	}
	return ban;
}

void tree_dp(int x){
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x])tree_dp(y);
	int s=ch[x].size();
	int maxs=1<<s;
	rep(set,0,maxs){
		int res=0;
		rep(i,0,s)
			if(set>>i&1){
				res+=dp[ch[x][i]];
			}
		Max(f[x][set],res);
	}
	int c=qy[x].size();
	rep(i,0,c){
		int u=tmp[qy[x][i]].u;
		int v=tmp[qy[x][i]].v;
		int res=tmp[qy[x][i]].w;
		int bu=max(0,1<<swim(u,x,res));
		int bv=max(0,1<<swim(v,x,res));
		rep(set,0,maxs){
			if(bu&&(set&bu)==bu||bv&&(set&bv)==bv)
				continue;
			int ns=set^bu^bv;
			Max(f[x][ns],res+f[x][set]);
		}
	}
	rep(set,0,maxs){
		rep(i,0,s)
			if(!(set>>i&1)){
				Max(g[x][i],f[x][set]);
			}
		Max(dp[x],f[x][set]);
	}
}

inline void Solve(){
	tree_dp(1);
	ans-=dp[1];
	printf("%d\n",ans);
}

int main(){
	freopen("run.in","r",stdin);
	freopen("run.out","w",stdout);
	Init(); Solve(); return 0;
}