Codeforces Round #554 (Div. 2) 1152B. Neko Performs Cat Furrier Transform

时间:2021-06-30 04:56:30
学了这么久,来打一次CF看看自己学的怎么样吧

too young too simple

1152B. Neko Performs Cat Furrier Transform

题目链接:"https://codeforces.com/contest/1152/problem/B"

题目大意:将数字经过一系列的处理 (轮流进行加法操作和异或操作且加数和异或数有要求,加法只能加一,异或只能对2的n次方-1异或)( + ^ + ^ + ^ + ^ ......) 后变成——在二进制表示下从最高位到最低位都是1。比如

       39     →   56   →   57    →   62   →   63
0010 0111→0011 1000→0011 1001→0011 1110→0011 1111

题目思路:从最高位开始把0变成1(因为对更小的数进行异或操作只会对低位影响而不会对高位有影响)

代码如下

#include<bits/stdc++.h>
using namespace std;
int main()
{
int x,xx,op=0,j=0,opp=0;
int ans[50]={0};
cin>>x;
while(1)
{
xx=x;
int sum=0,man=0;
for(int i=0;xx!=1;i++){
if(xx%2==1)man++;
xx>>=1;
sum++;
} if(sum==man)break; xx=x;
for(int i=0;xx!=1;i++){
if(xx%2==0)op=i;
xx>>=1;
}
int er=1;
for(int i=0;i<=op;i++)er*=2;
x=x^(er-1);
opp++;
ans[j++]=op;
xx=x;
man=0;
sum=0;
for(int i=0;xx!=1;i++){
if(xx%2==1)man++;
xx>>=1;
sum++;
}
if(sum==man)break;
x=x+1;
opp++;
}
printf("%d\n",opp);
for(int i=0;i<j;i++)printf("%d ",ans[i]+1);
return 0;
}