题解 P6380 【『MdOI R2』Mayuri】

· · 题解

看了看题解区的题解，纠结了一下还是把官方题解发出来吧。

感觉做的都比较麻烦，仅有的几个贪心写法的基本也都没给证明。

以下是官方题解。

首先，我们分析输出 -1 的情况。

容易发现，当 a=10 并且 S 的第一个字符为 1 时显然无解，具体证明同样例二。

除此以外的情况都是有解的。证明如下：

对于 1 位数的情况，显然有解。

假设对于 k(k\ge 1) 位有解，则对于 k+1 位一定有解。

假设 k 满足前位的一个数为 c，

则只需证明 c\times 10,c\times 10+1\ldots c\times 10+9 中必有一个数为 a 的倍数，且必有一个不为 a 的倍数。

熟知对于任意正整数 m，相邻的 m 个正整数中，必有 1 个数为 m 的倍数，m-1 个数不为 m 的倍数。

由于 a\ge 2，c\times 10,c\times 10+1\ldots c\times 10+a-1 为 a 个相邻的整数，

故它们中必定有一个数为 a 的倍数，a-1(a-1\ge 1) 个不为 a 的倍数。

故在接下来的讨论中排除无解的情况。

Subtask 1:

由于 n 是正整数，在字符串长度为 1 位的情况下，如果输入的串是 0 ，则 1 显然是最小的答案。

如果输入的串是 1 ，则显然直接输出 a 是最小的，因为 a 的最小倍数就是 a 本身。

Subtask 2:

对于 n 为两位数的情况，我们可以选择直接打表，直接算出每种可能的对应最小解。

我们也可以采用枚举所有两位数逐个判断的方式。

当我们判断某一个数是否符合条件时，我们通过除以 10 的方式得到其第一位，并判断其是否整除 a。

如果第一位符合条件，我们再直接判断其是否整除 a 以判断前 2 位是否满足条件。

Subtask 3:

与上面的做法相似，直接枚举所有 6 位数。

不同的是对于每一个数我们要判断 6 次。

我们通过除以 100000 得到其第一位，通过除以 10000 得到其前两位构成的数，以此类推。

对于每个数，逐一判断。先分离其第一位判断是否满足条件，若满足则分离前两位，以此类推。

由于 6 位数一共只有 900000 个，因此我们只需要经过不超过 900000 次枚举就可以找到符合条件的数。

Subtask 4:

要判断一个数是否是 2 的倍数只需要判断最后一位是否为 2 的倍数 。

所以我们可以考虑从高位开始往后添加数字。

如果某一位是 1 ，则我们需要添加的数字是 2\ 4\ 6\ 8\ 0 中的一个。本着最小的原则，我们选择 0 。

同理，如果某一位是 0 则我们选择添加一个 1。

另外，如果字符串的第一位是 1 ，则我们需要进行特判。

Subtask 5:

考虑延续上面的做法，从高位往后添加数字。

由于我们是在高位上添加的，因此我们只需保证我们添加的数字最小，就一定是最优的。

对于第一位，如果第一位的字符是 0 则我们添加 1 最优，否则第一位添加 a 最优。

然后对于后面的每一位，设我们当前的数是 n_1 ，添加的数是 j ，则得到的数是 10\times n_1+j。

由于 j 只有十种可能性，分别枚举尝试，选取最小的加到数的尾端。

另外，由于 n 过大，无法直接记录，故每添加一个数后对 a 取模，然后输出时以字符串的方式输出。

以下是 std 代码。

#include <bits/stdc++.h>
using namespace std;
char c[100005],n[100005];
int a,b;
int now;
int main(){

    cin>>a>>b>>c;
    if(c[0]=='0')n[0]='1',now=1;
    else{
        if(a==10){
            puts("-1");
            return 0;
        }
        else n[0]=a+'0';
    };
    for(int i=1;i<b;i++){
        now*=10;
        for(int j=0;j<=9;j++)
        if((now+j)%a==0&&c[i]=='1'||(now+j)%a!=0&&c[i]=='0'){
            now+=j;
            now%=a;
            n[i]=j+'0';
            break;
        }
    }
    cout<<n;
    return 0;
}