正解: 数位 $dp$
解题报告:
传送门 $w$ http://poj.org/problem?id=3252
沉迷写博客,,, 不想做题,,,$QAQ$ 口胡一时爽一直口胡一直爽 $QAQ$
先港下题目大意嗷 $QwQ$ 大概就说, 给定区间 $[l,r]$, 求区间内满足二进制中 0 的个数小于等于 1 的个数的数个数
数位 $dp$ 板子,,,?
首先区间转成 $[1,r]-[1,l-1]$ 然后十进制转二进制这个就不港了,,,
然后就考虑 $dfs$ 中要记录哪些东西 $QwQ$?
首先依然是一个 $pos$ 一个 $lim$, 因为 01 的个数对结果会有影响, 所以显然考虑还要记一个 $num$ 表示实际位数. 另外, 因为是要比较 01 个数多少, 所以显然还要有一维记录 01 数量的 (记一维就够了 $QwQ$, 当然为了方便记两维显然对 $dfs$ 不会有任何影响,,, 不写进真正的 $f$ 中就好 $QwQ$
然后 $return$ 的条件也不难想到昂, 一个 $pos==0$ 和一个 $f!=0$ 不说, 显然还有个就, 当 1 的数量大于 0 的数量加未填的数量时也可以 $return$ 了
然后就做完辣,,,?
$over$
代码是不会有代码的, 更新随缘, 欢迎催更 $QwQ$
来源: http://www.bubuko.com/infodetail-3089611.html