【题目描述】
给定一个整数$k$.求一个$k$的整数倍$sum$,使得$sum$的数字和最小
题解
考试的时候想尽一切办法枚举,卡时 最多卡到70pts
其实如果把那几个最毒瘤的数放上去完全可以把暴力卡掉
正解是要建图跑最短路
考虑$sum$在模$k$意义下的值
我们建立$k$个节点 编号为$0\sim n-1$
对于每个$i$连一条$i$到$(i+1)\operatorname{mod} k$的边 边权为$1$表示$sum+1$数字和也$+1$
再连一条$i$到$i* 10\operatorname{mod} k$的边 边权为$0$表示$sum* 10$数字和不变
然后从节点$0$开始 因为第一步肯定走$0$到$1$的边(你让$0* 10$也没有意义) 所以跑一次节点$1$到节点$0$的最短路即可 到节点$0$时$sum$肯定是被$k$整除的 满足题意
有人可能会问 万一连续走了$10$次第一类边 导致加法进位了怎么办
由于我们是在图上跑最短路 连续走$10$次第一类边($sum+1+1+1\dots +1$) 边权和为$10$一定是不如走一次第一类边再走一次第二类边($(sum+1)* 10$) 到达的是图上的同一个点 但是第二种走法边权和仅为$1$所以$1$到$0$的最短路中一定不会有连续走$10$次第一类边的情况
所以此题的答案就是$0$号节点到$1$号节点的最短路长度+1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii;
inline int read() { int x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); return x * f; }
int n, ans; int head[100005], pre[2000005], to[2000005], val[2000005], sz; int dis[100005]; bool vis[100005];
inline void addedge(int u, int v, int w) { pre[++sz] = head[u]; head[u] = sz; to[sz] = v; val[sz] = w; }
priority_queue<pii, vector<pii> , greater<pii> > q;
inline void dijkstra(int st) { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); q.push(make_pair(0, st)); dis[st] = 1; while (!q.empty()) { int x = q.top().second; q.pop(); if (vis[x]) continue; else vis[x] = 1; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (dis[x] + val[i] < dis[y]) { dis[y] = dis[x] + val[i]; q.push(make_pair(dis[y], y)); } } } }
int main() { #ifdef ONLINE_JUDGE freopen("K.in", "r", stdin); freopen("K.out", "w", stdout); #endif n = read(); for (int i = 0; i < n; i++) { addedge(i, (i + 1) % n, 1); addedge(i, (i * 10) % n, 0); } dijkstra(1); printf("%d\n", dis[0]); return 0; }
|