题目链接:https://atcoder.jp/contests/aising2020/tasks/aising2020_d
题意:对输入的二进制串x,设它每一位分别取反后的十进制结果为f,二进制的f中1的个数为n,令f=f%n,输出使f=0需要经过该操作的次数。
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long //简便快速幂 ll power(ll a,ll b,ll mod){ return b?power(a*a%mod,b/2,mod)*(b%2?a:1)%mod:1; } ll cal(ll n){ ll cnt=1; while(n){ n=n%__builtin_popcount(n); cnt++; } return cnt; } int main(){ int n;cin>>n; string x;cin>>x; ll ans1=0,ans2=0,cnt=0,ans; for(int i=0;i<n;i++){ if(x[i]=='1') cnt++; } if(cnt>1){ for(int i=0;i<n;i++) if(x[i]=='1'){ ans1=(ans1+power(2,n-i-1,cnt+1))%(cnt+1),ans2=(ans2+power(2,n-i-1,cnt-1))%(cnt-1); } for(int i=0;i<n;i++){ if(x[i]=='1'){ ans=(ans2+((cnt-1)-power(2,n-i-1,cnt-1)%(cnt-1))%(cnt-1))%(cnt-1); cout<<cal(ans)<<endl; } else{ //cout<<ans1; ans=(ans1+power(2,n-i-1,cnt+1)%(cnt+1))%(cnt+1); //cout<<' '<<ans<<endl; cout<<cal(ans)<<endl; } } } else if(cnt){ for(int i=0;i<n;i++) if(x[i]=='1') ans1=power(2,n-i-1,cnt+1)%(cnt+1); for(int i=0;i<n;i++){ if(x[i]=='0'){ ans=(ans1+power(2,n-i-1,cnt+1)%(cnt+1))%(cnt+1); cout<<cal(ans)<<endl; } else{ cout<<'0'<<endl; } } } else{ for(int i=0;i<n;i++) cout<<'1'<<endl; } return 0; }
原文链接: https://www.cnblogs.com/asunayi/p/13330346.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/367577
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!