MiQiu

CF2195G - Idiot First Search and Queries 1. 题面梗概 中译中：背景同 E 题，CF2195E Idiot First Search。有 qqq 次询问，每次询问给定起点 vvv 和步数 kkk，求 Bob 移动 kkk 步后所处的节点。 2. 逻辑推导 简单回顾上一题的思路：dp1[u]dp1[u]dp1[u] 为遍历 uuu 的子树并移动到父节点 pp

CF2195E - Idiot First Search 1. 题面梗概 中译中：Bob 在一棵二叉树上漫游。 规则：如果是叶子就回父节点；如果是非叶子，按 “无标记 →\to→ 走左子树、标记 L →\to→ 走右子树、标记 R →\to→ 回父节点” 的顺序循环。 求从每个节点 kkk 出发到达根节点 000 所需的总步数。 2. 逻辑推导 虽然规则看起来很绕，但其物理意义非常明确：Bob 必

CF2195F - Parabola Independence 1. 题面梗概 中译中：给定 nnn 个二次函数。如果两个函数在所有实数域上都不相交，则称其独立。求包含函数 fif_ifi​ 的最大独立集合的大小。 2. 逻辑推导 如果函数 fff 在 ggg 上方，且 ggg 在 hhh 上方，则 fff 一定也在 hhh 上方，那么这题就转化为了一个偏序问题。 如果我们把 f→gf \to g

CF2195D - Absolute Cinema 1. 题面梗概 中译中：给定 nnn 个位置的函数值，其中 aia_iai​ 是隐藏的整数序列。已知所有的 f(1…n)f(1 \dots n)f(1…n)，求原序列 aaa。 f(x)=∑i=1nai∣i−x∣f(x) = \sum_{i=1}^n a_i |i - x| f(x)=i=1∑n​ai​∣i−x∣ 2≤n≤3⋅1052 \leq

A. Sieve of Erato67henes 1. 题意梗概 给定一个数列 aaa，问能否选出任意数量的元素，使它们的乘积为 676767。 n≤5n \leq 5n≤5 1≤ai≤671 \leq a_{i} \leq 671≤ai​≤67 2. 逻辑推导 鉴于 n≤5n \leq 5n≤5，这个数量级可以直接用搜索搜，秒了。 等等，Div3T1 就搜索不太对吧，注意到 676767 是

E - Many LCMs 1. 题面梗概 中译中：给一个序列 AAA，对于每一个位置 kkk，求出除去 AkA_kAk​ 之外剩下所有元素的最小公倍数（LCM）对 998244353998244353998244353 取模的结果。 2. 逻辑推导 直接暴力求 N−1N-1N−1 个数的 LCM 是 O(N2log⁡A)O(N^2 \log A)O(N2logA)，显然会炸。我们需要对 LCM

C - Sugoroku Destination 1. 题意梗概 有 NNN 个单元格，每个格子写着一个数字 AiA_iAi​。棋子从位置 sss 出发，每次移动到当前格子上写的数字对应的格子。求 1010010^{100}10100 次移动后棋子的位置。 1≤N≤5×1051 \le N \le 5\times10^51≤N≤5×105 i≤Ai≤N (1≤i≤N)i \le A_i \le

D - Reconstruct Chocolate 1. 题意梗概 给定 NNN 个矩形巧克力碎片的尺寸 (hi,wi)(h_i, w_i)(hi​,wi​)，这些碎片是通过对一个 H×WH \times WH×W 的大矩形进行 N−1N-1N−1 次操作得到的；操作为切下一块放在桌上，手里留一块。求出每个碎片的左上角坐标 (xi,yi)(x_i, y_i)(xi​,yi​)。 Constrain

CF2196C1 - Interactive Graph (Simple Version) 1. 题面梗概 中译中：交互题，给定有一个 DAG，你可以询问 所有路径按字典序排序后，第 kkk 条路径是什么。 目标是在有限次数内通过询问把所有的边都还原出来。 限制条件 32⋅(n+m)32 \cdot (n + m)32⋅(n+m) 次询问，n≤15n \leq 15n≤15。 2. 逻辑推导

CF2196C2 - Interactive Graph (Hard Version) 1. 题面梗概 中译中：交互题，给定有一个 DAG，你可以询问 所有路径按字典序排序后，第 kkk 条路径是什么。 目标是在有限次数内通过询问把所有的边都还原出来。 限制条件 n+mn + mn+m 次询问，n≤30n \leq 30n≤30。 2. 逻辑推导 限制条件不允许我们采用二分了，它要求我们的每一