2020-2021:teams:the_great_wave_off_kanagawa:week_summary_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:the_great_wave_off_kanagawa:week_summary_2 [2020/05/15 12:31] airbust |
2020-2021:teams:the_great_wave_off_kanagawa:week_summary_2 [2020/05/16 23:31] (当前版本) airbust |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ==== airbust ==== | ==== airbust ==== | ||
| - | CF 1342D Mulitple Cases | + | CF 1350C Orac and LCM |
| - | 先求出一共要多少个case，假设大于等于i的$m_i$个数是$b_i$，根据抽屉原理，case的个数要大于等于$\lceil \frac {b_i}{c_i} \rceil$，所以一共需要$ans=max(\lceil \frac {b_i}{c_i} \rceil)$个case。然后是构造方案，将$m_i$从小到大排序，每个$m_i$放入第$(i\ mod\ ans)$个case即可。 | + | * 分类：数论 |
| + | * 简要题意： 给定一个长度为$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 ==== | ==== kazamori ==== | ||
| 行 18: | 行 20: | ||
| ==== Ket98 ==== | ==== Ket98 ==== | ||
| + | |||
| + | ABC E - Colorful Blocks | ||
| - | CF 1344A Hilbert’s Hotel | + | * 分类：统计/组合数 |
| - | + | * 题目大意：现有$M$种颜色，$N$个块。问有多少种上色方式，使得两两之间相邻且颜色相同的块不超过$K$组，对$998244353$取模。 | |
| - | 这道题很简单，直接在$0\leq i<n$之间统计''%%(i+a[i])%n%%''的值，用''%%unique%%''判断有没有重复的即可。 | + | * 思路：两两之间相邻且颜色相同的块为$i$组时，可以在$N-1$个空隙中插入$N-1-i$个隔板，这样分出来的$N-i$个组，只有第一组颜色有$M$种选择，后边的组都只有$M-1$中选择。将$0\le i \le K$之间的情况求和即可。 |
| - | + | ||
| - | 注意的是本题有负数，所以取模要写成''%%((i+a[i])%n+n)%n%%'' | + | |
| ===== 个人 ===== | ===== 个人 ===== | ||
| 行 31: | 行 33: | ||
| === 比赛 === | === 比赛 === | ||
| - | + | * [[https://codeforces.com/contest/1353|Codeforces Round #642 (Div. 3)]] | |
| - | * [[https://codeforces.com/contest/1345|Codeforces Round #639 (Div. 2)]] | + | * [[https://codeforces.com/contest/1350|Codeforces Round #641 (Div. 2)]] |
| - | * [[https://codeforces.com/contest/1348|Codeforces Round #638 (Div. 2)]] | + | * [[https://codeforces.com/contest/1352|Codeforces Round #640 (Div. 4)]] |
| - | * [[https://codeforces.com/contest/1342|Educational Codeforces Round 86 (Rated for Div. 2)]] | + | * [[https://codeforces.com/contest/1351|Testing Round #16 (Unrated)]] |
| + | * [[https://codeforces.com/contest/1343|Codeforces Round #636 (Div. 3)]] | ||
| ==== kazamori ==== | ==== kazamori ==== | ||
| 行 47: | 行 49: | ||
| === 比赛 === | === 比赛 === | ||
| - | *[[https://codeforces.com/contest/1344|Codeforces Round #639 (Div. 1)]] | + | * [[https://atcoder.jp/contests/abc167|AtCoder Beginner Contest 167]] |
| + | * [[https://codeforces.ml/contests/1353|Codeforces Round #642 (Div. 3)]] | ||
2020-2021/teams/the_great_wave_off_kanagawa/week_summary_2.1589517100.txt.gz · 最后更改: 2020/05/15 12:31 由 airbust
