首页 > 其他分享 >CF908G New Year and Original Order 题解

CF908G New Year and Original Order 题解

时间:2024-08-09 20:52:11浏览次数:26  
标签:10 数字 题解 贡献 插入 CF908G Original

CF908C

定义 \(S(n)\) 为将 \(n\) 所有数位从小到大排序后得到的数,求 \(\sum_{i=1}^{n} S(i)\)

\(1 \leq n \leq 10^{700}\)

  • 看到这个题大部分人都会奔着数位 \(dp\) 的地方想

  • 但这个题的难度在于插入一个数后不好算贡献

  • 其实也挺好算的

  • \(dp\) 维护当前若干数字排完序的贡献,转移有三种情况

    • 选择更小的数字:在高位插入,没有贡献。

    • 选择更大的数字:在低位插入,贡献为 \(\times 10\)

    • 选择当前数字:在中间位插入,贡献不确定,继续递推

  • 最终复杂度 \(O(\log_{10}^2 n)\)

标签:10,数字,题解,贡献,插入,CF908G,Original
From: https://www.cnblogs.com/fox-konata/p/18351453

相关文章

  • CF641E Little Artem and Time Machine 题解
    题目传送门前置知识CDQ分治解法单点修改区间查询,但值域巨大,考虑离散化掉\(x\)。时刻\(t\)仍很大,考虑将其作为CDQ分治的第一维,然后套个CDQ分治即可,注意及时清空桶数组。代码CodeForces275382150#include<bits/stdc++.h>usingnamespacestd;#definelllonglon......
  • CF1209E2 Rotate Columns (hard version) 题解
    CF1209E2给定\(n\timesm\)的矩阵,可以对每一列进行若干次循环移位,求操作完成后每一行的最大值之和的最大值。\(1\leqn\leq12,1\leqm\leq2000\)这里\(m\)很大,但有一个很重要的性质这\(m\)列中只有最大的前\(n\)个会对答案产生贡献因此我们直接就把......
  • 【题解】ABC365(A~E)
    前四题30min切,然后T5死磕70min+几发小唐错,距离比赛结束还有16s交最后一发,AC了。目录A.LeapYear题目描述思路代码B.SecondBest题目描述思路代码C.TransportationExpenses题目描述思路代码D.AtCoderJanken3题目描述思路代码E.XorSigmaProblem题目描述思路代码A.Lea......
  • CF908E New Year and Entity Enumeration 题解
    CF908E给定\(m\),令\(M=2^m-1\)。给定\(\{0,1,\cdots,M\}\)的大小为\(n\)的子集\(T\),定义集合\(T\subseteqS\subseteq\{0,1,\cdots,M\}\)是好的当且仅当:\(a\inS\Rightarrowa\oplusM\inS\)\(a,b\inS\Rightarrowa\and\b\inS......
  • 题解:CF1209E1 Rotate Columns (easy version)
    题目传送门题意给出一个\(n\timesm\)的矩阵,我们可以对每一列进行循环位移,不限次数,最后求每一行的最大值之和。\(1\leqn\leq4,1\leqm\leq100\)思路注意到\(n\)的范围很小,那么我们也可以缩小\(m\)的范围。正确的方案显然是取整个矩阵的前\(n\)大值,并且将它......
  • CF1647F Madoka and Laziness 题解
    CF1647F给定排列\(p\),将其划分为两个单峰子序列,求两个单峰子序列的峰的组合的情况数。\(2\leqn\leq5\times10^5\)首先要注意到一个非常常见的地方:两个单峰子序列中的一个的峰值一定在整个排列\(p\)的最大值处这个非常显然,但并不注意到他的重要性,容易被忽视为......
  • 2024牛客暑期多校训练营8 I Haitang and Ranking 题解
    乱搞看到\(n=1e5\),时限3s,存在修改操作,很自然的想到根号分治。考虑按照时间分治。对每\(B\)个交换统一处理,\(B\)个交换最多有\(2B\)个元素改变状态,剩下都不变。那么只要对这\(2B\)元素内,暴力枚举,剩下的元素构建数据结构实现二维数点,平面内区间最值。因为\(a,b\)是不......
  • luogu题解:P10456 The Pilots Brothers' refrigerator【缺少 SPJ】
    思路此题题意酷似P10449.费解的开关。https://www.luogu.com.cn/problem/P10449不同之处便是状态连锁改变不同,但做法截然不同,此题是一个\(4\times4\)的矩阵。暴力枚举的复杂度是\(O(10^7)\),即\(2^{16}\times16\times16=16777216\),\(10^7\)的复杂度可以通......
  • P2901题解
    题目大意输出一张有向带权图前k短路的长度思路分析这是道k短路板子题我们可以用Astar算法来实现它OIwiki相关算法的网页简单来讲,Astar定义了一个估值函数f(x)=g(x)+h(x)g(x)表示由起点到达x点的路程(不一定是最短路),而h(x)则是终点到x点的最短路程这个估值函数可以预估从该......
  • Codeforces 165E Compatible Numbers 题解
    思路高维前缀和高维前缀和把数的二进制看成一个集合,二进制的每一位为\(1\)为全集\(V\)。根据题目描述,若两数\(a,b\)相容,则\(a\operatorname{and}b=0\),容易发现,\(b\in\complement_{V}a\),所以我们只需要用高维前缀和处理出\(\complement_{V}a\)的一个元素即可。......