2020-2021:teams:the_great_wave_off_kanagawa:week_summary_3
2020/05/16 -- 2020/05/22 周报
本周推荐
airbust
CF 1354D Multiset
- 分类：二分，数据结构
- 简要题意： 给定一个长度为$n(n \leq 1e6)$的数组$a_1,\ldots,a_n$，$q$次询问，每次插入一个数或删除第$k$小数，保证每次操作有$1 \leq a_i \leq n$，输出最后结果
- 解法： 可以用树状数组维护$1$到$n$每个数字出现的次数，插入很简单，直接将对应的数的次数加1，删除第$k$小数可以通过在树状数组上二分求得第$k$小数，然后将次数减1，最后再输出结果。
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
比赛
kazamori
比赛
Ket98
比赛
2020-2021/teams/the_great_wave_off_kanagawa/week_summary_3.1590391971.txt.gz · 最后更改: 2020/05/25 15:32 由 airbust
