2023.11~2024.1 做题记录

djwj233 · 2024-02-06 14:33:09 · 个人记录

越来越摆了。

* LOJ 3103

对于两字符串 T_1,T_2，设 T_1 优于 T_2 当且仅当：

首先容易观察到，设 F(i) 为所有 j 满足 S[j,i] 不被任意 S[k,i] 优于，则 F(i)\sube F(i-1) \cap \{i\}。

把 F(i) 中元素看成字符串，设它们从短到长依次为 T_{1\cdots k}，有 T_j 是 T_{j+1} 的 Border。

可得，F(i) 可以被划分为 \mathcal O(\log i) 个等差数列。

假设我们可以维护出这些等差数列，可以证明，对于每个等差数列，只有其中的最小项和最大项可能成为答案。

借助后缀排序，我们可以在 \mathcal O(1) 时间内比较两个答案，这样问题只剩下如何维护 F(i)。

（事实上这里也可以不使用后缀排序而使用 Z 函数）

事实上，对于同一个等差数列，我们只需要维护其最小项和最大项即可，所以整题可以在 \mathcal O(n\log n) 内完成，代码好写。

CTT 2021 D4T1

看完题感觉极其神秘，先分析一下简单情况。

对于一个数 X，若 X<b^k 易证显然合法。下面记 x\sim y 表示 [p\mid x]=[p\mid y]，下文将混用等号和同余号。

若 b^k\le X<b^{2k}，设 X=xb^k+y(0\le y<b^k)，条件等价于 (xb^k+y)\sim (yb-x)。

由于 b>p，所以我们可以忽略 x\ge 1 的限制，认为 x,y\in [0,p)。

当且仅当 yb\equiv x 时有 xb^k+y\equiv 0，随意取一个 y\perp p，可以得到 b^{k+1}\equiv -1\pmod{p}，由此一定有 p\perp b。

只要 b^{k+1}\equiv -1\pmod{p} 满足，可以证明 yb\not\equiv x 时有 xb^k+y\not\equiv 0.

对 b^{2k}\le X<b^{3k}，设 X=xb^{2k}+yb^k+z，有 X\sim (zb^2-yb+x)。

推理一下依然可得条件是 b^{k+1}\equiv -1\pmod{p}。我们对更大的数证明这个结论。

具体地，设 X=\sum_{i=0}^d x_ib^{ik}，有 X\sim \sum_{i=0}^d (-1)^{i}x_i b^{d-i} 成立。由于 b\perp p，我们可以把 b^{d-i} 改为 b^{-i}。

右边为 0 当且仅当：

x_0=\sum_{i=1}^d (-1)^{i-1}x_i b^{-i}

若此式满足，则左边等于：

\sum_{i=1}^d (-1)^{i-1}x_i b^{-i}+\sum_{i=1}^d x_ib^{ik}=\sum_{i=1}^d x_i(b^{ik}-(-b)^{-i})

我们考虑由于 b^{k+1}\equiv -1\pmod{p}，那么 b^{ik}-(-b)^{-i}=b^{ik}-b^{ik}=0。

若上式不满足，由 p\nmid b^{ik}，则左边也不为 0，证毕。

由上我们只需要找到 b\bmod p 对 p 的半阶即可。但是半阶怎么找呢？

事实上，若存在半阶，设半阶为 d，阶为 D，则 d< D\le 2d，即 d\in [\left\lceil\frac{D}{2}\right\rceil,D)。

而若 \frac{D}{2}<d<D，那么由于 2d 一定是阶的某个倍数，又矛盾了。所以如果半阶存在，其一定是 \frac{D}{2}。

综上，我们只需求其阶然后除二用快速幂验证即可，复杂度 \mathcal O(\sqrt{p}+T\log^2 p)。

P5633 最小度限制生成树

胡策场上我用了和我的 JOISC 2023 D4T2 类似的做法，现在学学另一种做法。

这种做法主要利用：考虑一条边 e 的贡献，取 Kruskal 重构树中边权 \le w(e) 的连通块 C。

若 e 被删去，则新生成的两连通块最小值应都属于 C，否则可以调整。

这样我们可以对每条边求出其被删除时最小的增加值。直接把它们排序取前 k 小，证明可以取到即可。

这种做法较于我之前的做法需要更强的结论：

我之前的做法是直接按照顺序维护合并，因此需要维护边权和点权的差；
此做法在证明如下结论后强制按照边权顺序模拟合并，更好写：
- 结论：由于每次我们都会取二者路径上的 \max，最终此边删去时的贡献不可能高于 C 中的情况。

线性筛 i^i 的做法

做法是：

对所有质数位置使用快速幂求值，这部分线性。
对于非质数位置，考虑设其最小质因子为 p，设此数为 pq，那么有 (pq)^{pq}=(p^p)^{q}(q^q)^p.

由于 p\le \sqrt{n}，因此设 C=p^p，可以直接使用类似 BSGS 的技巧求 C^{1\cdots \sqrt{n}},(C^{\sqrt{n}})^{1\cdots \sqrt{n}}，前半部分是平凡的.

对于后者，由于我们是在枚举 q 时从小到大枚举 p，因此设 C=q^q，需要求的数形如：
C^2,C^3,C^5,C^7,\cdots
是质数序列。考虑预处理出 prime gap 以内的 C^i，就可以从前一个数转移到后一个。

在合理数据范围内我们认为 prime gap 的上界约为 \Theta(\log^2 n)，那么使用 BSGS 依然可以只预处理 C^{1\cdots \log (n/q)}。

累加起来是经典的 \sum_{q=1}^n \ln(n/q)=\mathcal O(n).

事实上也可以筛出 i^{\varphi(i)} 啥的？

CTT 2021 D1T1

感觉这个问题非常朴素，不过要写代码，差评！

部分分的思考过程当时没写，现在也懒得写了，记一下做法。

我们设 f(n,k) 分别为 (n,k) 的答案，可以使用 DP 进行转移，枚举块长为 a_{1\cdots d}，那么有：

f(n,k)=f(d-1,k-2)+\sum f(a_i,k)

不过事实上可能不能直接 f(a_i,k)，由于前缀和后缀都要处理，因此可能是 f(a_i-2,k)+2a_i 这种形式的东西。

据说还要卡卡才能过，懒得写代码了。

* P3642 [APIO2016] 烟火表演

一个显然的想法是 DP：我们设 dp_{x,i} 为让 x 子树内所有叶子的深度都变为 i 的最小代价。

我们观察 dp_{x,*} 的形态，不难发现 dp_{x,*} 一定是凸的。证明可以考虑归纳，利用凸函数的和依然是凸函数证明。

如果导火索可以被减到负数，那么对于任意子树可以只维护一个区间 [L,R] 和其 DP 值，这样问题就简单了。

但是很可惜导火索不能被减到负数，这样我们对于一个凸函数 F_y(i)，把它合并到 F_x 时其形态为：（C 是边权）

F^\prime(i)= \begin{cases} F(i) + C & i < L \\ F(L) + L + C - i & L\le i<L+C \\ F(R) & L+C\le i\le R+C\\ F(R) + i - R-C & R+C<i \end{cases}

我们发现后三种情况都是较为平凡的，第一种情况由于只加了一个常数所以也是可以维护的。

不难想到我们可以使用双堆维护凸函数的技巧维护之。对于此题，我们可以使用可并堆维护。

注意我们只能维护出所有的函数断点和无穷远处的斜率 K，然后利用 F_1(0)=\sum C_i 求答案，维护 (L,R,V) 是极其困难的。

启示：维护凸函数时不一定需要及时维护 (L,R,V) 的平台信息。

** THUPC 2024 初赛 A

* THUPC 2024 初赛 B

应该算是经典 slope trick 题目了，但是我场上没看出来，太菜了。

有一个显然的 \mathcal O(n^2) DP 是，设 dp(i,j) 为 i 子树中选择了 j 个黑点的最小权值。那么转移时合并子树就是：

dp_{x,i+j}\gets \min(dp_{x,i+j},dp_{x,i}+dp_{y,j})

转移完了以后加上这个点的贡献是 dp_{x,i}\gets \min(dp_{x,i},dp_{x,i-1})，加上这条边的贡献就是：

dp_{x,i}\gets dp_{x,i}+|k-2i|

事实上，我们可以归纳地证明 dp_{x} 是凸的，这样上面一个方程等价于闵可夫斯基和，就是合并两个差分数组。

之后的部分分别相当于向差分数组中扔进一个 0 和把一个前缀的差分数组减去 2、把一个后缀的差分数组减去 2。

这可以直接使用平衡树维护，由于 Splay 合并总复杂度是 \mathcal O(n\log n) 的，因此可以直接通过。

事实上还有一种实现方法只需要使用可并堆：

对每个子树维护两个对顶的可并堆 L,R，其中 L 维护前 \min(siz_x,\frac{k}{2}) 个元素。
可以发现两个子树的 L,R 是可以合并的，合并完成后暴力弹出 L 中的元素直到元素个数正确。

由于每个元素只会有一次从 L 堆中弹出，所以总复杂度是 \mathcal O(n\log n)。
这样两部分分别转化为打加法标记，可以简单处理。
此做法唯一的问题是需要支持在堆上打加法标记，所以必须手写。

启示：遇到需要优化的 DP 先看看有没有凸性，出题人不一定有你想象得那么聪明。

THUPC 2024 初赛 C

一个相当漂亮的题目，可惜场上我是暴力推式子的。

正解就是考虑给这个模型找一个组合意义：

对于有一排无限长的灯，每个灯有 p 的概率亮起（否则熄灭）。

设 pos_i 为第 i 个亮起的灯的位置，那么 x_i 就是 pos_{i+1}-pos_{i} 的值。

可以发现 x_i 的概率分布与原问题相等。

这样，原问题等价于 [l,r] 中期望有多少个灯亮起。这样答案就是 (r-l+1)p 了。

THUPC 2024 初赛 D

shaber 题。

首先考虑有一个显然的 2D-1D 区间 DP，使用树状数组优化之，可以直接做到 \mathcal O(n^2\log n)，卡一卡空间常数就过了：https://loj.ac/s/1956918

要做到 \mathcal O(n^2) 也是简单的，只需注意到对于 f(l,r) 一定不劣于 f(l',r')(l'\le l\le r\le r')（也即有单调性）。那么我们考虑对于每个状态找到最长回文前缀判一判即可，后缀是类似的。

"找到最长回文前缀"在 \mathcal O(n^2) 语境下是平凡的，可以参考 https://qoj.ac/submission/286648。

THUPC 2024 初赛 E

考虑第二问怎么做。

假如所有 a_i\ge 1，那么显然答案就是 \sum (a_i+c_i)。现在问题是如何吃到那些 a_i=0 的位置的贡献。

设存在某个时间点 a_i>0 集合为 S，我们需要做的就是每次扩展 S。

对于 S 中的位置，显然不可能从 u 跳到 v 再跳到 w 以跳出 S（其中 u,v\in S, w\notin S），因此每个位置的“出边”条数是 \min(b_i,a_i+c_i)。若 b_i>0 则全部选了不劣，否则贪心地从大往小选即可。

有了这个启发让我们再看看第一问，设当前枚举到 i。

不难发现对 j\ne i 且 b_j=0，j 没有任何用处，所以我们直接忽略。

可以证明，对于所有 a_j=0,b_j>0 的位置，送一个数进去再拿出来一定不劣。

所以依然是维护集合 S，维护当前可以被送到 i 的数量和可以被“更改”（中途切到一个 a_j=0,b_j>0 再到 i）的数量，贪心即可做到 \mathcal O(n^2)。简单优化一下就是 \mathcal O(n)。

非常容易写出罚时，shaber 小 E。

THUPC 2024 初赛 K

考虑假如只有一个点是 o 那么先手必败，有恰好两个点是 oo 那么先手必胜。

若连通块大小为 3 就有些复杂了，不过我们注意到无论先手如何操作，后手一定可以在 6 次内构造出合法的图形，只需要保证先手不在 3 次内构造出答案即可，这是容易的。

只剩 4 了，经过旋转 / 翻转对称后本质不同的图形有：

oooo
----------------
o..
ooo
----------------
oo
oo
----------------
o.
oo
.o
----------------
o.
oo
o.

这几种。由于先手不可能在 3 次内构造出它们，因此只需要考虑后手在 6 次内能否构造出它们。

换言之，先手需要尽可能让后手 6 步以内构造不出来这个图形。

I 可以，J/L 不行，O 可以，Z/S 都不行。

THUPC 2024 初赛 G

THUPC 2024 初赛 H

显然数字的长度不超过 \mathcal O(\log n)，记为 m。

考虑 \mathcal O(n\log n) 怎么做。注意到长度是单调的，所以我们对于每种长度独立开来做。

对于每个数 i，我们用 set 维护其每次出现的位置；出现移除操作就在 set 中维护即可。

复杂度为什么是对的呢？我们知道，在每种长度的重建过程中数组都是有序的，所以总复杂度是单次线性，总共 \mathcal O(n)。

而若当前删除了一个长为 L 的串，加、删操作都只会出现 \mathcal O(L) 次，单次代价为 \mathcal O(\log n)，容易证明其均摊复杂度是 \mathcal O(n\log n) 的。

THUPC 2024 初赛 I

我们考虑假如给定的串中有 m 个 1，那么复杂度是 \mathcal O(m\log m)。

考虑优化一下底层，我们确定一个 B，预处理出所有 2^B 种集合，然后总复杂度就变成了 \mathcal O(n\log(n/B))。

预处理出所有集合的过程可以直接暴力递推地对所有 i\le B 都处理出所有 2^i 种子集，复杂度是 \mathcal O(B\times 2^B)。

计算一下可知，这种线段树式的二分思路应该已经走到头了。我们考虑优化后半部分。

对于所有长为 B 的块其应当只有最多 2^B 种可能，我们对于每种可能看 \frac{n}{B} 个部分中有哪些部分是这个段，记录之。

这样就可以用 B 次操作得到所有这些段的贡献了，这部分的总复杂度是 \mathcal O(n\log B+\frac{n}{B}\log n)。

然后把这 2^B 个部分合并起来，总复杂度是 \mathcal O(nB)，取 B=\sqrt{\log n} 可以做到 \mathcal O(n\sqrt{\log n}) 的复杂度，非常科幻。

启示：底层也可以整体操作。

THUPC 2024 初赛 J

事实上，使用区间 \text{mex} 的矩形结构可以比较容易地完成此题。我们复习一下这个结构：

对于 a_{1\cdots n}，设 M_{l,r}=\operatorname{mex}_{l\le i\le r}，那么 M 可以被表达为 O(n) 个不交矩形的并，其中每个矩形中的数都相等。

证明的过程就是求出这 O(n) 个矩形的过程。固定一个 r，那么 M_{l,r} 的值一定是随 l 单调递减的。

类似扫描线地，我们从 M_{*,r-1} 继承而来的时候有若干个未封口的矩形，我们加上 M_{r,r} 处的 0，然后处理 a_r 带来的影响。

找到值为 a_r 的一段 [l,r]，然后（不断地）求出这一段的新 \text{mex} 值。根据颜色段均摊，这部分复杂度应该是对的。

上述所有东西可以使用 set 配合线段树上二分实现，复杂度 \mathcal O(n\log n)。

fo(r, 1, n) {
    int l = r; lst[a[r]] = r, fix(1, a[r], r);
    if(S.size() && prev(S.end())->v == 0) {
        v[++tot] = *prev(S.end()), v[tot].yr = r - 1;
        l = v[tot].xl, S.erase(prev(S.end()));
    }
    S.insert({l, r, r, 0, 0});
    auto it = S.lower_bound({0, 0, 0, 0, a[r]});
    if(it->v != a[r]) continue;
    if(it->yl < r) v[++tot] = *it, v[tot].yr = r - 1;
    int lb = it->xl, rb = it->xr; S.erase(it);
    while(lb <= rb) {
        int x = query(1, rb - 1), nxt = lst[x];
        if(nxt >= lb)
            S.insert({nxt + 1, rb, r, 0, x});
        else {
            it = S.lower_bound({0, 0, 0, 0, x});
            if(it != S.end() && it->v == x)
                v[++tot] = *it, v[tot].yr = r - 1, S.erase(it);
            S.insert({nxt + 1, rb, r, 0, x});
        }
        rb = nxt;
    }
}
for(auto z : S) v[++tot] = z, v[tot].yr = n;
// fix / query 分别是单点修改和查询最小的值 <= x 的位置

然后每个矩形的覆盖范围就恰好是一段区间，使用扫描线线段树维护即可。