出题人题解｜加密信息

题目大意

给定一个长度为 $n$ 的数组，对进行如下操作：

1. 从数组中任意选择 $2$ 个不同数字
2. 同时交换两个数字的最高位和最低位
3. 交换后的两个数字都不在原数组中，那么用空格将交换后的数字串联起来，从而生成一个有效的数字组合
4. 否则，不是一个有效的数字组合

求可以生成多少个不同且有效的新数字组合。

题意分析

样例 $1$ 中 123344 和 8004，虽然这样的两个数字完全不一样，但如果进行了交换，会得到数字 823344，它在原数组中，不符合题目要求。

又例如数组 = [102，112，122，927，937，947]，将其分为两组：

• 第一组：102，112，122
• 第二组：927，937，947

其中第一组内的数字不能进行最高位和最低位的交换，因为交换后数字不变，必然在原数组中，第二组也同理。

考虑交换第一组和第二组的数字。

• 第一组的 122 无法与第二组的任何数字交换，因为交换后会得到 927，它在原数组中
• 第二组的 927 无法与第一组的任何数字交换，因为交换后会得到 122，它在原数组中
• 其余数字对可以交换最高位和最低位

解题思路

按照最高位和最低位，将数组分成至多 90 组数字，从 10 到 99。

例如数组 = [102，112，122，927，937，947]，分成如下两组（去掉最高位和最低位）：

• $A$ 组：0，1，2
• $B$ 组：2，3，4

分组后，只需要去掉组中相同的数字，然后求出排列数情况就是 $A$ 组和 $B$ 组可以生成的新数字数量。

上述案例中 $A$ 和 $B$ 相同的数字有 $1$ 个，不同且有效的新数字组合数为 $(3-1)*(3-1)*2=8$​

枚举所有组对，同上述计算方法，累加起来即为答案。

时间复杂度解析

此程序时间复杂度为 $O(NM \vert \sum \vert)$，$N$ 为数组长度， $M$ 为数字长度，$\vert \sum \vert = 90$ 是首尾数字组合集合的大小。

枚举组对的逻辑看上去是 $O(NM \vert \sum \vert^2)$ 的，但去掉内层 $O(\vert \sum \vert)$ 的循环后，剩余循环相当于把数组遍历一遍，是 $O(NM)$，所以总的时间复杂度是 $O(NM \vert \sum \vert)$。

代码演示

#include <iostream>
#include <unordered_set>
using namespace std;

typedef long long LL;

const int max_n = 50010;

string a[max_n];

int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; ++ i ) cin >> a[i];

  unordered_set<string> st[100];
  for (int i = 1; i <= n; ++ i ) {
    // 将首尾元素组合起来
	int it = ((a[i][0] - '0') * 10 + (a[i][a[i].size() - 1] - '0'));
    // 将去掉首尾的部分插入到对应集合中
    st[it].insert(a[i].substr(1, a[i].size() - 2));
  }

  LL ans = 0;
  for (int i = 10; i < 100; ++i) {
    for (int j = 10; j < i; ++j) {
      // 统计交集个数
      LL cnt = 0;
      for (auto &it : st[i]) {
        cnt += st[j].count(it);
      }
      ans += 1LL * (st[i].size() - cnt) * (st[j].size() - cnt);
    }
  }
  // 计算排列情况
  cout << ans * 2 << endl;
  return 0;
}