北京信息科技大学第十一届程序设计竞赛（重现赛）C kotori和出道

链接：https://ac.nowcoder.com/acm/contest/940/C
来源：牛客网

题目描述
kotori和一些偶像们围成一圈，一共有n个偶像（包括kotori自己），她们的序号顺时针从1到n。现在她们从1号开始进行顺时针报数：1,2,1,2,1……

每个报到2的人出列。直到剩下最后一个人为止。那么这个剩下的人就能被选中发专辑出道啦！

kotori可以暗箱操作决定自己的序号。她很想发专辑，于是向聪明的你求助，初始序号设定为多少才可以呢？

输入描述:
第一行输入一个正整数t，代表共有t组样例。

第2行到第t+1行，每行一个正整数n，代表一次询问。

(1≤t≤10000，1≤n≤10^18)
输出描述:
一共t行，每行一个正整数，代表kotori的初始序号。

思路
先递推求出每一轮报数是奇数位还是偶数位出局直到只剩一个人，然后将该过程逆推即可求得获胜者编号

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e6; 
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--){
        LL x;
        scanf("%lld",&x);
        int cnt=0;
        int flag=1;//flag表示从奇数位开始还是从偶数位开始
        while(x>1){
            if(x%2){
                if(flag==1){
                    a[++cnt]=0;
                    x=(x>>1)+1;
                }
                else{
                    a[++cnt]=1;
                    x=(x>>1);
                }
                flag=!flag;
 
            }
            else{
                if(flag==1){
                    a[++cnt]=0;
                }
                else{
                    a[++cnt]=1;
                }
                x=x>>1;
            }
        }
        LL num=1;
        for(int i=cnt;i>=1;i--){
            if(a[i]==1){
                //如果这一轮出局的是奇数位,那么num必为偶数，因此对于num来讲其前面的人会减少一半
                num=num+num;
            }
            else{
                //反之num为奇数，其前面的人减少一半减一
                num+=num-1;
            }
        }
        cout<<num<<endl;
 
    }
    return 0;
}