[ZJ][數學解] a534. IOI2008 Day2.1.花園問題＠Morris' Blog

2012-09-23 20:59:00| 人氣1,063| 回應0 | 上一篇 | 下一篇

[ZJ][數學解] a534. IOI2008 Day2.1.花園問題

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

拉姆西斯(Ramesses)二世剛打勝戰回來，為了慶祝戰爭勝利，他決定建一座皇家花園。花園將由一長排的植物所組成，從他在路克索(Luxor)的皇宮一直延伸到卡納克神殿(Temple of Karnak)。而所種的植物僅由連花(lotus)及紙莎草(papyrus)二種組成，它們分別是上埃及與下埃及的象徵。

此花園必須種植N顆植物：而且植物數必須平衡，也就是在花園的任何連續區段中蓮花與紙莎草的數量差異不能大於2。

一個花園可以用字母L(lotus)與P(papyrus)所組成的字串表示。例如，當N=5時，有14種可能的平衡花園，依英文字母次序排序如下：

LLPLP, LLPPL, LPLLP,LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP,及 PPLPL。

某一長度的所有可能平衡花園，可依英文字母次序排序，並從1開始編號。例如，當N=5時，編號12的花園是平衡花園PLPPL。

給定N棵植物及一表示平衡花園的字串，請寫一個程式計算出該平衡花園的編號，並取其除以一給定整數M的餘數。

注意，M在本題中與解題無關，它只是用來簡化計算。

輸入說明：

程式需從標準輸入讀入下列資料：

· 第一行有一整數N，指花園中的植物的總數。

· 第二行有一整數M。

· 第三行有一N個字元的字串，由字母L(lotus)與P(papyrus)組成，代表某一個平衡花園。

輸出說明：

程式輸出一個介於0到M-1的整數至標準輸出。輸出的整數是輸入的平衡花園的編號，除以M所得到的餘數。

範例輸入： help

範例輸入157PLPPL範例輸入2	1210000LPLLPLPPLPLL

範例輸出：

範例輸出15範例輸出239

提示：

100%的數據滿足

1 <= N <= 1,000,000

7 <= M <= 10,000,000

出處：

IOI2008 Day2 第一題 (管理：david942j)

網路上有這麼一篇解答, 雖然我看不是很懂英文, 但是他給了我上面這張圖, 再加上文中零零碎碎關鍵字
我明瞭了一切, 只考慮 L 開始的話, 而且我們關注於值域 [0, 2] 的走法, 從 0 出發,
我們可以很明顯的觀察到程式碼中的遞迴公式

dp[i][j] : i 長度, j 最後停流位置

那還有一種是上下上下的情況 (ababbaabba ...), 我們可以用 2^(剩餘長度) 去表示

然後要寄算第幾個的時候, 遇到 P 的時候, 試圖將 P 換成 L 去計算 rank,
當遇到目前最低的值域等於目前所在的位置時, 則可以看做 dp[i][0,1,2] + 上下上下的可能,
但是這兩個會有一種交集 (ababababab ...), 必須扣掉這一種,

另外一種是差 1 的情況, 將 P 換成 L 相當於在上升一個, 就可以直接當作 dp[i][0,1,2]

相差 2 的情況就可以不理會了, 因為沒辦法替換

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char s[1000005];
int dp[1000005][3] = {};
long long Mpow(long long x, long long y, long long mod) {
    if(!y) return 1;
    if(y&1)
        return (x*Mpow((x*x)%mod, y/2, mod))%mod;
    return Mpow((x*x)%mod, y/2, mod);
}
int main() {
    int n, m;
    int i, j;
    scanf("%d %d", &n, &m);
    scanf("%s", s);
    dp[0][0] = 1;
    for(i = 0; i <= n; i++) {
        dp[i+1][0] = dp[i][1]%m;
        dp[i+1][1] = (dp[i][0]+dp[i][2])%m;
        dp[i+1][2] = (dp[i][1])%m;
    }
    int line = 0, rk = 0, mn = 0;
    for(i = 0; i < n; i++) {
        if(s[i] == 'P') {
            if(mn == line) {
                rk += dp[n-i][0]+dp[n-i][1]+dp[n-i][2]-1;
                int tmp = (n-i)/2;
                if((n-i)%2 == 0)    tmp--;
                rk += Mpow(2, tmp, m);
            } else if(abs(mn - line) == 1) {
                rk += dp[n-i-1][0]+dp[n-i-1][1]+dp[n-i-1][2];
                rk %= m;
            }
        }
        if(s[i] == 'L') line++;
        else line--;
        if(line < mn)   mn = line;
    }
    rk++;
    printf("%d\n", rk%m);
    return 0;
}

我要檢舉

#a534#IOI2008#Day2#1.花園問題

台長： Morris

您可能對以下文章有興趣

[ZJ][DP] a365. 3. 新井字遊戲

a081. NOI2000 Day2.2.青蛙过河

d915. 3. 洗街車路線問題

[ZJ][二分+凸包計算面積] b221. 6. 耕者有其田

人氣(1,063) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[CSAPC][dp解] b178. 遊輪 Boat
此分類上一篇:[ZJ][N*NlogN][BIT] a533. IOI2004 Day1.1.阿特米斯

回應(0)