模拟赛题讲解[5]

来自 Roundgod 2022-07-26 noi.ac #2678

题目描述：

对于任意非负整数 $x$ 和 $m(2\le m\le 10)$ ，定义 $f_m(x)$ 为 $x$ 在 $m$ 进制下的各位数字之和。给定两个整数 $k$ 和 $m$ 。你需要计算在所有满足是 $k$ 倍数的正数 $x$ 中,最小的 $f_m(x)$ 值是多少。

输入格式：

输入第一行包含两个整数 $k,m(2\le m\le 10)$ 。

输出格式：

在一行中输出一个整数，表示答案。

输入1：

5 10

输出1：

1

输入2：

79992 10

输出2：

36

输入3：

4 5

输出3：

4

数据范围：

对于 $30\%$ 的数据，$1\le k\le 100$

对于 $100\%$ 的数据，$1\le k\le 10^6$

题解：

尝试以最小的花费构造一个数使得其是 $k$ 的倍数

如果我们把这个构造的过程放在模 $k$ 的意义下

问题就转化为了，如何以最小的花费构造一个 $0$

设 $d_x,~x \in [0,k)$ 表示构造一个模 $k$ 意义下为 $x$ 的数的最小花费

然后尝试转移？

对于构造的数，我们可以乘 $m$ ，也可以加 $1$

前者对应的花费为 $0$ ，后者对应的花费为 $1$

为什么只加 $1$ 呢？因为加 $2$ 等价于两次加 $1$

于是，这个题就转化为了同余最短路

然后就是同余最短路，甚至不用 $\text{Dijkstra}$ ，直接01bfs就好了

考场直接打暴力骗分，至今不是很理解同余最短路，有待补充

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+15)

int k,m,d[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> k >> m;
    for(int i=0; i<k; i++) d[i]=INF;
    d[1]=1; deque<int> q;
    q.push_back(1);
    while(!q.empty())
    {
        int u=q.front(); q.pop_front();
        if(!u){return cout << d[0] << '\n',0;}
        int v=u*m%k; if(d[v]>d[u]){d[v]=d[u]; q.push_front(v);}
        v=(u+1)%k; if(d[v]>d[u]+1){d[v]=d[u]+1; q.push_back(v);}
    }
    cout << d[0] << '\n';
    return 0;
}