2020-2021:teams:i_dont_know_png:multi2020-nowcoder-5
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-5 [2020/07/28 18:16] nikkukun add H |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-5 [2020/08/07 09:24] (当前版本) potassium DF |
||
|---|---|---|---|
| 行 112: | 行 112: | ||
| 总时间复杂度 $O(T\min(n, m))$。 | 总时间复杂度 $O(T\min(n, m))$。 | ||
| + | |||
| + | |||
| + | |||
| + | ===== D - Drop Voicing ===== | ||
| + | |||
| + | Solved by qxforever. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一个 $1-n$ 的排列 $p$，有两种操作： | ||
| + | |||
| + | - 把序列最前面数的放到最后面 | ||
| + | - 把序列倒数第二后的数放到最前面 | ||
| + | |||
| + | 要把原排列变为元排列，求最少的（连续第二种操作）的次数。 | ||
| + | |||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 排成一个环之后发现，一操作就是旋转，二操作就是交换，故问题转化成求环排列的最大 LIS，答案即为 $n-$ 最大 LIS。 | ||
| 行 117: | 行 137: | ||
| ===== E - Bogo Sort ===== | ===== E - Bogo Sort ===== | ||
| + | |||
| + | Solved by Potassium. | ||
| + | |||
| + | 水题不表。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== F - DPS ===== | ||
| Solved by Potassium. | Solved by Potassium. | ||
| 行 150: | 行 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.1595931396.txt.gz · 最后更改: 2020/07/28 18:16 由 nikkukun
