cf刷题笔记: 1739赛后补题(一)

最近由于想参加icpc，于是沉迷上cf(codeforces)无法自拔。。。这个平台举行比赛还挺频繁的，里面还有icpc顶级大佬tourist, 像我这种菜鸡是不可能上分的, 只能赛后补题来维持生活这样子了。。。

A题: Immobile Knight

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

题目大概意思是找一个旗盘的孤立点, 里面的骑士(Knight)相当于象棋里面的马， 需要我们找到一个不能移动的点(孤立点), 没有则输出任意网格。

一看就是签到题了, 我们知道一共有8种走法，遍历即可

B题: Array Recovery

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

求数组的前缀和, 只是加了点绝对值的判断而已，这题也是个签到题(可惜粗心了WA了3发。。。)

C题: Card Game

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

大概意思是Alex和Boris打牌(牌的数量为偶数), 计算Alex赢的方案数, Boris赢的方案数, 平局的方案数.

这题属实有点恶心了，强度马上上来了。。。

一开始的想法是直接dfs暴力搜索所有情况，看到测试用例结果数字那么大, 绝逼会超时...

我们可以观察测试用例或用数学归纳法证明平局的方案数总为1

那么总的方案有 C(n, n / 2)种

所以 C(n, n / 2) = 1 + (Alex赢的方案数) + (Boris赢的方案数)

现在我们只需考虑Alex赢的方案数就可以得出Boris赢的方案数了

首先 Alex赢有两种情况:

Alex 获得了最大的牌n, 那么这种情况的数量有 C(n - 1, (n / 2) - 1) 种

Alex 没有获得最大的牌n, 如果要赢的话必须逼出Boris打出牌n, 所以牌n-1必须在Alex手里

定义一个数组, 我们定义f[n][0]为先手赢方案, f[n][1]为后手赢的方案

于是我们可以得到递推关系:

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 存储数据, 因为结果可能非常大):

看到讨论区还有一种动态规划的解法, 菜鸟表示没理解，就不写啦。。。