ARTICLE · 1229193

CSP 2026 S组模拟赛题解:A-file

发布时间：2026-10-22 16:16:04 最近访问：2026-10-22 16:15:49

从 10 分暴力到 100 分满分：枚举排列、两种优化、性质 A、性质 B、排序不等式。

NOIP ：2025-A 2025-B 2025-D 2024-A

NOIP-J：2007 2006 2005 2004 2003 2002 2001 2000199919981997

NOIP-S：2004 2003 2002 2001 2000 199919981997

NOI：1998-day1 1998-day2 1997-day1 1997-day2

CSP-J ：2025 2024 2023 2022 2022-SD 2021 2020 2019

CSP-S ：2025 2024 2023 2022 2021 2020

备考：得分技巧环境准备CSP-J 题型分析 CSP-S 题型分析

算法：二分线段树状态最短路动态规划数学常见算法和数据结构 DFS序单调栈/队列倍增ST表 LCA倍增虚树

零、背景

最近在洛谷上做了 CSP 2026 复赛 S 组的模拟赛，一共四道题。

这篇文章分享第一道题「档案 file」的题解。

题目链接：https://www.luogu.com.cn/problem/P17722

题解代码：https://github.com/tiankonguse/leetcode-solutions/tree/master/other/luogu/contest/358588/A.file

一、题目

初始时有 n 个核心档案已经归档，编号用序列 a 表示。

另外还有 m 批待归档的档案，第 i 批的编号用序列 b_i 表示。

所有档案的编号互不相同，即 a, b_1, b_2, ..., b_m 中包含的所有元素两两不同。

初始时已归档序列 x = a，小 Z 需要执行 m 次归档操作，每次操作依次进行两步：

选择一批尚未归档的档案 b_i，将其中的所有元素加入序列 x。

将序列 x 中的元素从小到大排序。

本次操作的代价为排序后序列 x 中所有核心档案的下标之和，下标从 1 开始编号。

进行全部 m 次操作的总代价为每次操作的代价之和。

小 Z 可以任意决定这 m 批档案的处理顺序，需执行全部 m 次操作的最小总代价。

数据范围：

1 ≤ n, m, L ≤ 10^6
，其中 L = Σ l_i 为所有待归档档案的数量。
1 ≤ a_i ≤ 2×10^6
，1 ≤ b_{i,j} ≤ 2×10^6。
所有编号互不相同。
测试点 1~2：m ≤ 7，n, L ≤ 100。
测试点 3~5：m ≤ 11，n, L ≤ 1000。
测试点 6~8：m ≤ 100，n, L ≤ 10^4。
测试点 9~12：m ≤ 10^5，n, L ≤ 10^6。
测试点 13：性质 A，n = 1。
测试点 14：性质 B，每批 b_i 内部编号连续，且 a 的编号也连续。
测试点 15~20：m ≤ 10^6，n, L ≤ 10^6，无特殊性质。

二、题意分析

特征 1：任意时刻的序列是唯一的。

所有档案的编号互不相同，所以谁排在谁前面是定死的：把已归档的档案按编号从小到大排，就是当前序列。

顺序能改变的，只是某个时刻序列里已经有哪些档案。

特征 2：核心档案的下标怎么算。

一个核心档案排在第几位，等于它前面比它小的档案个数加 1。

比它小的核心档案数量是固定的；比它小的普通档案数量，会随着归档的批次越来越多。

特征 3：普通档案是怎么让代价变大的。

一个普通档案 x 一旦被归档，就会永久排在所有比它大的核心档案前面，让这些核心档案的下标都加 1。

每次操作的代价是所有核心档案下标之和，所以只要 x 已归档，每一轮代价都会比没有它时增加「比 x 大的核心档案个数」这么多。

这个增加的数额只由 x 与核心档案的大小关系决定，和 x 属于哪一批、什么时候被归档都无关。

三、10 分算法：暴力枚举顺序

如果 m 很小，最朴素的做法就是枚举所有处理顺序，按题意一步步模拟，取最小总代价。

测试点 1~2 只要求 m ≤ 7，最多 7! = 5040 种排列，随便跑。

标记法枚举排列（10 分）

用 vis 记录当前的处理顺序，flag 记录哪些批次已经被选过，递归枚举全部 m! 个排列。

对每个排列按题目模拟：把这一批的元素加到序列末尾，整体排序，再从头扫一遍，遇到核心档案就把下标累加进这一轮的代价。

判断某个编号是不是核心档案，用哈希表 unordered_map 最快。

vector<int> vis;   // 当前的处理顺序vector<int> flag;  // 哪些批次已经被选过unordered_map<ll, int> mp;  // 标记核心档案ll allCnt = 0, ans = 0;voidUpdateAns(){  // 计算当前排列的总代价  vector<ll> a = A;  // 初始序列  a.reserve(allCnt);  ll sum = 0;  for (int b : vis) {  // 按当前顺序处理一批    for (ll x : B[b]) a.push_back(x);    sort(a.begin(), a.end());    for (int i = 1; i <= (int)a.size(); i++) {      if (mp.count(a[i - 1])) sum += i;  // 核心档案的下标    }  }  ans = min(ans, sum);}voidDfs(constint visCnt){  if (visCnt == m) {  // 生成一个完整排列    UpdateAns();    return;  }  for (int i = 0; i < m; i++) {    if (!flag[i]) {      vis.push_back(i);      flag[i] = 1;      Dfs(visCnt + 1);      flag[i] = 0;      vis.pop_back();    }  }}

复杂度：m! 个排列，每个排列做 m 次操作，每次操作排序 O((n+L) log(n+L))

总复杂度 O(m! · m · (n+L) log(n+L))。

m = 7、n + L ≤ 200 时轻松通过测试点 1~2。

优化一，交换法生成排列（10 分）

标记法每一层都要从头扫一遍 flag 找没用过的批次，这一步是 O(m) 的常数开销。

优化：直接在 vis 数组上交换元素来生成排列，去掉 flag 数组。

做法是：第 k 层把 vis[0..k-1] 中的某个元素换到第 k-1 位，向下递归一层，回溯时再换回去。

voidDfs(constint leftNum){  // 交换法生成排列  if (leftNum == 0) {    UpdateAns();    return;  }  for (int i = 0; i < leftNum; i++) {    swap(vis[leftNum - 1], vis[i]);    Dfs(leftNum - 1);    swap(vis[leftNum - 1], vis[i]);  }}

生成的排列数量与解法一完全一致，复杂度公式不变，仍是 O(m! · m · (n+L) log(n+L))，但常数小了很多。

优化二，有序归并代替排序（10 分）

前面在 UpdateAns 里每加入一批序列就整体 sort 一次，单次 O(N log N)。

优化：保证「当前序列有序」且「新加入的这一批内部也有序」，就可以用一次线性归并替掉随机排序，复杂度从 O(N log N) 降到 O(N)。

具体做法是初始时把 A 排好序，每一批 B 读入后各自排好序，之后维护的序列 a 就始终有序。

归并时从后往前填：两个有序序列的末尾谁大，谁就落到整个序列的末尾空位，不会覆盖还没看过的数据。

vector<ll> a;  // 当前序列，始终保持有序voidUpdateAns(){  a.clear();  for (ll x : A) a.push_back(x);  ll sum = 0;  for (int b : vis) {    // 两个有序序列从后往前归并，谁大谁落到末尾空位    int an = a.size(), bn = B[b].size(), abn = an + bn;    a.resize(abn);    while (an > 0 && bn > 0) {      if (a[an - 1] > B[b][bn - 1]) {        a[abn - 1] = a[an - 1];        an--;      } else {        a[abn - 1] = B[b][bn - 1];        bn--;      }      abn--;    }    while (bn > 0) {  // 这一批剩余的元素更小      a[abn - 1] = B[b][bn - 1];      bn--;      abn--;    }    for (int i = 1; i <= (int)a.size(); i++) {      if (mp.count(a[i - 1])) sum += i;    }  }  ans = min(ans, sum);}

复杂度降到 O(m! · m · (n+L))。

为什么三个版本都只能拿 10 分

暴力做法的瓶颈在排列数量：m 每加 1，排列数就乘以 m+1，增长极快。

m = 7 时只有 5040 种，m = 8 时是 40320 种，都还跑得动。

但测试点 3~5 把 m 直接提到了 11，有 11! ≈ 4×10^7 个排列。

就算把单次统计优化到线性，总操作量接近 4×10^7 × 11 × 10^3，必然超时。

所以想继续拿分，必须放弃枚举排列，回到题意分析里「普通档案让代价增加的数额固定」这个特征上。

四、15 分：性质 A（n=1）

暴力解决不了 m 大的数据，先看题目给的第一个特殊性质 A：n = 1，只有一个核心档案 a_0。

只有比 a_0 小的普通档案会插到它前面，影响它的下标；

比 a_0 大的都排在它后面，完全不影响。

所以第 i 批只需要关心一件事：批内有多少个元素小于 a_0，记为 b_i。

处理顺序怎么排最优呢？

看相邻的两批 b1、b2：

b1 在前：第一次操作 a_0 的下标是 1 + b1，第二次是 1 + b1 + b2，总代价 2 + 2*b1 + b2。

b2 在前：同理总代价 2 + 2*b2 + b1。

两者相差 (2 + 2*b1 + b2) - (2 + 2*b2 + b1) = b1 - b2。

当 b1 ≤ b2 时，b1 在前更优。

不断做相邻交换，最优顺序就是把所有 b_i 从小到大排序。

实现：统计每个 b_i 需要 O(L)，排序 O(m log m)，最后模拟：核心档案的下标从 1 开始，每处理一批 v 个元素，下标就增加 v，本次代价就是新下标，累加到答案。

if (n == 1) {  // 性质 A  vector<ll> b(m, 0);  for (int i = 0; i < m; i++) {    for (ll x : B[i]) {      if (x < A[0]) b[i]++;  // 统计比核心档案小的个数    }  }  sort(b.begin(), b.end());  ans = 0;  ll index = 1;  // 核心档案当前的下标  for (ll v : b) {    index += v;    // v 个数字插到核心档案前面    ans += index;  // 本次操作的代价  }}

这个版本在暴力 10 分的基础上，额外通过性质 A 的测试点 13（5 分），共 15 分。

五、20 分：性质 B（编号连续）

性质 A 只覆盖 n = 1，测试点 14 又给了第二个特殊性质 B：核心档案 a 是连续整数，每一批 b_i 内部也是连续整数。

由于所有编号互不相同，两个连续整数区间不可能相交：每一批要么整体在 a 的左边，要么整体在 a 的右边。

在左边的批次：每个元素都小于所有核心档案，整批使所有核心档案都后移 l_i 位。

在右边的批次：对核心档案的下标没有任何影响。

所以这批「插到核心档案前面的个数」v_i 等于 l_i或 0。

实现时先判断数据是否满足性质 B。

读入时检查 a_i + 1 == a_{i+1} 与 b_{i,j} + 1 == b_{i,j+1}，任意一处不满足就不满足性质 B。

由于 a 连续，核心档案占据一段连续的下标区间 [L, R]，初始 L = 1, R = n。

按 v_i 从小到大处理，每插入 v 个元素，区间整体右移 v 位。

本次代价就是区间内所有下标的和 (L + R) · n / 2。

bool flagB = 1;  // 是否满足性质 Bfor (int i = 0; i < n; i++) {  // 读入核心档案  scanf("%lld", &A[i]);  if (flagB && i > 0 && A[i] != A[i - 1] + 1) flagB = 0;}// 读入每一批时同理检查 b_{i,j} 是否连续...if (flagB) {  // 性质 B  vector<ll> b(m, 0);  for (int i = 0; i < m; i++) {    if (B[i][0] < A[0]) b[i] = B[i].size();  // 整批在核心档案左边  }  sort(b.begin(), b.end());  ans = 0;  ll L = 1, R = n;  // 核心档案占据的连续下标区间 [L, R]  for (ll v : b) {    L += v;    R += v;    ans += (L + R) * n / 2;  // 等差数列求和，本次操作的代价  }}

这个版本在 15 分的基础上，额外通过性质 B 的测试点 14（5 分），共 20 分。

六、100 分：标准做法

性质 A、B 都只占一个测试点，而测试点 15~20 没有任何特殊性质，必须想一个通用做法。

把每一轮的代价分开看。

每个普通档案 x 会让每一轮操作的代价增加 c(x)，其中 c(x) 是核心档案中比 x 大的个数。

而且只要 x 已归档，之后每一轮代价都会加上它。

所以第 i 批档案被处理之后，对后面每一轮代价的贡献，就是把批内每个元素各自增加的数额加起来，记作 W_i：

这是一个固定不变的数，跟顺序无关。

它排在第 pos_i 个位置处理，就会从这一轮起被计入，共 m - pos_i + 1 轮。

先算与顺序无关的基础部分。

如果从头到尾没有归档任何普通档案，n 个核心档案的下标正好是 1 到 n，每轮代价就是 1+2+...+n，也就是 n(n+1)/2。

m 轮合计就是它的 m 倍，这部分无论怎么排都不变。

再想顺序影响什么。

总代价 = 基础部分 + 每批权重 × 该批被计入的轮数。

一批排得越靠前，被计入的轮数越多：第 1 批被算 m 轮，第 2 批被算 m-1 轮，……，最后一批只被算 1 轮。

要让总代价最小，权重大的批次少被算几轮、权重小的批次多被算几轮，也就是权重小的批次先处理。

即越靠前的位置，放权重越小的批次。

排序证明（相邻交换）。

假设两个相邻位置分别放权重 A、B，其他批次的位置都不动，只交换这两个。

A 在前时，A 会比 B 在前时多被算一轮，B 少被算一轮，其余批次完全不变。

所以两种顺序的总代价之差就是 A - B：A 比 B 大时，A 在前会让总代价更大，说明 B 应该在前。

不断做相邻交换，最优顺序就是按 W_i 从小到大处理。

这也解释了前面性质 A、性质 B 为什么都是升序排序：它们只是这个结论的特例。

怎么算每个档案的 c(x)。

把核心档案 A 从小到大排序，之后对任意编号 x，用二分在 A 里找到第一个不小于 x 的位置，从这个位置到末尾的个数，就是比 x 大的核心档案数量。

题目保证所有编号互不相同，x 一定不在 A 里，所以「不小于」和「大于」等价。

每一批边读边累加权重，不需要把全部档案存下来。

统计答案。

权重排序后模拟前缀和：base 表示「前 k 批都插入后，单次操作的代价」，初始为 n(n+1)/2。

每处理一批 b：base += b（新一批的贡献），ans += base（累加第 k 次操作的代价）。

ll n, m;vector<ll> A;vector<ll> B;  // B[i] 保存第 i 批的权重 W_ivoidSolver(){  scanf("%lld%lld", &n, &m);  A.resize(n);  B.resize(m);  for (int i = 0; i < n; i++) scanf("%lld", &A[i]);  sort(A.begin(), A.end());  for (int i = 0; i < m; i++) {  // 边读边计算每批权重    ll L;    scanf("%lld", &L);    ll sum = 0;    for (int j = 0; j < L; j++) {      ll x;      scanf("%lld", &x);      // c(x) = 核心档案中大于 x 的个数，二分计算      ll cnt = A.end() - lower_bound(A.begin(), A.end(), x);      sum += cnt;    }    B[i] = sum;  }  sort(B.begin(), B.end());  // 权重小的先处理  ll ans = 0;  ll base = (1 + n) * n / 2;  // 只有核心档案时的基准代价  for (ll b : B) {    base += b;    // 第 k 批处理完，本次操作的代价    ans += base;  // 累加总代价  }  printf("%lld\n", ans);}