Atcoder ARC084D Small Multiple

\(O(k)/O(k)\)

解法

标签：
建图 最短路

考虑对于一个数 \(x\)，考虑由它在末尾改变能产生哪些状态：

1. \(x+1\)，此时对应的数位和 \(+1\)
2. \(x\times 10\)，对应数位和不变

那直接把这些能到达状态缩成一条边，跑一个点的值是在 \(\bmod k\) 意义下数位和的最小值的最短路
初始值设成 \(dis_1=1\)，因为 \(k\ge 2\)，\(dis_1=1\) 绝对是最优解
最终答案即为 \(dis_0\)

边权只有 \(01\)，跑个 \(\operatorname{01BFS}\) 就行啦

Q：\(9+1=10\) 数位和 \(=1\) 啊？

A：能发现，\(10\) 明显有更简单的方法推来：\(1\times 10\)，这个状态一定会出现在 \(9+1\) 之前（\(dis_1=1,dis_9=9\)），所以不会挂掉

代码

# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int dis [N];
bool vis [N];
int main () {
	int k;
	scanf ("%d", & k);
	memset (dis, 0x3f, sizeof (dis));
	dis [1] = 1;
	deque <int> q;
	q .push_front (1);
	while (! q .empty ()) {
		int u = q .front ();
		q .pop_front ();
		if (vis [u]) {
			continue;
		}
		vis [u] = 1;
		int v_0 = (u * 10) % k;// * 10
		if (dis [u] < dis [v_0]) {
			dis [v_0] = dis [u];
			q .push_front (v_0);
		}	
		int v_1 = (u + 1) % k;// + 1
		if (dis [u] + 1 < dis [v_1]) {
			dis [v_1] = dis [u] + 1;
			q .push_back (v_1);
		}
	}
	printf ("%d", dis [0]);
	return 0;
}