Warning: session_start(): open(/tmp/sess_f418fbe0e538e22209fc961bb744bc21, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/6/6a0f3843c5ea426c08feea4e44f84973.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2020 Summer Week 4 Report ======
====== 团队训练 ======
[[2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_7|2020牛客暑期多校训练营（第七场）]] ''%%task:4/6/10%%'', ''%%rank:56/1140%%''
[[2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_8|2020牛客暑期多校训练营（第八场）]] ''%%task:3/4/11%%'', ''%%rank:255/1033%%''
[[2020-2021:teams:mian:cf_gym:2020-2021 BUAA ICPC Team Supplementary Training 02|2020-2021 BUAA ICPC Team Supplementary Training 02]] ''%%task:6/7/10%%'', ''%%rank:3/18%%''
====== 本周推荐 ======
===== Pantw =====
[[..:cf_gym:2020-2021_buaa_icpc_team_supplementary_training_02#h|【加训 2】H]]
* 分类：计算几何
* 题意：给一个第一象限内的简单多边形，引一条过原点的直线，问最多把原多边形分成多少部分。
* 做法：极角排序（其实就是排下斜率）完了之后扫描处理，详见上面的题解链接
* 评论：细节很多
===== Withinlover =====
[[https://codeforces.com/problemset/problem/546/E|CF 546E]]
* 分类：网络流，输出方案
* 题意：给定一个图，每个节点上有一定士兵，士兵可以沿边到达距离不超过 1 的点，给定每个点的目标人数，问是否能够达成。
* 做法：网络流，把每个点拆成入点和出点。判断有解就是最大流是否跑满，输出解按顺序找反向边
* 评论：细节得慢慢调
===== Gary =====
[[http://acm.hdu.edu.cn/showproblem.php?pid=6824|HDU6824]]
* 分类：2-SAT, 线段树
* 题意： n场考试 每场考试两个时间段(a,a+at),(b,b+bt) 必须选择一个 问完成所有考试的最小时间
* 解法：通过2-sat可以解决一个方案是否有解，因而我们可以二分完成考试的最小时间mid，对符合条件的考试间连边，发现对于一场考试$(a_i,a_i+at_i)$，所有(i,j)满足$a_i\le a_j \le a_i+at_i$都要连边，也就是j是一段区间，于是可以对考试按开始时间排序，2-sat建图时，通过线段树优化建图
* 评论：场上没有想到2-sat,线段树的优化非常的巧妙
====== 个人训练 ======
===== Pantw =====
==== 专题 ====
无
==== 比赛 ====
[[https://atcoder.jp/contests/abc174|ABC174]]
==== 题目 ====
ARC090D, ARC090E, ARC090F, ABC088D, AGC021B
SRM304A, SRM304B
===== Withinlover =====
==== 专题 ====
网络流（总结ing）
==== 比赛 ====
[[https://atcoder.jp/contests/abc174|ABC174]]
==== 题目 ====
CF546E CF576B
===== Gary =====
==== 专题 ====
无
==== 比赛 ====
[[https://atcoder.jp/contests/abc174|ABC174]]
[[http://acm.hdu.edu.cn/contests/contest_show.php?cid=883|2020 Multi-University Training Contest 5]]
==== 题目 ====
cf 298 div2 C D E F
AtCoder Beginner Contest 149 D E
2020 Multi-University Training Contest 5 1001 1007 1009