进制好题

思路

小学我们都学过，两个数之和的数字和等于他们的数字和的和减去$9$乘上进位次数。很显然前半部分很好求，那如何求进位次数呢？

很显然，对于两个数$x$和$y$，如果想要他们在$10^k$位产生进位，那么必然要满足$x\mod10^k+y\mod 10^k$（$x$的后$k$位加上$y$的后$k$位）大于$10^k$。由此，我们可以枚举每一位的每一个数，通过lower_bound来查找是否会产生进位，最终从$ans$中减去即可。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[33][N],n;
signed main()
{
	scanf("%lld",&n);
	int ans=0;
	for(int i=1,x;i<=n;i++)
	{
		scanf("%lld",&x);
		for(int b=10,j=1;j<=16;j++,b*=10)a[j][i]=x%b;
		while(x)
		{
			ans+=x%10,x/=10;
		}
	}
	ans*=2*n;
	for(int i=1,b=10;i<=16;i++,b*=10)
	{
		sort(a[i]+1,a[i]+n+1);
		for(int j=1;j<=n;j++)
		{
			int id=lower_bound(a[i]+1,a[i]+n+1,b-a[i][j])-a[i];
			ans-=9*(n-id+1);
		}
	}
	printf("%lld\n",ans);
	return 0;
}