2020.09.01 2020杭电多校第五场

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)

最小生成树

最短路

Codeforces Round #666 (Div. 1)

ecr 94 F

平衡树专题

拓扑排序与2-sat专题

2020.08.25 2020杭电多校第三场

2020.08.28 2020杭电多校第四场

abc 176

cf 1791g

无

Atcoder Beginner Contest 177

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

题意

序列里有k种不同的数，你每次可以询问l~r，可以得到其中众数是多少，这个众数出现了多少次，最多询问4*k次。

思路：

如果这个众数大于len/2，那么能确定[r-l+1,l+r-1]的区间里是众数

4*k很容易想到线段树

每次在线段树上询问，如果能确定的话，就询问剩下两个区间，否则询问l，mid和mid+1，r

算一下最坏情况也是4*k

评论：

4*k的操作数可以想线段树

一个数如果在区间出现次数大于len/2，那么能确定[r-l+1,l+r-1]的区间里是它

ecr 94 F

题意

有一个由1-9组成的字符串，定义x-prime串为该串所有数字之和等于x并且不存在连续字串使得和是x的真约数。

求最少删多少字串可以使得不存在x-prime。($x\leq20$，$|S|\leq1000$)

思路：

直接状压dp是不太可能的，如果能细心一下，可以发现所有不合法的x-prime串实际上在字典树上的节点个数非常少，因此我们可以在AC自动机上

dp，这样就能通过这道题。

评论：

本题巧妙在于它存储状态是采用了AC自动机来存储，而不是状压，这个题可以好好琢磨琢磨。

来源：CF 1388

算法：凸包、二分、区间

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

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

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

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

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

代码

评论：

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

注意特殊处理垂直的情况

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