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

发表评论

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

你是机器人吗? =。= *