CF1070A Find a Number 题解【BFS搜索】【同余】【图论】

点击量：120

    当时打这场ACM的时候是julao队友Mayfly做出来的，要把数位转化到图上去跑。

目录

Description

You are given two positive integers \(d\) and \(s\). Find minimal positive integer \(n\) which is divisible by \(d\) and has sum of digits equal to \(s\).

Input

The first line contains two positive integers \(d\) and \(s\ (1\le d\le 500,\ 1\le s\le 5000)\) separated by space.

Output

Print the required number or \(\tt -1\) if it doesn’t exist.

Examples

input

13 50

output

699998

input

61 2

output

1000000000000000000000000000001

input

15 50

output

-1

题意：

    给定正整数\(d\)和\(s\)，求出最小的一个\(x\)使得\(d|x\)且\(x_{(10)}\)的各位加起来等于\(s\)。如果无解输出\(\tt -1\)。

题解：

    这个题极短的描述以及精华的输入输出让人感觉啊这就是今年联赛duliuT1吧这题一定不简单，事实证明它的确需要一些套路。

    和AT3621类似，我们可以建有\(d\)个点的图来跑。跑什么呢？\(\tt AT\)那个题是求\(x_{(10)}\)数位和的最小值，可以转化为最短路。但是这个题要求\(x\)最小，直接跑最短路貌似行不通，但是我们可以爆搜啊这时考虑搜索。

    因为\(d\le 500,s\le 5000\)，如果我们只在图上建\(d=500\)个点，肯定存不下全部的状态，但是对于各位和超出\(s\)的肯定是无用状态。因此考虑存\(f[i][j]\)表示在\(i(i\in[0,d))\)号节点，各位和是\(s\)的方案是否存在。根据贪心，要求所得数的方案和字典序最小，因此我们转移按\(0\sim 9\)的顺序，每种方案我们只需要最早进队的那一个，我们把\(f\)置为\(1\)即可。

这里和AT那题不同的一点在于，那个题为了利用01BFS，把i向i×10连了一条0权边；而这个题直接在后面加
数字即可，因为状态数很少。

    然后我们将\((0,0)\)的初始状态入队即可，要保证队列中元素的层次性，即位数多的排在后面，各位和大于\(s\)的可以废除。最后取出\((d,s)\)，存下前驱输出方案即可。时间复杂度为\(O(ds)\)。

    这道题思路清晰，做法新颖，是一道数位方面的好题。（雾

Code：

#include<cstdio>
#include<cstring>
bool used[500][5050];
int pred[500][5050],pres[500][5050];
int pre[500][5050];
struct statu
{
    int d,s;
    statu(int d,int s)
    {
        this->d=d;
        this->s=s;
    }
    statu(){}
}q[2500000];
int l=0,r=0;
int stk[2500000],top=0;
int main()
{
    int d,s;
    scanf("%d%d",&d,&s);
    q[++r]=statu(0,0);
    while(l<r)
    {
        statu t=q[++l];
        if(t.d==0&&t.s==s)
        {
            d=0;
            while(pred[d][s]!=0||pres[d][s]!=0)
            {
                stk[++top]=pre[d][s];
                int tmp=pred[d][s];
                s=pres[d][s];
                d=tmp;
            }
            stk[++top]=pre[d][s];
            for(int i=top;i;--i)
                printf("%d",stk[i]);
            return 0;
        }
        for(int i=0;i<=9;++i)
            if(t.s+i<=s&&!used[(t.d*10+i)%d][t.s+i])
            {
                int gd=(t.d*10+i)%d,gs=t.s+i;
                used[gd][gs]=1;
                pred[gd][gs]=t.d;
                pres[gd][gs]=t.s;
                pre[gd][gs]=i;
                q[++r]=statu(gd,gs);
            }
    }
    puts("-1");
    return 0;
}