キサラギの世界

概况#

上周末参加了 2026 ICPC Asia 的第一次网络赛，最终做了 5 题出来，许久不碰算法题，水平退步太明显，因此打算复盘一下这次比赛。
根据外部榜单，题目的通过情况如下：
A：$\textcolor{green}{1019/8342}$
B：$\textcolor{red}{0/104}$
C：$\textcolor{green}{1587/5185}$
D：$\textcolor{orange}{704/4575}$
E：$\textcolor{red}{0/140}$
F：$\textcolor{green}{2482/3226}$
G：$\textcolor{orange}{135/1461}$
H：$\textcolor{red}{57/221}$
I：$\textcolor{red}{1/43}$
J：$\textcolor{orange}{120/737}$
K：$\textcolor{red}{15/106}$
L：$\textcolor{green}{1039/2121}$
M：$\textcolor{green}{2419/3163}$
N：$\textcolor{orange}{153/1348}$

以上标绿色的 5 道题目是我们做出来的，标橙色的是相对可做但没做出来的，标红色的是相对不可做的，基本都是省选以上难度的题目，对我们来说已经足够难了 (#｀-_ゝ-)。
我打算就复盘一下可做的 9 道题目，记录一下这些题目的解法，拓宽自己的思路，根据通过人数，按简单到困难的顺序记录。

N 题、G 题、J 题附 ChatGPT 给出的参考代码。

Problem F#

签到题，直接模拟。

Problem M#

签到题，直接用 map。

Problem C#

给定某些区间中元素从小到大的顺序，构造满足条件且逆序对最少的排列，或报告无解。

可转化为图论问题，将每个位置视作一个点，连有向边来表示两个元素的大小关系，完成建图过程后，再看是否存在拓扑排序。 由于题目要求排列逆序对最少，因此可以维护一个小根堆，每次从中选择编号最小的入度为 0 的点。
关于时间复杂度，设所有区间长度和为 $S$，建边+堆操作，总复杂度 $O(S+n\log n)$。

Problem L#

定义 $f_{i, j}$ 为前 $i$ 个字符串恰好选 $j$ 个的公共前缀长度最大值。要对每一个 $i$ 求 $A_i=\sum_{j=1}^{i}\bigl(f(i,j)\oplus j\bigr)$

建一个 Trie 字典树，Trie 的一个节点对应一个前缀，节点的深度代表对应前缀的长度，并记录每个前缀有多少个字符串共用，Trie 的定义如下：

1
struct trienode {
2
  int cnt;
3
  int p[26];
4
  trienode(int num): cnt(num), p({0}) {}
5
};

当插入字符串时，每次走到一个节点，先更新 multi = ++nodes[cur].cnt，再判断 $f(i,multi)$ 是否会改变，当发生改变时动态更新 $A_i$。
时间复杂度为 $O(L)$，$L$ 代表所有字符串的总长度。

Problem A#

一个初始为空的栈，按顺序给定操作：将 x 入栈，询问 x 是否在栈中且回答为在，询问 x 是否在栈中且回答为不在。向操作序列中插入若干个出栈操作，使得：任何时刻栈中没有两个相同的元素，且所有回答都符合实际情况。

首先对输入进行离散化，然后用贪心思路，先扫一遍每个元素在何时完成最后一次必要查询，接下来按顺序执行入栈和查询操作，若栈顶元素完成最后一次必要查询立刻弹出。
现场想到贪心的思路并没用多久，不过在离散化的实现上耗费了点时间，手写了个 hash 表，ChatGPT 说可以直接用 unordered_map 实现，其实内部也是 hash 表：

1
unordered_map<int,int> mp;
2
int cnt = 0;
3
for(int i = 1; i <= n; i++) {
4
    if(!mp.count(a[i]))
5
        mp[a[i]] = ++cnt;
6
    num[i] = mp[a[i]];
7
}

时间复杂度是线性的。

Problem D#

01 序列 $s$，$d_i$ 定义为 $s_1$、$s_2$、…、$s_i$ 中与 $s_i$ 不同的元素个数。乱序给定 $d$，求满足条件的序列 $s$ 的个数 $\mod998244353$，保证有解。

虽然解法看起来很简单，但是如果你的注意力没有放在重点上，就很难想到。
在赛场的时候有点纠结题面中 multiset 的意思，总之应该是知道 $d_i$ 有哪些以及出现次数，不知道它原来的顺序。

先假设目前已经构造的字符中有 $a$ 个 0 和 $b$ 个 1，记录为 $(a,b)$，假如下一位放 0 的话 $d_i=b$，下一位放 1 的话 $d_i=a$。
由于对称性，将一个序列取反后 $d_i$ 不会发生改变，因此不妨假设 $a\le b$。
我们再关注构造下一个字符的时候，需要消耗 multiset 里的什么数字，当 $a=b$ 的时候，必然消耗 $d_i=a$，且由于下一位放 0 或 1 都合法，因此将方案数乘 2。
当 $a<b$ 时，若 multiset 中还有 $a$ 没有被消耗，若选择让 $d_i=b$ 的话，接下来的状态为 $(a+1,b)$，$a$ 再也不可能被消耗，因此需要优先消耗 $a$，若 $a$ 消耗完再消耗 $b$，这也是我们现场没有想到的地方。
实现很简单，时间复杂度为线性。

Problem N#

题面链接

能看出来是 DP，但是需要思考如何同时处理两个条件。
定义 $Y_i=\sum_{k=1}^i(a_k-b_k)$，$B_i=\sum_{k=1}^i(a_k-c_k)$，$dp_i=\text{前 }i\text{ 个位置最多能获得多少得分}$，列出状态转移方程：

这是一个二维偏序查询，但事实上我们只需查询两个边界，即 $Y_j=Y_i,\ B_j\le B_i$ 和 $B_j=B_i,\ Y_j\le Y_i$ 的情况，非边界的情况肯定不是最优的。
最终 DP 有四种转移，即不选第 $i$ 个、整个 $[1,i]$ 都是 R 主导、以及上述的两个边界，大体可以写成以下形式：

1
dp[i] = dp[i - 1];
2

3
if(Y[i] >= 0 && B[i] >= 0)
4
    dp[i] = i;
5

6
best1 = 查询(Y相等，B<=当前B);
7
best2 = 查询(B相等，Y<=当前Y);
8

9
dp[i] = max(dp[i], i + best1);
10
dp[i] = max(dp[i], i + best2);

关于查询，可以给每个 $Y_i$ 值分别对 $B_i$ 建树状数组，再给每个 $B_i$ 值分别对 $Y_i$ 建树状数组，这样一次查询只需要 $O(\log n)$，总复杂度 $O(n \log n)$。

Problem G#

题面链接

先用正反向 BFS 筛出所有最短路上的点和边，若点 $v$ 在最短路上则 $d_1[v]+d_n[v]=D=d_1[n]$，边 $u\to v$ 在最短路上则 $d_1[u]+1=d_1[v]$ 且 $u,v$ 都在最短路上。
接下来得到一个 $D$ 层的分层 DAG，若 $C$ 较小的话可以直接点权和 DP，但是此处 $C \le 10^{12}$，空间显然不够。

但这里 $n\le 90$，甚至可以考虑将所有路径都枚举出来，由于得到的 DAG 是分层的，因此将点分为前半部分和后半部分。
直接暴搜 1 到前一半点的所有最短路，再搜出后一半点到 n 的所有最短路，可以估算最短路的数量为 $\frac{n}{2}$ 分成若干个数使得乘积最大，即 $P\le3^{\frac{n}{6}}= 4.7\times 10^6$。
最后直接对每一个前缀路径，二分法匹配后缀，时间复杂度 $O(n3^{\frac{n}{6}})$。

Problem J#

题面链接

将 N 视作 0，H 视作 1，考虑 op=3 的操作意义，它会将从 i 开始往左连续的 1 变成 0，并将第一个遇到的 0 变成 1，这等价于给长度为 i 的前缀二进制表示 +1。
而重复 k 次就相当于是 +k，剩下三种操作的意义也类似，因此只考虑 op=3 的操作，可拆分为：将从 i 开始的 $\log k$ 位单点赋值、将连续的一段 1 推平为 0。
这些操作可以通过线段树来维护，最终复杂度为 $O(m(\log k+\log n))$。

总结#

这次卡在 D 题还是很可惜的，理想情况下应该能更快更轻松地做出来前面 5 题，然后集中注意力想出 D 题，再尝试做出 N 题、G 题、J 题中的一两道，主要是熟练度不够。
总之还有机会，希望周日的第二次网络赛能好好发挥吧，加油(*^▽^*)。