2020-2021:teams:the_great_wave_off_kanagawa:week_summary_3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:the_great_wave_off_kanagawa:week_summary_3 [2020/05/22 11:42] airbust 创建 |
2020-2021:teams:the_great_wave_off_kanagawa:week_summary_3 [2020/05/25 21:56] (当前版本) airbust |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ==== airbust ==== | ==== airbust ==== | ||
| - | CF 1350C Orac and LCM | + | CF 1354D Multiset |
| - | * 分类：数论 | + | * 分类：二分，数据结构 |
| - | * 简要题意： 给定一个长度为$n$的数组，求$gcd\{lcm(a_i,a_j)|i<j\}$ | + | * 简要题意： 给定一个长度为$n(n \leq 1e6)$的数组$a_1,...,a_n$，$q$次询问，每次插入一个数或删除第$k$小数，保证每次操作有$1 \leq a_i \leq n$，输出最后结果 |
| - | * 解法： 对于$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)$ | + | * 解法： 可以用树状数组维护$1$到$n$每个数字出现的次数，插入很简单，直接将对应的数的次数加1，删除第$k$小数可以通过在树状数组上二分求得第$k$小数，然后将次数减1，最后再输出结果。 |
| ==== kazamori ==== | ==== kazamori ==== | ||
| - | CF 1348E Phoenix and Berries | + | CF 1354C2 Not So Simple Polygon Embedding |
| - | * 分类：DP | + | * 分类：计算几何 |
| - | * 简要题意： 有$n$棵树，每棵树上有$a_i$个红果实和$b_i$个蓝果实。有可以装$k$个果实的篮子，一个篮子只能放同种颜色或同一棵树上的果实。求最多可以放满多少个篮子？ | + | * 简要题意： 给出奇数n，求覆盖边数为 2n 边长为 1 的正凸多边形的最小正方形的边长。 |
| - | * 解法： 最多只有$n$个篮子内的果实是不同色的（若同一棵树上装了多个不同色的篮子 ，则可以转化为多个同色的篮子加上一个不同色的篮子 ），枚举第$i$棵树生成的不同色的篮子的组成，dp求解。''%%dp[i][j]%%''表示前$i$棵树装完后，剩下$j$颗红果实时，最多能填满的篮子的数量。 | + | * 解法： 对于一个正多边形，设个顶点与中心连线形成的每个小三角形的顶角为 θ，假设多边形旋转角度为 α。 当 α等于0 和θ/2时情况相同中心距离最远的顶点的距离最大 ，且变化具有对称性。因此猜想最优解在中间位置取得。$$ans=\frac{cos(\frac{\pi}{4n})}{sin(\frac{\pi}{2n})}$$ |
| ==== Ket98 ==== | ==== Ket98 ==== | ||
| 行 33: | 行 33: | ||
| === 比赛 === | === 比赛 === | ||
| - | * [[https://codeforces.com/contest/1353|Codeforces Round #642 (Div. 3)]] | + | * [[https://codeforces.com/contest/1354|Educational Codeforces Round 87 (Rated for Div. 2)]] |
| - | * [[https://codeforces.com/contest/1350|Codeforces Round #641 (Div. 2)]] | + | * [[https://codeforces.com/contest/1355|Codeforces Round #643 (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 ==== | ==== kazamori ==== | ||
| === 比赛 === | === 比赛 === | ||
| - | * [[https://codeforces.com/contest/1348|Codeforces Round #638 (Div. 2)]] | + | * [[https://codeforces.com/contest/1354|Educational Codeforces Round 87 (Rated for Div. 2)]] |
| - | * [[https://codeforces.com/contest/1342|Educational Codeforces Round 86 (Rated for Div. 2)]] | + | |
| ==== Ket98 ==== | ==== Ket98 ==== | ||
2020-2021/teams/the_great_wave_off_kanagawa/week_summary_3.1590118944.txt.gz · 最后更改: 2020/05/22 11:42 由 airbust
