【GDOI2015】Good Luck 2 U.
【JUNE】

【May】

Enzo2 posted @ 2015年5月19日 16:51 in 未分类 , 478 阅读

【Codeforces 438E】The Child and Binary Tree

递推式的优化处理(FFT,按照时间分治)

2013集训队互测的城市规划

优化递推式的计算(F已经计算):\( G_{n} = \sum_{i=1}^{n-1} G_{i} * F_{n-i} \)

直接计算G的值的时间复杂度是平方级别的。但经过观察,整个式子是卷积形式的,使用FFT(快速傅里叶变换)可以优化计算时间复杂度。

但瓶颈是:G的计算依赖于G。如果式子是\( G_{n} = \sum_{i=1}^{n-1} F_{i} * F_{n-i} \),则是一个很基础的问题了。在G里的元素尚未确定的情况下,是不能够直接套用FFT的。

解决问题的方式是按照时间分治。类似于CDQ分治,计算前一段(已经计算的)对后一段(正在计算的)的贡献。

实现的方法如下:

  1. 定义SOLVE(l,r)为计算 \( G_{l} \cdots G_{r} \)的值。
  2. 定义mid = (l+r)/2。递归处理SOLVE(l, mid), 处理完成后,这是l到mid的G值都计算完毕了。
  3. 下面计算(l,mid)对(mid+1,r)的贡献。即,计算\( T_{n} = \sum_{i=l}^{mid} G_{i} * F_{n-i} \),T为(l,mid)的每一项对(mid+1,r)的每一项的贡献,这一部分可以使用FFT进行优化(卷积形式)。
  4. 处理SOLVE(mid+1, r)。

每两个位置i,j(i<j),他们之间的影响被分到了每一层计算,累加则能得到结果,总时间复杂度为\( O(NLog^{2}N)\)。

Codeforces 438E : The Child and Binary Tree

优化递推式的计算(C已经计算):\( G_{n} = \sum_{i=0}^{n-1} \sum_{j=0}^{n-i} C_{i} * G_{j} * G_{n-i-j} \)

这道题的瓶颈是G的计算需要更加细节的处理。在一些时候需要两倍计算:因为(i,j)与(j,i)都会对n产生影响,而只会在i<j的时候计算,所以在区间不相交的时候需要计算两次。

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

typedef long long LL;

const int N = 6e5 + 5;
int Mod = 998244353;

int n, m, l, lm, x[N];

int tr[20][N], wi[20][N];
int a[N], ci;
int b[N], c[N], d[N], tp[N];

int pow(int a, int b)
{
	LL r(1), s(a);
	for(; b; b>>=1, s=s*s%Mod) if(b&1) r=r*s%Mod;
	return r;
}

void maketh(int L, int lm, int *tr, int *wi)
{
	for(int i=0, p, j, k; i<l; tr[i++] = p)
	for(p=0, j=i, k=0; k<lm; k++, j>>=1) p = (p<<1) + (j&1);
	wi[0] = 1, wi[1] = pow(3, (Mod-1) / l);
	for(int i=2; i<=l; i++) wi[i] = LL(wi[i-1]) * wi[1] % Mod;
}

void makett(int L)
{
	l=L, ci = pow(l, Mod-2);
}

void dft(int *a, int sig, int *tr, int *wi)
{
	for(int i=0; i<l; i++) tp[tr[i]] = a[i];
	int bei = l, hal, lei;
	for(int i=2; i<=l; i+=i)
	{
		hal = i>>1, lei = sig>0?0:l, bei>>=1;
		for(int j=0; j<hal; j++, lei+=bei*sig)
		for(int k=j, w=wi[lei]; k<l; k+=i)
		{
			int u=tp[k], v=LL(tp[k+hal])*w%Mod;
			tp[k] = (u+v) % Mod;
			tp[k+hal] = (u-v+Mod) % Mod;
		}
	}
	for(int i=0; i<l; i++) a[i]=tp[i];
}

void solve(int l, int r)
{
	if(l==r) return;
	
	int m = (l+r)>>1, lg = r-l, L;
	
	solve(l, m);
	for(L = 1, lm = 0; L <= lg * 2; L += L, ++lm);
	makett(L);
	
	for(int i=0; i<L; i++) b[i] = c[i] = d[i] = 0;
	for(int i=l; i<=m; i++) b[i-l] = a[i];
	for(int i=0; i<=lg; i++) c[i] = x[i];
	
	// DETAIL
	if(lg<=l) for(int i=0; i<=lg; i++) d[i] = (a[i] + a[i]) % Mod;
	else for(int i=l; i<=m; i++) d[i-l] = a[i];
	
	dft(b, 1, tr[lm], wi[lm]), dft(c, 1, tr[lm], wi[lm]), dft(d, 1, tr[lm], wi[lm]);
	for(int i=0; i<L; i++) b[i] = LL(b[i]) * c[i] % Mod * d[i] % Mod;
	dft(b, -1, tr[lm], wi[lm]);
	for(int i=0; i<L; i++) b[i] = LL(b[i]) * ci % Mod;
	
	for(int i=m+1; i<=r; i++) (a[i] += b[i-l]) %= Mod;
	
	solve(m+1, r);
}

int main()
{
	scanf("%d%d", &n, &m), a[0] = 1;
	for(int i=1, p; i<=n; i++) scanf("%d", &p), x[p] = 1;
	
	for(l=1, lm=0; l <= m*3; l+=l, ++lm) maketh(l, lm, tr[lm], wi[lm]);
	maketh(l, lm, tr[lm], wi[lm]);
	
	solve(0, m);
	for(int i=1; i<=m; i++) printf("%d\n", int(a[i]));
	
	return 0;
}

【Codeforces 343E】Pumping Stations(Gomory-Hu Tree的定义与构建)

定义

WIKI:一个带权无向图G(V,E)的Gomory-Hu树,代表了图中所有s-t最小割。使用V-1次最小割可以构建出Gomory-Hu树。

简单的来说,树上的两点之间的路径最小值,就是在原图中两点的最小割。

构建

  1. 我们一开始将所有点的父亲指向1。
  2. 枚举每一个点i,计算它和父亲fi的最小割,并连边。
  3. 再枚举对于点j,若满足fj=fi并且j与i在最小割的一边,那么把fj=i

实现

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

const int N = 205;
const int M = 1005;

int n, m, v[N], fa[N], f[N];

namespace netw
{
	const int P = N;
	const int E = M + M;
	const int inf = 1e9;
	
	int to[E], next[E], end[P], f[E], tms;
	
	void link(int x, int y, int z)
	{
		to[++tms]=y, next[tms]=end[x], end[x]=tms, f[tms]=z;
		to[++tms]=x, next[tms]=end[y], end[y]=tms, f[tms]=z;
	}
	
	int dat[P], pred[P], cur[P], cnt[P], dist[P];
	
	int sap(int S, int T)
	{
		for(int i=1; i<=n; i++) dist[i]=1, cnt[i]=0, cur[i]=end[i];
		dat[S]=inf, dist[T]=0, cnt[1]=n-1, cnt[0]=1;
	
		int x(S), p, q, ret(0);
		for(;;)
		{
			for(p=cur[x]; p; p=next[p]) if(f[p]>0 && dist[to[p]]+1==dist[x]) break;
			if(p)
			{
				dat[to[p]]=min(dat[x],f[p]), pred[to[p]]=p, cur[x]=p, x=to[p];
				if(x==T) for(ret+=dat[T]; x!=S; x=to[pred[x]^1]) f[pred[x]]-=dat[T], f[pred[x]^1]+=dat[T];
			}
			else
			{
				if(--cnt[dist[x]]==0) return ret;
				for(dist[x]=n+1, q=end[x]; q; q=next[q]) if(f[q]>0 && dist[to[q]]+1<dist[x])
				dist[x]=dist[to[q]]+1, cur[x]=q;
				++cnt[dist[x]];
				if(dist[S]>n) return ret;
				if(x^S) x=to[pred[x]^1];
			}
		}
	}
	
	void paint(int x, int *v)
	{
		if(v[x]) return; v[x]=1;
		for(int p=end[x]; p; p=next[p]) if(f[p]) paint(to[p], v);
	}
	
	void bfs(int x, int *v)
	{
		for(int i=1; i<=n; i++) v[i] = 0;
		paint(x, v);
		for(int i=2, j; i<=tms; i+=2) j = f[i] + f[i+1], f[i] = f[i+1] = j / 2;
	}
}

int to[N+N], next[N+N], end[N], d[N+N], fv[N+N], tms;
int per[N], cp;

void cgg(int x, int fa)
{
	for(int p=end[x]; p; p=next[p]) if(!fv[p] && to[p]!=fa)
	{
		if(!cp || d[p]<d[cp]) cp=p;
		cgg(to[p], x);
	}
}

void sp(int x)
{
	int u(1), tp;
	for(int p=end[x]; p && u; p=next[p]) if(!fv[p]) u=0;
	if(u) {per[++per[0]] = x; return;}
	
	cp=0, cgg(x, 0), fv[cp] = fv[cp^1] = 1;
	tp=cp, sp(to[tp]), sp(to[tp^1]);
}

int main()
{
	scanf("%d%d", &n, &m), netw :: tms = 1;
	for(int i=1, x, y, z; i<=m; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		netw :: link(x, y, z);
	}
	
	for(int i=1; i<=n; i++) fa[i] = 1;
	for(int i=2; i<=n; i++)
	{
		f[i] = netw :: sap(i, fa[i]), netw :: bfs(i, v), f[0] += f[i];
		for(int j=i+1; j<=n; j++) if(v[j] && fa[j] == fa[i]) fa[j] = i;
	}
	// Gomory-Hu Tree 的 中心构造过程
	tms = 1;
	for(int i=2; i<=n; i++)
	{
		to[++tms]=i, next[tms]=end[fa[i]], end[fa[i]]=tms, d[tms]=f[i];
		to[++tms]=fa[i], next[tms]=end[i], end[i]=tms, d[tms]=f[i];
	}

	sp(1);
	
	printf("%d\n", f[0]);
	for(int i=1; i<n; i++) printf("%d ", per[i]);
	printf("%d\n", per[n]);
	
	return 0;
}

应用

Codeforces 343E:找出一个排列,使得相邻两项的最小割之和最大

最小割之和就是树上的边权总和:找出在Gomory-Hu树上的最大边权的一条边,假如它连接的是u与v,那么排列中u与v必定是相邻的,不然就会浪费这条边权了。这样分析下来,每一条边权都会取到,而这是能够达到的上界。

下面分析如何得到一组合法的解。找出树上一条边权最小的边,把树分为两半,递归处理,把两边的答案合并就可以了。这样做是可以达到上界的,因为最大的边必定会留到最后,而最小的边权由于约束最松,可以最先处理。

UVA 11594 : All Pairs Maximum Flow

直接套用构建的模板就可以。

UVA 11603 : Its all about the Bandwidth /HDU 4700 : FLOW

给出N点之间的最小割,构建出图G满足其约束。

一个合法的G必能转化成一个合法的Gomory-Hu树,所以直接构建一棵树就好了。找出其中一条最短的边L,将树分成两半A与B:A与B之间最小割均为边权L则合法,递归处理。(如何分割A与B?固定其中一个点X在A,与X的最小割值大于L则只能在A,否则放置于B)为什么这个算法一定能得到正确解呢?

【POJ 3986】Math Teacher's Homework

一道比较有趣的数位DP

【POJ 1777】Vivian's Problem

梅森素数的应用


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter