【题解】[ARC158C] All Pair Digit Sums

传送门

题目分析

我们可以先从简单一点的情况开始分析，如果现在 \(a_{[i]},a_{[j]}\) 都不会进位，那么最后的 \(f(a_{[i]}+a_{[j]})=f(a_{[i]})+f(a_{[j]})\)。证明如下：

有两个数 \(x=\overline{x_nx_{n-1}....x_1}\) 和 \(y=\overline{y_my_{m-1}...y_1}\)。令 \(n\le m\)，由于不会进位,所以最后它们两相加应该是 \(z=\overline{y_my_{m-1}...y_{n+1}(x_n+y_n)...(x_1+y_1)}\)，那么 \(f(z)=y_m+y_{m-1}...y_{n+1}+x_n+y_n+....x_1+y_1=\sum\limits_{i=1}^n x_i+\sum\limits_{i=1}^m y_i=f(x)+f(y)\)。

考虑进位的情况，还是先从简单的入手，比如现在 \(x\) 和 \(y\) 都是一位数且它们的和要大于 \(10\)。那么 \(z=x+y=\overline{1(x+y-10)}\)，于是 \(f(z)=1+x+y-10=x+y-9=f(x)+f(y)-9\)。

根据之前的分析，我们可以推测一下，每进一次位最终的答案就会减去 \(9\)，那么 \(f(x+y)=f(x)+f(y)-9g(x+y)\)。其中 \(g\) 函数表示进位次数。

考虑如何求 \(g\) 函数，一个显然的结论：如果 \(x+y\) 会进位并且 \(z\ge y\)，那么 \(x+z\) 也必定进位。根据这个性质，我们可以存储所有数的后 \(i\) 位放进 \(nbr_{[i]}\) 中，从小到大排个序。接着双指针维护，一个指针指现在是求第 \(i\) 与多少个数发生进位，另一个指针指向现在第一个不能与 \(a_{[i]}\) 发生进位的数。前面这个指针从小往大扫，后面这个指针从大往小扫。

当然二分也是可行的，只是其他题解二分已经很详细了，但是双指针题解比较少，所以我来补充一发，顺便提供一下此题是如何一步一步思考到正解的。

最大时间复杂度大概是 \(O(n \log n)\)。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,a[N];
int sum[N][20];
vector<int>nbr[20];

int f(int cur,int x){
	int ansi=0,cnt=0,now=1;
	while(x){
		cnt++;
		ansi+=(x%10);
		sum[cur][cnt]=sum[cur][cnt-1]+(x%10)*now;
		now*=10;
		x/=10;
	}
	return ansi; 
}

signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	int ansi=0;//所有f函数的和
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ansi+=f(i,a[i]);
		
		for(int j=1;j<=15;j++){
			if(!sum[i][j]) sum[i][j]=sum[i][j-1];//有可能这个数不满15位
			nbr[j].push_back(sum[i][j]);
		}
	}
	
	for(int i=1;i<=15;i++){
		nbr[i].push_back(0);
		sort(nbr[i].begin(),nbr[i].end());
	}
	
	int tmp=0,k=1;//tmp表示所有g函数的和
	for(int i=1;i<=15;i++){
		int now=n;
		k*=10;
		for(int j=0;j<=n;j++){
			while(nbr[i][j]+nbr[i][now]>=k) now--;
			tmp+=n-now;
		}
	}
	cout<<ansi*2*n-tmp*9;
	return 0;
}

感谢巨佬 Biuld 帮我 debug 并教我怎么算时间复杂度/bx