题意
设 \(f(x)\) 表示 \(x\) 的各位之和。例如 \(f(158)=1+5+8=14,f(2023)=2+0+2+3=7,f(1)=1\) 等。
给定一个正整数序列 \(A=(A_1,...,A_N)\),求 \(\sum_{i=1}^N\sum_{j=1}^Nf(A_i+A_j)\)。
数据范围:\(1\le N\le 2\times 10^5,1\le A_i<10^{15}\)。
题解
这题思路非常自然,先计算出如果每次加法都没有进位,即若 \(f(A+B)=f(A)+f(B)\) 时的答案,为 \(2N\sum_{i=1}^Nf(A_i)\)。
考虑到每次加法进位都会使答案 \(-9\),则只要统计有多少次进位即可。
从低到高地枚举每一位的进位,设当前为第 \(k\) 位,则在这一位进位的条件就是 \(A_i\bmod 10^{k+1}+A_j\bmod 10^{k+1}\ge 10^{k+1}\)。
那么取 \(x_i=A_i\bmod 10^{k+1}\),对 \(x_i\) 进行排序,然后用二分或者 two pointers 即可。
时间复杂度为 \(O(KN\log N)\) 或 \(O(KN)\),其中 \(K\) 为位数。
反思
赛时想这道题时,没有想到这个直接判断 \(\ge 10^{k+1}\),而是把每一位拆开来看,看前面连续的和为 \(9\) 的进位。这样拆开使得计算冗杂,并且不好维护。
所以要换个角度再看一看问题。
代码
//none
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rept(i,n) for(int i=1;i<=n;i++)
#define repe(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define fi first
#define se second
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define sz(v) (int)(v.size())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template<typename T>void chmax(T& a,T b){if(a<b)a=b;return;}
template<typename T>void chmin(T& a,T b){if(a>b)a=b;return;}
const int N=2e5+5;
int n,a[N],b[N][15],cur[N];
signed main(){
n=read();
int ans=0;
rept(i,n){
a[i]=read();
rep(j,15){
b[i][j]=a[i]%10;
ans+=2*n*b[i][j];
a[i]/=10;
}
}
vector<int> vec;
rep(i,15){
vec.clear();
rept(j,n){
cur[j]+=b[j][i]*fast(10,i,0);
vec.pb(cur[j]);
}
sort(vec.begin(),vec.end());
rep(j,n){
int pos=lower_bound(vec.begin(),vec.end(),fast(10,i+1,0)-vec[j])-vec.begin();
ans-=(sz(vec)-pos)*9;
}
}
out(ans);
return 0;
}
标签:10,int,题解,ARC158C,vec,res,Pair,进位,define
From: https://www.cnblogs.com/Jerry-Jiang/p/17209408.html