1
bengol 2015-07-07 23:31:27 +08:00
好像是编程之美上的题吧
|
2
msg7086 2015-07-07 23:32:13 +08:00
花点时间想想更高效率的算法不行么?
|
3
20015jjw 2015-07-07 23:42:28 +08:00
|
6
yangqi 2015-07-08 00:02:29 +08:00
没看Hint说的是注意overflow么
|
8
msg7086 2015-07-08 00:36:10 +08:00
@20015jjw count_digit_one(2147483647) == 2971027783 你看看你是不是这结果。
|
11
20015jjw 2015-07-08 00:57:01 +08:00
@msg7086 啊哈懂了 xD 看错题了xDDDDD 谢谢!
>>> sum((1 for i in range(76543+1) if '1' in str(i))) 33179 >>> sum((str(i).count('1') for i in range(76543+1) if '1' in str(i))) 41015 |
12
mickeyandkaka 2015-07-08 00:57:02 +08:00
递归,举个例子 51234 = 50000 + 1000+ 200+ 30 + 4
低位可以对高位做贡献,复杂度log(n) 数位dp很容易做出来。部分代码 long long dfs(int pos, bool bound) { if(pos == -1) return 0; if(!bound && ~dp[pos]) return dp[pos]; int end = bound ? dig[pos]-'0' : 9; long long ret = 0; for(int i=0; i<=end; i++) { ret += dfs(pos-1, bound && i == end); if(i == 1) { if(bound && i == end) ret += q[pos] + 1; else ret += p[pos]; } } if (!bound) dp[pos] = ret; return ret; } |
14
xhuuanniqege 2015-07-08 01:12:37 +08:00 via Android
数位dp
|
15
IwfWcf 2015-07-08 01:17:00 +08:00 1
|
16
msg7086 2015-07-08 01:47:03 +08:00 1
40 / 40 test cases passed.
Status: Accepted Runtime: 72 ms Submitted: 1 hour, 3 minutes ago https://gist.github.com/msg7086/4477fb824f1d7968178c |
19
20015jjw 2015-07-09 05:33:42 +08:00 1
10 minutes ago Accepted 44 ms (submitted without the doctest) python
https://gist.github.com/20015jjw/74ab03818741aaa0e7bb |
20
plantparknet OP @20015jjw Great!
|
21
plantparknet OP |
22
ChangxuBlack 2015-07-10 18:38:26 +08:00
@20015jjw 我不知道你当时过了没,反正现在你的代码会超时
|
23
20015jjw 2015-07-12 02:07:25 +08:00
@ChangxuBlack
并没有啊.... 你看我gist里的代码啊.... 顺便去掉doctest提交..... (虽然就算带了doctest也会过啊..... <img src="http://s1.momo.moda/2015/07/12/1cc3633c579a90cfdd895e64021e2163.png" alt="" title="" /> |