P11201 sol

· · 题解

我们知道，一个数 x 有 k 位，等价于 10^{k-1} \leq x < 10^{k}。

那么，a_i+b_j 有 k 位等价于 10^{k-1} \leq a_i+b_j < 10^{k}，即 10^{k-1}-a_i \leq b_j < 10^{k}-a_i。

所以我们考虑枚举每一个 a_i，对所有 1\le k \le 10 计算 B 中满足 10^{k-1}-a_i \leq b_j < 10^{k}-a_i 的 b_i 数量 s_{i,k}，这可以很容易地用 lower_bound 函数求出。

最终答案为：

ans=\sum_{i=1}^n \sum_{k=1}^{10}s_{i,k}\times k

至于为什么只需要计算 1\le k \le 10 即可，是因为 a_i+b_j 的最大值不超过 999999999+999999999=1999999998 < 10^{10}，所以一个和最多只有 10 位。

ACcode

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[150005],b[150005],n,ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    sort(b,b+n);
    for(int i=0;i<n;i++){
        int lim=1;//lim为10的k-1次方
        for(int k=1;k<=10;k++){
            if(lim*10<a[i]){//小优化，如果a[i]>10^k，那就不用算
                lim*=10;
                continue;
            }
            int ps1=lower_bound(b,b+n,lim-a[i])-b;
            int ps2=lower_bound(b,b+n,lim*10-a[i])-b;
            ans+=k*(ps2-ps1);//计算 k*s[i][k]
            lim*=10;
            if(b[n-1]+a[i]<lim)break;//和上面差不多的小优化
        }
    }
    cout<<ans<<endl;
    return 0;
}