2020-2021:teams:manespace:codeforces_round_646_div2
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:codeforces_round_646_div2 [2020/06/07 17:10] iuiou |
2020-2021:teams:manespace:codeforces_round_646_div2 [2020/06/07 17:26] (当前版本) iuiou |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| ===== B ===== | ===== B ===== | ||
| - | 题意： | + | 题意：定义一个字符串合法当且仅当其中选不出一个字串(不要求连续)，其中包含$[010]$或者$[101]$,问一次翻转可以把0变成1，或者1变成0，问最少要多少次变化能把一个字符串变成合法的？ |
| + | |||
| + | 题解：不包含$[010]$或者$[101]$，就是说明该字串满足前面全为0或1，在某一个数(可能没有)后全部为1或0，这样问题就变得十分简单，计算1的前缀和然后枚举那个分界的数即可。 | ||
| + | |||
| + | ===== C ===== | ||
| + | 题意：A和B在一颗树上，有一个目标节点，A和B轮流从树上摘掉一个叶子节点（即度小于的等于1），规定谁第一个摘下目标节点算赢，双方都不会让对方赢，给定树的结构与目标节点，问最后谁会赢。 | ||
| + | |||
| + | 题解：这是一道博弈论问题，一开始我想复杂了，其实就是一个脑经急转弯，首先有个比较显然的事情，如果目标节点出现在叶节点或者只有一个节点，则先手必胜。否则无论双方怎么玩，一定会出现，将树上所有节点全部消去最后只剩下两个节点，和一条边，两个节点中一个必定为目标节点。我们反证，如果结果不是这样，则对手一定会在达成这种局面之前就阻值其发生(语言匮乏，可以想象一下)。所以最后只会剩下两个节点，这种局面后下一个玩家一定是赢的。则我们可以通过判断树的节点的奇偶性来判断最后的胜负。 | ||
2020-2021/teams/manespace/codeforces_round_646_div2.1591521020.txt.gz · 最后更改: 2020/06/07 17:10 由 iuiou
