链接: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;
}