Beyond the Void
BYVoid
NOI 2009 管道取珠

问题简述

有上下两个管道,管道内排列着两种颜色的珠。从两个管道中按照某种次序取出珠,可以形成一个输出序列。显然不同的取珠方法可以形成相同的输出序列,设某种输出序列的取珠方法数为a[i],任务是求出所有输出序列的∑a[i]2

问题建模

解法1 搜索

算法描述
最直观的想法就是求出每种可能的取珠方案的输出序列,并把它们的平方和加起来。由于只有两种颜色的珠,我们可以用二进制位01表示一个取珠序列,然后搜索出每个取珠序列的方案数。
复杂度分析
搜索的时间复杂度和空间复杂度都为O(2N+M)。在实际测试中得到30分。
参考程序
```cpp /* * Problem: NOI2009 DAY2 ball * Author: Guo Jiabao * Time: 2009.7.29 10:34 * State: Done * Memo: DFS */ #include #include #include #include #include

using namespace std;

const int MAXN=501,MAXS=1«24,MOD=1024523;

FILE *fi,*fo;

int P[2][MAXN],C[2]; int Cnt[MAXS],Ans;

void dfs(int i,int c0,int c1,int s) { if (c0 == 0 && c1 == 0) { Cnt[s] ++; return; } if (c0 >= 1) { dfs(i+1,c0-1,c1,s + (P[0][c0] « (i-1)) ); } if (c1 >= 1) { dfs(i+1,c0,c1-1,s + (P[1][c1] « (i-1)) ); } }

void solve() { int i; long long t; dfs(1,C[0],C[1],0); for (i=0;i<MAXS;i++) { if (Cnt[i]) { t = Cnt[i]; t *= t; t %= MOD; Ans += t; if (Ans >= MOD) Ans -= MOD; } } fprintf(fo,"%d\n",Ans); }

int main() { int k,i,c; fi = fopen(“ball.in”,“r”); fo = fopen(“ball.out”,“w”); fscanf(fi,"%d%d",&C[0],&C[1]); for (k=0;k<=1;k++) { for (i=1;i<=C[k];i++) { do c=fgetc(fi); while (c==10 || c==13); P[k][i] = c-‘A’; } } solve(); fclose(fi); fclose(fo); return 0; }


<h4><a name="_Toc241907157">解法</a>2 组合计数</h4>

<h5><a name="_Toc241907158">算法描述</a></h5>
我们可以把问题进行一个转化。设X,Y分别为一个取珠方法,某个输出序列S的取珠方法数为a[i],那么a[i]<sup>2</sup>可以被认为是输出序列为S的有序对(X,Y)的数量。设对于一个取珠方法状态(i,j)表示上管道已经取出了前i个,下管道已经取出了前j个。于是状态F[i<sub>1</sub>,j<sub>1</sub>,i<sub>2</sub>,j<sub>2</sub>]可以表示为取珠方法X状态为(i<sub>1</sub>,j<sub>1</sub>),取珠方法Y状态为(i<sub>2</sub>,j<sub>2</sub>),X,Y的输出序列相同的有序对(X,Y)的数量。设U[i]为上管道第i个珠子,L[i]为下管道第j个珠子。则状态F[i<sub>1</sub>,j<sub>1</sub>,i<sub>2</sub>,j<sub>2</sub>]可以更新的状态

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0021.gif"><img title="clip_image002" src="https://byvoid.com/attachments/wp/2010/01/clip_image0021.gif" alt="clip_image002" width="360" height="85" /></a>

由于X,Y应当同步,所以当i<sub>1</sub>,j<sub>1</sub>,i<sub>2</sub>都确定以后j<sub>2</sub>可以被表示为i<sub>1 </sub>+ j<sub>1</sub> - i<sub>2</sub>,于是状态表示可以减少一维。
<h5><a name="_Toc241907159">算法证明</a></h5>
已知:X,Y分别为一个取珠方法,某个输出序列S的取珠方法数为a[i]。求证:a[i]<sup>2</sup>是输出序列为S的有序对(X,Y)的数量。

证明:设Z为输出序列为S的取珠方法。Z的数量|Z| = a[i]。(X,Y)是一个有序对,且X与Y相互独立,所以X可以有|Z|种取值。对于X的某个特定取值,Y都有|Z|种取值。根据分步计数原理,有序对(X,Y)的取值有|Z|<sup>2</sup> = a[i]<sup>2</sup>种,命题得证。
<h5><a name="_Toc241907160">复杂度分析</a></h5>
状态数是O(N<sup>2</sup>M),转移代价是O(1),时间复杂度为O(N<sup>2</sup>M)。在实际测试中通过了所以测试点,得到100分。
<h5><a name="_Toc241907161">参考程序</a></h5>
```cpp
/* 
 * Problem: NOI2009 ball
 * Author: Guo Jiabao
 * Time: 2009.9.28 12:39
 * State: Solved
 * Memo: 组合计数 递推
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN = 502,MOD=1024523;

int N,M,Ans;
char U[MAXN],L[MAXN];
int F[MAXN][MAXN][MAXN];

void init()
{
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	scanf("%d%d",&N,&M);
	scanf("%s",U+1);
	scanf("%s",L+1);
	F[0][0][0] = 1;
}

inline void update(int &F,int &c)
{
	F += c;
	if (F >= MOD)
		F -= MOD;
}

void solve()
{
	int i,j,k,l;
	for (i=0;i<=N;i++)
	{
		for (j=0;j<=M;j++)
		{
			for (k=0;k<=N;k++)
			{
				int &t = F[i][j][k];
				if (!t) continue;
				l = i+j-k;
				if (U[i+1] == U[k+1])
					update(F[i+1][j][k+1],t);
				if (U[i+1] == L[l+1])
					update(F[i+1][j][k],t);
				if (L[j+1] == U[k+1])
					update(F[i][j+1][k+1],t);
				if (L[j+1] == L[l+1])
					update(F[i][j+1][k],t);
			}
		}
	}
	Ans = F[N][M][N];
}

int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}

上次修改时间 2017-05-26

相关日志