2020-2021:teams:hotpot:2020nowcoder8
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder8 [2020/08/07 11:44] misakatao 更新 |
2020-2021:teams:hotpot:2020nowcoder8 [2020/08/07 16:37] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| ===题解=== | ===题解=== | ||
| - | 单独一个状态的问题可以通过并查集解决，然后题目还有$q$次询问，是比较经典的动态图连通块个数判断，只需要把所有的边按照出现时间挂在时间线段树上，然后从根往叶子走，经过的边加入即可，为了可以回溯，需要用可以撤销的并查集 | + | 单独一个状态的问题可以通过并查集解决，然后题目还有$q$次询问，是比较经典的动态图连通块个数判断，只需要把所有的边按照出现时间挂在时间线段树上，然后从根往叶子走，经过的边加入即可，为了可以回溯，需要用可以撤销的并查集，并查集部分需要像一般的按秩合并并查集一样维护点个数，还需要维护粉丝的个数来方便答案的统计。 |
| ====B - ==== | ====B - ==== | ||
| 行 55: | 行 55: | ||
| ===题解=== | ===题解=== | ||
| - | ====E - ==== | + | ====E - Enigmatic Partition==== |
| - | ===solved by === | + | ===solved by gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 定义n的一种划分为一个不减数列，相邻两项最多差1，首项和末项差2。f(n)为n的划分种数。求T组数据，f(n)。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $1\le T\le 10^4,1\le n\le 10^5$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 设数列为m项。枚举$a_1，m$。对于这样的$a_1,m$的数列，计算其对f(a_1m+k)的贡献。发现，对$3\le k\le m$，其贡献为$\lfloor \frac {k-1}2 \rfloor$，对$m\le k\le 2m-3$，其贡献为$\lfloor \frac {2m-k-1}2 \rfloor$。设g(x)=f(x)-f(x-2)。先求g(x)，再得到f(x) | ||
| ====F - ==== | ====F - ==== | ||
2020-2021/teams/hotpot/2020nowcoder8.1596771899.txt.gz · 最后更改: 2020/08/07 11:44 由 misakatao
