2020-2021:teams:farmer_john:2016_ccpc_长春站
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2016_ccpc_长春站 [2020/10/15 17:30] jjleo [题解] |
2020-2021:teams:farmer_john:2016_ccpc_长春站 [2020/10/15 17:55] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 49: | 行 49: | ||
| **solved by 2sozx JJLeo** | **solved by 2sozx JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给定一个序列，多次询问一个子区间，所有数第一次出现的下标拿出来组成一个新序列的中位数，强制在线。 | ||
| ====题解==== | ====题解==== | ||
| + | 见后缀和主席树，然后设区间内有 $x$ 个不同的数，直接查询第 $\lceil \frac{x}{2} \rceil$ 小即可。 | ||
| =====J.===== | =====J.===== | ||
| **solved by ** | **solved by ** | ||
| 行 60: | 行 60: | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 求 $1$ 到 $n$ 所有数二进制中 $1$ 的个数和以及两两之间最长公共前缀中 $1$ 的数量之和，不同的算两遍，相同的算一遍。 | ||
| ====题解==== | ====题解==== | ||
| + | 前者直接数位dp就行，后者也用数位dp的思想，考虑当每一位为 $1$ 时，对于相同的前缀后面有多少种方案。记录不压上界这一位为 $0$ 或 $1$ 的数量，对于 $1$ 后面随便填很好算出答案，对于压上界的，当这一位为 $1$ 时，后面能填的方案数可以算出来，直接加上平方即可。最后减去每个数的 $1$ 的数量，因为它们多算了。 | ||
| =====记录===== | =====记录===== | ||
| before:CSK查询比赛找到这场比赛，MJX找个空教室并多次眼神暗示教室另外一人将其劝退\\ | before:CSK查询比赛找到这场比赛，MJX找个空教室并多次眼神暗示教室另外一人将其劝退\\ | ||
2020-2021/teams/farmer_john/2016_ccpc_长春站.1602754241.txt.gz · 最后更改: 2020/10/15 17:30 由 jjleo
