首页 > 其他分享 >[AGC011E] Increasing Numbers

[AGC011E] Increasing Numbers

时间:2022-11-25 20:33:11浏览次数:63  
标签:10 dfrac sum AGC011E Numbers Increasing

\(\mathcal Link\)

思维题。

考虑将不降数不进位相加,则最终结果可以看成 \(\sum_{i=0}^\infty a_i\cdot 10^i\),其中 \(a_i>a_{i+1}\)。

显然,对于一种合法拆分,我们可以分成至少 \(\lceil \dfrac{a_0}{9} \rceil\) 个数字,所以我们要做的是让 \(a_0\) 最小。

考虑等价变换。将一种划分等价为

\[N=\sum_{i=1}^{a_0} \dfrac{10^{r_i}-1}{9} \]

\[9N+9a_0=\sum_{i=1}^{a_0} 10^{r_i} \]

可以发现 \(a_0\) 可行充要于左边数字和小于等于 \(a_0\) 且左边数字和与 \(a_0\) 模 \(9\) 同余。

发现答案不是很大,直接枚举即可。

标签:10,dfrac,sum,AGC011E,Numbers,Increasing
From: https://www.cnblogs.com/pref-ctrl27/p/16925594.html

相关文章

  • POJ3252 Round Numbers
    终于一遍就写对了.第一次没有注意读题导致了一个没有注意到什时候要开始统计.Code#include<iostream>#include<string>#defineintlonglongusingnamespacestd;......
  • [数学记录][sosdp]CF449D Jzzhu and Numbers
    前几天做arc时连做两道高维前缀和,今天去看dp题单时发现这东西居然叫sosdp,来刷一下板子。粘一篇找到的blog,感觉引入那里非常自然!linktoCF|linktoLuogu给......
  • [LeetCode] 2133. Check if Every Row and Column Contains All Numbers
    An nxn matrixis valid ifeveryrowandeverycolumncontains all theintegersfrom 1 to n (inclusive).Givenan nxn integermatrix matrix,re......
  • 738.单调递增的数字 monotone-increasing-digits
    问题描述738.单调递增的数字解题思路将该数字的每一位数字变成数组dec<int>的一部分,然后依次遍历,直到dec[i]>dec[i+1],然后将dec[i+1]及以后的数字都变成9,如果dec[......
  • UESTC 1272 Final Pan's prime numbers
    DescriptionFinalPanlikesprimenumbersverymuch.Oneday,hewanttofindthesuperprimenumbers.Aprimenumbers n(n>4)isasuperprimenumberonlyif ......
  • HUST 1600 Lucky Numbers
    DescriptionIsun lovesdigit4and8verymuch.Hethinksanumberisluckyonlyifthenumbersatisfythefollowingconditions: 1.      The......
  • k-Amazing Numbers
    题目:Youaregivenanarrayaconsistingofnintegersnumberedfrom1ton.Let’sdefinethek-amazingnumberofthearrayastheminimumnumberthatoccursin......
  • [??记录]arc137C Distinct Numbers
    这段时间第一道没能自己想出来的题。题意:给定\(n\)个数,二人玩游戏,每次把全局最大数减小并改成一个当前未出现的数,不能操作者败。求胜者。首先我们来研究一次操作时的情......
  • CodeForces - 914C Travelling Salesman and Special Numbers
    题意:给出一个二进制数a,每次操作将当前数变成其二进制下1的个数,若干次操作后可以将其变为1.给定k,求不大于a的数中,经过k次操作能变成1的数的数量。解:观察一下这个操作,可以求......
  • 300.longest-increasing-subsequence 最长递增子序列
    问题描述300.最长递增子序列解题思路关键在于,dp[i]表示什么含义便于解这道题,子序列不一定连续,所以为了便于求解,dp[i]应该表示为以nums[i-1]结尾的最长严格递增子序列......