NC14380 位数差
NC14380 位数差
题目
题目描述
给一个数组 \({a}\) ,定义 \(h(a,b)\) 为在十进制下 \(a + b\) 与 \(a\) 的位数差,求 \(\displaystyle\sum_{1\leq i < j \leq n} h(a_i,a_j)\),\(0\) 的位数为 \(1\) 。
输入描述
第一行读入一个正整数 \(n (1 <= n <= 10^5)\)。第二行读入 \(n\) 个非负整数,第 \(i\) 个表示 \(a[i] (0 <= a[i] <= 10^8)\) 。
输出描述
一行表示答案。
示例1
输入
10
0 1 2 3 4 5 6 7 8 9
输出
20
题解
思路
知识点:二分,数学。
我们用 \(bit(a)\) 表示 \(a\) 的十进制位数,则有:
\displaystyle\sum_{1\leq i < j \leq n} h(a_i,a_j) &= \displaystyle\sum_{1\leq i < j \leq n} bit(a_i+a_j) - bit(a_i)\\
&=\displaystyle\sum_{1\leq i < j \leq n} bit(a_i+a_j) - \displaystyle\sum_{1\leq i < j \leq n}bit(a_i)\\
&=\displaystyle\sum_{1\leq i < j \leq n} bit(a_i+a_j) - \displaystyle\sum_{1\leq i \leq n}(n-i)bit(a_i)\\
&=\displaystyle\sum_{1\leq i < j \leq n} bit(a_i+a_j) - \displaystyle\sum_{1\leq i < j \leq n}(n-i)bit(a_i)\\
\end{align*}
\]
其中,\(- \displaystyle\sum_{1\leq i < j \leq n}(n-i)bit(a_i)\) 可以在输入时候处理完。
而 \(\displaystyle\sum_{1\leq i < j \leq n} bit(a_i+a_j)\) 与 \(i\) 和 \(j\) 顺序可以互换,因此该式与序列的排列顺序无关。所以从小到大排序,对每一个数查找某一结果的区间,由于选择比 \(a_i\) 小的数与 \(a_i\) 配对答案只可能是 \(0\) 和 \(1\) 而选择大的数会出现 \(0\) 到 \(9\) ,而选择一种即可结果是相同的,我们选择前者查找答案 \(01\) 分界点,非常方便。显然只要查找大于等于 \(10^{bit(a_i)} - a_i\) 的第一个数 \(a_{pos}\),即第一个 \(bit(a_i+a_j)\) 结果为 \(bit(a_i)+1\) 的数即可。随后因为这个区间的所有数的位数至少是 \(bit(a_i)\) ,因此加上 \((i-1)bit(a_i)\) ,再加上位数多一的个数 \((i-pos)\) ,于是对于这个数与小于他的数的配对总和就是 \((i-1)bit(a_i)+(i-pos)\) ,对每个数如此操作即可。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[100007];
int p[10] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000 };
int bit(int n) {
if (!n) return 1;
int ans = 0;
while (n) n /= 10, ans++;
return ans;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
ll ans = 0;
for (int i = 1;i <= n;i++) cin >> a[i], ans -= (n - i) * bit(a[i]);
sort(a + 1, a + n + 1);
for (int i = 1;i <= n;i++) {
int pos = lower_bound(a + 1, a + i, p[bit(a[i])] - a[i]) - a;
ans += (i - 1) * bit(a[i]) + (i - pos);
}
cout << ans << '\n';
return 0;
}
最新文章
- web主题公园版权信息破解:script.js加密文件
- protobuf初体验
- 使用 xtrabackup 进行MySQL数据库物理备份
- [LeetCode]题解(python):094 Binary Tree Inorder Traversal
- HDU 4862(费用流)
- effective c++:引用传递与值传递,成员函数与非成员函数
- IOS中的内存不足警告处理(译)
- kafka offset-check工具失效的问题
- cf B. Sereja and Suffixes
- hdu3068之manacher算法+详解
- Tomcat 80 端口被占,解决方案
- Android LayoutInflator 解析
- Mac下git配置
- Python全栈开发之---输入输出与流程控制
- CISCO 动态路由(OSPF)
- 面试官问我,使用Dubbo有没有遇到一些坑?我笑了
- bzoj千题计划198:bzoj1084: [SCOI2005]最大子矩阵
- vs2013和vs2010的配置
- CUBA 7:崭新的篇章
- apacheserver全局配置具体解释
热门文章
- 技术管理进阶——一线Leader与大Leader的差异是什么?
- Mysql 计算地址经纬度距离实时位置
- .NET LoongArch64 正式合并进入.NET
- Linux下高效实用的grep命令
- WPF中的依赖属性
- django小项目,使用paramiko自动备份网络设备配置
- spring 事务传播(Propagation)
- 在Windows2003 server 64位系统上使用ArcEngine开发的WCF服务
- 数仓选型必列入考虑的OLAP列式数据库ClickHouse(上)
- 109_Power Pivot客户ABC(帕累托)分析度量值写法(非计算列)