Solution
本来想的是枚举 \(d\) 的倍数的,以为一定能搜到解的,然后看了眼英文发现“无解输出-1”,就果断去想搜索了。
用啥搜?
因为这个题要求最小数 \(n\) ,所以不能用dfs,应该用bfs+记忆化搜索,这样是可以保证最小的。
然后设计搜啥?
因为只和各位相加和 \(s\) 与 \(d|n\) 有关,所以可以将原来bfs换成存储此时数字和此时各位之和,往下搜就是从 \(0\)~\(9\) 枚举增加的这一位。同时拿一个数组 \(p[dx][dy]\) 记录当数字是 \(dx\) ,数位之和是 \(dy\) ,储存从 \(x,y\) 这个状态而来,枚举的 \(i\) 。拿 \(pair\) 就行了。
是不是这样就完了?
当然不是。当你建 \(p\) 数组的时候,你就会又和我本来的枚举想法一样,不知道要建多大。想先打个过样例的,发现样例二自己就不行了。所以要优化,可以将第一维转化为数字 \(\%d\) 的值,因为bfs所以答案还是对的。
空间复杂度: \(O(ns)\)
代码
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int D=510,S=5010;
int d,s;
bool vis[D][S];
queue<PII> q;
pair<PII,int> p[D][S];
inline void bfs(){
vis[0][0]=true;
q.push(make_pair(0,0));
while(!q.empty()){
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=0;i<10;i++){
int dx=(x*10+i)%d,dy=y+i;
if(dy<=s&&!vis[dx][dy]){
vis[dx][dy]=true;
p[dx][dy]=make_pair(make_pair(x,y),i);
q.push(make_pair(dx,dy));
}
}
}
}
void print(int x,int y){ //注意这里的输出和我的记录方式是对应的
if(!x&&!y) return ;
print(p[x][y].first.first,p[x][y].first.second);
putchar('0'+p[x][y].second);
}
int main(){
scanf("%d%d",&d,&s);
bfs();
if(!vis[0][s]) puts("-1");
else print(0,s);
return 0;
}