2020.07.25 2020牛客暑期多校训练营（第五场） prob:4:4:11 rnk:244/1116

20200725比赛记录

2020.07.27 2020牛客暑期多校训练营（第六场） prob:6:7:11 rnk:62/1019

20200727比赛记录

牛客五

牛客六

fwt刷题——有更新

牛客五

牛客六

无

牛客六

来源：luogu#P5994

tag：思路，最小生成树。

概述：

魔术师的桌子上有$n$个杯子排成一行，编号为$1,2,…,n$，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费$c_{i,j}$元，魔术师就会告诉你杯子$i,i+1,…,j$底下藏有球的总数的奇偶性。

采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

答案：

我们知道，要想确切的知道位置i的底下是否有球，就必须确切的知道$c_{i,i}$的奇偶性，换句话说，我们必须知道$sum_i$和$sum_{i-1}$的奇偶性，这样，我们只需要知道$n$个$sum$的奇偶性即可。

这样我们需要把原序列分为$n$段，每次查询一个$i，j$会把原序列分为2段，所以只需要查询$n-1$次，我们发现这其实是一个最小生成树问题，在$i-1$和$j$之间连接边权为$c_{i,j}$的边然后求最小生成树即可。

comments：很精巧的最小生成树模型转化。