题目
题目描述:
给一个数组{a},定义 h(a,b)为在十进制下 a + b 与 a 的位数差,求 ,0的位数为1。
输入描述:
第一行读入一个正整数 n (1 <= n <= 105)。 第二行读入 n 个非负整数,第 i 个表示a[i] (0 <= a[i] <= 108)。
输出描述:
一行表示答案。
解析
1)知识点
这道题包含了分支递归和二分思想。
2)看题目
首先我们理解题目的话,就是要求出一个两层循环就散公式呗,平方复杂度可以算,但是会超时(代码放下面了)。
3)算法分析
- 但是这个问题很大,我们就想要把他变成很多小问题来解决。所以我们自然就会想到dp和分治递归。
- 这道题我们一个大问题我们就对半分成两个小问题来写,问题之间互不相干,我们也自然而然的分治递归。
- 递归的话,大问题怎么划分成小问题呢?
- 我们假设有一个问题ans,分成左右两个小问题 l,r (我们下面用calc表示递归函数):就可以得到ans = calc(l) + calc(r) + h(l, r)。
(这里的h(l, r)就是两个区块之间关联的计算过程) - 也就是说,我们现在就按照这个思路递归就可以得出答案了。
4)算法操作
- 既然我们都已经有思路了,我们现在最重要的就是求出h(l, r)了。calc(l) 和 calc(r) 都不重要,因为递归自己会求:
ll ans = calc(l, mid) + calc(mid + 1, r); //h(l, r)下面会求
- 这里注意一下,我们的递归终点,就是左界 == 右界的情况:
if (l == r) return 0;
- 然后呢,我们的h(l, r)怎么求?
- 这里我就直接举例说明:h(a, b)我们已知一个确定的b = 12345。这说明如果答案要+1的a,一定会比1e6 - b要大。
- 这里你大概就能懂了:也就是说,如果大于1e6 - a的数据全都可以+1。同理可得,1e7 - b的数全都可以+2。
- 这就有一个好办法可以节省时间的做后面的步骤了:二分对答案进行查找。判断比10n - b大的a,有多少个,就统计下来就是答案:
int cmp[9] = { 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; for (int i = l; i <= mid; i++) for (int j = 0; j < 9; j++) if (cmp[j] - info[i] > 0) { auto en = info + r + 1; auto pos = lower_bound(info + mid + 1, info + r + 1, cmp[j] - info[i]); ans += en - pos; }
5)打代码
- 首先保存我们的数据。
- 然后就按我说的分治递归就好了。
- 下面全代码~
TLE代码
#include <iostream> #include <string> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int MAX = 1e5 + 7; int info[MAX]; //全局变量区 int main() { IOS; int n; cin >> n; for (int i = 1; i <= n; i++) cin >> info[i]; int ans = 0; for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) { int x = info[i] + info[j], y = info[i]; string s1 = to_string(x), s2 = to_string(y); ans += s1.length() - s2.length(); } cout << ans << endl; return 0; } //函数区
AC代码
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int MAX = 1e5 + 7; int cmp[9] = { 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; int info[MAX]; //全局变量区 ll calc(int l, int r); //函数预定义区 int main() { IOS; int n; cin >> n; for (int i = 1; i <= n; i++) cin >> info[i]; cout << calc(1, n) << endl; return 0; } ll calc(int l, int r) { if (l == r) return 0; int mid = l + r >> 1; ll ans = calc(l, mid) + calc(mid + 1, r); sort(info + mid + 1, info + r + 1); for (int i = l; i <= mid; i++) for (int j = 0; j < 9; j++) if (cmp[j] - info[i] > 0) { auto en = info + r + 1; auto pos = lower_bound(info + mid + 1, info + r + 1, cmp[j] - info[i]); ans += en - pos; } return ans; } //函数区