最近由于想?yún)⒓觟cpc，于是沉迷上cf(codeforces)無(wú)法自拔。。。這個(gè)平臺(tái)舉行比賽還挺頻繁的，里面還有icpc頂級(jí)大佬tourist, 像我這種菜雞是不可能上分的, 只能賽后補(bǔ)題來(lái)維持生活這樣子了。。。

A題: Immobile Knight

https://codeforces.com/problemset/problem/1739/A

題目大概意思是找一個(gè)旗盤的孤立點(diǎn), 里面的騎士(Knight)相當(dāng)于象棋里面的馬， 需要我們找到一個(gè)不能移動(dòng)的點(diǎn)(孤立點(diǎn)), 沒(méi)有則輸出任意網(wǎng)格。

一看就是簽到題了, 我們知道一共有8種走法，遍歷即可

B題: Array Recovery

https://codeforces.com/problemset/problem/1739/B

求數(shù)組的前綴和, 只是加了點(diǎn)絕對(duì)值的判斷而已，這題也是個(gè)簽到題(可惜粗心了WA了3發(fā)。。。)

C題: Card Game

https://codeforces.com/problemset/problem/1739/C

大概意思是Alex和Boris打牌(牌的數(shù)量為偶數(shù)), 計(jì)算Alex贏的方案數(shù), Boris贏的方案數(shù), 平局的方案數(shù).

這題屬實(shí)有點(diǎn)惡心了，強(qiáng)度馬上上來(lái)了。。。

一開始的想法是直接dfs暴力搜索所有情況，看到測(cè)試用例結(jié)果數(shù)字那么大, 絕逼會(huì)超時(shí)...

我們可以觀察測(cè)試用例或用數(shù)學(xué)歸納法證明平局的方案數(shù)總為1

那么總的方案有 C(n, n / 2)種

所以 C(n, n / 2) = 1 + (Alex贏的方案數(shù)) + (Boris贏的方案數(shù))

現(xiàn)在我們只需考慮Alex贏的方案數(shù)就可以得出Boris贏的方案數(shù)了

首先 Alex贏有兩種情況:

Alex 獲得了最大的牌n, 那么這種情況的數(shù)量有 C(n - 1, (n / 2)?- 1) 種

Alex 沒(méi)有獲得最大的牌n, 如果要贏的話必須逼出Boris打出牌n, 所以牌n-1必須在Alex手里

定義一個(gè)數(shù)組,?我們定義f[n][0]為先手贏方案, f[n][1]為后手贏的方案

于是我們可以得到遞推關(guān)系:

f[n][0] =?C(n - 1, (n?/ 2)?-?1) + f[n - 2][1]

f[n][1] = C(n, n / 2) - f[n][0] - 1

最后寫出代碼(用到long long 存儲(chǔ)數(shù)據(jù), 因?yàn)榻Y(jié)果可能非常大):

看到討論區(qū)還有一種動(dòng)態(tài)規(guī)劃的解法, 菜鳥表示沒(méi)理解，就不寫啦。。。?