louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共4篇）

题解 | 信息学奥赛一本通不要 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