题解 AT3621 【[ARC084B] Small Multiple】

· · 题解

AT3621$ $ $ [ARC084B] $Small\ Multiple

link

难度虚高，大概绿题。

设 f(s) 为 s 各个位数上的和

我们要求的 ans 满足 ans\equiv 0\ \pmod k\ 且 \ f(ans) 最小

考虑 dp[i] 表示 \min {f(x)}\ (\ x \equiv i\pmod k)

怎么转移，

考虑在\ x (\ x \equiv i\pmod k) 后加上一个数 y(y \in [0,9]), 那么易得加上后的余数为

(x\times 10+y) \mod k

即

(i\times 10+y) \mod k

所以

dp[(i\times 10+y)\mod k] = \min (dp[i]+y)

有木有感觉和松弛操作的方程很像？

接下去就建图确定转移顺序，再跑一遍单源最短路径板子即可，答案即 dis[0]

边是 k 的 10 倍，复杂度带只 \log

\mathcal{O(k\log_{2} k)} code:($ 大半部分都是 dijkstra 板子，核心就几行 $) 
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
template <typename T>
inline void read(T &x) {
    char c = getchar(); int w = 1; x = 0;
    while (!isdigit(c))
        (c == '-') && (w = -w), c = getchar();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
    x *= w;
}

const int N = 100005;
int k, cnt = 0, dis[N], head[N];
struct edge {
    int dis, to, nxt;
} e[N<<4];//k的10倍，这里开了16倍
struct node {
    int u, d;
    node(int x, int y) : u(x), d(y) { }
    inline bool operator < (const node & a) const {
        return d > a.d;
    }
} ;
inline void add(int u, int v, int w) {
    e[++ cnt].dis = w; e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;
}
inline void Dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    priority_queue<node> q;
    q.push(node(s, 0));
    while (!q.empty()) {
        node h = q.top(); q.pop();
        int u = h.u, d = h.d;
        if (d != dis[u]) continue;
        for (register int i=head[u]; i; i=e[i].nxt) {
            int to = e[i].to;
            if (dis[u] + e[i].dis < dis[to]) {
                dis[to] = dis[u] + e[i].dis;
                q.push(node(to, dis[to]));
            }
        }
    }
    return;
}         //板子
signed main() {
    read(k);
    for (register int i=0; i<k; ++i)
        for (register int j=0; j<10; ++j) {
            add(i, (i*10+j)%k, j);
        }
    for (register int i=1; i<10; ++i)
        add(k, i%k, i);//建虚点,第一位不能为0
    Dijkstra(k);
    cout << dis[0];
    return 0;
}