CF1527B1 Palindrome Game (easy version)
知识点:博弈
题意
给定01串和两个操作:
- 如果当前不是回文串,翻转串,花费0
- 把0变成1,花费1
一方最多且必须执行1个操作,且如果对方上一步是1操作,当前必须执行2操作(记为限制1)。
花费少的胜。
思路
题意可归纳出:
- 对应回文位置的两个数字可组成独立的一组,互相交换或交换其他组在串中的位置无影响。
- 可组成 0,00,01,11四种类型,11可忽略。
- 0只能转化为1,00只能转化为01,01只能转化为11。
显然只有1个0或只有1个00后手胜,状态转移关键在于限制1。
不考虑0类型:
后手只有00的串上一步先手一定含01,如果后手在上上步没有给上步限制1,先手在上一步一定可以反转操作转化为后手在01状态,无法转移为后手只有00的串。
后手在上上步给上步限制1一定是上上步为反转操作,一定含01。递推可知后手含01先手一定只有00,即给定串有偶数个0。
考虑0类型:
先手先选0,后手只能选00,此时为上面一种情况交换先后手,答案相反。
总结:
只有一个0,后手胜。
否则偶数个0,后手胜。
否则先手胜。
代码根据总结实现即可。