UVALive 5004 Balanced Number && hdu-3967 Zero's Number（数位dp）

非常相似的两题，都是枚举分界点。

hdu 3967 ：

题意:求A到B之间有多少个数，满足这个数分为两半之后（非零）的和能被k整除；

dp[i][j][rest][k][f],   i表示当前位数，cut表示分界点，rest表示余数，f == 0 表示有前导零

 

 

 

UVALive5003：

题意：求x到y之间有多少个balanced number；即.........自己看题目样例吧- -

dp[i][j][sum], i表示当前位数，j表示分界点，sum表示分界点两边的和；

 

注意分界点前面不能有前导零，

 

 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <vector>

#include <queue>

using namespace std ;

#define eps e-8

#define inf 0x3f3f3f3f

#define LL long long

#define ULL unsigned long long

#define FOR( i, s, t ) for( int i = s; i < t; i++ )

#define REP( i, s, t ) for( int i = s; i <= t; i++ )

#define lson id << 1, l, m

#define rson id << 1 | 1, m + 1, r

#define maxn ( 100000 + 10 )

#define maxe ( 10000 + 10 )

int K ;

LL A , B ;

LL dp [ 22 ][ 22 ][ 22 ][ 22 ][ 2 ], mul [ 22 ];

int bit [ 22 ];

LL DP ( int i , int cut , int rest , int e , int f ) {

if ( i == 0 ) return rest ? 0 : 1 ;

if ( ! e && dp [ i ][ cut ][ rest ][ K ][ f ] != - 1 ) return dp [ i ][ cut ][ rest ][ K ][ f ]; // i表示当前位数，cut表示断电，rest表示余数，f == 0 表示有前导零

LL res = 0 ;

int top = e ? bit [ i ] : 9 ;

for ( int j = 0 ; j <= top ; ++ j ) {

if ( i > cut ) {

if ( f == 0 && i == cut + 1 && j == 0 ) continue ;

res += DP ( i - 1 , cut , ( j * mul [ i - cut ] + rest ) % K , e && j == top , f || j != 0 );

}

else

res += DP ( i - 1 , cut , ( j * mul [ i ] + rest ) % K , e && j == top , f || j != 0 );

}

if ( ! e ) dp [ i ][ cut ][ rest ][ K ][ f ] = res ;

return res ;

}

LL solve ( LL x ) {

int len = 0 ;

if ( x < 0 ) return 0 ;

while ( x ) {

bit [ ++ len ] = x % 10 ;

x /= 10 ;

}

LL ans = 0 ;

for ( int i = 1 ; i < len ; i ++ )

ans += DP ( len , i , 0 , 1 , 0 );

return ans ;

}

int main ( ){

memset ( dp , - 1 , sizeof ( dp ) );

mul [ 1 ] = 1 ;

for ( int i = 2 ; i < 19 ; i ++ )

mul [ i ] = mul [ i - 1 ] * 10 ;

while ( ~ scanf ( "%I64d%I64d%d" , & A , & B , & K ) ){

printf ( "%I64d \n " , solve ( B ) - solve ( A - 1 ) );

}

}

 

 

 

#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<stdio.h> #include<algorithm> #include<cmath> #include<set> #include<map> #include<queue> using namespace std;

#define inf 0x3f3f3f3f #define eps 1e-9 #define mod 10007 #define FOR(i,s,t) for(int i = s; i < t; ++i ) #define REP(i,s,t) for( int i = s; i <= t; ++i ) #define LL long long #define ULL unsigned long long #define pii pair<int,int> #define MP make_pair #define lson id << 1 , l , m #define rson id << 1 | 1 , m + 1 , r #define maxn ( 300+10 ) #define maxe ( 20000+10 )

int bit[22]; LL dp[22][22][3333]; int len; LL dfs( int cur, int cut, int sum, bool e, bool f ) {  if( cur == 0 ) return sum == 0 ? 1 : 0;  if( !e && dp[cur][cut][sum] != -1 ) return dp[cur][cut][sum];  LL res = 0;  int top = e ? bit[cur] : 9;  for( int i = 0; i <= top; ++i ) {   if( cur > cut ) {    //if( !f && cur == cut + 1 && i == 0 ) continue;    res += dfs( cur-1, cut, sum + i * ( cur - cut ), e && i == top , f || i != 0 );   }   else if( cut == cur ) {    if( !f && i == 0 ) continue;    res += dfs( cur-1, cut, sum, e && i == top, f || i != 0  );   }   else {    res += dfs( cur - 1, cut, sum - i * ( cut - cur ), e && i == top, f || i != 0 );   }  }  if( !e ) dp[cur][cut][sum] = res;  return res; }

LL solve ( LL x ) {  if( x < 0 ) return 0;  len = 0;  while( x ) {   bit[++len] = x % 10;   x /= 10;  }  LL res = 0;  for( int i = 1; i <= len; ++i )   res += dfs( len, i, 0, 1, 0 );  return res+1; }

int main () {  int T;  scanf("%d", &T );  memset( dp, -1, sizeof( dp ) );  while( T-- ) {   LL x, y;   scanf("%lld%lld", &x, &y );   printf("%lld\n", solve( y ) - solve( x-1 ) );  } }