做题记录

10.9#

Luogu P12195 [NOISG 2025 Prelim] Itinerary#

关键在于发现按 $s$ 的次序依次走是最优的，并且能够想到通过维护路径经过次数来判断合不合法还有不同的起点只有 $u \to s _ 1$ 这一段的差异。想到这些就能自然而然的想到树剖了。

还是思维的锅啊，一直往子序列靠没往路径经过次数。

AtCoder ABC250E Prefix Equality#

哈希不要用和哈希这种容易被卡的，用类 $Base$ 进制数或者异或哈希。

还有就是比较长的代码或者纯模拟，注意细节与理清思路，不要没想好就开写导致调的时间大于重构时间。

10.10#

LibreOJ 2833 「JOISC 2018 Day 1」帐篷#

思维灵活一点，限制放宽，不需要确定每一行的存在情况。

我们发现同一行与同一列不能同时放两个以上的帐篷，同时不能在同行与同列交点处有帐篷，我们就可以考虑对这个状态进行刻画。

记 $dp _ {i,j}$ 表示考虑了 $i$ 行 $j$ 列的方案数，则对于第 $i$ 行，我们分为以下四种情况考虑：

• 一个都不放：$dp _ {i,j} = dp _ {i,j}$。
• 放且不同行也不同列：则有 $4j$ 种选择（四种状态和 $j$ 列可选），有一行与一列正在决定，从 $dp _ {i - 1,j - 1}$ 转移来。
• 和之前一个放同列不同行： 之前的帐篷可选 $i - 1$ 行，自己可以选 $j$ 列，有两行一列正在决定，从 $dp _ {i - 2,j - 1}$ 转移来。
• 和之前一个放同行不同列： 在 $j$ 个空位中选两个，即 $C _ {j} ^ 2 = \frac{j(j - 1)}{2}$，有两列一行正在决定，从 $dp _ {i - 1,j - 2}$ 转移来。

所以，总的 DP 方程就是 $dp _ {i,j} = dp _ {i - 1,j} + 4j \cdot dp _ {i - 1,j - 1} + (i - 1)j \cdot dp _ {i - 2,j - 1} + \frac{j(j - 1)}{2} \cdot dp _ {i - 1,j - 2}$。

初始状态是 $dp _ {0,j} = dp _ {i,0} = 1$。

AtCoder ABC251D At Most 3 (Contestant ver.)#

很有意思的一道构造题。

发现 $W \in [1,10 ^ 6]$ 而砝码只有 $300$ 个，所以我们需要一个高度压缩的方式表示出所有正整数。

我们发现，十进制下任意 $\lt 10 ^ 6$ 的正整数都可以被写成 $\overline{abcdef}$ 的形式。

考虑用百进制来表示出来这个数，发现只需要表示出 $\{x \mid x = 100 ^ 2 \times y,y \in [1,99] \cap \Z\} \cap \{x \mid x = 100 \times y,y \in [1,99] \cap \Z\} \cap \{x \mid x = 100 ^ 2 \times y,y \in [1,99] \cap \Z\}$ 就可以出所有的 $x \in [1,10 ^ 6) \cap \Z$。

上述一共有 $99 \times 3 = 297$ 个砝码，再加上 $10 ^ 6$ 本身只需要 $298$ 个砝码，可以通过。

心得：关于数的构造题不一定要从纯数论角度，也可以通过数的构成来构造。

10.11#

A 询问#

发现这个 $2a - i$ 和 $2b - i$ 的增长率显然大于 $a + i$ 和 $b + i$ 的增长率，所以大胆猜测经过足够多的次数后选取的全是 $2a - i$ 与 $2b - i$。

所以可以暴力预处理前 $30$ 次操作，因为 $a,b \in [0,10 ^ 9 + 7)$ 所以再大就爆 long long 了，然后后面用矩阵快速幂转移。

B k-绍兴序列#

正问题不好做，我们考虑取约束条件的否命题，即 $\neg (\exist i \lt j,a _ i \lt k a _ j) = \forall i \lt j,a _ i \ge k a _ j$，则答案就是 $(m + 1) ^ n - Ans$。接下来分情况讨论：

• $k = 1$：等价于问有多少个值域为 $[0,m]$，长度为 $n$ 的单调不升序列。我们考虑插板法，则原问题等价于有 $n$ 个 $1$，放入 $m$ 块隔板的方案数，就等价于有 $n + m$ 个空位，放入 $n$ 个 $1$ 与 $m$ 个隔板的方案数，等于 $C _ {n + m} ^ n$。
• $k \ge 2$：我们发现有值的位置很少，所以我们就可以把值放进状态里做 DP，设 $dp _ {i,x}$ 表示第 $i$ 个位置是 $x$ 的方案数，则转移为 $dp _ {i,x} = \sum \limits _ {y = kx} ^ {n} dp _ {i - 1,y}$，初始状态为 $dp _ {1,[0,m]} = 1$。发现 $dp$ 中很多位置都是 $0$，于是我们可以维护一个上界等于 $\lfloor \frac{m}{k ^ {i - 1}} \rfloor$，然后用前缀和优化。答案就是 $\sum \limits _ {i = 0} ^ {\lfloor \frac{m}{k ^ {n - 1}} \rfloor} dp _ {n,i}$。

C 二次根式#

显然 $G = \frac{N!}{F}$，所以我们只考虑求 $F$。

考虑对每个平方因子求有多少个数有这个因子，我们枚举质数，然后计算含有这个质数的所有倍数的平方的数的个数之和，所以 $F = \prod \limits _ {p \le \sqrt{N},p \in \text{Prime}} p ^ {\sum \limits _ {k = 1} \lfloor \frac{N}{p ^ {2k}} \rfloor}$。

线性筛预处理出 $[1,\sqrt{10 ^ 9 + 7}]$ 内的所有质数，这部分的复杂度是 $\Omicron(\frac{\sqrt{N}}{ \ln N} \times \log N) = \Omicron(\sqrt{n})$。

现在问题是如何快速求出 $N !$，快速阶乘我写不来，巧了，出题人也写不来。因为模数固定，所以考虑分块打表，设 $B = 3 \times 10 ^ 5$，用打表程序算出 $B!,(2B)!\dots$，然后主程序查表，多出来的部分暴力计算，时间复杂度是 $\Omicron(B)$，打完程序是 $33.8\text{kB}$，能过。

10.12#

打 CF，汇总链接。

10.13#

AtCoder ABC250G Stonks#

第一次见这种题。

我们先考虑一个贪心，如果 $i \lt j$ 且 $a _ i \lt a _ j$，则在第 $i$ 天买入，在第 $j$ 天卖出。

这玩意显然不对，因为后面可能会有更高的价格，于是我们考虑带上反悔操作，如果 $a _ i \lt a _ k$ 则在第 $i$ 天买入在第 $k$ 天卖出，后面如果有 $a _ k \lt a _ j$ 我们可以视为则在第 $k$ 天买入在第 $j$ 天卖出，总的来看是在第 $i$ 天买入在第 $j$ 天卖出。

实现上，我们维护一个小根堆，对于 $a _ i$，我们看堆顶 $a _ j$ 是否小于 $a _ i$，是的话，就将答案加上 $a _ i - a _ j$，并且删除 $a _ j$ 加入 $a _ i$。注意，后面不管成没成功加入都再将 $a _ i$ 加入一遍，因为一个是代表反悔操作，一个是代表直接购入。