AcWing 631. Googol字符串 (递归、思维题）

原题链接

对于每个字符串，分为三个部分、前中后，中间由最独立的0组成，前面一直继承下来不变，后面记录一个反转对应的位置以及将本位上的值翻转的次数（0变1,1变0）

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,k,res;
void dfs(int k,int p,int cnt){if(k==(p+1)/2){res=0;for(int i=0;i<cnt;i++){res^=1;}return;}if(k<(p+1)/2){dfs(k,p/2,cnt);}else{int tep=p/2+1-(k-p/2-1);//cout<<tep<<" "<<p/2<<endl;dfs(tep,p/2,cnt+1);}}
signed main(){cin>>t;for(int _=1;_<=t;_++){cin>>k;int p=1;while(p<k){p*=2;p++;}//cout<<p<<endl;dfs(k,p,0);printf("Case #%lld: %lld\n",_,res);}
}