hdu 3709 Balanced Number

Balanced Number

题意

定义一个非负整数在第 $p$ 位为 $pivot$ 的权重为：这个数位的值 $\times$ 这个数位到 $pivot$ 的距离 之和。如果在 $pivot$ 左边的权重等于在 $pivot$ 右边的权重，那么这个数就是 平衡 的。

求出 $[l,r]$ 的平衡数的数量

思路

观察发现：如果一个数是平衡的，那么它有且仅有 一个 使得它平衡的 $pivot$ （$0$ 除外，有前导 $0$）。如果它还有别的 $pivot$ （假设在现在 $pivot$ 的右边），那么从现在 $pivot$ 往右边移动的过程中，左边的权重一定是增加的，右边的权重一定是减少的，如果一开始左右相等，那么移动后左右一定不等。

我们可用枚举 $pivot$ ，定义限制条件为：$pos$ 个全变化位，当前左边权重 $?$ 右边权重为 $sum$，$pivot$ 在 $pivot$ ，那么 $dp[pos][sum][pivot]$ 就表示符合条件的数的数量。

转移过程中，对于当前位为 $p$，$sum$ 变化为：$sum+=p\times (pos?pivot)$。

底层返回 $sum=0$ 即可。需要注意 $0$ 会被重复计算，这是因为我的代码没有判前导零。但是只有 $0$ 会被重复计算，而且刚好计算了我们当前边界数的长度 $len$ 次，由于 $0$ 本身是平衡的，所以我们多算了 $len?1$ 次，最后结果减去 $len?1$ 即可。

权重的范围是：$[?1377,1377]$，我们将数组第二维开足够空间后，对于当前 $sum$ 加一个偏移量 $D=1500$ 就可以规避负数下标的问题。

时间复杂度： $O(len\times 1377\times 2\times pivot)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3e;
const long long INFLL=1e18;

typedef long long ll;

ll dp[20][3000][20];
int num[20];
const int D = 1500;

ll dfs(int pos, int sum, int pivot, bool limit){
    if(!pos) return !sum;
    if(!limit && ~dp[pos][sum + D][pivot]) return dp[pos][sum + D][pivot];
    ll res = 0;
    int up = (limit ? num[pos] : 9);
    fore(i, 0, up + 1){
        res += dfs(pos - 1, sum + i * (pos - pivot), pivot, limit && i == up);
    }
    if(!limit) dp[pos][sum + D][pivot] = res;
    return res;
}

ll solve(ll x){
    if(x < 0) return 0;
    int len = 0;
    while(x){
        num[++len] = x % 10;
        x /= 10;
    }
    ll res = 0;
    fore(p, 1, len + 1) res += dfs(len, 0, p, true);
    return res - len + 1;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    memset(dp, -1, sizeof(dp));
    int t;
    std::cin >> t;
    while(t--){
        ll l, r;
        std::cin >> l >> r;
        std::cout << solve(r) - solve(l - 1) << endl;
    }
    return 0;
}