【HDU 3709】 Balanced Number （数位DP）

 

【题意】

　

　　　　一个数n是平衡数当且仅当选一个位置j时，对于每一位(i-j)*a[i]的和为0,例如4139，4921，求l到r中有多少个平衡数(l<=r<=2^63-1)多组数据

 

【分析】

 

　　

　　一开始纠结的地方呢就是一个数可不可能有两个平衡点。。然后就觉得会重复。
　　用物理的思想想的话好像一个物体又没有两个重心？？可是我不会用数学方法严谨证明ORZ。。。
　　然后就是普通的数位DP，f[i][j][k]表示填i位j是平衡点，然后k是当前的计算值。（不超过4000）
　　记忆化搜索大法好，又快又好打，特别是多组！！

　　记得减掉00、000、0000的！

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define LL long long

 LL f[][][];

 int a[],c;

 LL ffind(int n,int k,int sum,bool flag)

 {

     if(n==) return (sum==);

     if(!flag&&f[n][k][sum]!=-) return f[n][k][sum];

     int ed=flag?a[n]:;

     LL ans=;

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

       ans+=ffind(n-,k,sum+i*(k-n),flag&&(i==ed));

     if(!flag) f[n][k][sum]=ans;

     return ans;

 }

 LL get_ans(LL n)

 {

     if(n==-) return ;

     if(n==) return ;

     c=;

     LL x=n;

     while(x) a[++c]=x%,x/=;

     LL ans=;

     for(int i=;i<=c;i++) ans+=ffind(c,i,,);

     return ans-c+;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     memset(f,-,sizeof(f));

     while(T--)

     {

         LL x,y;

         scanf("%lld%lld",&x,&y);

         get_ans();

         LL ans=get_ans(y)-get_ans(x-);

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

     }

     return ;

 }

[HDU 3709]

感觉我没有判负就A了？！！

2016-10-08 20:31:48