我要成为百度之星

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4233

题解：题目和解答完全不一样，答案是101010101010101010......的字符串

题意是和二进制位有关的字符串排列。

某一位的状态和这一位的序号-1的二进制中1个数的奇偶有关

C++版本一

AC版本

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
ll l,r;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&l,&r);
        if(l>r){
            swap(l,r);
        }
        temp=0;
        if(l%2==0){
            l++;
        }
        if(r%2==1){
            temp++;
            r--;
        }
        printf("%lld\n",(r-l+1)/2+temp);

    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

AC版本

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<vector>
using namespace std;
vector<int> V;
int solve(int x)
{
    if(x==0) return 0;
    if(x==1) return 1;
    int y=lower_bound(V.begin(),V.end(),x)-V.begin();
    if(V[y]==x) return x/2;
    int dif=V[y]-x;
    return solve(dif)+(x-dif)/2;
}
int main()
{
    V.push_back(2);
    int x=2;
    while(x<=(int)1e9)
    {
        x=x*2;
        V.push_back(x);
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",solve(r)-solve(l-1));
    }
   return 0;
}

C++版本三

符合题意版本

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
ll l,r;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //scanf("%d",&n);
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&l,&r);
        if(l>r){
            swap(l,r);
        }
        if(l%2==0){
            if(__builtin_popcount(l-1)%2==0)
                l--;
            else
                l++;
        }
        if(r%2==1){
            if(__builtin_popcount(r-1)%2==0)
                r++;
            else
                r--;
        }
        printf("%lld\n",(r-l+1)/2);
    }
    //cout << "Hello world!" << endl;
    return 0;
}