题解-1002-小q的数列

解题思路

题目中给的递推式的操作包含两项，前一项 $f[n\mathrm{/}2]f[n/2]$ 是对 $n\mathrm{/}2n/2$ 后的递归操作， $f[n\mathrm{\%}2]f[n\backslash \%2]$ 是对当前的 $nn$ 对 $22$ 取余的操作，而 $f[0]=0f[0]\; =\; 0$ , $f[1]=1f[1]\; =\; 1$ , 因此第一问实际上就是对输入的 $nn$ ，计算其二进制表示中有多少个 $11$ ，第二问求的就是拥有相同个数 $11$ 的数中最小的那个，可以直接造出答案，只要让这个数的二进制表示全为 $11$ 即可，这一步操作可以用 来完成， $11$ 左移 $xx$ 位得到 $11$ 后面 $xx$ 个 $00$ ，再减去 $11$ 即可得到二进制表示为 $xx$ 个 $11$ 相连的数。
注意点是这里 $11$ 的个数在 $intint$ 的范围内， 但是左移之后的数字可能会超过 $intint$ 的范围，不能直接用 来完成，要设一个 $longlong$ $longlong$ 类型的 $ansans$ ，初始化为 $11$ ，执行
操作，才能输出正确答案。

通过代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int cal(ll x)
{
    int ans = 0;
    while(x)
    {
        ans += (x & 1);
        x >>= 1;
    }
    return ans;
}
int main()
{
    cin >> t;
    ll n;
    while (t--)
    {
        scanf("%lld", &n);
        int x = cal(n);
        cout << x << " ";
        ll ans = 1;
        cout << (ans << x) - 1<< endl;
    }
    return 0;
}