POJ 3286 How many 0's?(数位DP)

题目链接

终于过了，边界让我wa了好几次，猥琐的用AC代码对拍，很无奈，用非常麻烦的方法。写一下，估计以后再碰到，肯定看不懂这是写的什么了。

以前做过，统计1和2的，统计0比1和2麻烦多了，有前导0的情况，不太好弄。

算是用统计方法，先把sp[len-1]所有的加上，长度为len-1的情况。

然后就是长度为len的情况。从高位到低位，遍历。

如果此位是0，judge(str+1) + 1 + dfs(str+1)，是统计当前为是0的，多少情况，但是会漏解，算是受以前那个题统计1和2的影响把。

如果下一位是0，那么就不用管了，交给下位统计去把。下位不是0，计算会漏掉下位是0的情况，所以定住下位是0，组合一下长度len-2的所有0的个数。

不是0的情况，类似。

以前那个题的题解http://www.cnblogs.com/naix-x/archive/2013/03/12/2955544.html

完全没有策略，乱写，乱搞过的。。。

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <string>

 using namespace std;

 #define LL __int64

 LL dp[],sp[],o[];

 LL judge(char *str)

 {

     int i,len;

     LL ans;

     len = strlen(str);

     ans = ;

     for(i = ; i <= len-; i ++)

     {

         ans = (ans* + str[i]-'');

     }

     return ans;

 }

 LL dfs(char *str)

 {

     int len;

     LL sum;

     len = strlen(str);

     if(len == )

         return ;

     sum = (len-)*o[len-];

     if(str[] == '')

     {

         if(str[] == '')

             return judge(str+) +  + dfs(str+);

         else if(len >= )

             return judge(str+) +  +dfs(str+)+o[len-] + (len-)*o[len-];

         else

             return judge(str+) +  + dfs(str+);

     }

     else

     {

         if(str[] == '')

             return (str[]-'')*sum + dfs(str+);

         else if(len >= )

             return (str[]-'')*sum + dfs(str+)+o[len-] + (len-)*o[len-];

         else

             return (str[]-'')*sum + dfs(str+);

     }

 }

 LL fun(LL x)

 {

     int i,len;

     char str[];

     if(x == ) return ;

     else if(x < ) return ;

     len = ;

     while(x)

     {

         str[len++] = x%+'';

         x = x/;

     }

     for(i = ; i < len/; i ++)

     {

         swap(str[i],str[len-i-]);

     }

     str[len] = '\0';

     return sp[len-] + dfs(str);

 }

 int main()

 {

     int i;

     LL temp = ,x,y;

     dp[] = ;

     sp[] = ;

     o[] = ;

     o[] = ;

     for(i = ; i <= ; i ++)

     {

         dp[i] = (i-)**temp;

         sp[i] = sp[i-] + dp[i];

         o[i] = *o[i-];

         temp = temp*;

     }

     while ( scanf("%I64d%I64d",&x,&y) && (y>=) )

     {

         printf("%I64d\n",fun(y)-fun(x-));

     }

     return ;

 }

巴特西

POJ 3286 How many 0's?(数位DP)

最新文章

热门文章