Find a Number CodeForces – 1070A(记忆化 BFS)

题目链接:https://cn.vjudge.net/problem/CodeForces-1070A
题目大意:让你构造一个数字,要求数位之和等于 s 且能被 d 整除并且尽可能地小。

记忆化bfs,vis标记数组第一维是取模后的数,第二维是数位之和,这样保证相同的数位之和模后相同的数只判断一次,又因为每一位都是从0到9的BFS所以一定是最小的。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int d,s;
bool vis[550][5500];
int pre[550][5050][5];
void bfs()
{
    queue<int>mod,sum;
    vis[0][0]=1;
    mod.push(0);
    sum.push(0);
    while(!mod.empty())
    {
        int pre_mod=mod.front();
        mod.pop();
        int pre_sum=sum.front();
        sum.pop();
        int t_mod,t_sum;
        for(int i=0;i<=9;i++)
        {
            t_mod=(pre_mod*10+i)%d;
            t_sum=pre_sum+i;
            if(t_sum>s||vis[t_mod][t_sum])
                continue;
            vis[t_mod][t_sum]=1;
            pre[t_mod][t_sum][0]=pre_mod;
            pre[t_mod][t_sum][1]=pre_sum;
            pre[t_mod][t_sum][2]=i;
            mod.push(t_mod);
            sum.push(t_sum);
        }
    }
}

void print(int mod,int sum)
{
    if(mod==0&&sum==0)
        return;
    print(pre[mod][sum][0],pre[mod][sum][1]);
    cout<<pre[mod][sum][2];
}

int main()
{
    cin>>d>>s;
    bfs();
    if(!vis[0][s])
    {
        cout<<"-1"<<endl;
    }
    else print(0,s);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注