2020-2021:teams:hotpot:200606-200612
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200606-200612 [2020/06/12 12:21] misakatao 勘误 |
2020-2021:teams:hotpot:200606-200612 [2020/06/12 19:37] (当前版本) lotk |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| =====本周推荐===== | =====本周推荐===== | ||
| - | 林星涵： | + | 林星涵：「2017 山东二轮集训 Day6」汇合 |
| + | |||
| + | [[https://loj.ac/problem/6115|传送门]] | ||
| + | |||
| + | 题目大意：求任意两点的最近公共祖先。 | ||
| + | |||
| + | 数据范围：$n$ (点数) $\le$ 900000 $m$（询问） $\le$ 100000 内存限制 4 $Mib$。 | ||
| + | |||
| + | 解题思路：乍看之下 $2s$ 时限，$900000$ 的点数，可以用爬树法水过，但是由于内存限制感人，显然 $nlogn$ 的空间是会 $MLE$的。因此，这题我们需要采用树上分块的思想，用块来统计信息爬树。只需处理好每一块深度最浅的点，每一块的上一块的编号，每一块在由块组成的这个新树中的深度等信息，别的操作基本上都与爬树法相同。 | ||
| 陶吟翔：[FJOI2014]树的重心 | 陶吟翔：[FJOI2014]树的重心 | ||
| 行 34: | 行 42: | ||
| 郭衍培： | 郭衍培： | ||
| + | |||
| + | [[http://codeforces.com/contest/1366/problem/E|题目链接]] | ||
| + | |||
| + | 题目大意：给定一个长度为n的序列A，一个长度为m的序列B。保证B序列单增。将A分成m个子串，满足第i个子串最小值为$b_i$。求满足要求的划分方案。答案模998244353 | ||
| + | |||
| + | 数据范围：$n,m\le 2\times 10^5$ | ||
| + | |||
| + | 解题思路：要利用好B单增的性质。由于b[j]递增，所以A中最后一个等于b[j]的元素一定在第j个子串中。维护一个后缀最小$c[i]=\min_{k=i}^na[k]$。若$c[1]\ne b[1]$，结果显然为0。对于j>1，只需看C中有多少个元素等于b[j]，每个等于b[j]的元素之前都可以切开。下一次切开的地方，一定有c>b[j]。所以，最终答案就是所有等于b[j]的元素个数的乘积。 | ||
2020-2021/teams/hotpot/200606-200612.1591935705.txt.gz · 最后更改: 2020/06/12 12:21 由 misakatao
