Codeforces 1221E. Game With String

传送门

首先每一段连续的 $...$ 都是互不影响的,所以可以一段段考虑

考虑最简单的情况,此时每一段都大于等于 $a$ 并且小于 $2b$ ,那么每一段都只能放一次,胜负直接根据段数即可得到答案

考虑如果存在段长小于 $a$ 却大于等于 $b$ 的情况,此时后手可以随时放在那个位置,当然也可以不放,这样胜负就被掌握在后手手里(他可以随时选择交换先后手)

所以对于上面那一种情况,后手是必胜的

否则考虑如果存在两个及以上的段长度大于等于 $2b$,那么后手一定可以在其中一个长度大于等于 $2b$ 段内做做手脚,即把这个段分出一个长度大于等于 $b$ 却小于 $a$ 的段,那么此时后手也是必胜的

那么此时我们只要考虑有且只有一个段长度大于等于 $2b$ ,那么先手第一步必须放在这一段里面,并且放完以后必须保证分出的两段长度都小于等于 $2b$ 且大于等于 $a$,这样第一步完剩下的段都是只能放一步的,再跟据段数判断胜负即可

所以我们只要枚举先手第一步放的位置看看是否存在可以胜利的情况即可

代码?参考别人的吧,我懒得写了

原文地址:https://www.cnblogs.com/LLTYYC/p/11556660.html