2020-2021:teams:wangzai_milk:weekly12
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly12 [2020/07/23 21:06] wzx27 |
2020-2021:teams:wangzai_milk:weekly12 [2020/07/24 22:22] (当前版本) zars19 |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| [[20200720比赛记录]] | [[20200720比赛记录]] | ||
| + | 2020.07.23 [[https://codeforces.com/group/azDPdoF24f/contest/288496|2020.07.23codeforces加训]] ''prob:6:6:11'' ''rnk:7/17'' | ||
| + | |||
| + | [[20200723比赛记录]] | ||
| ===== _wzx27 ===== | ===== _wzx27 ===== | ||
| 行 51: | 行 54: | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | 牛客3 | ||
| + | |||
| + | | [[20200718比赛记录#C - Operation Love]] | [[20200718比赛记录#G - Operating on a Graph]] | [[20200718比赛记录#L - Problem L is the Only Lovely Problem]] | | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| 行 172: | 行 179: | ||
| 做矩阵快速幂的题只在刷专题的时候做过，然而比赛的时候容易想不到，可以用来提示一下^。以及这个按位拆分也挺有意思的（吧）。 | 做矩阵快速幂的题只在刷专题的时候做过，然而比赛的时候容易想不到，可以用来提示一下^。以及这个按位拆分也挺有意思的（吧）。 | ||
| + | |||
| + | ==== Zars19 ==== | ||
| + | |||
| + | **来源**：在做[[20200719 - 一些非常简单的计算几何扫描线题#POJ 3004 Subway Planning]]的时候看到了这个——[[https://www.cnblogs.com/I-Love-You-520/p/11147003.html|三类贪心区间覆盖问题 BY Ra煞]] | ||
| + | |||
| + | **tag**：贪心。 | ||
| + | |||
| + | **概述**： | ||
| + | |||
| + | 1. 给出 $n$ 个区间，问最少使用多少个可以实现某个大区间的完全覆盖？ | ||
| + | |||
| + | 2. 给出 $n$ 个区间，问最多选择多少个可以使得两两不重叠？ | ||
| + | |||
| + | 3. 给出 $n$ 个区间，问最少选择多少点可以使得每个区间中都有至少一个点（点可被共用）？ | ||
| + | |||
| + | **答案**： | ||
| + | |||
| + | 1. 排序，枚举起始区间，之后选择左端点在当前覆盖范围内且右端点最大的一个，重复直至目标达成。 | ||
| + | |||
| + | 2. 排序（第一关键字左端点从大到小，第二关键字右端点从小到大），按顺序尝试加入每一个区间（这个顺序可以维持留给左边的空白区域达到极大），如果重叠则丢掉。 | ||
| + | |||
| + | 3. 排序（第一关键字左端点从小到大，第二关键字右端点从小到大），按顺序加入，维护当前重叠区域的右端点，如果新区间左端点大于当前右端点，则丢掉之前维护的区域''答案++''增加一个点，否则如果新区间右端点小于当前右端点，更新右端点。 | ||
| + | |||
| + | **comments**：虽然很简单但可能会在出现在奇怪的辅助位？可以撕烤一下。 | ||
| + | |||
| + | ==== Infinity37 ==== | ||
| + | |||
| + | **来源**：uoj#171 | ||
| + | |||
| + | **tag**：带花树，一般图匹配。 | ||
| + | |||
| + | **概述**： | ||
| + | |||
| + | 给定$n$个球和$m$个篮子，每个篮子最多放3个球，给定$e$个关系，关系$(x,y)$代表编号为$x$的球可以放在编号为$y$的篮子里，我们定义一个半满的篮子为篮子中有不超过1个球。 | ||
| + | |||
| + | 问最多有多少半满的篮子，并给出其中一种方案。 | ||
| + | |||
| + | **答案**： | ||
| + | |||
| + | 可以先设想，每个篮子都是一个有三个凹槽，所以我们把一个篮子拆成3个点，如果一个球和这个篮子有关系，那就把这个球和三个凹槽都连上边。同时我们把这三个凹槽之间也相互连边，这样我们得到的这个图的最大匹配数其实就相当于半满的篮子数+n。 | ||
| + | |||
| + | 因为题目中保证有一种方案能放下所有的球，而如果某个篮子是半满的篮子，那么一定有两个凹槽形成了一个匹配。所以我们把匹配好的球从答案中减去，就是半满的篮子数。 | ||
| + | |||
| + | **comments**：因为上周出现了带花树所以做一点带花树的题，这是一个比较妙的建图。 | ||
| + | |||
2020-2021/teams/wangzai_milk/weekly12.1595509594.txt.gz · 最后更改: 2020/07/23 21:06 由 wzx27
