首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >AcWing 631. Googol字符串 (递归、思维题)

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

作者头像
glm233
发布2021-05-27 11:05:41
2200
发布2021-05-27 11:05:41
举报

原题链接

对于每个字符串,分为三个部分、前中后,中间由最独立的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);
        
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2021-05-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档