这是本文档旧的修订版！

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$，在$L$里存入$\{n-k,r-l\}$

3.$l=r$，随便放

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

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

CF 1354C2 Not So Simple Polygon Embedding

分类：计算几何
简要题意：给出奇数n，求覆盖边数为 2n 边长为 1 的正凸多边形的最小正方形的边长。
解法：对于一个正多边形，设个顶点与中心连线形成的每个小三角形的顶角为 θ，假设多边形旋转角度为 α。当 α等于0 和θ/2时情况相同中心距离最远的顶点的距离最大，且变化具有对称性。因此猜想最优解在中间位置取得。$$ans=\frac{cos(\frac{\pi}{4n})}{sin(\frac{\pi}{2n})}$$

ABC E - Colorful Blocks

分类：统计/组合数
题目大意：现有$M$种颜色，$N$个块。问有多少种上色方式，使得两两之间相邻且颜色相同的块不超过$K$组，对$998244353$取模。
思路：两两之间相邻且颜色相同的块为$i$组时，可以在$N-1$个空隙中插入$N-1-i$个隔板，这样分出来的$N-i$个组，只有第一组颜色有$M$种选择，后边的组都只有$M-1$中选择。将$0\le i \le K$之间的情况求和即可。