NOI 2009 管道取珠

問題簡述

有上下兩個管道,管道內排列着兩種顏色的珠。從兩個管道中按照某種次序取出珠,可以形成一個輸出序列。顯然不同的取珠方法可以形成相同的輸出序列,設某種輸出序列的取珠方法數爲a[i],任務是求出所有輸出序列的∑a[i]2

問題建模

解法1 搜索

算法描述
最直觀的想法就是求出每種可能的取珠方案的輸出序列,並把它們的平方和加起來。由於只有兩種顏色的珠,我們可以用二進制位01表示一個取珠序列,然後搜索出每個取珠序列的方案數。

複雜度分析
搜索的時間複雜度和空間複雜度都爲O(2N+M)。在實際測試中得到30分。

參考程序

/*
* Problem: NOI2009 DAY2 ball
* Author: Guo Jiabao
* Time: 2009.7.29 10:34
* State: Done
* Memo: DFS
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

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;
}

解法2 組合計數

算法描述
我們可以把問題進行一個轉化。設X,Y分別爲一個取珠方法,某個輸出序列S的取珠方法數爲a[i],那麼a[i]2可以被認爲是輸出序列爲S的有序對(X,Y)的數量。設對於一個取珠方法狀態(i,j)表示上管道已經取出了前i個,下管道已經取出了前j個。於是狀態F[i1,j1,i2,j2]可以表示爲取珠方法X狀態爲(i1,j1),取珠方法Y狀態爲(i2,j2),X,Y的輸出序列相同的有序對(X,Y)的數量。設U[i]爲上管道第i個珠子,L[i]爲下管道第j個珠子。則狀態F[i1,j1,i2,j2]可以更新的狀態

clip_image002

由於X,Y應當同步,所以當i1,j1,i2都確定以後j2可以被表示爲i1 + j1 - i2,於是狀態表示可以減少一維。

算法證明
已知:X,Y分別爲一個取珠方法,某個輸出序列S的取珠方法數爲a[i]。求證:a[i]2是輸出序列爲S的有序對(X,Y)的數量。

證明:設Z爲輸出序列爲S的取珠方法。Z的數量|Z| = a[i]。(X,Y)是一個有序對,且X與Y相互獨立,所以X可以有|Z|種取值。對於X的某個特定取值,Y都有|Z|種取值。根據分步計數原理,有序對(X,Y)的取值有|Z|2 = a[i]2種,命題得證。

複雜度分析
狀態數是O(N2M),轉移代價是O(1),時間複雜度爲O(N2M)。在實際測試中通過了所以測試點,得到100分。

參考程序

/* 
 * 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;
}

相關日誌