題意：定義?h(a,b)為在十進制下?a + b?與?a?的位數(shù)差，求

題解：觀察式子可以發(fā)現(xiàn)每個數(shù)要往找到b,計算h(a, b)不能每個都算，位數(shù)變化很少，所以應(yīng)該按位數(shù)變化分類，計算多少個數(shù)位數(shù)變化為t可以用數(shù)狀數(shù)組或者線段樹維護一下

#include <bits/stdc++.h> #define maxn 101000 #define INF 0x3f3f3f3f typedef long long ll; using namespace std; ll c[maxn], ans; int n, a[maxn], b[maxn]; void update(int x,int d){for(int i=x;i<maxn;i+=i&(-i))c[i] += d; } ll sum(int x){ll ans = 0;for(int i=x;i>=1;i-=i&(-i)) ans += c[i];return ans; } int bit(ll a){if(a == 0) return 1;else return (int )log10(a)+1; } int main(){scanf("%d", &n);for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];sort(b+1, b+1+n);int num = unique(b+1, b+1+n)-(b+1);for(int i=1;i<=n;i++) update(lower_bound(b+1, b+1+num, a[i])-b, 1);for(int i=1;i<=n;i++){update(lower_bound(b+1, b+1+num, a[i])-b, -1);for(ll j=10;j<=1e8;j*=10){if(j < a[i]) continue;int t1 = lower_bound(b+1, b+1+num, j*10-a[i])-b;t1--;int t2 = lower_bound(b+1, b+1+num, j-a[i])-b;t2--;ans += (sum(t1)-sum(t2))*(bit(j)-bit(a[i]));}}printf("%lld\n", ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Noevon/p/7821105.html

總結(jié)

以上是生活随笔為你收集整理的nowcoder20C 位数差的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。