[HDU - 3709] Balanced Number

---

题目链接

---

大致题意:

给定区间[a,b]，求区间内平衡数的个数

平衡数:即有一位做平衡点，左右两边数字的力矩相等

---

解题思路:

判断力矩是否相等,需要参数sum记录力矩情况,初始为0,递归到最低位还是0,说明左右两边力矩相等

对于平衡点,需要进行枚举统计

所以枚举的平衡点,每一次dfs结果会加上固定平衡点满足条件的数字个数

除此之外,数字0也是满足的,但是00,000,0000不满足,所以最终答案res-len+1

---

AC代码:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 20;
int a[N];
ll f[N][N * 100];

ll dfs(int pos, int limit, int x, int sum) {
	if (sum < 0)return 0; //剪枝
	if (!pos)return !sum;
	if (!limit && f[pos][sum] != -1)return f[pos][sum];
	ll res = 0;
	int end = limit ? a[pos] : 9;
	for (int i = 0; i <= end; ++i)
		res += dfs(pos - 1, limit && i == end, x, sum + i * (pos - x));
	if (!limit)f[pos][sum] = res;
	return res;
}

ll dp(ll n) {
	int len = 0;
	while (n) {
		a[++len] = n % 10;
		n /= 10;
	}
	ll res = 0;
	for (int i = 1; i <= len; ++i) {
		memset(f, -1, sizeof f);
		res += dfs(len, 1, i, 0);
	}
	return res - len + 1;
}
int main(void)
{
	int t; scanf("%d", &t);
	while (t--) {
		ll l, r;
		scanf("%lld%lld", &l, &r);
		printf("%lld\n", dp(r) - dp(l - 1));
	}
	return 0;
}