CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== codeforces round 646(div2) ======
===== A =====
<del>谁说签到都是水题的？</del>

题意：从$n$个数中选择$x$个数，要求选出来的数满足，这$x$个数的和为奇数，问给的这一系列数能不能满足这个条件。

题解：首先有一个比较基本的结论，只有奇数个奇数相加才会出现奇数，否则出现的一定是偶数。所以先统计这个$n$个数中有多少奇数，比较奇数的数量与$x$的大小，如果$x$的值小，则判断$x$是否为偶数，若是偶数，判断原序列是否有偶数存在，若无则一定不成立。如果$x$的值大，则判断奇数个数的奇偶性，若为奇数，一定成立，若为偶数，则判断是否存在偶数，不存在一定不存在。<del>这坑太多了</del>

===== B =====
题意：定义一个字符串合法当且仅当其中选不出一个字串(不要求连续)，其中包含$[010]$或者$[101]$,问一次翻转可以把0变成1，或者1变成0，问最少要多少次变化能把一个字符串变成合法的？

题解：不包含$[010]$或者$[101]$，就是说明该字串满足前面全为0或1，在某一个数(可能没有)后全部为1或0，这样问题就变得十分简单，计算1的前缀和然后枚举那个分界的数即可。

===== C =====
题意：A和B在一颗树上，有一个目标节点，A和B轮流从树上摘掉一个叶子节点（即度小于的等于1），规定谁第一个摘下目标节点算赢，双方都不会让对方赢，给定树的结构与目标节点，问最后谁会赢。

题解：这是一道博弈论问题，一开始我想复杂了，其实就是一个脑经急转弯，首先有个比较显然的事情，如果目标节点出现在叶节点或者只有一个节点，则先手必胜。否则无论双方怎么玩，一定会出现，将树上所有节点全部消去最后只剩下两个节点，和一条边，两个节点中一个必定为目标节点。我们反证，如果结果不是这样，则对手一定会在达成这种局面之前就阻值其发生(语言匮乏，可以想象一下)。所以最后只会剩下两个节点，这种局面后下一个玩家一定是赢的。则我们可以通过判断树的节点的奇偶性来判断最后的胜负。
CVBB ACM Team

用户工具

站点工具

页面工具
