原题链接
考察:博弈论
完全给我WA麻了,没有特判4这个点,结果是一直WA.
思路:
??3种情况:
- n为奇数,只有一种取法
- n为偶数且n/2也为偶数,此时和奇数一样取
- n为偶数且n/2为奇数,直接取一半.
当n==4这个点一定要特判
Code
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 10;
LL n;
int f[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
LL res =0,t = n;
bool ok = 1;
while(n)
{
if(n==4)
{
if(ok) res+=3;
else res++;
n = 0;
}else if(n&1){
if(ok) res++;
n--;
}else if(n/2%2!=0){
if(ok) res+=n/2;
n/=2;
}else{
if(ok) res++;
n--;
}
ok = ok^1;
}
printf("%lld\n",res);
}
return 0;
}