首页 > 其他分享 >ABC077D / ARC084B Small Multiple 题解

ABC077D / ARC084B Small Multiple 题解

时间:2024-08-20 15:38:42浏览次数:9  
标签:10 int 题解 dd ARC084B vec Small include dis

AtCoder Luogu

考虑数位和的来源:从 \(1\) 开始进行若干次 \(\times 10\) 和 \(+1\) 操作可以得到任意正整数,此时 \(+1\) 操作的次数为其数字和。注意不能连续进行 \(10\) 次及以上 \(+1\) 操作。

不难列出转移,设 \(f(i)\) 表示 \(i\) 的数字和,则:

  • \(f(10 i) = f(i)\)
  • \(f(i + 1) = f(i) + 1\)

考虑题目求 \(k\) 的正整数倍,使用 同余最短路,在模 \(k\) 意义下建图:

  • \(i \xrightarrow{0} 10 i\)
  • \(i \xrightarrow{1} i+1\)

答案即为 \(1\) 到 \(0\) 的最短路。因为进行 \(10\) 次及以上 \(+1\) 操作一定更劣,无需特别处理。

#include <iostream>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;

int n;
int dis[100005];
vector<pair<int, int>> vec[100005];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("ABC077D.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        vec[i].push_back({10 * i % n, 0});
        vec[i].push_back({(i + 1) % n, 1});
    }
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({1, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d != dis[u])
            continue;
        for (auto [v, w] : vec[u]) {
            int dd = d + w;
            if (dd < dis[v]) {
                dis[v] = dd;
                q.push({dd, v});
            }
        }
    }
    cout << dis[0] << endl;
    return 0;
}

标签:10,int,题解,dd,ARC084B,vec,Small,include,dis
From: https://www.cnblogs.com/bluewindde/p/18369542

相关文章

  • [AtCoder - tdpc_game] :ゲーム 题解
    [AtCoder-tdpc_game]:ゲーム题解一道小清新\(dp\)题。定义\(dp_{i,j}\)为第一堆山还有\(i\)个物品,第二堆山还有\(j\)个物品,すぬけ君能取得物品的最大价值。由于只能取两座山最上面的物品,假设当前两座山分别有\({x,y}\)个物品,すぬけ君选后只能有两种情况,分别为\(d......
  • 题解:P10279 [USACO24OPEN] The 'Winning' Gene S
    思路建议升蓝。算法一考虑暴力。我们先枚举\(K,L\),考虑如何求解。直接枚举每一个\(K\)-mer,再枚举里面的每一个长度为\(L\)的子串,找到最大的子串并在起始部分打一个标记。最后直接看有几个地方被打标记就行。时间复杂度:\(O(n^4)\)。预计能过测试点\(1-4\)。算法二我们......
  • [题解]P4052 [JSOI2007] 文本生成器
    P4052[JSOI2007]文本生成器正难则反,我们发现用总字符串个数\(26^m\),减去不可读的字符串个数,就是答案。要使一个字符串不可读,就不能让任何模式串在其中出现。如果某个主串的第\(i\)位与自动机的节点\(j\)相匹配,那么如果状态\(j\)包含模式串(即有一个前缀是一个模式串),那么不管主......
  • 关系代数、函数依赖、Armstrong公理及软考试题解析
    注:本文面向于软考高级—系统架构设计师,具体来说是数据库部分,知识点偏零碎化。想要系统学习数据库原理的,可考虑去看《数据库原理》,清华大学出版社或其他出版社皆可。概述概念关系,就是二维表。特性:列不可分性:关系中每一列都是不可再分的属性,即不能出现如下复合属性行列无序性:......
  • P1543 [POI2004] SZP 题解
    P1543[POI2004]SZP题解传送门。题目简述有\(n\)个人,每个人都会监视另一个人,要求选出尽可能多的同学,使得选出的每一名同学都必定会被监视到。且选出的同学不可再监视其他人。思路简述因为任意一个人只能被另一个人管,那么就想到,如果没人管的同学就不能被选(不被监视)。若某......
  • 题解:[TJOI2018] 游园会
    所谓dp套dp,实际上就是在说求解一个dp的过程中,我们用另一个dp求解出他应该从某个状态转移到另一个状态。考虑一下这道题,首先求LCS的dp如下:\[dp_{i,j}=\max\{dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1}+[s_i==t_j]\}\]显然,当\(i\)固定的时候,\(dp_{i,j}\)是单调不降的,且相邻两......
  • 【LGR-196-Div.4】洛谷入门赛 #26 题A - H 详细题解--优化思路简洁代码(C++,Python语
    前言:    觉得这个比赛很有意思的,都是暴力题,涉及一些细节,难度比较适合刚学编程语言的,可以很好的锻炼基础还有手速,最后两题也是比较有意思,之后也准备更新atc的比赛题解和洛谷的一些高质量比赛题解(算法网瘾就是想参加各种比赛)   如果觉得有帮助,或者觉得我写的好,......
  • [NOI]2024 登山 题解
    好像在洛谷题解区里还没人和我做法一样,,?考场做法,只用到了倍增和线段树,感觉挺好写。考场上从开题到过题只用了2h。最底下有省流版(?)。以下是我考场里比较详细的思路,所以比较长。先考虑如何\(O(n^2)\)做,然后再想优化。容易先想到一个状态数是\(O(n^2)\)的DP,即记录起点,并将向......
  • AGC002 题解
    目录A-RangeProductB-BoxandBallC-KnotPuzzleA-RangeProduct分情况讨论:\(a\le0\leb\)时,乘积一定为\(0\);否则:\(0<a\leb\)时,乘积一定为正;否则,负数的个数有\(b-a+1\)个,判断这个数是否为奇数,若是,乘积为负,否则为正。#include<bits/stdc++.h......
  • P10423题解
    P10423[蓝桥杯2024省B]填空问题先贴上答案#include<iostream>usingnamespacestd;intmain(){stringans[]={"1204","1100325199.77",};charT;cin>>T;cout<<ans[T-'A']......