====== 2020/05/09 -- 2020/05/15 周报 ======

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

==== airbust ====

CF 1350C Orac and LCM

  * 分类：数论
  * 简要题意： 给定一个长度为$n$的数组，求$gcd\{lcm(a_i,a_j)|i<j\}$
  * 解法： 对于$a_i$，产生的lcm有$lcm(a_i,a_1),...,lcm(a_i,a_{i-1}),lcm(a_i,a_{i+1}),...,lcm(a_i,a_n)$，则它们的gcd为$gcd_i=gcd(lcm(a_i,a_1),...,lcm(a_i,a_{i-1}),lcm(a_i,a_{i+1}),...,lcm(a_i,a_n))$，由于它们中的每一项都含有$a_i$，故$a_i$必为$gcd_i$的因子，那么可化简为$gcd_i=lcm(a_i,gcd(a_1,...,a_{i-1},a_{i+1},...,a_n))$，那么答案为$gcd(gcd_1,...,gcd_n)$

==== kazamori ====

CF 1348E Phoenix and Berries

  * 分类：DP
  * 简要题意： 有$n$棵树，每棵树上有$a_i$个红果实和$b_i$个蓝果实。有可以装$k$个果实的篮子，一个篮子只能放同种颜色或同一棵树上的果实。求最多可以放满多少个篮子？
  * 解法： 最多只有$n$个篮子内的果实是不同色的（若同一棵树上装了多个不同色的篮子 ，则可以转化为多个同色的篮子加上一个不同色的篮子 ），枚举第$i$棵树生成的不同色的篮子的组成，dp求解。''%%dp[i][j]%%''表示前$i$棵树装完后，剩下$j$颗红果实时，最多能填满的篮子的数量。

==== 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/1353|Codeforces Round #642 (Div. 3)]]
  * [[https://codeforces.com/contest/1350|Codeforces Round #641 (Div. 2)]]
  * [[https://codeforces.com/contest/1352|Codeforces Round #640 (Div. 4)]]
  * [[https://codeforces.com/contest/1351|Testing Round #16 (Unrated)]]
  * [[https://codeforces.com/contest/1343|Codeforces Round #636 (Div. 3)]]
==== kazamori ====

=== 比赛 ===

  * [[https://codeforces.com/contest/1348|Codeforces Round #638 (Div. 2)]]
  * [[https://codeforces.com/contest/1342|Educational Codeforces Round 86 (Rated for Div. 2)]]

==== Ket98 ====

=== 比赛 ===

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