专栏文章

题解：P14074 [GESP202509 五级] 有趣的数字和

tthe_moon
P14074题解参与者 16已保存评论 17

文章操作

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

当前评论
17 条
当前快照
1 份
快照标识符
@minqqia3
此快照首次捕获于
2025/12/02 06:48
3 个月前
此快照最后确认于
2025/12/02 06:48
3 个月前
查看原文

打表+枚举

题目大意

统计区间 [l,r][l,r] 内所有二进制表示中包含奇数个 11 的整数之和。

思路分析

根据题意，使用如下的暴力枚举可以轻松通过 40% 的数据，但是剩余的数据，可能就TLE了。这是因为我们的枚举量太大，可能达到 10910^9。
CPP
ll ans=0;
for(ll i=l;i<=r;i++){
  ll cnt=0,t=i;      
  while(t){
    if(t&1) cnt++;
    t>>=1;
  }
  if(cnt&1) ans+=i;   
}
cout<<ans;
那要怎么优化呢？枚举优化的一个常见策略是打表，首先离线预处理一部分数据，存进数组里，后续计算时直接使用，减少枚举量。
结合本题数据规模分析，我们可以预处理计算出 1∼1091\sim10^9 长度为 10710^7 的每一段数据，如图所示：
根据前缀和的思想，还可以将本题 [l,r][l,r] 区间上的问题，转化为求解 [1,r]−[1,l−1][1,r]-[1,l-1]。
因此，可以使用如下代码预处理出 [1,n][1,n] 的有趣的数的和，并输出到控制台，其中 n 是 107 的倍数，且 n≤109n \text{ 是 } 10^7 \text{ 的倍数，且 } n \leq 10^9。
CPP
ll l=1,r=1e7,pre=0;  // pre 保存前一个区间的和 
while(r<=1e9+3e7){   
  ll ans=0;
  for(ll i=l;i<=r;i++){
    ll cnt=0,t=i;
    while(t){      
      if(t&1) cnt++;
      t>>=1;
    }
    if(cnt&1) ans+=i;
  }
  ans+=pre;
  pre=ans;
  cout<<ans<<",";
  r+=1e7;
  l+=1e7;
}
最后，使用这些预处理数据，拼凑答案即可。
即将 [1,n][1,n] 划分为 [1,l][1,l] 和 [l+1,n][l+1,n]，其中 [1,l][1,l] 已经预处理得出，[l+1,n][l+1,n] 暴力枚举，[l+1,n][l+1,n] 区间大小不超过 10710^7，暴力枚举不会超时。
CPP
ll pre[]={0,24999997500000,...};// 打表

ll calc(ll n){ 
	ll ans=0;
	ll l=n/10000000*10000000;
	for(ll i=l+1;i<=n;i++){
		ll cnt=0,t=i;
		while(t){
			if(t&1) cnt++;
			t>>=1;
		}
		if(cnt&1) ans+=i;
	}
	return ans+pre[n/10000000];
}

void solov(){
	ll l,r;
    cin>>l>>r;
	cout<<calc(r)-calc(l-1);
}

AC Code

CPP
#include<bits/stdc++.h>/
#define quick_read ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long int ll;
ll pre[]={0,24999997500000,99999995000000,224999992500000,399999990000000,624999987500000,899999985000000,1225000052500000,1599999980000000,2025000067500000,2499999975000000,3025000082500000,3599999970000000,4224999967500000,4900000105000000,5624999962500000,6399999960000000,7224999957500000,8100000135000000,9024999952500000,9999999950000000,11024999947500000,12100000165000000,13224999942500000,14399999940000000,15625000187500000,16899999935000000,18225000202500000,19600000210000000,21024999927500000,22499999925000000,24024999922500000,25599999920000000,27225000247500000,28899999915000000,30624999912500000,32400000270000000,34225000277500000,36099999905000000,38024999902500000,39999999900000000,42025000307500000,44099999895000000,46225000322500000,48400000330000000,50624999887500000,52899999885000000,55225000352500000,57599999880000000,60025000367500000,62500000375000000,65024999872500000,67599999870000000,70225000397500000,72900000405000000,75625000412500000,78400000420000000,81225000427500000,84099999855000000,87025000442500000,89999999850000000,93025000457500000,96099999845000000,99224999842500000,102399999840000000,105624999837500000,108900000495000000,112224999832500000,115599999830000000,119025000517500000,122499999825000000,126025000532500000,129600000540000000,133224999817500000,136900000555000000,140624999812500000,144399999810000000,148224999807500000,152099999805000000,156025000592500000,159999999800000000,164024999797500000,168100000615000000,172225000622500000,176399999790000000,180625000637500000,184900000645000000,189224999782500000,193600000660000000,198024999777500000,202499999775000000,207025000682500000,211599999770000000,216225000697500000,220900000705000000,225625000712500000,230399999760000000,235225000727500000,240100000735000000,245025000742500000,250000000750000000,255025000757500000,260099999745000000,265225000772500000};
ll calc(ll n){
	ll ans=0;
	ll l=n/10000000*10000000;
	for(ll i=l+1;i<=n;i++){
		ll cnt=0,t=i;
		while(t){
			if(t&1) cnt++;
			t>>=1;
		}
		if(cnt&1) ans+=i;
	}
	return ans+pre[n/10000000];
}
void solov(){
	ll l,r;
    cin>>l>>r;
	cout<<calc(r)-calc(l-1);
}
int main(){
	quick_read;
	solov();
    return 0;
}

评论

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

正在加载评论...