P14507 缺零分治 mexdnc
2025-11-15
题目大意
给定正整数 n 和 n 个二元组 (bi,ai),表示有 bi 个大小为 ai 的数。
定义 mex 表示一个集合中最小未出现的自然数。
你需要将这 i=1∑nbi 个数分为 k(k≥1) 个可重集合,使得这 k 个集合的 mex 和恰好为 m,求 k 的最小值。
给定 T 组询问,每次给定一个 m,求最小的 k,若无解则输出 −1。
数据范围:
1≤T≤10
1≤n,q≤105
0≤ai≤109 且 ai<ai+1
1≤bi≤109
1≤m≤1018
Solution
很容易注意到有些 ai 是没有用的,我们考虑如何将其去除。
从题目中可以发现,ai 是升序给我们的,那么有用的 ai 一定是形如 0,1,...,x 的一个排列。
结论
找到最小的 i 使得 ai+1=ai+1(若不存在则 i 为 n),则 ai+1 到 an 都没有用
我们令 n 为上面的 i。 于是问题变成了对于 i∈[1,n],有 bi 个 i−1。
先来考虑无解的情况,分讨一下有两种:
- m=0,若 n=0,那么一定有一个集合被分到 0,即 mex≥1,总和一定不是 0,无解。
- 令目前所有数能凑出来的 mex 的和的最大值为 x,若 m>x,则无解。
考虑怎么求最大和:
- 一个集合中的所有数当且仅当出现一次,否则多余的数不产生贡献。
- 如果可以组成一个 [0,u−1] 的序列,那么将其拆分为 [0,v−1](v<u) 一定不优,因为 [v,u−1] 被浪费了。
所以我们只需要每次找到最大的 u 满足可以构成 [0,u−1] 的一个序列,产生 u 的贡献,重复这个步骤就能得到最大值。
考虑怎么进行代码实现,我们令 fi=j=1minibj,gi 为最小的满足 bj=fi 的 j。 进行如下步骤:
- 初始化
初始时令 p=n,d=0(p 为上面最大的 u,d 为删掉的 0 的个数)
由于删掉的 0 的数其实就是序列总数,所以 d 就是删除的序列数。 - 计算贡献
令 c=fp−d 即为能够取出多少个 [0,p−1] 的序列,产生的贡献就是 p×c。 - 更新变量
拿出 c 个序列后,d←d+c。
这个时候的 gp−1 已经用完(gp 在原数组对应 gp−1 这个数),所以 gp−1 到 p−1 之间剩的数都没有用了,令 p←gp−1(注意这个时候指的是下标) - 完成
重复这个步骤,直到 p=0。
这样我们得到了最大值。
如何计算 f 和 g?
很明显要考虑递推。
如果当前位置 i 的 bi<fi−1,那么 fi=bi,gi=i。
如果当前位置 i 的 bi≥fi−1,那么 fi=fi−1,gi=gi−1
这样,我们成功处理了无解的情况。
当前情况一定有解。
我们把所有构成最大值的数组存下来,记作 e,则 ei 代表一个 [0,ei−1] 的序列。
同时,为了用尽量少的集合,我们应该尽可能选择 mex 大的集合。
怎么选呢?事实上,ei 为单调不增的。
这样就好办了,只需要每次找到一个 i 满足 j=1∑iei≤m 且 j=1∑i+1ei>m,则为了凑 m,可以将第 i+1 个集合拆开,只留 [0,m−j=1∑iei](若 m=j=1∑iei,可以直接不要这个集合),那么前 i+1 个集合的 mex 和刚好为 m。
至于多出来的东西,可以丢到前面的集合中让其重复,这样就不会对答案产生贡献了。(其实可以全都丢到 e1,因为 ei 单调不增)
这个时候的答案就是 i+[m=j=1∑iei]。
时间复杂度 O(Tmaxbi),空间复杂度 O(maxbi)。
很显然还没完事。。。
上面做法的问题在于,最大化时一定会带来一堆重复的 ei,不如开个 f,让 fi 表示 ei 有多少个,空间复杂度 O(n)。
时间上,这一坨 ∑ 显然是可以二分的,令 hi=j=1∑iei×fi,在 h 中找到 hi≤m 且 hi+1>m 的 i,再加上第 i+1 块可能的数量,结果为:
(i=1∑nfi)+⌈ei+1m−hi⌉
时间复杂度 O(Tlogn)
注意
若 m<e1,则应将 e1 拆成两半,即 [0,m] 和 [m+1,e1−1]
若 m=0 且 n=0,请直接将所有询问判断完。(被卡了好久)
Code
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long LL;
struct Node {LL a , b; };
const int N = 1e5+10;
int n , q , cnt;
LL A[N] , B[N];
LL f[N] , g[N];
LL w[N] , sw[N] , sc[N];
void slove() {
memset(w , 0 , sizeof w);
memset(sw , 0 , sizeof sw);
memset(sc , 0 , sizeof sc);
memset(f , 0 , sizeof f);
memset(g , 0 , sizeof g);
scanf("%d%d" , &n , &q); cnt = 0;
int tmp = n;
for(int i = 1 ; i <= n ; i ++) {
scanf("%lld%lld" , &A[i] , &B[i]);
if(tmp == n && A[i] != i-1) {
tmp = i-1;
}
}
n = tmp;
if(n == 0) {
while(q --) {
LL m; scanf("%lld" , &m);
if(m) puts("-1");
else puts("1");
}
return;
}
f[1] = B[1]; g[1] = 1;
for(int i = 2 ; i <= n ; i ++) {
f[i] = f[i-1]; g[i] = g[i-1];
if(B[i] < f[i]) {
f[i] = B[i];
g[i] = i;
}
}
int p = n; LL d = 0;
while(p) {
LL c = f[p]-d;
++ cnt;
w[cnt] = p;
sc[cnt] = sc[cnt-1] + c;
sw[cnt] = sw[cnt-1] + c*p;
p = g[p]-1; d += c;
}
while(q --) {
LL m; scanf("%lld" , &m);
if((m == 0 && n != 0) || m > sw[cnt]) {
puts("-1");
continue;
}
if(m < w[1]) {
puts("2");
continue;
}
int l = 0 , r = cnt , mid , pos = 0;
while(l <= r) {
mid = (l+r) >> 1;
if(sw[mid] <= m) {
pos = mid;
l = mid+1;
} else {
r = mid-1;
}
}
LL res = 0;
if(pos == 0) {
res = (m+w[1]-1)/w[1];
} else if(pos == cnt || sw[pos] == m) {
res = sc[pos];
} else if(w[pos+1] == 0) {
res = sc[pos];
} else {
res = (m-sw[pos]+w[pos+1]-1)/w[pos+1]+sc[pos];
}
printf("%lld\n" , res);
}
}
int main() {
int T; scanf("%d" , &T);
while(T --) slove();
return 0;
}后记
UPD 2025/11/21: 这个题实在太毒瘤了,边界情况超多。
