蒟蒻求助DIV2.C的思路
  • 板块题目总版
  • 楼主NewJeanss
  • 当前回复10
  • 已保存回复10
  • 发布时间2020/8/8 18:25
  • 上次更新2023/11/6 20:55:30
查看原帖
蒟蒻求助DIV2.C的思路
282080
NewJeanss楼主2020/8/8 18:25

最后四个点WA了QAQ

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
long long a[maxn];
int cnt0[65],cnt1[65];
long long f[65],res0[65],res1[65],s[65];
int maxlen; 
void change(long long x){
	int len=-1,now;
	while(x){
		++len;
		now=x%2;
		if(now==1) cnt1[len]++;
		else cnt0[len]++;
		x>>=1;
	}maxlen=max(maxlen,len);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	long long n,q,m,len,ans,now;
	f[0]=1;
	for(int i=1;i<=60;i++)
		f[i]=f[i-1]*2;
	while(cin>>n){
		memset(cnt0,0,sizeof(cnt0));
		memset(cnt1,0,sizeof(cnt1));
		maxlen=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			change(a[i]);
		}
		for(int i=0;i<=maxlen;i++){
			if(cnt0[i]+cnt1[i]!=n){
				cnt0[i]+=n-cnt0[i]-cnt1[i];
			}
		}
		for(int i=0;i<=maxlen;i++){
			res0[i]=cnt1[i]*f[i];
			res1[i]=cnt0[i]*f[i];
		}
		s[0]=min(res0[0],res1[0]);
		for(int i=1;i<=maxlen;i++){
			s[i]=s[i-1]+min(res0[i],res1[i]);
		}
		/*for(int i=0;i<=maxlen;i++){
			cout<<cnt0[i]<<" "<<cnt1[i]<<" "
			<<res0[i]<<" "<<res1[i]<<endl;
		}
		for(int i=0;i<=maxlen;i++)
			cout<<s[i]<<" "; cout<<endl;*/
		cin>>q; 
		while(q--){
			cin>>m;
			long long mm=m;
			len=-1;
			while(mm){
				++len; mm>>=1;
			}
			ans=0; now=0;
			for(int i=min(len+10,(long long)60);i>maxlen;i--){
				if(f[i]*n+s[maxlen]+now<=m){
					now+=f[i]*n; ans+=f[i];
				}
			}
			if(s[maxlen]>m){
				cout<<-1<<endl;
				continue;
			}
			for(int i=maxlen;i>=0;i--){
				if(now+res1[i]+s[i-1]<=m){
					ans=ans+f[i]; now+=res1[i]; 
				}
				else{
					now=now+res0[i];
				}
			}
			if(ans==0&&now<=m) cout<<0<<endl;
			else if(ans==0) cout<<-1<<endl;
			else cout<<ans<<endl;
		}
	}
	return 0;
}
2020/8/8 18:25
加载中...