2020-2021:teams:farmer_john:2016_ccpc_长春站
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2016_ccpc_长春站 [2020/10/15 17:27] jjleo [题意] |
2020-2021:teams:farmer_john:2016_ccpc_长春站 [2020/10/15 17:55] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 29: | 行 29: | ||
| 环套树，求最短路程走完所有节点，如果有多个答案，优先选起点最小，如何还有多个答案，优先选终点最小。 | 环套树，求最短路程走完所有节点，如果有多个答案，优先选起点最小，如何还有多个答案，优先选终点最小。 | ||
| ====题解==== | ====题解==== | ||
| + | 先找环，然后如果起点终点在同一颗树，那么答案等价于所有树边的两倍加上环长减去这棵树的直径；否则等于所有树边的两倍加上环长减去两点在环上的距离再减去两棵树的最深点的深度，破链成环使用单调队列即可维护。 | ||
| =====F.===== | =====F.===== | ||
| **solved by ** | **solved by ** | ||
| 行 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_长春站.1602754025.txt.gz · 最后更改: 2020/10/15 17:27 由 jjleo
