这是本文档旧的修订版！

2020/07/12 -- 2020/07/18 周报

本周推荐

AIsing Programming Contest 2020 E Camel Train

这题比赛时没有做出来，后来发现用优先队列可以解决。每个骆驼有两个快乐值，用pair保存，然后用两个vector $L$和$R$存放各个骆驼，分三种情况：

1.$l>r$，此时要把骆驼放在前$k$个位置才能获得最大快乐值，但不能确定最终队伍里这个骆驼是否在前$k$个位置，所以总答案先加上$r$，在$L$里存入$\{k,l-r\}$

2.$l<r$，此时要把骆驼放在后$n-k$个位置才能获得最大快乐值，但不能确定最终队伍里这个骆驼是否在后$n-k$个位置，所以总答案先加上$l$，在$R$里存入$\{n-k,r-l\}$

3.$l=r$，随便放

下面考虑$L,R$内快乐值的计算：

我们将vector按位置先后排序，然后创建一个从小到大的优先队列，每取一个元素就向队列中存一个快乐值，答案也加上该快乐值。此时队内元素的个数也代表排好的队形，如果元素个数大于当前元素的位置，就相当于已经排满了，就必须减去队首的快乐值，直到可以插入元素为止，最后返回答案即可。

CF 1374E2 Reading Books

分类：贪心
简要题意：有两个人以及n本书，每本书有3个属性：t：表示读完这本书要的时间，a：第一个人是否喜欢这本书，b：第二个人是否喜欢这本书。让你构造一种方案使得他们读的书正好是m本，并且这些书中第一个人喜欢的书有>=k本，第二个人喜欢的书有>=k本，并且读书总时间最少。
解法：先将每本书按a,b属性分类(00,01,10,11)按时间从小到大放入各自的优先队列，然后贪心选择数量最少且时间和尽量小的x本书，满足a，b属性此时的和均>=k(先尽量选择属性为11的书，若不够则从队首选择属性为01，10的两本书)。若此时x>m，则不存在满足条件的方案。否则记录此时未选中的所有的书，并放入优先队列。若此时选中的属性为11的书中时间最大的加上未选中的书中时间最小的时间和小于未选中的属性为10的书中时间最小以及未选中的属性为01的书中时间最小的时间和，则进行替换并x++，并更新未选中的书的优先队列。否则选择未选中的书中的队首，并x++。当x==m时，输出方案。

Boundary

分类：计算几何
题目大意：考虑所有经过原点的圆，在所给$n$个点中，找出在同一个圆上最多的点的数量。
思路：一开始因为测试用例，我错以为是以所给的点中选择一个点作为圆心，之后就一直错。其实圆心不局限在所给点中，只要圆经过所给点即可。利用圆周角的思路。先枚举所有的点$A$，然后在每一次枚举中在枚举一遍所有的点$B$，计算圆周角$ABO$的cos值，寻找出众数的数量。在每一次枚举的众数的数量，寻找最大的那一个即可。