louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共16篇）

题解 - [JLOI2010]足彩投注

思路题目又臭又长,其实没有什么卵用....真正有用的只有那个式子.根据乘法原理,我们可以转换成这样: 于是设计状态表示当前进行到场,有场为 ,有场为 .因为都是级别的,所以总复杂度为 .最终结果可能会很大,最好不要用 double,用 long double...

期望概率动态规划

2019-12-01

1 770

题解 | 信息学奥赛一本通不要 62

思路比较套路的一道数位DP题.按照套路转换成前缀和.先预处理出表示第位为,位为,位及之前不需要考虑(可以看做全是)满足条件的数的个数.我们枚举位到最高位与相同,位小于的答案.发现不满足条件记得及时退出.最后答案别忘+1.复杂度为. 代码 #include<bits/stdc++.h> ...

动态规划数位动态规划

2019-09-05

0 644

题解 | 信息学奥赛一本通恨7不成妻

思路设计状态表示不大于的数中,满足个位数之和模为,该数模为的数的平方和.最后一维为表示等于上界,为表示小于上界.很明显平方和不方便直接转移,因为,我们可以同时维护满足条件的数的个数以及和,然后我们就可以快乐地转移啦.我们在转移的同时去除那些有一位为的数,枚举下一位是啥转移即可.具体操作参考代码.时...

数位动态规划动态规划

2019-09-05

1 845

题解 | 信息学奥赛一本通 Windy 数

思路简单的数位DP题.预处理出表示位,最高位为的Windy数有多少.然后将范围转换为前缀和(这是有多套路qwq),从高位枚举到低位,加上选小于当前位的数的合法方案数,如果当前位到顶,继续枚举低位.然后别忘了最后答案+1.(一切都是多么经典qwq)算法复杂度为. 代码 #include<bit...

动态规划数位动态规划

2019-09-04

0 697

题解 | 信息学奥赛一本通Amount of Degrees

思路我们先用前缀和将问题转化为求范围内满足条件的数的个数-范围内满足条件的数个数.我们设当前我们在求范围内满足条件的数.我们可以考虑一棵二叉树,往左走表示第位为,往右走为.(表示深度;第位表示最高位,以此类推;这里是进制时).这样走到叶子节点都会得到一个数,我们的任务就是找出恰好往右走了次,结果得...

数位动态规划动态规划

2019-09-04

0 772

题解 | 信息学奥赛一本通股票交易

思路因为所有限制都是整数,中间过程参与运算的数字也肯定都是整数,而且数据范围允许,我们可以设计状态表示第天拥有支股票时相对初始状态最多有的钱.这天可以不买也不卖,所以的一种决策是.只有天前的状态有用,我们可以直接取的状态.(由于上一种转移,这肯定是最优的)然后这天要么买,要么卖,否则肯定不是最优的...

单调队列动态规划

2019-09-03

0 686

题解 | 信息学奥赛一本通 2^k 进制数

思路跑动态规划.表示第位的数位,前位已经确认的数的个数.转移应该挺好转移的,需要用前缀和优化一下.内存可能比较大,需要滚动数组.最后把满足要求的答案全部加起来就可以了.复杂度为,看起来比较大,实际上基本上跑不满,还是可以过的. 代码 #include<bits/stdc++.h> us...

高精度动态规划

2019-09-01

0 690

题解 | 算法竞赛进阶指南 Polygon

思路很明显的区间DP.环形处理可以使用枚举断哪条边(复杂度为,比较危险)或者复制一遍接在后面(复杂度为).这里采用后者.转移时乘法需要注意负数,因为负负得正可能反而比两个最大值相乘更大,因此需要同时记录区间能得到的最大值和最小值.加法转移:乘法转移:然后在取最大值即可. 代码 #include&l...

动态规划区间动态规划

2019-08-27

0 784

题解 | 算法竞赛进阶指南 Naptime

思路我们可以分情况讨论. 第N个小时正在休息这种情况就是一个DP题.设表示当前处理到第个小时,已经休息了个小时,最后一维为表示第个小时正在休息,否则不在休息.转移也不难: ,这个时刻不休息的话前面休不休息无所谓. ,这个时刻休息的话要考虑前一个小时休不休息.如果前一个小时休息的话这个小时休息是有...

动态规划

2019-08-27

0 594

题解 | 算法竞赛进阶指南赤壁之战

思路设计状态表示最后一个数为,长度为的严格递增子序列个数.我们可以轻松地推出转移方程: 注意到这两个限制是二维的,第一维直接按顺序枚举不断加入状态即可解决,第二维套一个树状数组即可解决.因为可能很大需要离散化.复杂度为看起来有点大,但是因为树状数组常数小,还是可以过的.实现中为了减小内存使用了滚动...

树状数组计数类动态规划动态规划

2019-08-26

0 780