====== 2020/05/16 -- 2020/05/22 周报 ======

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

==== airbust ====

CF 1354D Multiset

  * 分类：二分，数据结构
  * 简要题意： 给定一个长度为$n(n \leq 1e6)$的数组$a_1,...,a_n$，$q$次询问，每次插入一个数或删除第$k$小数，保证每次操作有$1 \leq a_i \leq n$，输出最后结果
  * 解法： 可以用树状数组维护$1$到$n$每个数字出现的次数，插入很简单，直接将对应的数的次数加1，删除第$k$小数可以通过在树状数组上二分求得第$k$小数，然后将次数减1，最后再输出结果。

==== kazamori ====

CF 1354C2  Not So Simple Polygon Embedding 

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

==== Ket98 ====
   
ABC E - Colorful Blocks

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

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


==== airbust ====

=== 比赛 ===
  * [[https://codeforces.com/contest/1354|Educational Codeforces Round 87 (Rated for Div. 2)]]
  * [[https://codeforces.com/contest/1355|Codeforces Round #643 (Div. 2)]]

==== kazamori ====

=== 比赛 ===

  * [[https://codeforces.com/contest/1354|Educational Codeforces Round 87 (Rated for Div. 2)]]

==== Ket98 ====

=== 比赛 ===

  * [[https://atcoder.jp/contests/abc167|AtCoder Beginner Contest 167]]
  * [[https://codeforces.ml/contests/1353|Codeforces Round #642 (Div. 3)]]