1145. 简单游戏(easygame) 

题目描述

一天，小R准备找小h去游泳，当他找到小h时，发现小h正在痛苦地写着一列数，1，2，3，…n,于是就问小h痛苦的原因，小h告诉他，现在他要算1..n这些数里面，1出现的次数是多少，如n=11的时候，有1,10,11共出现4次1，现在给出n,你能快速给出答案么？

输入

一行，就是n,(1<=n<=maxlongint)

输出

一个整数，表示1..n中1出现的次数。

样例输入

11

样例输出

4

思路：

这题找规律，代码如下：

var s,s1,s2:string; i,x,x1,n,j:longint; ans:int64; begin assign(input,'easygame.in');reset(input); assign(output,'easygame.out');rewrite(output); readln(s); s:='0'+s; for i:=length(s) downto 2 do begin n:=1; if (i<>length(s)) then begin s1:=copy(s,1,i-1); s2:=copy(s,i+1,length(s)-i+1); for j:=1 to length(s)-i do n:=n*10; val(s1,x); val(s2,x1); x:=x+1; if (s[i]='0') then begin x1:=0;dec(x);end; if (s[i]='1') then ans:=ans+x*n-(n-x1-1) else ans:=ans+x*n; end; if i=length(s) then begin s1:=copy(s,1,length(s)-1); val(s1,x); ans:=ans+x+1; if s[i]='0' then dec(ans); end; end; writeln(ans); close(input);close(output); end.