CF1977B 题解

ikunTLE · 2024-06-03 20:51:10 · 题解

题目传送门

思路

对于任意一个整数，我们可以将其转为二进制并逆转。

可以发现如果第 A_i=A_{i+1}=1 ，即又两个 1 相邻，那么就会累加到 2，就需要考虑进位了。

例如：29 的二进制逆转后是 1,0,1,1,1，可以发现 A_3=A_4=1 时，满足了上述的条件，可以将 A_3 变成 -1，A_4 变成 0，将 A_5 加上 1。此时 A_5=2，需要进位。最终，整个序列变成了 1,0,-1,0,0,1。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=32+10;
int t,n,a[N];
void solve(int x){
    int cnt=0,ans=0;
    //如果将其反转，那么a数组就是x的二进制。所以不反转刚好起到了转成二进制并反转的作用
    while(x){
        a[++cnt]=(x&1);
        x>>=1;
    }
    a[cnt+1]=0;
    for(int i=1;i<=cnt;++i){
        if(a[i]==2)//进位
            a[i]=0,++a[i+1];
        if(a[i]==1&&a[i+1]==1)//判断当有连续两个1的情况
            a[i]=-1,a[i+1]=0,++a[i+2];
    }
    for(int i=1;i<=cnt+1;++i)
        if(a[i]) ans=i;//找到最终的位数
    printf("%d\n",ans);
    for(int i=1;i<=ans;++i)
        printf("%d ",a[i]);
    printf("\n");
    return;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        solve(n);
    }
    return 0;
}