1. 题目

传送门= ̄ω ̄=

题意:给出一个正整数 $K(K \in [2, 10 ^ 5])$,求一个正整数 $X$使得 $X \equiv 0 \mod K$且 $X$的各个位的数字之和最小(比如 $123$的各个位的数字之和为 $1 + 2 + 3 = 6$)

输出 $X$各个位的数字之和。

可以证明这个答案是唯一的(这不是废话吗)

2. 题解

考场碰到这题直接暴力了,我 TCL

实际上我把这题写个题解只是觉得 01BFS 很妙 OvO…

首先可以在模 $K$意义下连边:

  • $i$到 $i+1$连一条长度为 $1$的边(各个位数字之和 $+1$)
  • $i$到 $i \times 10$连一条长度为 $0$的边(各个位置数字之和不变)

(注意 $i + 1$和 $i \times 10$都是要对 $K$取模的)

然后从 $1$为起点跑一遍单源最短路即可。

最后输出 $dis[0] + 1$

如果最短路用 DIJ 复杂度是 $O(k log _ 2 k)$的

但是如果用 01BFS 就能做到 $O(k)$!

01BFS 能在 $O(n + m)$的复杂度内解决边权为 $0$或 $1$的图上的单源最短路问题。

具体实现很简单:

搞个双端队列,每次取出队首元素,从它开始扩展,如果下一条边长度为 $0$,则把这条边对应的后继节点插入到队首,如果为 $1$则插入到队尾。

这样我们能保证每次队首取出来的元素的 $dis$值是队列中最小的,思想就是和 DIJ 一样的,但是它没有 $log _ 2$,多棒~

注意这个 BFS 和普通的有所不同,01BFS 的 $dis$是该点作为队首元素时确定的,而不是第一次作为后继节点时确定的

具体看代码吧,代码很简单的 OvO…

(对了,实际上不推荐使用 STL 的 deque,慢得一匹。。。双端队列你手写是最好的,反正空间复杂度不超过时间复杂度,实在不行写个循环队列就行了。。。)

(要是实在是懒的话可以用 STL 的 list 都比这个好。。。dequelist 多一个 []运算符随机访问,类似于 vector

(被这玩意坑过)

代码:

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

int n, dis[NS];

deque<int> que;

bool book[NS];

int main(int argc, char const* argv[])
{
    freopen("num.in", "r", stdin), freopen("num.out", "w", stdout);
    scanf("%d", &n), memset(dis, 127, sizeof(dis));
    que.push_back(1), dis[1] = 1;
    while (!que.empty())
    {
        int F = que.front(); que.pop_front();
        if (book[F]) continue;
        book[F] = 1;
        if (dis[F * 10 % n] > dis[F])
            dis[F * 10 % n] = dis[F], que.push_front(F * 10 % n);
        if (dis[(F + 1) % n] > dis[F] + 1)
            dis[(F + 1) % n] = dis[F] + 1, que.push_back((F + 1) % n);
    }
    printf("%d\n", dis[0]);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注