2020-2021:teams:mian:weekly_report:2020_summer_week_4_report
目录
2020 Summer Week 4 Report
团队训练
2020牛客暑期多校训练营（第七场） task:4/6/10, rank:56/1140
2020牛客暑期多校训练营（第八场） task:3/4/11, rank:255/1033
2020-2021 BUAA ICPC Team Supplementary Training 02 task:6/7/10, rank:3/18
本周推荐
Pantw
Withinlover
Gary
- 分类：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
专题
无
比赛
题目
Withinlover
专题
比赛
题目
Gary
专题
无
比赛
题目
cf 298 div2 C D E F
[AtCoder Beginner Contest 149] D E
2020 Multi-University Training Contest 5 1001 1007 1009
2020-2021/teams/mian/weekly_report/2020_summer_week_4_report.1596776341.txt.gz · 最后更改: 2020/08/07 12:59 由 grapelemonade
