青岛网站设计公司价格,注册360建筑网公司,网页设计实训报告2022,wordpress 文章更新Balanced Number 题意
定义一个非负整数在第 p p p 位为 p i v o t pivot pivot 的权重为#xff1a;这个数位的值 \times 这个数位到 p i v o t pivot pivot 的距离 之和。如果在 p i v o t pivot pivot 左边的权重等于在 p i v o t pivot pivot 右边的权重#xf…Balanced Number 题意
定义一个非负整数在第 p p p 位为 p i v o t pivot pivot 的权重为这个数位的值 × \times × 这个数位到 p i v o t pivot pivot 的距离 之和。如果在 p i v o t pivot pivot 左边的权重等于在 p i v o t pivot pivot 右边的权重那么这个数就是 平衡 的。
求出 [ l , r ] [l,r] [l,r] 的平衡数的数量
思路
观察发现如果一个数是平衡的那么它有且仅有 一个 使得它平衡的 p i v o t pivot pivot 0 0 0 除外有前导 0 0 0。如果它还有别的 p i v o t pivot pivot 假设在现在 p i v o t pivot pivot 的右边那么从现在 p i v o t pivot pivot 往右边移动的过程中左边的权重一定是增加的右边的权重一定是减少的如果一开始左右相等那么移动后左右一定不等。
我们可用枚举 p i v o t pivot pivot 定义限制条件为 p o s pos pos 个全变化位当前左边权重 − - − 右边权重为 s u m sum sum p i v o t pivot pivot 在 p i v o t pivot pivot 那么 d p [ p o s ] [ s u m ] [ p i v o t ] dp[pos][sum][pivot] dp[pos][sum][pivot] 就表示符合条件的数的数量。
转移过程中对于当前位为 p p p s u m sum sum 变化为 s u m p × ( p o s − p i v o t ) sum p \times (pos - pivot) sump×(pos−pivot)。
底层返回 s u m 0 sum 0 sum0 即可。需要注意 0 0 0 会被重复计算这是因为我的代码没有判前导零。但是只有 0 0 0 会被重复计算而且刚好计算了我们当前边界数的长度 l e n len len 次由于 0 0 0 本身是平衡的所以我们多算了 l e n − 1 len - 1 len−1 次最后结果减去 l e n − 1 len - 1 len−1 即可。
权重的范围是 [ − 1377 , 1377 ] [-1377,1377] [−1377,1377]我们将数组第二维开足够空间后对于当前 s u m sum sum 加一个偏移量 D 1500 D 1500 D1500 就可以规避负数下标的问题。
时间复杂度 O ( l e n × 1377 × 2 × p i v o t ) O(len \times 1377 \times 2 \times pivot) O(len×1377×2×pivot)
#includebits/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 INF0x3f3f3f3e;
const long long INFLL1e18;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;
}
