题解：P8712 [蓝桥杯 2020 省 B1] 整数拼接

1.题目描述

给定一个长度为 $n$ 的数组 $A_1,A_2,\cdots,A_n$ 。你可以从中选出两个数 $A_i$ 和 $A_j$ （ $i\neq j$ ），然后将 $A_i$ 和 $A_j$ 一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换 $A_i$ 和 $A_j$ 的顺序总是被视为 $2$ 种拼法，即便是 $A_i=A_j$ 时。

请你计算有多少种拼法满足拼出的整数是 $K$ 的倍数。

2.思路

由于

1 \le n \le 10^5

，使用时间复杂度为

\mathcal O(n^2)

的算法枚举每种拼接显然不可行。面对这个问题，我们需要一种储存数组

A

中信息的方法，可以让我们在每次遍历

A_i

时以较少的时间复杂度得知能与

A_i

拼接的整数个数。

设数组中两个元素

A_j

和

A_i

的数字位数分别为

v

和

u

，因为拼接后的数是

K

的倍数，所以有

A_j \cdot 10^u + A_i \equiv 0 \pmod K

，即

A_j \cdot 10^u \equiv -A_i \pmod K

。由于

A_i \le 10^9

，即

A_i

最多有十位，我们可以开

10

个哈希表，对于第

p

个哈希表，存储

A_i \cdot 10^u \mod K

的每个值出现的次数。这样我们在遍历时就能用哈希表里的值进行快速相加了。

3.注意事项

由于 $K \le 10^5$ ，我们把两个模 $K$ 的余数相乘时会超出int的范围。此外拼接方法的总数在极限情况下也会超出int的范围。所以记得开long long。
按以上方法计算会多算到自己与自己拼接的情况。所以当 $A_i \cdot 10^u + A_i \equiv 0 \pmod K$ 时，要把答案减 $1$ 。
可以用log10(x) + 1快速计算 $x$ 的数字位数。

4.代码

CPP

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
int n, k, a[N];
long long pw[11]; // 10^u % k
unordered_map<int, int> mp[11];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k;
  pw[0] = 1;
  for (int i = 1; i <= 10; i++)
      pw[i] = (pw[i-1] * 10) % k;
  for (int i = 1; i <= n; i++) {
      cin >> a[i];
      for (int j = 1; j <= 10; j++)
          mp[j][a[i] * pw[j] % k]++;
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
      int len = log10(a[i]) + 1, mod = (k - a[i] % k) % k; // mod等价于数学上的-a[i] mod k
      ans += mp[len][mod];
      if (a[i] * pw[len] % k == mod)
          ans--;
  }
  cout << ans << endl;
  return 0;
}

5.复杂度分析

时间复杂度：

\mathcal O(n \log_{10} \max A_i)

The End

题解：P8712 [蓝桥杯 2020 省 B1] 整数拼接

文章操作

1.题目描述

2.思路

3.注意事项

4.代码

5.复杂度分析

相关推荐

评论

题解：P8712 [蓝桥杯 2020 省 B1] 整数拼接