题目

题目描述:
给一个数组{a},定义 h(a,b)为在十进制下 a + b 与 a 的位数差,求 ,0的位数为1。

输入描述:
第一行读入一个正整数 n (1 <= n <= 105)。 第二行读入 n 个非负整数,第 i 个表示a[i] (0 <= a[i] <= 108)。 

输出描述:
一行表示答案。


解析

1)知识点

这道题包含了分支递归和二分思想。

2)看题目

首先我们理解题目的话,就是要求出一个两层循环就散公式呗,平方复杂度可以算,但是会超时(代码放下面了)。

3)算法分析

  1. 但是这个问题很大,我们就想要把他变成很多小问题来解决。所以我们自然就会想到dp和分治递归
  2. 这道题我们一个大问题我们就对半分成两个小问题来写,问题之间互不相干,我们也自然而然的分治递归。
  3. 递归的话,大问题怎么划分成小问题呢?
  4. 我们假设有一个问题ans,分成左右两个小问题 l,r (我们下面用calc表示递归函数):就可以得到ans = calc(l) + calc(r) + h(l, r)
    (这里的h(l, r)就是两个区块之间关联的计算过程
  5. 也就是说,我们现在就按照这个思路递归就可以得出答案了。

4)算法操作

  1. 既然我们都已经有思路了,我们现在最重要的就是求出h(l, r)了。calc(l) 和 calc(r) 都不重要,因为递归自己会求:
    ll ans = calc(l, mid) + calc(mid + 1, r);
    //h(l, r)下面会求
  2. 这里注意一下,我们的递归终点,就是左界 == 右界的情况:
    if (l == r) return 0;
  3. 然后呢,我们的h(l, r)怎么求?
  4. 这里我就直接举例说明:h(a, b)我们已知一个确定的b = 12345。这说明如果答案要+1的a,一定会比1e6 - b要大。
  5. 这里你大概就能懂了:也就是说,如果大于1e6 - a的数据全都可以+1。同理可得,1e7 - b的数全都可以+2。
  6. 这就有一个好办法可以节省时间的做后面的步骤了:二分对答案进行查找。判断比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)打代码

  1. 首先保存我们的数据。
  2. 然后就按我说的分治递归就好了。
  3. 下面全代码~


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;
}
//函数区