SCP 2026 复赛 S 组模拟赛第一题 档案 file 题解

零、背景

最近在洛谷上做了 SCP 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_m 里出现的所有数字互不相等。

每次操作分两步：先挑一批还没归档的档案加进已归档序列 x，再把 x 从小到大排序。

这次操作的代价是排序后 x 里所有核心档案的下标之和，下标从 1 开始。

一共做 m 次操作，总代价是每次的代价加在一起。

小 Z 可以任意决定这 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。
• 特殊性质 A：n = 1。
• 特殊性质 B：每批 b_i 内部编号连续，且 a 也连续。

二、代价换一种数法

先做一件看起来很琐碎的事：把「单次操作的代价」换一个写出来的方式。

把核心档案按编号从小到大排成 a_1 < a_2 < ... < a_n。

某次操作做完后，设已经归档的非核心档案集合为 S。

对第 j 份核心档案 a_j，它排在排序后序列的第几个位置？

它前面有 j-1 份核心档案（都比它小），还有 S 里那些比它小的非核心档案。

所以它的下标是 j + |{x ∈ S : x < a_j}|。

所以这次操作的代价可以写成：

cost = Σ_j (j + |{x ∈ S : x < a_j}|) = n(n+1)/2 + Σ_j |{x ∈ S : x < a_j}|

后面那一项换个数法：不去数「每份核心档案前面有多少非核心档案」，改成数 (x, a_j) 这样的配对有多少个。

一个非核心档案 x 和一份核心档案 a_j 配成一对的条件是 x < a_j。

两种数法数出来的对数是一样的，只是分组方式不同。按 x 来分组，就得到了：

cost = n(n+1)/2 + Σ_{x∈S} c(x)，其中 c(x) = |{a ∈ A : a > x}|

写成这个样子之后，后面的活就轻松了：每一份非核心档案的贡献是一个固定的数 c(x)，只要在 S 里就被算一次，跟它被插进来的先后顺序、跟它在序列里落在哪个位置都没有关系。

所以真正要决定的只有一件事：哪几批先被放进 S，哪几批后被放进 S。

三、处理顺序该怎么排

设第 i 批处理的时候排在第 t_i 个位置（位置从 1 数到 m）。

这一批里的元素从第 t_i 次操作开始就在 S 里了，一直到第 m 次操作结束，一共被算了 m - t_i + 1 次。

记 W_i = Σ_{x ∈ b_i} c(x)，也就是第 i 批合起来的总贡献，那么总代价是：

ans = m * n(n+1)/2 + Σ_i W_i * (m - t_i + 1)

前一项跟顺序无关，先放到一边。

后面一项里，(m - t_i + 1) 这一串系数恰好取遍 m, m-1, ..., 1，每个位置一个。

问题到这里就换成了一个很好认的样子：把 m 个权重 W_i 和 m 个系数 m, m-1, ..., 1 一一配对，让乘积之和尽量小。

拿相邻的两个位置看一下。

假设第 t 个位置和第 t+1 个位置上放的是权重 A 和 B，对应的系数是 m-t+1 和 m-t。

它们对答案的贡献是 A*(m-t+1) + B*(m-t)。

把两者交换一下，贡献变成 A*(m-t) + B*(m-t+1)。

前者减后者等于 A - B。

也就是说 A > B 的时候交换之后答案变小，A < B 的时候不交换更好。

换成大白话：权重大的批次要往后排，权重小的往前排。

照着这条规则不停地做相邻交换（就是冒泡排序那一套），一定能排到「权重从小到大」为止，而且每一步答案都不会变大。

所以最优顺序是：按 W_i 从小到大依次处理这 m 批。

四、权重怎么算

c(x) 是核心档案里比 x 大的个数。

把 a 排好序，用二分找到第一个不小于 x 的位置，从这个位置到末尾的长度就是 c(x)。

sort(A.begin(), A.end());
ll cnt = A.end() - lower_bound(A.begin(), A.end(), x);

题目保证所有编号互不相同，所以这里「不小于 x」和「大于 x」是一回事，用 lower_bound 还是 upper_bound 都一样。

每一批内部把所有元素的 c(x) 加起来，就是这一批的权重 W_i。

这里不需要真的把 m 批都存下来，边读边累加就行，读完只留 m 个权重。

五、代码实现

ll n, m;
vector<ll> A;
vector<ll> B;
void Solver() {  //
  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);
      ll cnt = A.end() - lower_bound(A.begin(), A.end(), x);
      sum += cnt;
    }
    B[i] = sum;  // 第 i 批的权重
  }

  sort(B.begin(), B.end());  // 权重小的先处理
  ll ans = 0;
  ll base = (1 + n) * n / 2;
  for (ll b : B) {
    base += b;    // 前 t 批都进来了，这是第 t 次的单次代价
    ans += base;  // 累加到总代价
  }
  printf("%lld\n", ans);
}

最后那个循环是在模拟「前缀和」：按权重从小到大处理，第 t 次操作时 S 里正好是前 t 批的元素，单次代价等于 n(n+1)/2 加上前 t 批的权重和，累加 m 次就是总代价。

复杂度：给 A 排序是 O(n log n)；每个非核心档案二分一次 O(log n)，L 个档案合计 O(L log n)；m 个权重排序是 O(m log m)。总复杂度 O((n + L) log n + m log m)，空间 O(n + m)。

最大规模下（本地构造 n = m = L = 10^6 的数据）跑起来不到 200ms，很宽裕。

另外，答案的上界大约是 m * (n(n+1)/2 + n*L)，最大规模下量级接近 10^18，所有累加的变量必须用 long long。

六、10 分写法：暴力枚举顺序

测试点 1~2 满足 m ≤ 7，最多只有 7! = 5040 种处理顺序，全部试一遍就行。

版本一：标记法枚举排列

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

对每一种排列按题目说的那样模拟：把这一批的元素接到数组末尾，整体排序，然后从头扫一遍，遇到核心档案就把下标加进这一轮的代价里。

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

vector<int> vis;   // 当前的处理顺序
vector<int> flag;  // 哪些批次已经选过
unordered_map<ll, int> mp;  // 核心档案

ll allCnt = 0;
ll ans = 0;
void UpdateAns() {  //
  vector<ll> a = A;
  a.reserve(allCnt);
  ll sum = 0;
  for (int b : vis) {
    for (auto v : B[b]) a.push_back(v);
    sort(a.begin(), a.end());
    for (int i = 1; i <= a.size(); i++) {
      if (mp.count(a[i - 1])) {
        sum += i;
      }
    }
  }
  ans = min(ans, sum);
}

void Dfs(const int 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 次排序，序列最大规模是 n+L，所以是 O(m! * m * (n+L) log(n+L))。

版本二：交换法枚举排列

标记法每一层都要扫一遍 flag 找没用过的批次，改成在原数组上 swap 来生成排列，可以省掉 flag 数组。

做法是：第 k 层把位置 i 的元素换到第 k 位，往下递归一层，回来时再换回去。

void Dfs(const int 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]);
  }
}

生成的排列数量跟版本一完全一致，m 从 1 到 6 试下来，两种写法都是恰好 m! 个排列。

顺便提一句，这里判断核心档案用的是哈希表，A 排不排序都无所谓，所以 sort(A) 那一行可以去掉。

版本三：有序合并代替整体排序

版本一、二在 UpdateAns 里每加一批就整体 sort 一次。

如果保证「当前序列有序」且「新加的这一批内部也有序」，就可以用一次线性合并把排序替掉，这一步从 O(N log N) 降到 O(N)。

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

合并时从后往前填：谁大谁就先落到末尾的空位上。

for (int b : vis) {
  int an = a.size();
  int bn = B[b].size();
  int 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--;
  }
  // 下面照旧：从头扫一遍，统计核心档案的下标之和
}

从后往前填的原因是提前 resize 出来的位置都在尾巴上，先处理大的元素不会覆盖还没看过的数据。

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

为什么卡在 10 分

m ≤ 7 差不多是 m! 能吃得住的上限。

再到测试点 3~5 的 m = 11，就有 11! ≈ 4×10^7 种排列。

就算把单次统计压到线性，这 4×10^7 个排列也一个都少不了，怎么优化都要超时。

要拿满分，得回到第二节那条路：把「每份非核心档案的贡献」单独拎出来，让每一批的代价变成一个固定的权重，之后「枚举顺序」就退化成「给权重排序」了。

七、最后

这道题的数据范围看着吓人，n、m、L 都是 10^6，很容易让人一开始就往数据结构上想。

真正要跨过去的一步，是把单次操作的代价写成「每份非核心档案各贡献一次」的形式。

写完这个形式，剩下就是排序不等式的一个结论——被重复计的次数多的位置，放权重小的批次。

另外有三个容易写错的地方：

1）所有累加的变量要用 long long，int 会溢出。
2）别真的去维护那个排序后的序列，边读边把每一批的权重累加出来就够了，空间是 O(n + m)。
3）权重排序要按从小到大，别按错方向：先处理的批次会被反复计算，理应放贡献小的。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code