首页 > itarticle > hdu3709 balanced number 题解 题解： 代码：

hdu3709 balanced number 题解 题解： 代码：

admin 11月 13, 2020 0

A balanced number is a non-negative integer that can be balanced if a pivot is placed at some digit. More specifically, imagine each digit as a box with weight indicated by the digit. When a pivot is placed at some digit of the number, the distance from a digit to the pivot is the offset between it and the pivot. Then the torques of left part and right part can be calculated. It is balanced if they are the same. A balanced number must be balanced with the pivot at some of its digits. For example, 4139 is a balanced number with pivot fixed at 3. The torqueses are 42 + 11 = 9 and 9*1 = 9, for left part and right part, respectively. It’s your job
to calculate the number of balanced numbers in a given range [x, y]. (1 <= x,y <=10^18)

题目大意：给T组x和y，求在这个范围内，满足可以找到一个点，使得左右力矩平衡的数的个数。

题解：

数位dp，记忆化搜索记录支点，左力矩-右力矩的值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
#define REP(i, a, b) for(int i = a; i <= b; i ++)
#define REPG(i, x) for(int i = head[x]; i; i = g[i].nxt)
#define clr(x, y) memset(x, y, sizeof(x));
using namespace std;
typedef long long LL;
typedef double LF;
LL (LL a, LL b){return a > b ? a : b;}
LL Min(LL a, LL b){return a < b ? a : b;}
LL abs(LL x){return x > 0 ? x : -x;}
LL T, num[25], f[25][25][2500], a, b;
inline LL read(){
	LL r = 0, z = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar();}
	return r * z;
}
LL dfs(int len, int mid, int sum, bool sx){		
	if(len <= 0) return sum == 0;
	if(sum < 0) return 0;
	if(!sx && f[len][mid][sum] != -1) return f[len][mid][sum];
	LL cnt = 0; int sum_, sx_, maxx = sx ? num[len] : 9;
	for(int i = 0; i <= maxx; i ++){
		sum_ = sum + i * (len - mid);
		sx_ = (sx && i == maxx);
		cnt += dfs(len - 1, mid, sum_, sx_);
	}
	if(!sx) f[len][mid][sum] = cnt;
	return cnt;
}
LL solve(LL x){
	int k = 0;
	while(x){num[++ k] = x % 10; x /= 10;}
	LL ret = 0;
	for(int i = k; i > 0; i --) ret += dfs(k, i, 0, 1);
	return ret - k + 1;
}
void work(){
	T = read(); clr(f, -1);
	while(T --){
		a = read(), b = read();
		printf("%lldn", solve(b) - solve(a - 1));
	}
}
int main(){
	work();
	return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能