我来水个题解——基础第五题 Sramoc问题

常规
1

基础第5题 Sramoc问题，一遍过的题，但是有坑。

  • 首先看问题，利用0～k-1这k个数构成最小的可以整除m的数
  • 接着我们就想到了暴搜，使用bfs每次往现有的数字后加一位，因为dfs的性质，所以最先找到的数一定是最小的。（显然这样是过不了的
  • 但是我们可以发现 a≡≡b(mod m)，那么显然a×10+c≡≡b×10+c(mod m)。而我们又只需要最小的答案，所以当一个数的模数曾经出现过，我们就不需要这个数了。
    可是，这么写会有大问题！！！
    因为最后一个点超大，所以longlong也会爆。
    所以我们进一步想，由之前提到的a≡b(mod m)而a×10+c≡b×10+c(mod m)，我们没有必要把整个数放入队列，只需放对m的模数就ok，最后为了输出，保存每个数的father和这时选的是哪个数，反向输出就OK。
    然后，放代码：
void bfs(){
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<k;i++){
			int to=(now*10+i)%m;
			if (mod[to]==0){
				mod[to]=1;
                which[to]=i;
                fa[to]=now;
				q.push(to);
				if (to==0){
                    out(to);
                    return;
                }
			}
		}
	}
}

为了防止抄袭，这里只放bfs代码
好了，完事了。
image

3 个赞