2020-2021:teams:wangzai_milk:weekly13

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:weekly13 [2020/07/31 15:15]
wzx27
+++ 2020-2021:teams:wangzai_milk:weekly13 [2020/07/31 20:58] (当前版本)
zars19 [题目]
@@ 行 47: / 行 47: @@
 ==== 专题 ====
+做了点半平面交。
 ==== 题目 ====
+牛客五
+|  [[20200725比赛记录#B - Graph]]  |  [[20200725比赛记录#I - Hard Math Problem]]  |
 牛客六
@@ 行 77: / 行 82: @@
 **comments**：很精巧的最小生成树模型转化。
+==== _wzx27 ====
+**来源**：[[https://codeforces.com/problemset/problem/510/E|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}$ 最后一题几乎和这题一样。
+==== Zars19 ====
+**来源**：POJ 1066 Treasure Hunt
+**tag**：简单计算几何
+**概述**：
+正方形区域中有一点存放宝藏，若干从正方形边界一点到另一点的线段作为屏障将局域分为很多小空间，对于每个空间可以在每面墙上的中点开门。问从外界进入宝藏区最少开多少门。
+**答案**：
+重要的一个转化是正方形边界上取各个点（墙的端点即可）与宝藏相连，相交意味着需要通过这面墙。在不在中点其实是无所谓的，总可以移到中点的位置。
+**comments**：实现比较简单，主要是转化思想。

2020-2021/teams/wangzai_milk/weekly13.1596179747.txt.gz · 最后更改: 2020/07/31 15:15 由 wzx27