当前位置: 首页 > news >正文

AT_arc084_b [ABC077D] Small Multiple 题目分析

题目描述

给定一个整数 \(K\)。求一个 \(K\) 的正整数倍 \(S\),使得 \(S\) 的数位累加和最小。

  • \(2 \le K \le {10}^5\)
  • \(K\) 是整数。

分析

一个很妙的思路就是暴力。

考虑什么时候会对答案多 \(1\)。无非就是某一位 \(+1\)

如果没有变化就是 \(\times 10\)

我们发现这样做一定可以把所有的情况搞到。

本质上就是一个 01 bfs 求最短路。

代码

时间复杂度 \(\mathcal{O}(k)\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#define int long long
#define PII pair<int,int> 
#define N 100005
using namespace std;
int k,b[N];
deque<PII> q;
bool vis[N];
signed main(){cin >> k;q.push_back({1,1});while(!q.empty()) {auto t = q.front();q.pop_front();if (vis[t.first]) continue;vis[t.first] = 1; if (t.first == 0) return cout << t.second,0;if (t.first % 10 < 9) q.push_back({t.first + 1,t.second + 1});q.push_front({t.first * 10 % k,t.second});}return 0; 
}
http://www.hskmm.com/?act=detail&tid=23125

相关文章:

  • 287. 寻找重复数
  • 福州市 2025 国庆集训 Day2 前三题题解
  • 2025 年马赛克厂家 TOP 企业品牌推荐排行榜,陶瓷,游泳池,喷墨,冰裂,拼花,防滑,复古,家装马赛克推荐这十家公司!
  • oppoR9m刷Linux系统: 手动备份系统与基带IMEI/NVRAM/QCN
  • 原来你是这样的claude code aciton:没想象中好
  • 实用指南:【Python】正则表达式
  • FlareOn1 -- 5get_it
  • 2025 年阀门厂家 TOP 企业品牌推荐排行榜,管道阀门,气动,调节,电动执行器,生产,电磁,不锈钢,进口,耐高温阀门推荐这十家公司
  • 深入解析:Ceph 分布式存储学习笔记(二):池管理、认证和授权管理与集群配置(下)
  • tcp与udp 协议 - 摘星
  • 赛前训练4 extra 字典树
  • CF1450E Capitalism
  • 二分图最大匹配 匈牙利算法
  • 2025 年脱硫剂厂家 TOP 企业品牌推荐排行榜,氧化铁,羟基氧化铁,常温氧化铁,沼气,天然气,煤气,煤层气,液化气,二氧化碳,氨气脱硫剂公司推荐
  • 2025 年砝码厂家 TOP 企业品牌推荐排行榜,不锈钢,标准,校准,天平,无磁,锁型,蓬莱,铸铁,定制,单双钩砝码公司推荐!
  • Java 在Word 文档中添加批注:高效文档协作的利器 - 指南
  • 2025雨棚生产厂家 TOP 企业品牌推荐排行榜,西安,陕西,西北推拉雨棚,推拉,移动,活动,户外,电动伸缩雨棚推荐这十家公司!
  • 关于整除分块
  • 2025 年木工机械设备厂家 TOP 企业品牌推荐排行榜,深度剖析木工机械设备推荐这十家公司!
  • Python语言自动玩游戏的消消乐游戏程序代码3QZQ
  • Python语言自动玩游戏的数字拼图游戏程序代码ZXQMQZQ
  • 如何找出集合的两个子集使得和相等?
  • Python语言自动玩游戏的俄罗斯方块游戏程序代码QZQ
  • Spring AI(七)Spring AI 的RAG搭建集合火山向量模型+阿里云Tair(企业版)
  • Python语言自动玩游戏的数字拼图游戏程序代码QZQ
  • 赛前训练4 字符串哈希
  • 英语
  • 处处吻
  • ThreadLocal原理与使用详解
  • WinCC监控框架实战解析:打通物联网网关的关键步骤