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

· · 题解

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

题目分析

题目要求统计区间 [l, r] 内所有二进制表示中包含奇数个 1 的正整数的和。

第一次

#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）

再来一次！

#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)的函数，超时！

方法思路

::::warning[注意注意！！]{open} 数据非常大！会超时！

:::: 块 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.

最终！！！

#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 记录……

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