专栏文章

P14507 缺零分治 题解

sshaotianyu
P14507题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@min7sr39
此快照首次捕获于
2025/12/01 21:58
3 个月前
此快照最后确认于
2025/12/01 21:58
3 个月前
查看原文

一个不用二分的写法

题意

要将一堆数划分为尽量少个可重集合，使得每个集合内部的 mex 加起来恰好为 mm 。求最少集合个数。多个询问。

性质分析

我们如果要求一个集合的 mex 为 xx ，那么就要求集合中包含 [0,x−1][0,x-1] 的所有数。

解法

题目给出了每个数字出现的次数，于是我们可以结合这个信息，处理出 f[i]f[i] ，表示最多能选多少次区间 [0,i][0,i] 中的每个数一次，也就是组成一个 mex 为 i+1i+1 的集合。
处理的时候有一个类似于递归的过程，为了方便接下来的处理（避免写一堆 map 的处理），我们把它存进栈中：
CPP
  for(int i=1;i<=n;i++){
    int x,y;
    scanf("%lld%lld",&x,&y);
    cnt[x]=y;
    if(!s.empty()){
      auto pr=s.top();
      int u=pr.first,v=pr.second;
      if(u==x-1){
        s.pop();
        if(cnt[x]>=v) s.push(make_pair(x,v));
        else{
          s.push(make_pair(u,v-cnt[x]));
          s.push(make_pair(x,y));
        }
      }	
    }
    else if(x==0) s.push(make_pair(x,y));
  }
接下来我们处理询问，可以这样想，如果我们按照 f[i]f[i] 选择出了若干个集合，并且是尽量选 mex 大的集合，他们的 mex 恰好等于 mm ，太好了，只需要看看没被选的数合不合法就行：不合法的情况，当且仅当选出的所有集合的 mex 都等于一个 cc ，且 cnt[c]>0cnt[c]>0 。不合法就调整，合法的话直接输出答案就好。
如果按照前面的选法，选出来 mex 大于 mm ，可以直接不管他，就是不管选出来区间末端的一些元素，对答案无影响。不合法的情况同上。
直接写，特判 m=0m=0 的情况，如下：
CPP
    while(Q--){
			scanf("%lld",&m);
			stack <pair<int,int> > tmp;
			int ret=0,ans=0,is_all_same=1;
			int how_many_time_we_cal=0,is_output_ans=0;
			if(m==0){
				if(cnt[0]) printf("-1\n");
				else printf("1\n");
				continue;
			}
			while(!query.empty()){
				if(how_many_time_we_cal) is_all_same=0;
				how_many_time_we_cal++;
				auto pr=query.top();
				int u=pr.first,v=pr.second;
				int t=min((m-ret)/(u+1ll)+((m-ret)%(u+1ll)>0),v);//这一步全选/选最少并达到m
				ans+=t;
				ret+=(u+1)*t;
				if(ret==m){
					if(!is_all_same){
						is_output_ans=1;
						printf("%lld\n",ans);
						break;	
					}
					else {
						if(cnt[u+1]){//选法不可行 
							ret-=u+1;
							ans--;
						}
						else {
							is_output_ans=1;
							printf("%lld\n",ans);
							break;
						}
					}
				}
				else if(ret>m){
					is_output_ans=1;
					if(cnt[m]>0&&(ans==1||is_all_same)) ans++;
					printf("%lld\n",ans);
					break;
				}
				tmp.push(pr);
				query.pop();
			} 
			while(!tmp.empty()){//还原栈 
				query.push(tmp.top());
				tmp.pop();
			}
			if(!is_output_ans) printf("-1\n");
		}
由于栈长度差不多是 O(n)O(n) 的，所以整份代码复杂度为 O(Tnq)O(Tnq) 。
考虑优化，我们发现一次一次跳这个栈有点太慢了，于是可以把询问离线下来，从小到大排好序，这样就只用跑一遍栈，每次统计答案的时候要退回一位，防止询问之间互相影响。复杂度优化为线性。

参考代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10; 

int n,m,Q,T;
map <int,int> cnt;

struct node{
	int num,id,res;
}ask[N];

bool cmp1(node A,node B){
	if(A.num!=B.num) return A.num<B.num;
	else return A.id<B.id; 
}
bool cmp2(node A,node B){
	return A.id<B.id; 
}

signed main(){
	scanf("%lld",&T);
	for(int test=1;test<=T;test++){
		scanf("%lld%lld",&n,&Q);
		stack <pair<int,int>> s;
		
		for(int i=1;i<=n;i++){
			int x,y;
			scanf("%lld%lld",&x,&y);
			cnt[x]=y;
			if(!s.empty()){
				auto pr=s.top();
				int u=pr.first,v=pr.second;
				if(u==x-1){
					s.pop();
					if(cnt[x]>=v) s.push(make_pair(x,v));
					else{
						s.push(make_pair(u,v-cnt[x]));
						s.push(make_pair(x,y));
					}
				}	
			}
			else if(x==0) s.push(make_pair(x,y));
		}
		
		for(int i=1;i<=Q;i++){
			scanf("%lld",&ask[i].num);
			ask[i].id=i;
			ask[i].res=0;
		}
		sort(ask+1,ask+Q+1,cmp1);
		int ret=0,ans=0,is_all_same=1,how_many_time_we_cal=0;
		for(int i=1;i<=Q;i++){
			m=ask[i].num;
			if(m==0){
				if(cnt[0]) ask[i].res=-1ll; 
				else ask[i].res=1ll;
				continue;
			}
			while(!s.empty()){
				if(how_many_time_we_cal) is_all_same=0;
				how_many_time_we_cal++;
				auto pr=s.top();
				int u=pr.first,v=pr.second;
				int t=min((m-ret)/(u+1ll)+((m-ret)%(u+1ll)>0),v);
				int lst_ans=ans,lst_ret=ret;
				ans+=t;
				ret+=(u+1ll)*t;
				if(ret==m){
					if(!is_all_same){
						ask[i].res=ans;
						ans=lst_ans,ret=lst_ret;
						break;	
					}
					else {
						if(cnt[u+1]) ret-=u+1ll,ans--;
						else {
							ask[i].res=ans;
							ans=lst_ans,ret=lst_ret;
							break;
						}
					}
				}
				else if(ret>m){
					if(cnt[m]&&(ans==1||is_all_same)) ans++;
					ask[i].res=ans;
					ans=lst_ans,ret=lst_ret;
					break;
				}
				s.pop();
			} 
			if(!ask[i].res) ask[i].res=-1ll;
		} 
		sort(ask+1,ask+Q+1,cmp2);
		for(int i=1;i<=Q;i++) printf("%lld\n",ask[i].res);
		cnt.clear();
	}
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...