2023-2024:teams:cute_red_meow:nowcoder1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2023-2024:teams:cute_red_meow:nowcoder1 [2023/07/23 10:52] toby-shi [D] |
2023-2024:teams:cute_red_meow:nowcoder1 [2023/07/24 01:02] (当前版本) projekt_red |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| Meow | Meow | ||
| + | ===== A ===== | ||
| + | toby: | ||
| + | |||
| + | <html> | ||
| + | 设给定 01 序列的长度为 n，1 的个数为 k。我的思路是进行如下几步：<br> | ||
| + | <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 ===== | ===== D ===== | ||
| toby: | toby: | ||
| 行 6: | 行 20: | ||
| 这是一个经典的数学问题（许多书上有提到）。当然不知道结论也可以猜。下面给出一个证明： | 这是一个经典的数学问题（许多书上有提到）。当然不知道结论也可以猜。下面给出一个证明： | ||
| - | 首先可以发现 (n, m) 格肯定是最后拿到的，拿到的人就输了。<br> | + | 首先可以发现 (n, m) 格肯定是最后拿到的，拿到的人就输了。<html><br></html> |
| - | 当 n==1 && m==1 时，由于只有一个拿取的方案，所以先手必败。<br> | + | 当 n==1 && m==1 时，由于只有一个拿取的方案，所以先手必败。<html><br></html> |
| 其他情况，假设先手必败，则先手取 (1, 1)，后手必有必胜方案，不妨设为取 (a, b)，那么先手只需要在第一手取 (a, b) 就可以得到一致的必胜局面，导出矛盾。故先手必胜。 | 其他情况，假设先手必败，则先手取 (1, 1)，后手必有必胜方案，不妨设为取 (a, b)，那么先手只需要在第一手取 (a, b) 就可以得到一致的必胜局面，导出矛盾。故先手必胜。 | ||
| 行 22: | 行 36: | ||
| Dirty： 线段树写错了（我是笨蛋） | Dirty： 线段树写错了（我是笨蛋） | ||
| + | |||
| + | |||
| + | ===== J ===== | ||
| + | red: | ||
| + | |||
| + | 简单期望题，推两下得到式子，交给 toby 但他不愿意写，然后就自己写一发过了 | ||
| + | |||
| + | Dirty: 这怎么会有 dirty 呢（x) | ||
| + | |||
| + | ===== K ===== | ||
| + | red: | ||
| + | |||
| + | 图论题，构建出最短路的生成树后最大化延长所有非树边，然后对叶节点特殊讨论即可。 | ||
| + | |||
| + | Dirty: 太弱智了。边数开少了 t 了两次，距离 1 未特判 wa 了两次。 | ||
| ===== M ===== | ===== M ===== | ||
| + | red: | ||
| + | |||
| + | 开局看到感觉可做，发现是解不定方程后发现忘了怎么解，于是交给 yuki 了。 | ||
| + | |||
| yuki: | yuki: | ||
| 行 30: | 行 63: | ||
| Dirty： 考虑了最后一杯水可以不倒掉的情况，但只考虑了一半（我是笨蛋） | Dirty： 考虑了最后一杯水可以不倒掉的情况，但只考虑了一半（我是笨蛋） | ||
| + | |||
| + | ====== 场上没过的题 ====== | ||
| + | |||
| + | ===== L ===== | ||
| + | red: | ||
| + | |||
| + | 发现置换 3k 次是个环，剩下就只需要解同余方程组。因为模数不一定互质，所以不能直接用中国剩余定理。想到可以对模数分解后再用，但 toby 已经硬解出来了，然后就基本正确了。 | ||
| + | |||
| + | 场上没过的原因似乎是 exgcd 过程爆 ll 了，改成 int128 就对了，太气人了。 | ||
2023-2024/teams/cute_red_meow/nowcoder1.1690080750.txt.gz · 最后更改: 2023/07/23 10:52 由 toby-shi
