======2020/08/29 -- 2020/09/03 周报======

======团队======

2020.09.01 [[.hdu_2020_5|2020杭电多校第五场]]

======个人======

=====todolist（补题）=====

2020牛客暑期多校训练营（第一场）CJY G XX C

2020牛客暑期多校训练营（第二场）**Finish**

2020牛客暑期多校训练营（第三场）CJY J/K ZRX I

2020牛客暑期多校训练营（第四场）CJY E XX G

2020牛客暑期多校训练营（第五场）CJY G/J

2020牛客暑期多校训练营（第六场）CJY F XX I ZRX D

2020牛客暑期多校训练营（第七场）CJY E ZRX **A**

2020牛客暑期多校训练营（第八场）XX J ZRX B/C

2020牛客暑期多校训练营（第九场）ZRX L

2020牛客暑期多校训练营（第十场）CJY G XX B ZRX F

2020加赛1 CJY E XX B/C ZRX D

2020加赛2 CJY E

2015ICPC北京 ZRX E (B/F/H)

2020杭电多校第一场 ZRX **C**

2020杭电多校第二场 CJY B ZRX **K** (C)

2020杭电多校第三场 CJY B XX A ZRX C (K)

2020杭电多校第四场 XX F ZRX J (A/H)

2020杭电多校第四场 XX F ZRX J (A/H)

2020杭电多校第五场 CJY E/**J** XX B ZRX K (D/F/M)
=====CJY=====

====专题====

最小生成树

最短路
====比赛====

Codeforces Round #666 (Div. 1)
====题目====

2020杭电多校第五场 J
=====ZRX=====

====专题====

哈希专题

====比赛====

2020.09.01 [[.hdu_2020_5|2020杭电多校第五场]]

abc 177

====题目====

abc 177f

=====XX=====

====专题====

无
====比赛====

Atcoder Beginner Contest 177
====题目====

Codeforces 1381/D 1388/E 1389/G 1391/E 1400/G

======本周推荐======

=====zrx=====

**题意**

（n+1）*m网格，第2-n+1行每一行li-ri不能向下

你可以从第1行任意一个位置出发，问到第i行的最小步数，每行独立。

**思路**：

存一个map pre ai 维护，每个位置最靠右可以从第1行哪来，

li ri相当于删去li到ri，并加入ri+1即可

**评论**：

考虑特殊的位置

=====cjy=====

**题意** 

一个N*N的网格，在上面放T个石子，要求每行每列不超过2个，问方案数？(N小于等于200，T小于等于400)

**思路**：

直接动态规划，$f_{ijk}$表示已经填了i行，上面有j列填了1个，k列填了2个的方案数。

转移的时候枚举这一行填0，1还是2。修改j和k即可。

时间复杂度是O($N^3$)

**评论**：

一定要注意，这类转移状态比较少的，不要把它转换成二部图找环去考虑，因为那样复杂度太大了。

=====XX=====

====CF 1388 E Uncle Bogdan and Projections====

来源：[[https://codeforces.com/contest/1388/problem/E|CF 1388]] 

算法：凸包、二分、区间

**题意**：
给n($n\leq$ 2000)条水平线段，求一个方向向量，使得这些直线按照该方向向量向x轴做投影后，所有线段不相交，求这些线段所覆盖的位置的最左端的和最右端的距离最小。

**思路**：
考虑两条线段AB、CD，只有AC、BD才可能成为答案。同时，斜率处于AC与BD之间的向量不能作为答案，否则会使AB、CD的投影相交。

所以，我们需要枚举出所有可能的答案，然后用区间覆盖的方式除去矛盾的线段，然后再比较哪一个向量求得的答案最小的答案。

对于一个已知向量，我们需要求出投影后最左端和最右端的点。可以建凸包，然后根据叉积（或者斜率）进行二分即可。

注意，可能所有直线都在同一高度，此时需要特判垂直的情况（见样例3）。

[[https://blog.csdn.net/micaudience/article/details/108381788|代码]]

**评论**：

运用凸包+二分可以快速找最左/右端点，但需要注意每次凸包只能左/右侧跑一半！！

注意特殊处理垂直的情况

尽量使用long long代替long double来减少浮点误差。(用叉积代替斜率，用乘法代替除法)