2020-2021:teams:i_dont_know_png:multi2020-nowcoder-5
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-5 [2020/07/27 03:04] nikkukun add A & C |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-5 [2020/08/07 09:24] (当前版本) potassium DF |
||
|---|---|---|---|
| 行 29: | 行 29: | ||
| - $f(i, u, a)$：完成前 $i$ 个任务，目前在 $u$，当前位置有一个传送门，另一个在 $a$。状态的化简是基于**传送门一定是用的时候当场打开**的观察的。 | - $f(i, u, a)$：完成前 $i$ 个任务，目前在 $u$，当前位置有一个传送门，另一个在 $a$。状态的化简是基于**传送门一定是用的时候当场打开**的观察的。 | ||
| - | 正解还可以继续精简状态：$f(i, u, a)$ 表示完成前 $i$ 个任务且站在结束节点上，当前令一个传送门在 $a$。状态的化简是基于**一次任务只会改变最多一次传送门**的观察的。这样枚举本次任务后传送门变为 $b$，有三种转移： | + | 正解还可以继续精简状态：$f(i, a)$ 表示完成前 $i$ 个任务且站在结束节点上，当前令一个传送门在 $a$。状态的化简是基于**一次任务只会改变最多一次传送门**的观察的。这样枚举本次任务后传送门变为 $b$，有三种转移： |
| - $c_i \to c_{i+1}$，不用传送门； | - $c_i \to c_{i+1}$，不用传送门； | ||
| 行 112: | 行 112: | ||
| 总时间复杂度 $O(T\min(n, m))$。 | 总时间复杂度 $O(T\min(n, m))$。 | ||
| + | |||
| + | |||
| + | |||
| + | ===== D - Drop Voicing ===== | ||
| + | |||
| + | Solved by qxforever. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一个 $1-n$ 的排列 $p$，有两种操作： | ||
| + | |||
| + | - 把序列最前面数的放到最后面 | ||
| + | - 把序列倒数第二后的数放到最前面 | ||
| + | |||
| + | 要把原排列变为元排列，求最少的（连续第二种操作）的次数。 | ||
| + | |||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 排成一个环之后发现，一操作就是旋转，二操作就是交换，故问题转化成求环排列的最大 LIS，答案即为 $n-$ 最大 LIS。 | ||
| 行 121: | 行 141: | ||
| 水题不表。 | 水题不表。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== F - DPS ===== | ||
| + | |||
| + | Solved by Potassium. | ||
| + | |||
| + | 水题不表。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== H - Interval ===== | ||
| + | |||
| + | Upsolved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给长度为 $n \leq 10^5$、值域在 $[0, 2^{30})$ 的序列 $a_1, a_2, \ldots, a_n$，强制在线 $q \leq 10^5$ 次询问下标 $[l, r]$ 的所有子区间中，区间按位与能获得的值的个数。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 比赛时想到了对于确定的左端点，其右端点最多能产生 $O(\log V)$ 个值，因此实际只需要统计 $[l, r]$ 里包含了多少个这样的极小区间即可，这是一个二维偏序问题。但是这样显然是不行的，同一个值只能统计一次，当时并没有想到如何消除影响。 | ||
| + | |||
| + | 题解给出了一种很妙的做法：对同一个值的所有区间，首先消除掉所有包含关系（事实上，如果一开始找区间就选的极小区间，是不会出现除了全等之外的包含关系的），并按左端点依次排序为 $(l_1, r_1), (l_2, r_2), \ldots (l_k, r_k)$。额外添加 $k-1$ 个区间 $(l_1, r_2), (l_2, r_3), \ldots (l_{k-1}, r_k)$ 并令其贡献为 $-1$，则刚才的统计就是对的了。 | ||
| + | |||
| + | 可以手玩一下上面的构造，当包含了相邻两个区间时会自动让结果 $-1$，这个结果在两区间相交与否的情况都成立。 | ||
| 行 130: | 行 179: | ||
| 水题不表。 | 水题不表。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== K - Git Merge ===== | ||
| + | |||
| + | Upsolved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一段用 Git Merge 的、有两个 branch 的代码，需要你重新合并出一个最少行的结果，具体操作请参考原题。输入总行数不超过 $4000$ 行。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 先把两段源代码还原出来，令 $f(i, j, \mathrm{op})$ 为处理了第一段代码的前 $i$ 行、第二段代码的前 $j$ 行，目前正处于第一段单独区间/第二段单独区间/两段共用区间的最小行数，不同 $\mathrm{op}$ 之间的切换会增加一行的代价，DP 转移即可。可能需要用哈希判断行相等，用 short 存数组减少空间。 | ||
| + | |||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-5.1595790261.txt.gz · 最后更改: 2020/07/27 03:04 由 nikkukun
