自动搬运

查看原文

来自洛谷，原作者为

	Xuan_qwq QQ:3054662060 | 毫无实力

搬运于2025-08-24 23:05:12，当前版本为作者最后更新于2024-10-17 16:31:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们知道，一个数 $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 函数求出。

最终答案为：

至于为什么只需要计算 $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;
}