为什么我只有20分，实在不知道错在哪里，求各位AC程序研究下。。。。
以下我本渣的程序，求解答。
program ex;
var s:ansistring;
data:array[1..100001] of longint;
ans,sum,i,n:longint;
begin
readln(n); read(s); ans:=0; sum:=1;
for i:=1 to n-1 do
begin
sum:=(sum*2) mod 1000000007; ans:=(ans+sum) mod 1000000007;
data[i]:=sum mod 1000000007;
end;
sum:=(sum*2) mod 1000000007; data[n]:=sum mod 1000000007;
inc(ans);
for i:=1 to length(s) do
begin
if s[i]='7' then
begin
ans:=(ans+(data[n-i+1] div 2)) mod 1000000007;
end;
end;
write(ans);
end.
6 条评论
-
Platypus LV 9 @ 2015-02-16 18:30:47
直接把4视为二进制的0,7视为二进制的1，然后把这个二进制转成十进制就好了
因为可能有4444这样的数，直接转换的话相当于0，所以在最高位上加一个1，转换成10000这样，输出答案时再减掉1program vijos_1922;
const mo=1000000007;
var n,i,ans:longint;
ch:char;
begin
readln(n);
ans:=1;
for i:=1 to n do
begin
read(ch);
ans:=ans<<1;
if ch='7' then inc(ans);
ans:=ans mod mo;
end;
writeln(ans-1);
end.-
@ 2015-02-17 19:28:29
这想法真不错诶！！！
-
-
@ 2015-02-16 10:20:54
我是用二叉树的性质做的。。
-
@ 2015-02-16 10:25:33
感觉这个就是个纯粹数学题 = =跟那个幸福二次一样- -我还温习了下一些公式- -
-
-
@ 2015-02-16 10:16:58
没事了，看错题目，昨晚朝思夜想做梦的时候想出来了
-
@ 2015-02-16 00:31:53
实际上是考虑每一位的4或者7对这个数的index所产生的贡献
-
@ 2015-02-16 01:11:39
我清楚了。你是直接看贡献的。
-
-
@ 2015-02-16 00:30:56
从最高位开始扫，若第k位是4，则ans+=2^(k-1)，若第k位是7，则ans+=2*2^(k-1)
-
@ 2015-02-16 01:09:05
我是把前面n-1位先考虑了。再去看贡献的。4不贡献。然后7贡献该位的2的该为次的一半。
拿4747举例。
2+4+8（1,2,3位的总情况）是14.
所以4444是第15种。然后4747开始扫，4不管，7就是15+（8 div 2） 4又是不管 再是7 19+（2 div 2）答案20.
为什么这样的答案是错的？？？
-
@ 2015-02-16 10:24:31
昨晚做梦的时候。有个东西（忘记是什么了）让我看数据范围。
然后我仔细一想，呵呵10的6次方就是10W了，10W次方啊亲！！然后我就知道我这种办法为毛不能满分了。
这是我第几次做梦写题了？？？我去- -先是有道哈夫曼树，后来是个动态规划。每次睡觉完就会了，醉了
-
@ 2015-02-16 14:04:36
抱歉我没仔细看你的代码......你这么一说我才发现你的数据开太小了......当然你的想法是对的
-
-
@ 2015-02-16 00:20:18
不知道原因都睡不了觉了，诶！！！
- 1
