题解 P2841 【A*B Problem】

唐一文 · 2020-01-30 15:24:36 · 题解

前言

题解区里的方法都太深奥了，蒟蒻看不懂

思路 && Code

受到UVA1189的启发，我们可以先求出01串，再算出B。

认为数据一定很水的我立马打了个dfs，开了个longlong准备水过去：

#include<bits/stdc++.h>
using namespace std;
int n;
long long minn=LONG_LONG_MAX;
void dfs(long long ans,int k){
    if(k==20){//超出long long范围
        return ;
    }
    if(ans>minn){//剪枝
        return ;
    }
    if(ans%n==0){
        minn=min(minn,ans);//求最小值
        return ;
    }
    dfs(10*ans,k+1);
    dfs(10*ans+1,k+1);
}
int main(){
    cin>>n;
    dfs(1,1);
    cout<<minn/n<<" "<<minn;
    return 0;
}

然而，是这样的：

还是老老实实打高精度吧

把高精度模板一套：

#include<bits/stdc++.h>
using namespace std;
int n;
inline int mod(string a1){//求余数
    register int i;
    int b=0,len=a1.size();
    for(i=0;i<len;++i){
        b=((b<<1)+(b<<3)+(a1[i]^48))%n;
    }
    return b;
}
inline string chu(string a1){//高精度除法
    register int i;
    int s[10001],b=0,len=a1.size();
    for(i=0;i<len;++i){
        s[i]=((b<<1)+(b<<3)+(a1[i]^48))/n;
        b=((b<<1)+(b<<3)+(a1[i]^48))%n;
    }
    i=0;
    while(!s[i] && i<len){
        ++i;
    }
    a1="";
    while(i<len){
        a1+=s[i]+'0';
        ++i;
    }
    return a1;
}
string minn;
inline bool pd(string x){//判断是否超过已找到的最小值
    int lx=x.size(),ly=minn.size();
    if(lx<ly){
        return false;
    }
    if(lx>ly){
        return true;
    }
    register int i;
    for(i=0;i<lx;++i){
        if(x[i]<minn[i]){
            return false;
        }
        else if(x[i]>minn[i]){
            return true;
        }
    }
    return false;
}
void dfs(string ans){
    if(pd(ans)){
        return ;
    }
    if(!mod(ans)){
        minn=ans;
        return ;
    }
    dfs(ans+"0");
    dfs(ans+"1");
}
int main(){
    register int i;
    scanf("%d",&n);
    for(i=1;i<37;++i){//1~9999中答案的最大值
    /*
    不难发现，n为9的倍数时，答案总是很大
    当n=9999时最大
    那么n=9*1111
    因为9|111111111
    有9个1
    而1111有4个1
    又因为4和9互质
    所以minn=111...111(4*9=36个1)
    */
        minn+="1";
    }
    dfs("1");
    cout<<chu(minn)<<" "<<minn;
    return 0;
}

内心想法：我终于又水过了一道水蓝题!

还会超时?

让我们重新看一下题目：
给出一个数A，你需要给出一个最小的数B，使得A与B的乘积只含有0和1

在学搜索时，求最小的答案一般用bfs更快
那么这题不就可以用bfs了吗

因为要求最小的，所以先插入0比先插入1更好
找到的满足条件的第1个数就是B

把dfs改成bfs：

#include<bits/stdc++.h>
using namespace std;
int n;
inline int mod(string a1){
    register int i;
    int b=0,len=a1.size();
    for(i=0;i<len;++i){
        b=((b<<1)+(b<<3)+(a1[i]^48))%n;
    }
    return b;
}
inline string chu(string a1){
    register int i,j;
    int s[10001],b=0,len=a1.size();
    for(i=0;i<len;++i){
        s[i]=((b<<1)+(b<<3)+(a1[i]^48))/n;
        b=((b<<1)+(b<<3)+(a1[i]^48))%n;
    }
    i=0;
    while(!s[i] && i<len){
        ++i;
    }
    a1="";
    while(i<len){
        a1+=s[i]+'0';
        ++i;
    }
    return a1;
}
string p;
queue<string>q;
int main(){
    register int i;
    scanf("%d",&n);
    //以下代码为改动了一点的bfs模板
    p="1";
    q.push(p);
    while(!q.empty()){
        p=q.front();
        q.pop();
        if(!mod(p)){ 
            cout<<chu(p)<<" "<<p;
            return 0;
        }
        q.push(p+"0");
        q.push(p+"1");
    }
    return 0;
}

这次总能过了吧?

可以发现，有些数模A同余
根据同余的性质可得，它们乘上同一个数后模A也同余
因为要求最小的数，所以只要取这些数中最小的那一个数
用一个bool数组即可实现

因为我们是从小到大搜索的
所以第一个出现的数就是最小的那一个

AC Code

#include<bits/stdc++.h>
using namespace std;
int n;
inline int mod(string a1){
    register int i;
    int b=0,len=a1.size();
    for(i=0;i<len;++i){
        b=((b<<1)+(b<<3)+(a1[i]^48))%n;
    }
    return b;
}
inline string chu(string a1){
    register int i,j;
    int s[10001],b=0,len=a1.size();
    for(i=0;i<len;++i){
        s[i]=((b<<1)+(b<<3)+(a1[i]^48))/n;
        b=((b<<1)+(b<<3)+(a1[i]^48))%n;
    }
    i=0;
    while(!s[i] && i<len){
        ++i;
    }
    a1="";
    while(i<len){
        a1+=s[i]+'0';
        ++i;
    }
    return a1;
}
string p;
bool v[10005];//判断是否重复出现余数
queue<string>q;
int main(){
    register int i;
    scanf("%d",&n);
    p="1";
    q.push(p);
    while(!q.empty()){
        p=q.front();
        q.pop();
        if(!mod(p)){ 
            cout<<chu(p)<<" "<<p;
            return 0;
        }
        if(!v[mod(p+"0")]){//如果没有出现过这个余数
            v[mod(p+"0")]=true;//这个数为最小的那一个，这个余数现在出现了，标记为true
            q.push(p+"0");
        }
        if(!v[mod(p+"1")]){//同上
            v[mod(p+"1")]=true;
            q.push(p+"1");
        }
    }
    return 0;
}

（° - °)ノ✿ 完结撒花~