题目:http://acm.hdu.edu.cn/showproblem.php?pid=2451
题意: 问在所有小于n的i中,有多少个i计算表达式(i) + (i+1) + (i+2), i>=0的时候不会产生任何进位。
题解:对于个位,当个位为0,1,2时不会产生进位;对于非个位,为0,1,2,3时不会产生进位(题意表明没有低位向高位的进位)。因此我们可以根据n 的每位数字进行推算,比如24980,我们先算小于20000的符合条件的个数,再算20000~24000的,以此类推。
测试数据:
输入:
24980
25000
11000
12521
输出:
576
576
240
336
代码:
#include<cstdio> #include<cstring> using namespace std; #define LL __int64 using namespace std; LL numx[15]; char num[15]; int len; LL dfs(int x) { if(x==len-1) { if(num[x]>='3') return 3; else return (int)(num[x]-'0'); } int idx=(num[x]>'3'?4:(int)(num[x]-'0')); LL a=numx[len-x-2]*idx,b=dfs(x+1); if(idx>3) return a; else return a+b; } int main() { numx[0]=3; for(int i=1;i<=10;++i) numx[i]=numx[i-1]*4; for(;~scanf("%s",num);) { LL summ=0; len=strlen(num); if(len==1) { if(num[0]>='3') printf("3\n"); else printf("%d\n",(int)(num[0]-'0')); continue; } printf("%I64d\n",dfs(0)); } return 0; }