首页 > 其他分享 >数位dp

数位dp

时间:2023-09-08 13:11:25浏览次数:40  
标签:limits 传送门 sum 考虑 个球 dp 数位

字面意思。

恨妻不成7

传送门


前面的限制按照题意模拟即可,然后考虑维护平方和的常用手段:

本来是 \(\sum a^2\),变成了 \(\sum (a+x)^2=\sum a^2+2ax+x^2=\sum a^2+2x\sum a +\sum x^2\),发现维护一下“和”与“个数”即可。

完美数

传送门


首先有一个性质就是 \(\prod [a_i|n]=[\text{lcm}(a_1,a_2,\cdots,a_k)|n]\)。

意思就是要满足题面上的对任意一个都整除就等价于整除它们的 lcm。

那么发现所有的组合的 lcm 只有 48 种,这样模数就可以保存了。

现在又有一个性质:若 \(m1|m2\) 则有 \(a\bmod m1=(a\bmod m2)\bmod m1\)。

所以其实不用存余数,可以直接存对 \(\text{lcm}(1\sim9)=2520\) 取模的结果。

Umnozak

传送门


各个数位上的乘积种类不是特别多,大概就 \(36100\) 种,然后考虑暴力枚举每一种取值,发现一定能写成 \(2^{k_1}3^{k_2}5^{k_3}7^{k_4}\) 的形式(因为都是 \(1\sim 9\) 乘起来的),所以状态数不多,稍微剪一下枝。

完美消除

传送门


首先考虑什么时候能取到最小操作数:假设这个数是 \(\overline{a_na_{n-1}\dots a_{2}a_{1}}\),考虑贪心,每次消除最长的一段相同的,不妨设这段是 \([l,r]\) 则把这一段变成 \(\max(a_{l-1},a_{r+1})\)。

考虑上述的贪心操作可以使用单调栈来维护,单调栈可以用一个大小为 \(2^9\) 的数来表示。

LIS数

传送门


考虑求 lis 的一种二分方法实际上是维护了一个元素不重(因为是严格上升的)序列,所以也可以用 \(2^9\) 的数压位,具体实现大概和“完美消除”差不多。

数对

传送门


考虑在位运算中高位的大小关系一定程度上决定了整个数的大小关系,所以可以像数位 dp 那样写,在做的过程中维护两个条件的成立与否即可。

Zhu的数学问题

传送门


和“数对”差不多,在针对于整数做加减法后虽然进退位的影响没有位运算那样大,但还是可以这么做,但是需要维护一下进退位的值,当上面传下来的大于等于 \(2\) 或者小于等于 \(-2\) 就可以直接不管了。

[SDOI2010]代码拍卖会

传送门


考虑把一个不下降的数拆成这样的形式:

\( 11111111111111111...11111+ \)

\( 111111...111+ \)

\( ... \)

发现这样可以算出每一种模数在长度为 \(1\sim n\) 之间的连续“11111”的出现次数(使用循环节),这样问题就变成了:有 \(p\) 种球,每种有不同的 \(g_i\) 个球,现在要从里面可重地选出 \(8\) 个(因为不能为 \(0\),所以先加一个长度为 \(n\) 的“11111”),问组合数。就是一个简单的 dp 问题了。

最后考虑一个小问题:从 \(n\) 个球中可重地选 \(m\) 个进行组合,问方案数。

这个问题可以抽象为这 \(n\) 个球排成一排,有 \(m\) 个板子,假如第 \(j\) 个板子放在了第 \(i\) 个球的后面就表示选的第 \(j\) 个是 \(i\),那么就变成了一个关于 \(n-1\) 个球分成可空的 \(m+1\) 组的方案数,就是 \(C_{(n-1)+(m+1)-1}^{(m+1)-1}=C_{n+m-1}^{m}\)。

【APIO2015】巴厘岛的雕塑

传送门


数据比较特殊,发现大致分为一下两种:

  1. \(n\le 100\)

  2. \(n\le 2000,A=1\)

考虑做一个贪心的操作从高位到低位确定答案在二进制表示下的所有位值。

不妨把答案设为一个 40 位的大整数,一开始是 \(2^{41}-1\),假设现在正在枚举从低到高的第 \(i\) 位,已经确定了 \(i+1\sim 40\) 位的值,这时候可以先把这一位设为 \(0\),看一下能否找到一种拆分方式使得每一段的和都被当前这个数包含(因为 \(1\sim i-1\) 都是 \(0\),如果这样能满足那么答案一定是当前数的子集)。

考虑如何判断:其实就是一个简单的 dp,在 \(n\le 100\) 的情况下可以直接 \(O(\frac{n^3}{w})\) 做,而在 \(n\le 2000\) 的情况下相当于只需要最小的段数即可,可以 \(O(n^2)\)。

数数

传送门


首先考虑一个数 \(\overline{a_na_{n-1}\dots a_2a_1}\) 的贡献:\(\sum\limits_{i=1}\limits^{n}s_{i-1}a_i(n-i+1),s_n=\sum\limits_{i=0}\limits^{n}b^i\)。

设 \(f(l,r)\) 表示子串 \([l,r]\) 的贡献,\(k\) 表示 \(\sum\limits_{i=1}\limits^{n}f(i,n)\)。现在考虑在最高位增加一个数 \(a_{n+1}\) 产生的贡献:\(\sum\limits_{i=1}\limits^{n+1}f(i,n+1)=a_{n+1}+\sum\limits_{i=1}\limits^{n}\left(f(i,n)+b^{n-i+1}a_{n+1}\right)=k+s_na_{n+1}\)。

总之,就是 \(k'=k+s_na_{n+1},ans'=ans+k'\)。

发现只需要维护一下 \(k,ans\) 和数字个数就能 \(O(bn)\) 解决了。又发现除了取 \(0\) 和 \(up\),其它的贡献可以一起算,复杂度变为 \(O(n)\)。

众数

传送门


考虑如何打暴力板子:直接传一个大小为 \(10\) 的数组表示当前所有数字出现的个数(不含前导 \(0\)),那么当 \(limit=lead=0\) 的时候,用 dp 算出剩下的的方案数,具体来说:设 \(f_{i,j}\) 表示前 \(i\) 种数(不含 \(d\)),放在了 \(j\) 个位置的方案数,有 \(f_{i,j}=\sum C_{j}^{k}f_{i-1,j-k}\),注意需要枚举 \(d\) 在后面放多少个否则无法判断后面每一种数的放置个数上限。

【SDOI2013 R1 Day2】淘金

传送门


和“Umnozak”非常像,考虑用那题的方法算出每种 \(f(n)\) 的值所对应的值的个数,然后跑二路归并。

标签:limits,传送门,sum,考虑,个球,dp,数位
From: https://www.cnblogs.com/Judgelight/p/17687310.html

相关文章

  • AtCoder Beginner Contest 318 - D(状压 dp)
    目录D-GeneralWeightedMaxMatchingD-GeneralWeightedMaxMatching题意给定无向图,边有边权。让你选择一组边,满足任意两边不相交且总边权和最大。顶点数$\le16$思路状压DP求解该问题状态:利用n位二进制表示每个顶点是否已经被选择,0表示该顶点未选,1表示当前......
  • 数位dp总结---LZM
    数位DP总结BY----LZM当你学会了数位DP,那么你会发现,在考场上,你也写不出来。首先给出一道例题:给出一个区间\([l,r]\),求出区间内每个数字的数位和,答案\(\bmod\998244353\),\(1\lel,r\le10^{18}\)。样例输入样例输出2469411考虑枚举......
  • IPD集成产品开发进阶:新产品立项CDP流程
    目录前言立项流程专栏目录作者简介前言CDP流程原本是IPD产品开发的前端流程。之所以拿到《产品经理进阶专栏》中来讲解:一是因为这个流程承接了市场管理(也就是MM流程)和产品开发这两个关键业务流。这其实就拉通了从市场(客户)中来,到满足客户需求中去的一个核心闭环。这就从企业流......
  • 用友畅捷通T+ DownloadProxy.aspx 任意文件读取漏洞
    漏洞描述用友畅捷通T+DownloadProxy.aspx文件存在任意文件读取漏洞,攻击者通过漏洞可以获取服务器上的敏感文件漏洞复现fofa语法:app="畅捷通-TPlus"登录页面如下POC:/tplus/SM/DTS/DownloadProxy.aspx?preload=1&Path=../../Web.Confignuclei批量yaml文件id:yonyou_cha......
  • 2023年9月NPDP产品经理国际认证报名,找弘博创新
    产品经理国际资格认证NPDP是新产品开发方面的认证,集理论、方法与实践为一体的全方位的知识体系,为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。  【认证机构】 产品开发与管理协会(PDMA)成立于1979年,是全球范围内产品开发与管理专业人士最杰出的倡导者,协助个人、企业......
  • 【题解】CF2600DP 选练(23.9.5-23.9.6)
    低情商:感觉是比较套路的高情商:十分educational!!!CF258DLittleElephantandBrokenSorting题目描述:有一个\([1,n]\)的排列\(a\),会进行\(m\)次操作,操作为交换\((a_i,a_j)\)。每次操作都有\(50\%\)的概率进行。求进行\(m\)次操作以后的期望逆序对个数。\(n,m\le1......
  • API NEWS | Jetpack WordPress插件存在API漏洞
    欢迎大家围观小阑精心整理的API安全最新资讯,在这里你能看到最专业、最前沿的API安全技术和产业资讯,我们提供关于全球API安全资讯与信息安全深度观察。本周,我们带来的分享如下:一篇关于JetpackWordPress插件存在API漏洞的文章一篇关于如何应对不断增长的API安全漏洞的文章一篇关于AP......
  • Linux应用编程_网络通信TCP/UDP
    (1)网络协议被分为5层 1)应用层:直接为用户的应用进程提供服务 HTTP协议,FTP协议,DNS,POP3,SNMP,Telnet 2)运输层(传输层):负责向两个主机中进程之间的通信提供服务 (基于TCP/UDP) (1)传输控制协议TCP(TransmissionControlProtocol): 1)数据传输的单位是报文段 2)面向......
  • 【原创】基于QT编写的支持IPv4/IPv6双协议栈,TCP/UDP双模式,DLL内存加载的模块化远控木
    本人已经本科毕业一年有余,在平常实习过程中,发现大佬都对我的本科毕设--双协议栈远控木马感兴趣。据我所知,目前流行的C2远控软件中,MSF支持IPv4和IPv6,但是MSF生成的单个木马只是支持其中的一种协议,而不是双协议栈。CobaltStrike目前尚无IPv6的使用案例。其他支持双协议栈的C2软件......
  • 《产品经理认证(NPDP)》读后感
     背景:2023年8月随着DevOps有效实施,IT内部终于打造了一条需求交付的流水线,部门的需求交付能力肉眼可见的增长,月度人均需求交付数量从原来的1.5干到了2.8。随即而来的产品经理的需求承接能力就成了新瓶颈,也是就说交付的速度变快了,产品经理的需求处理速度跟不上。正如雷军所说:......