【计数】Simple Addition Expression

【来源】

2008年哈尔滨区域赛

【题目链接】：

http://acm.hdu.edu.cn/showproblem.php?pid=2451

【参考博客】：

HDU 2451 Simple Addition Expression

【题意】：

题意是要判断前n位数字（不包括n），有多少个数字 i 跟前面两个 i+1 , i+2 ,相加时不进位 。

符合要求的数字就是个位 0 ~ 2 ，其余位 0 ~ 3。

用一个dfs就可以搜出来了。

对于当前位是 x 的话 ， 若果 x > 3 ， 可以直接得出可以构成  [ 4^(位数-1) * 3 ] 个数

若果 x <= 3 的话 ， 就可以构成 [  (x-1)*4^(位数-1)*3 + 后面的位能组成数字的数目（递归求） ]。

【注意】

我第一次交的时候忽略了一种情况，就是其他位置（除个位外）为3的情况。

真的忽略了，一直以为都是3*3*3.....，其实是4*4*4*.....*3

别人都是用回溯什么写的，

我自己用for循环写出来了。

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const ll N = 1e10;

 const ll M = ;

 int main()

 {

     ll n;

     while(~scanf("%lld",&n)) {

         ll ans = , tmp = ;

         if( n <=  ){

             printf("%lld\n",min(3ll,n));

             continue ;

         }

         n ++ ;

         for (ll i = N, j = M; i >= ; i /= , j /= ) {

             if (n / i == ) continue;

             if (n / i >= ) {

                 //printf("# 1 %lld , %lld \n ",i,j);

                 ans += tmp * j;

                 break;

             }

             if (n / i <= ) {

                 ans += (n / i) * j/ ;

                 //printf("# 2 %lld , %lld \n ",i,j);

             }

             n = n % i ;

         }

         printf("%lld\n", ans);

     }

     return ;

 }