首页 > 其他分享 >动态规划杂题选练

动态规划杂题选练

时间:2023-09-28 15:13:49浏览次数:34  
标签:贡献 枚举 选练 动态 杂题 我们 数位

\(\text{CF908G}\)

题目描述

给\(n<=10^{700}\),问1到n中每个数在各数位排序后得到的数的和。答案膜 \(1e9+7\) 。

思路点拨

不是很难,自己想一会可以想出来。

因为 \(n\) 比较大,所以我们考虑数位dp。因为每一种数组产生的贡献十分复杂,所以我们将每一数字拆开统计贡献。

如果我们认为 \(n\) 表示数字的位数,相信 \(O(10^2n^3)\) 是比较好的出的。我们枚举一个数字 \(d\) ,则状态 \(f_{i,j,k,l}\) 表示目前考虑到第 \(i\) 位,比 \(d\) 小的有 \(j\) 位,比 \(d\) 大的有 \(k\) 位,目前有没有超出限制的 \(l=0/1\) 。转移比较简单,直接枚举下一位填什么,变动一下状态即可。但是不可以通过本题。

我们更改一下状态,我们定义 \(f_{i,j,k}\) 表示目前考虑到第 \(i\) 位,大于等于枚举的数 \(d\) 有 \(j\) 个,是否超出 \(limit\) 的 \(k=0/1\) 。转移比较类似。这样怎么计算贡献呢?因为 \(6\) 的数位可以拆成 \(5\) 的贡献加上 \(1\) 的贡献。所以我们这么统计是可行的。

标签:贡献,枚举,选练,动态,杂题,我们,数位
From: https://www.cnblogs.com/Diavolo/p/17735821.html

相关文章

  • 随想录Day8|344. 反转字符串、541. 反转字符串Ⅱ、LCR 122. 路径加密、151. 反转字符
    随想录Day8|344.反转字符串、541.反转字符串Ⅱ、LCR122.路径加密、151.反转字符串里的单词、LCR182.动态口令 题目越来越长了…… 344.反转字符串文章&视频讲解编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数......
  • Modbus动态链接库供多语言使用 | Go
    Modbus协议控制动态链接库应用场景基于各门语言都有各自的modbus协议库,且良莠不齐,而且在具体的框架下可能存在版本依赖问题,而且对modbus协议存在比较多的细节处理,可以查看modbusslave、或者modbuspoll中相关的配置可知,数据类型对应读写寄存器个数、大小端的处理等等细节,所以......
  • JAVA代码使用JNI的方式调用C/C++动态库
    JNI(javanativeinterface),通过JNI的方式调用动态库步骤比较麻烦,不用额外引入依赖,对java项目工程依赖侵入为0,类中含有native描述的方法都会与动态库去一一映射,能通过System.load()函数去加载动态库,这种方式主要使用的场景是java写好类(一般不是接口),让C或者C++去实现......
  • dp动态规划
    数位dp离谱dp,常用于有位置与位置之间的限制并计数的问题中。通过记忆化搜索求出。代码大致模板:constintN=50;//数的最高位数,可以往大点开ints[N],tot;//栈用来存每位的数值intdp[N][2][2];//状态可能还会多一些,大致与Dfs状态同步inlineintDfs(intx,boolf......
  • [转载] linux下 GCC编译链接静态库&动态库
    转载自:https://www.cnblogs.com/thechosenone95/p/10605172.html#_label0静态库有时候需要把一组代码编译成一个库,这个库在很多项目中都要用到,例如libc就是这样一个库,我们在不同的程序中都会用到libc中的库函数(例如printf),也会用到libc中的变量(例如以后要讲到的environ变量)。......
  • vue3项目table表格动态表头生成+行数据合并
    这两处地方是动态的,由后端数据返回思路流程  1,后端返回数据二次处理  2,根据后端数据生成动态表头  3,利用antd的customRender与rowSpan设置行合并 完整代码<template><Table:data-source="dataSource":columns="columns":pagination="......
  • Redis系列 - Redis底层数据结构(简单动态字符串(SDS)、链表、字典、跳跃表、整数集合
    转自:https://blog.csdn.net/u011485472/article/details/109460490Redis系列-Redis底层数据结构(简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表)简单动态字符串(simpledynamicstring,SDS)链表字典跳跃表整数集合压缩列表RedisObject在介绍Redis底......
  • 动态规划——矩阵优化DP 学习笔记
    动态规划——矩阵优化DP学习笔记前置知识:矩阵、矩阵乘法。矩阵乘法优化线性递推斐波那契数列在斐波那契数列当中,\(f_1=f_2=1\),\(f_i=f_{i-1}+f_{i-2}\),求\(f_n\)。而分析式子可以知道,求\(f_k\)仅与\(f_{k-1}\)和\(f_{k-2}\)有关;所以我们设矩阵\(F_......
  • 动态规划——状压DP 学习笔记
    动态规划——状压DP学习笔记引入前置知识:位运算动态规划的过程是随着阶段的增长,在每个状态维度上不断扩展的。在任意时刻,已经求出最优解的状态与尚未求出最优解的状态在各维度上的分界点组成了DP扩展的“轮廓”。对于某些问题,我们需要在动态规划的“状态”中记录一个集合......
  • [剑指offer] 动态规划篇
    JZ42连续子数组的最大和/*贪心*/publicclassJZ42_1{publicstaticintFindGreatestSumOfSubArray(int[]array){intsum=0,res=Integer.MIN_VALUE;for(inti=0;i<array.length;i++){sum+=array[i];......