题解：P13819 「LDOI R3」玩玩数字

思路

官方题解中已经给出了获胜条件，即

\sum_{j \in S} \frac{1}{2^{j}} \ge 1

。

这里给一个较为简单的实现方式。

首先明确一点：若某个

a_i \ge n

，则

a_i

不会对答案产生影响。

也就是说我们只需要维护一个

n

位的二进制数，并支持加减操作。

一个朴素的想法就是对序列分块，并做一个前缀和，而我们可以维护一个

2^w

进制数，这样进位会少很多，跑的较快。

Code

代码中取

w=50

。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define forr(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
const int N=4e4+10;
int n,m,LEN;
int a[N];
#define bl(x) (((x)-1)/LEN+1)
int rr[N],ll[N];
int sum[305][1005];
int arr[1005];
const int VAL=(1ll<<50);
void add(int *b,int pl,int val){
	b[pl]+=val;
	if(b[pl]>=VAL){
		b[pl]-=VAL;
		do{
			pl--;
			b[pl]++;
			if(b[pl]<VAL)break;
			b[pl]-=VAL;
		}while(pl>=0);
	}
}
void get(int l,int r){
	roff(i,800,0)arr[i]=0;
	if(l>r)return ;
	roff(i,800,0){
		arr[i]+=sum[r][i]-sum[l-1][i];
		if(arr[i]<0)arr[i]+=VAL,arr[i-1]--;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	LEN=200;
	forr(i,1,n)cin>>a[i];
	forr(i,1,n){
		rr[bl(i)]=i;
		ll[bl(i)]=(bl(i)-1)*LEN+1;
	}
	forr(i,1,bl(n)){
		forr(j,0,800)sum[i][j]=sum[i-1][j];
		forr(j,ll[i],rr[i])if(a[j]<=n)add(sum[i],(a[j]-1)/50+1,(1ll<<(50-(a[j]%50==0?50:a[j]%50))));
	}
	cin>>m;
	forr(i,1,m){
		int l,r;
		cin>>l>>r;
		if(bl(l)==bl(r)){
			forr(i,0,800)arr[i]=0;
			forr(j,l,r)if(a[j]<=n)add(arr,(a[j]-1)/50+1,(1ll<<(50-(a[j]%50==0?50:a[j]%50))));
		}else{
			get(bl(l)+1,bl(r)-1);
			forr(j,l,rr[bl(l)]){
				if(a[j]<=n)add(arr,(a[j]-1)/50+1,(1ll<<(50-(a[j]%50==0?50:a[j]%50))));
			}
			forr(j,ll[bl(r)],r){
				if(a[j]<=n)add(arr,(a[j]-1)/50+1,(1ll<<(50-(a[j]%50==0?50:a[j]%50))));
			}
		}
		if(arr[0]>=1){
			cout<<"Yes\n";
		}
		else cout<<"No\n";
	}
	return 0;
}
/*
time:
problem:
sample:


*/

题解：P13819 「LDOI R3」玩玩数字

文章操作

相关推荐

评论

题解：P13819 「LDOI R3」玩玩数字