题解：P6124 [NEERC 2015] Binary vs Decimal

· · 题解

分析

打个表或者通过直觉不难发现：新的数要在已有符合条件数的前面加1构造得到。因为10=5*2，在前面加数才能保证后面十进制和二进制的关系不被破坏。

我们考虑取出一个已经符合条件的数在前面添上1进行更新：

十进制: \overline{A}(i位)+\overline{100...0}(i位0)=\overline{1A}
二进制: \overline{XA}(i位)+\overline{Y0...00}(i位0)=\overline{ZA}
因为10^i=5^i\times2^i，所以Y\&1=1，十进制为二进制后缀当且仅当X\&1=0，即(A>>i)\&1=0，此时将A计入答案即可
否则，(A>>i)\&1=1，当前这个数A就不能通过+10^k(k>i)构造出新的合法数了。因为A+10^k十进制下第i位为0(因为i<k)，二进制下A第i位为1(即(A>>i)\&1=1)，10^k第i位为0(同上)，相加得1，不可能成立，标记一下，下次枚举到时跳过即可。

总体复杂度O(nl)

代码实现

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10003;
int n,m=1,M,f[N];//f[i]:上文提到的标记第i个答案是否能够生成新的答案
struct Bigint {//高精
    int len;
    vector <int> num;
    Bigint()=default;
    void clear(int size) {
        num.clear();
        num.resize(size+1);
        len=size;
    }
}d[N],p,tmp;
//d[i]:第i个符合要求的数
Bigint Bigint_add(const Bigint &a, const Bigint &b) {//高精加高精  
    Bigint res;
    res.clear(max(a.len,b.len)+1);
    for(int i=1; i<res.len; i++) {
        res.num[i]+=(i<=a.len?a.num[i]:0)+(i<=b.len?b.num[i]:0);
        if(res.num[i]>=10) {
            res.num[i+1]+=res.num[i]/10;
            res.num[i]%=10;
        }
    }
    while(res.len>1&&res.num[res.len]==0) res.len--, res.num.pop_back();
    return res;
}
Bigint Bigint_div2(Bigint a) {//高精右移操作  
    for(int i=a.len; i>=1; i--) {
        if(a.num[i]&1) a.num[i-1]+=10;
        a.num[i]>>=1;
    }
    if(a.len>1&&a.num[a.len]==0) a.len--, a.num.pop_back();
    return a;
}
Bigint Bigint_upd(const Bigint &a) {//更新p 相当于乘10
    Bigint res;
    res.clear(a.len+1);
    for(int i=1;i<res.len;i++) res.num[i]=0;
    res.num[res.len]=1;
    return res;
}
void print(const Bigint &a) {//高精输出
    for(int i=a.len;i>=1;i--) printf("%d",a.num[i]);
    return;
}
int main() {
    scanf("%d",&n);
    d[0].clear(1); d[0].num[1]=0;//0不计入总数 但可以用于更新
    d[1].clear(1); d[1].num[1]=1;
    p.clear(1); p.num[1]=1;
    for(int i=1;m<n;i++) {
        p=Bigint_upd(p);
        M=m;
        for(int j=0;j<=M;j++) {
            if(f[j]) continue;
            tmp=d[j];
            for(int k=1;k<=i;k++) tmp=Bigint_div2(tmp);//右移i位
            if(tmp.num[1]&1) f[j]=1;
            else {
                d[++m]=Bigint_add(d[j],p);
                if(m==n) break;
            }
        }
    }
    print(d[m]);
    return 0;
}

我知道我排版很丑 语言表达也很烂 不要喷我qwq