首页 > 其他分享 >[ARC158C] All Pair Digit Sums 题解

[ARC158C] All Pair Digit Sums 题解

时间:2024-11-09 15:08:24浏览次数:3  
标签:题解 ARC158C long times sum Pair ll 进位 数位

C - All Pair Digit Sums

题意:

设 \(f(x)\) 为 \(x\) 的数字和。例如 \(f(158)=1+5+8=14\)。

给定一个长度为 \(N\) 的正整数序列 \(A\),求 \(\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i+A_j)\)。

分析:

首先明确 \(f(x)\) 为 \(x\) 的数位和

举例情况:

若有两个数分别为:\(12,21\)。

\[f(12+21)=f(12)+f(21)=3 \]

可以发现两个数相加的数位和可以转化为第一个数的数位和第二个数数位和相加。

但总有特殊情况如:

这两个数分别为:\(53,27\)。

\[f(53+27)=f(80)=8 \]

\[f(53)+f(27)=8+9=17 \]

可以发现这两个数的数位相加时在个位上进了一位,就不符合上面的情况了,那该怎么办呢?

仔细思考进位数位和的贡献是什么?

相当于此位变为 \(0\) 和更高的一位 \(+1\),则是对总答案相当于贡献了 \(-9\)。

那么我们就明确了计算的过程

设 \(g(a,b)\) 表示 \(a+b\) 进位个数

\[f(a+b)=f(a)+f(b)-9\times g(a,b) \\ f(a)+f(b)=\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i)+f(A_j)=2N \times \sum_{i=1}^{N}f(A_i) \\ 9\times g(a,b)=9 \times \sum_{i=1}^{N}\sum_{j=1}^{N}g(A_i,A_j) \]

第二个式子为什么是 \(2n\) 呢?因为它作 \(a_i\) 时加了 \(n\) 次,它作 \(a_j\) 时被加了 \(n\) 次。

那怎么求 \(g(a,b)\) 呢?

对于两个数 \(a,b\),如果 \(a+b\) 在第 \(x\) 位上发生了进位,那么有 \(a+b\ge10^x\)。

那么我们就可以枚举 \(x\),按照每个前 \(x\) 位的数的大小排序,再枚举 \(j\),二分找到第一个 \(a_j+a_k\ge10^i\) 的数的下标 \(k\),\(k\) 后面的数就全是可以进位的,然后就可以 \((n-k+1)\) 求出 \(g(a,b)\) 的个数了。

时间复杂度为 \(O(n\log{n})\)。

下面见代码(有注释不要担心):

注:十年OI一场空,不开long long 见祖宗

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll x;
ll a[20][200005];//a[前几位的数][第几个数] 
ll ans=0;
ll p(ll x){//计算数位和 
	ll sum=0;	
	while(x){
		sum+=x%10;
		x/=10;
	}
	return sum;
}

int main() {
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		ans+=2*n*p(x);//先不考虑进位,单纯地都加上 
		ll mod=10;
		for(int y=1;y<=15;y++){
			a[y][i]=x%mod;//前i的数为记录起来 
			mod*=10;
		}
	}	
	ll w=1;
	for(int i=1;i<=15;i++){//枚举前i位 
		w*=10;
		sort(a[i]+1,a[i]+1+n);//对前i位的数的大小进行排序 
		for(int j=1;j<=n;j++){//对每个数进行排序 
		
			//统计加上a[i][j]后大于等于10^i的个数 
			ll k=n+1-(lower_bound(a[i]+1,a[i]+1+n,w-a[i][j])-a[i]);
			ans-=9*k;//减去进位减少的贡献 
		}
	}
	
	cout<<ans; 
	
    return 0;
}

标签:题解,ARC158C,long,times,sum,Pair,ll,进位,数位
From: https://www.cnblogs.com/sadlin/p/18536828

相关文章

  • QT中大量数据存储至excel的问题解决
            因为这个问题困扰了我很久,所以在这里记录一下,顺便给可能会遇到类似问题的人提供一点帮助。        在qt中,如果用C++处理数据保存到excel,正常来说在pro文件中添加axcontainer 然后就能够调用到excel,但是这只能适用于数量级没那么大时的需求。  ......
  • ffmpeg问题解决:Unrecognized option 'preset'. Error splitting the argument list: O
    来到这里,十有八九是手动编译安装的ffmpeg,在跑视频流程序或命令时出现这个问题。跟这个报错:ffmpeg:errorwhileloadingsharedlibraries:libx264.so.164:cannotopensharedobjectfile:Nosuchfileordirectory的错误本质是一样的,都是由于ffmpeg时使用到了libx264,而在......
  • 讲座の题解
    讲座配套题单的题解喵每题的文字解释会逐渐补充,如果有疑问直接私信喵目录讲座配套题单的题解喵目录A-看看你会不会用电脑B-求求你不要用内置函数C-GPAD-minE-for循环大神F-居然有人说这个是线性代数G-高三同学秒了H-无穷级数I-不要用内置函数......
  • 【题解】「NOIP2024模拟赛24 T3」钙绿
    【题解】「NOIP2024模拟赛24T3」钙绿https://www.becoder.com.cn/contest/5715/problem/3\(\mathcal{Description}\)给定\(n,p,m\)。对于每个\(k=0,1,\dots,m\),统计满足下面条件的\(n\)位\(10\)进制数:(允许前导零各位数之和不超过\(k\)。\(p\)能整除这个数。数据......
  • [USACO23FEB] Problem Setting P 题解
    [USACO23FEB]ProblemSettingP题目说的很绕,意思就是所有验题人都认为题目难度顺序单增。发现\(m\)很小,很容易想到状压。把H看作\(\tt1\),E看作\(\tt0\),则我们得到\(m\)个长度为\(n\)的\(\tt01\)串,这就是每道题的“状态”。发现状态相同的题没有本质区别,所以我们......
  • P11253 [GDKOI2023 普及组] 小学生数学题 题解
    题目传送门前置知识积性函数|乘法逆元解法观察到\(f(i)=\frac{1}{i^{k}}\bmodp\)是完全积性函数,线性筛预处理即可。需要适当的取模优化。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglong#definesortstab......
  • 【题解】CF1997
    A首先,插入的字符必须和左右两边的字符都不一样其次,对于插入位置的选择,显然最好插在两个一样的字符中间,如果没有一样的字符,插在最前面即可B观察样例发现题目中要求的位置就在样例中手玩一下,尝试改变样例里那个形状,发现改变任何一个格子都不满足题意,所以得出结论:题目要求的......
  • [USACO23JAN] Subtree Activation P 题解
    这种问题一看满足条件就知道,一般不用想着怎么模拟题意。考虑转化问题。假如节点\(u\)满足了条件一,也就是仅有子树节点全部开启。那么我们把转化具象为:进行\(\text{siz}_u\)次操作直接清空;进行\(\text{siz}_{\text{fa}(u)}-\text{siz}_u\)次操作使\(\text{fa}(u)\)满足......
  • 【题解】「NOIP2024模拟赛24 T2」子序列们
    【题解】「NOIP2024模拟赛24T2」子序列们https://www.becoder.com.cn/contest/5715/problem/2\(\mathcal{Description}\)给定一个0/1串\(a\),你需要生成一个长度为\(n\)的序列\(b\),其中\(b_i\)为\(a\)的一个子序列,且满足:\(|b_i|=n-i+1\);\(\foralli\in(1,n]\),\(b......
  • 题解:P11266 【模板】完全体·堆
    也算是对pb_ds库中的优先队列各种操作的科普?一些碎碎念提醒:你可以不看这部分,这部分算是作者探索未知功能的过程平常写优先队列的时候一般用不到对值进行修改或者删除的操作,所以我在看这到题的时候在想怎么才能实现题目中的操作,因为我不知道有什么成员函数可以直接获取具体哪......