算法挑战赛第二期题解

题目

  • 二进制小数的乘积~HC哥哥说这个很困！难！

  • Description

HC哥哥今天又突发奇想，它依然定义一个数字为二进制小数，如果它是一个正整数，并且其十进制表示中的所有数字都是0或1。例如，110 是一个二进制小数，而 102 和 787 不是。

现在HC哥哥给定你一个数 n，你被要求判断是否可能将 n 表示为一些（不一定是不同的）二进制小数的乘积。

  • Input

第一行包含一个整数 t（1≤t≤5⋅10^4）— 测试用例的数量。

每个测试用例的唯一一行包含一个整数 n（1≤n≤10^5）。

  • Output

对于每个测试用例，如果 n 可以表示为一些二进制小数的乘积，则输出 “YES”（不带引号），否则输出 “NO”（不带引号）。

  • 题目解释 （翻译成人话）

计算把01串强制转换为整数，再相乘得到的数就是合法的数字，其余都是不合法的。
那么直接打表就行了，总共1e5个数，打表还是很容易实现的

接下来我们来学习一下该怎么打表

打表

  • 定义 : 计算出所有情况，然后直接判断。

比如问你100以内的数是否是质数，你肯定能直接回答，因为你已经把100以内的质数全部背下来了。这其实就是打表的一种体现，你提前计算前100内的数是否是质数，然后直接调用答案。

但是我们的计算机实际上并不知道一个问题的所有解，那么你自己提前算好告诉它不就彳亍了吗。

这时我们需要两个重要程序：打表程序和判断程序。

打表程序

  • 用于计算所有情况的答案，不用关心时间复杂度，反正是提前计算

比如计算素数集，你直接暴力就好了，不会欧拉筛又有什么关系呢？

判断程序

  • 用于直接获得答案的程序，时间复杂度O(n),n为数据规模，每次查询的时间复杂度为O(1)。

接下来就该思考怎么写一个无脑的程序来计算这些情况了

做法

  • 首先先写一个无脑程序生成所有01组合的数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    vector<ll> ans;
    int main(){
        for(int i=1;i<=100000;i++){
            ll x=i,cnt=0,w=0;
            while(x){
                if(x%10<2) cnt++;
                w++;
                x/=10;
            }
            if(cnt==w) ans.push_back(i);
        }
        for(auto &i:ans)
            cout<<i<<",";
    }

此处是对每一位进行判断，如果01的个数和位数一样，那么就是一个合法的数字

  • 得到如下结果：

    1
    2
    3
    4
    5

    1,10,11,100,101,110,111,1000,1001,1010,
    1011,1100,1101,1110,1111,10000,10001,10010,
    10011,10100,10101,10110,10111,11000,11001,
    11010,11011,11100,11101,11110,11111,100000

  • 把以上结果复制进下一段生成代码，然后再计算所有合法的数字

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    ll number[1010]={0,1,10,11,100,101,110,111,1000,1001,
        1010,1011,1100,1101,1110,1111,10000,10001
        ,10010,10011,10100,10101,10110,10111,11000
        ,11001,11010,11011,11100,11101,11110,11111,100000};
    set<ll> s;
    ll dfs(ll n){
        s.insert(n);
        for(int i=2;i<=32;i++){
            if(n*number[i]<=100000)
               dfs(n*number[i]);
        }
        return 0;
    }
    signed main(){
        dfs(1);
        ll cnt=0;
        for(auto &i:s){
            cout<<i<<",";
            cnt++;
        }
        cout<<endl<<cnt<<endl;
        return 0;

    }

此处使用了dfs(Deep First Search)，文末会有详细介绍

  • 得到如下结果：

    1
    2
    3
    4
    5
    6
    7
    8
    1,10,11,100,101,110,111,121,1000
    ,1001,1010,1011,1100,1101,1110,
    1111,1210,1221,1331,10000,10001,
    10010,10011,10100,10101,10110,10111,
    10201,11000,11001,11010,11011,11100,
    11101,11110,11111,11121,11211,12100,
    12111,12210,12221,12321,13310,13431,
    14641,100000

  • 最后再是无脑的判断程序：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    vector<string> ans;
    ll a[1010]={0,1,10,11,100,101,110,111,121,1000,1001,1010,1011,1100,1101,
        1110,1111,1210,1221,1331,10000,10001,10010,10011,10100,10101,10110,
        10111,10201,11000,11001,11010,11011,11100,11101,11110,11111,11121,
        11211,12100,12111,12210,12221,12321,13310,13431,14641,100000};
    void solve(){
        ll x; cin>>x;
        for(int i=1;i<=47;i++){
            if(a[i]==x){
                ans.push_back("YES");
                return;
            }
        }
        ans.push_back("NO");
    }
    int main(){
        ll T; cin>>T;
        while(T--) solve();
        for(auto &i:ans)
            cout<<i<<endl;
    }

不是我说，这种做法在打表题目是真轮椅吧，时间复杂度完全没影响，计算出来总共就47个数字，简单版甚至20个都没到，非常适合不会搜索的蒻蒟(比如我)学习和理解。

下面是对dfs(Deep First Search)算法的详细介绍：

  • 什么是dfs？
    dfs是深度优先搜索的英文缩写，以深度为优先来进行计算

比如，要计算走n级楼梯（每次一到两级台阶）有几种走法，就可以使用dfs，假设第一次先走一步，依次遍历，如果能刚好走到n则方法数加1，如果超过了n则返回到上一步，回头找下一个方法。

  • 在本题的应用

那么在这题，我们已经提前计算了所有合法的数字，我们每次乘上可能的数字，看看是否依旧合法，之后在超过1e5时返回，相当于楼梯数为1e5，每次可以走number[1….n]步，但是每一个小于n的位置都合法，并存储答案。

如果想进一步了解dfs，可以访问OIwiki进行学习！

那么本期的题解就到此结束了，感谢阅读！如果想交流算法题，也可以添加我的qq哦(717056060)

关注ZestfulYK，谢谢喵！