=====A===== 过水已隐藏 =====B===== 影逝二度 =====C===== * 题意:每次去掉一个叶子节点,询问最后谁能够去掉选定的目标节点 * 题解:如果目标节点不是叶子节点,显然必输的情况是目标节点两侧各连一个,那么就需要去掉$n-3$个,看奇偶性即可。 =====D===== * 是好VAN的交互题 * 题意:给定$k$个不相交的集合,密码第$i$位为数列中除第$i$个集合所含下标以外的元素中的最大值,尝试问出密码。 * 题解:显然密码至少有$n-1$位是所有数中的最大值,然后二分询问找到含有最大值的集合,然后再问一下除它之外的最大值即可 =====E===== * 题意:一棵树,每个节点有当前值0/1和目标值0/1,对于每个节点的子树,可以选择$k$个将其当前值任意互换,求所有节点都变成目标值的最小代价。 * 题解:常规思路,对于一个节点,如果其父亲需要的费用比它少,那么肯定不会从当前节点shuffle,那么$dfs$令每个节点的代价等于其到根节点的链中节点代价的最小值,然后根据每个节点和父亲结点费用的大小关系判断即可。