C

核心思路

这个题目其实我们可以转换为把当前串转换为完美串有多少种方案呢，也就是我们从前往后一步一步往完美串去构造我们的方案。

这个思路非常巧妙，我刚开始的思路局限于算贡献去了。

完全就脱离了正确的思路。

集合定义

\(f[i][0/1]表示的是处理了前i个位置，并且当前位置是0的方案数\)

。

集合划分

其实就是需要保证和前面一个元素不同就好了。只要是不同的都是可以转移到的。

D

核心思路

这个题目有个非常经典的地方在于我们使用分治来模拟我们的操作，我们可以看那个图可以知道当某一个比赛更新的时候对应的之后的比赛的都会发生更新。所以我们可以稍微联想一下线段树的建树操作。其中可以把最后一个比赛看成我们的根节点，但是我们发现按照题目最后一个节点并不是根结点，所以我们需要进行一个转换。

这个转换就是把字符串逆一下，并且每次查询的节点位置也需要逆一下。

接下来考虑怎么跟新我们的答案吧。

假设\(ans[u]表示的是u场比赛的之后可能成为冠军的队伍的不同的个数\)。

很显然这个更新肯定取决于他的子节点吧：也就是\(u<<1或者u<<1|1\).然后看\(s[u]是什么呗\)。是0的话就根据他的右边的儿子跟新，这里千万要注意我们是换了编号的，所以虽然右边的编号更大，那是因为他是转换之后的。转换之后是\(n-(pos)\).转换之后的节点要更加大所以pos之前是要更加小的。

这个题目其实仔细一想有点树形dp的意思。