本文正體字版由OpenCC轉換
問題簡述
有上下兩個管道，管道內排列着兩種顏色的珠。從兩個管道中按照某種次序取出珠，可以形成一個輸出序列。顯然不同的取珠方法可以形成相同的輸出序列，設某種輸出序列的取珠方法數爲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 */ #includeusing 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