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

20200725比赛记录

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

20200727比赛记录

在$\text{CF}$上刷了一些网络流的题。

牛客五

牛客六

fwt刷题——有更新

牛客五

牛客六

无

做了点半平面交。

牛客五

牛客六

Codeforces Round 660 (Div. 2) Zars19

Educational Codeforces Round 92 (Rated for Div. 2) Zars19

来源：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：很精巧的最小生成树模型转化。

来源：CF 510E

tag：最大流建图

概述：

给 $n$ 个数字，两个数 $x,y$ 之间连边当且仅当 $x + y$ 是个质数。问是否能有找到几个环刚好包含了所有点，环长最少为 $3$。

$3 \le n \le 200$

$2 \le a_i \le 10^4$

答案：

数据范围这么小，以及有“每个数只能使用一次”对应容量为 $1$，“刚好包含所有点”对应满流的特点可以想到网络流。

又因为 $a_i \ge 2$，所以每个环一定是“奇偶奇偶”地相连，且长度为偶数，所以可以按数字的奇偶分成一个二分图。每个点的度都是 $2$，于是奇数部分向源点连边，偶数部分向汇点连边，看最大流是不是满的即可。

comments：二分图的建图思路比较有意思。以及会发现上周的 $\text{Topcoder SRM Div1}$ 最后一题几乎和这题一样。

来源：POJ 1066 Treasure Hunt

tag：简单计算几何

概述：

正方形区域中有一点存放宝藏，若干从正方形边界一点到另一点的线段作为屏障将局域分为很多小空间，对于每个空间可以在每面墙上的中点开门。问从外界进入宝藏区最少开多少门。

答案：

重要的一个转化是正方形边界上取各个点（墙的端点即可）与宝藏相连，相交意味着需要通过这面墙。在不在中点其实是无所谓的，总可以移到中点的位置。

comments：实现比较简单，主要是转化思想。