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

题目分析

题目要求统计区间

[l, r]

内所有二进制表示中包含奇数个 1 的正整数的和。

第一次

CPP

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll joxing(ll x)
{
    int count=0;
    while(x)
    {
        count+=x&0x01;
        x>>=1;
    }
    return count;
}
int main()
{
    ll sum=0;
    ll l,r;
    cin>>l>>r;
    for(ll i=l; i<=r; i++)
    {
        if(joxing(i)%2==1)
        {
            sum+=i;
        }
    }
    cout<<sum;
}

最终……

TLE

问题分析

数据大大大！！！！（1e9）

再来一次！

CPP

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int l,r;
    cin>>l>>r;
    long long sum=0;
    for(int i=l; i<=r; i++)
    {
        if(__builtin_parity(i))
        {
            sum+=i;
        }
    }
    cout<<sum;
}

最终……

调用了1e9次

O(1)

的函数，超时！

方法思路

注意注意！！

数据非常大！会超时！

块 t	数值范围	二进制表示（示例）	有趣数（二进制）	有趣数（十进制）	和（十进制）	公式验证
0	[0, 1, 2, 3]	0000, 0001, 0010, 0011	0001, 0010	1, 2	3	8×0 + 3 = 3
1	[4, 5, 6, 7]	0100, 0101, 0110, 0111	0100, 0111	4, 7	11	8×1 + 3 = 11
2	[8, 9, 10, 11]	1000, 1001, 1010, 1011	1000, 1011	8, 11	19	8×2 + 3 = 19
3	[12, 13, 14, 15]	1100, 1101, 1110, 1111	1101, 1110	13, 14	27	8×3 + 3 = 27
4	[16, 17, 18, 19]	10000, 10001, 10010, 10011	10000, 10011	16, 19	35	8×4 + 3 = 35
5	[20, 21, 22, 23]	10100, 10101, 10110, 10111	10101, 10110	21, 22	43	8×5 + 3 = 43

大发现

S(4k-1) = \sum_{t=0}^{k-1} (8t+3) = 4k^2 - k.

最终！！！

CPP

#include <bits/stdc++.h>//万能头
using namespace std;
int a[16] = {0, 1, 3, 3, 7, 7, 7, 14, 22, 22, 22, 33, 33, 46, 60, 60};//特判小于16的情况
using ll=long long;//ll就是long long（偷个懒～）
ll l, r;
int digit_cnt(int n)
{
	int cnt=0;
	while (n)
	{
		if (n&1)/* <--奇数  */cnt++;
		n /= 2;
	}
	return cnt;
}
ll sum(ll n)
{
	if (n<16) return a[n];
	ll k=(n-4)/4;
	ll ans=k*k*4-k;
	for (ll i=k*4; i<=n; i++)
	{
		if (digit_cnt(i)&1)
		{
			ans+=i;
		}
	}
	return ans;
}
int main()
{
	cin>>l>>r;
	cout<<sum(r) - sum(l - 1); //前缀和
  return 0;//画一个完美的句号
}

AC 记录……

（第一次写题解，不好请原谅）

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

文章操作

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

题目分析

第一次

问题分析

再来一次！

方法思路

大发现

最终！！！

相关推荐

评论

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