2023-2024:teams:cute_red_meow:nowcoder1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2023-2024:teams:cute_red_meow:nowcoder1 [2023/07/22 20:42] yuki |
2023-2024:teams:cute_red_meow:nowcoder1 [2023/07/24 01:02] (当前版本) projekt_red |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| Meow | Meow | ||
| - | ===== H ===== | + | ===== A ===== |
| - | 考虑到如果交换了 $a_x$ 和 $a_y$，答案将从 $|a_x - b_x| + |a_y - b_y|$ 变为 $|a_x - b_y| + |a_y - b_x|$ 假设 $a_x < a_y$，那么，发生交换后： | + | toby: |
| - | * $a_x < b_x$： | + | <html> |
| - | * 普通列表项目 | + | 设给定 01 序列的长度为 n，1 的个数为 k。我的思路是进行如下几步：<br> |
| - | * $a_x > b_x$： | + | <ol> |
| + | <li>将给定字符串所有 0 位置排序（冒泡）: 消耗次数 $\frac{(n-k)(n-k-1)}{2}$</li> | ||
| + | <li>剔除最后一个 0 的位置，将其他位置排序（把 1 的位置插入排序）: 消耗次数 $k(n-k-1)$</li> | ||
| + | <li>将末尾 k 位排序（把上一位锁定的 0 插入排序）: 消耗次数 $(k-1)$ </li> | ||
| + | </ol> | ||
| + | 合计次数最多 119 次。 | ||
| + | </html> | ||
| + | Dirty: 没考虑到最后一个位置可能不是 0，直接锁了最后一位。改了之后又太慌，忘记改第三步的排序了。（我是笨蛋） | ||
| + | ===== D ===== | ||
| + | toby: | ||
| - | 把序列按 $a$ 排序后，用线段树按 $b$ 的大小维护 $a - b$、$a + b$ 等信息。按 $a$ 排序后的顺序进行遍历，在大小关系相反的区间内的线段树上查找最优解。 | + | 这是一个经典的数学问题（许多书上有提到）。当然不知道结论也可以猜。下面给出一个证明： |
| + | |||
| + | 首先可以发现 (n, m) 格肯定是最后拿到的，拿到的人就输了。<html><br></html> | ||
| + | 当 n==1 && m==1 时，由于只有一个拿取的方案，所以先手必败。<html><br></html> | ||
| + | 其他情况，假设先手必败，则先手取 (1, 1)，后手必有必胜方案，不妨设为取 (a, b)，那么先手只需要在第一手取 (a, b) 就可以得到一致的必胜局面，导出矛盾。故先手必胜。 | ||
| + | |||
| + | Dirty: 无。考场花了 5 min 重导这个结论。 | ||
| + | |||
| + | |||
| + | ===== H ===== | ||
| + | yuki: | ||
| + | |||
| + | 考虑到如果交换了 $b_x$ 和 $b_y$（交换 $a$ 是等价的），答案将从 $|a_x - b_x| + |a_y - b_y|$ 变为 $|a_x - b_y| + |a_y - b_x|$ 那么 $a_x$ 和 $b_x$ 的大小关系和 $a_y$ 和 $b_y$ 的大小关系一定是相反的，否则交换后的结果要么不变，要么变大。因此把输入分为两类 $a \leq b$ 的和 $a > b$ 的。 | ||
| + | |||
| + | 假设：$a_x \geq b_x$ 那么可能交换的 $a_y < b_y$，按 $b_y$ 从小到大遍历所有的第二类元组，不断把第一类元组加入线段树，保持线段树中 $a_x \leq b_y$，再以 $a_y$ 作为分界在线段树上分别查询 $b_x < a_y$和 $b_x \geq a_y$ 两种情况的最优解。 | ||
| - | 若此时 $a_i < b_i$ 那么当前线段树上维护了所有 $a_j < a_i$ 的元组的信息。若 原始答案 | ||
| Dirty： 线段树写错了（我是笨蛋） | Dirty： 线段树写错了（我是笨蛋） | ||
| + | |||
| + | |||
| + | ===== J ===== | ||
| + | red: | ||
| + | |||
| + | 简单期望题，推两下得到式子，交给 toby 但他不愿意写，然后就自己写一发过了 | ||
| + | |||
| + | Dirty: 这怎么会有 dirty 呢（x) | ||
| + | |||
| + | ===== K ===== | ||
| + | red: | ||
| + | |||
| + | 图论题，构建出最短路的生成树后最大化延长所有非树边，然后对叶节点特殊讨论即可。 | ||
| + | |||
| + | Dirty: 太弱智了。边数开少了 t 了两次，距离 1 未特判 wa 了两次。 | ||
| + | |||
| + | |||
| + | ===== M ===== | ||
| + | red: | ||
| + | |||
| + | 开局看到感觉可做，发现是解不定方程后发现忘了怎么解，于是交给 yuki 了。 | ||
| + | |||
| + | yuki: | ||
| + | |||
| + | exgcd解方程，再凑一凑答案。 | ||
| + | |||
| + | Dirty： 考虑了最后一杯水可以不倒掉的情况，但只考虑了一半（我是笨蛋） | ||
| + | |||
| + | ====== 场上没过的题 ====== | ||
| + | |||
| + | ===== L ===== | ||
| + | red: | ||
| + | |||
| + | 发现置换 3k 次是个环，剩下就只需要解同余方程组。因为模数不一定互质，所以不能直接用中国剩余定理。想到可以对模数分解后再用，但 toby 已经硬解出来了，然后就基本正确了。 | ||
| + | |||
| + | 场上没过的原因似乎是 exgcd 过程爆 ll 了，改成 int128 就对了，太气人了。 | ||
2023-2024/teams/cute_red_meow/nowcoder1.1690029752.txt.gz · 最后更改: 2023/07/22 20:42 由 yuki
