hiho一下第158周《Invalid Binary Numbers》题目分析

12
1

《非法二进制数》题目分析

本题是一道动态规划题目。

阶段的划分比较明显,直接按照位数划分即可,换句话说我们要依次算出1位、2位、3位……非法二进制数的数目。

之后是状态的设计。有经验的同学能一步到位设计出合理的状态,我们这里介绍一种“缺啥补啥”的思路。

首先我们直接从问题出发,用f[i]表示i位非法二进制数的数目。然后我们想一想能不能用f[1], f[2] ... f[i-1]求出f[i]。

如果X的第i位是0,那么X是i位非法二进制数当且仅当X的前i-1位是个非法二进制数。

如果X的第i位是1,那么X是i位非法二进制数当且仅当以下2种情况:

  1. X的前i-1位是个非法二进制数
  2. X的前i-1位是个合法二进制数,并且X第i-1位是1

注意到以上两种情况是互斥的,所以我们只需对以上两种情况求和即可。

综合上面的讨论,可以发现我们要求f[i],需要知道:

  1. i-1位非法二进制数的数目,这个我们已经知道是f[i-1]
  2. i-1位末位是1的合法二进制数数目,这个目前我们不知道

对于不知道的量我们就设个变量表示,比如用g[i]表示“i位二进制数中末位是1的合法二进制数数目”。这样我们的问题就变成了如何求g[i]。

假设Y是个i位二进制数中末位是1的合法二进制数。那么Y的前i-1位必须是个末位是0的合法二进制数。

我们用h[i]表示末位是0的i位合法二进制数的数目。考虑到h[i]应该是所有i位二进制数的数目(2^i),减去非法二进制数的数目(f[i]),再减去合法二进制数中末位是1的二进制数(g[i]),所以h[i] = 2^i - f[i] - g[i]。

于是我们就有了边界条件:f[1] = 0, g[1] = 1, h[1] = 1

以及递推方程:

f[i] = f[i-1] * 2 + g[i-1]
g[i] = h[i-1]
h[i] = 2^i - f[i] - g[i]

最后在实现代码的时候需要注意对10^9+7取模。

以上就是我们“缺啥补啥”的设计状态的思路。当然本题还有很多不同的状态表示方法,大家可以多思考思考。

15 answer(s)

3

这道题目归纳法对合法数归纳更加容易理解啊,刚好合法数的排列是斐波那契数列。 记合法数的个数是f(n) f(n+1) = f(n) + f(n-1) (n位的合法数后补0 以及 n-1位的合法数补01)

1

直接数位dp暴力冲掉了

3

第一次在这上面写题。。。这一题感觉就是一个找规律的,后面再处理的时候用到了快速幂; 通过打表前32位数字,可以看出: a[1]=0; a[2]=1; a[3]=3; a[4]=8; a[5]=19; 其中a[4]:0000~0111的非法二进制数个数就是a[3]; 1000~1011的非法二进制数个数就是a[2]; 1100~1111的非法二进制数个数就是2^(4-2)=2^2=4; 其中a[5]:00000~01111的非法二进制数个数就是a[4]; 10000~10111的非法二进制数个数就是a[3]; 11000~11111的非法二进制数个数就是2^(5-2)=2^3=8; 则可以得到规律:a[n]=a[n-1]+a[n-2]+2^(n-2);

  • 我也是这么想的,但是我超时了,用了4000ms,请问你的时长是多少?

  • 时间超级长的原因在于 有a[n-1],a[n-2]这两个递归,浪费了大量的时间,你可以用数组建立一个快速查询表,初次计算 记录数值,第二次计算,直接引用数据。这样计算速度会快很多

  • 又想到了一个办法优化时间与空间复杂度,因为a[n]依赖于a[n-1],a[n-2],假如用递归,会计算所有的n以下的结果。所以,直接用循环从1计算到n就可以了。另外计算过了的n-3以及所有之前的数据都可以抛弃。n>3之后的数据只需要使用两个数组元素用来保存数据,稍微牺牲一点点时间,做到超级少的空间占用。

  • 我的代码是0ms过的

  • 先进行预处理,把前100个全部算出来,最后就可以直接输出了

  • 添加评论
  • reply
4

前排资磁

3

hihocoder最近怎么了,之前题目的精心设计不见了,十佳代码也好久不出,连续几次题目还没出来,评论题解先出来,感觉不是要转型就是要倒闭了。。。

6

hiho一下每周一题定位就是本来就是教学、练习向的活动,和正式的比赛不同。所以我们也没想比赛结束之后才发布题解,而是写完就发出来了。

最近的题目其实很早就在题库里了,大家可以看到来源是“太阁最新面经算法竞赛”。其实这些题目都是挑选、改编自当时北美著名IT公司的面试真题。怎么说呢,我觉得还是有一定参考价值的。

十佳代码已经发布。

  • 恩恩,没别的意思,从一开始同学推荐,就很喜欢hihocoder,学到了很多,祝越办越好!!!

  • 请问一下十佳代码在哪里看啊

  • 每期hiho一下比赛结束之后,比赛页面的子导航上会增加”十佳代码“,另外排名页面也能看到所有人的代码。

  • 添加评论
  • reply
0

为你们认真的态度赞一个

0

为你们认真的态度赞一个

0

直接上自动机+dp是不是也可以...

0

//#pragma comment(linker, "/STACK:102400000,102400000")

/** 题目: 链接: 描述

思路: */

include

include

include

include

include

include

include

include

include

include

using namespace std; typedef pair P; typedef long long LL; const int N = 104; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; int n; LL dp[104][2][2]; void init() { dp[1][0][0] = 1; dp[1][0][1] = 0; dp[1][1][1] = 0; dp[1][1][0] = 1; for(int i = 2; i < N; i++){ dp[i][0][0] = (dp[i-1][0][0]+dp[i-1][1][0])%mod; dp[i][1][0] = dp[i-1][0][0]; dp[i][0][1] = (dp[i-1][1][1]+dp[i-1][0][1])%mod; dp[i][1][1] = (dp[i-1][1][1]+dp[i-1][0][1]+dp[i-1][1][0])%mod; } } int main() { init(); while(scanf("%d",&n)==1) { printf("%lld\n",(dp[n][0][1]+dp[n][1][1])%mod); } return 0; }

0

数位dp 1A,看分析竟然还有这种操作 赞一个

0

打表滋瓷吗

1

h[i] = 2^i - f[i] - g[i] 可以改成 h[i] = h[i-1] + g[i-1] 用不着指数运算……

0

反向筛选其实挺容易想的……发现是斐波那契的真的好棒啊(:3 /)_

0

从最高位开始考虑,如果最高位为0,那么f[n]->f[n-1]: 如果最高位为1,次高位为0,那么f[n]->f[n-2]; 如果最高位1,次高位为1,那么f[n] += 2^(n-2); 所以: f[n] = f[n-1]+f[n-2]+2^(n-2);

write answer 切换为英文 切换为中文


转发分享