题解 | #位数差#

题目描述：

给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求 ，0的位数为1。

思路：

分治（递归+二分）

第一反应肯定是暴力，但是一看数据范围直接放弃

接着发现这是区间问题，可以考虑考虑分治，大化小，小化了

[l, r] = [l, mid] + [mid + 1, r]

如何快速的求出h(l, r), 这里肯定不能暴力，我们可以考虑给他排个序，然后就可以去快乐的二分查找，判断比 - r 大的 l 有多少个，统计下来就是答案：

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}
ll qpow(ll a,ll n){ll ans=1,base=a%mod;while(n){if(n&1)ans=(ans*base)%mod;base=(base*base)%mod;n>>=1;}return ans;}
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

ll n, l, r, x, y, len, ans;
int tr[MAX];
int br[] = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

ll cal(ll l, ll r){
    if(r == l)return 0;
    ll mid = (l + r) / 2;
    ll ans = cal(l, mid) + cal(mid + 1, r);
    sort(tr + mid + 1, tr + r + 1);
    for(ll i = l; i <= mid; ++i){
        for(int j = 0; j < 9; ++j){
            if(tr[i] < br[j]){
                ans += r - (lower_bound(tr + 1 + mid, tr + r + 1, br[j] - tr[i]) - tr) + 1;
            }
        }
    }
    return ans;
}


int main(){
    n = IntRead();
    for(int i = 1; i <= n; ++i)tr[i] = IntRead();
    cout<<cal(1, n)<<endl;
    return 0;
}