2021 TPC 腾讯程序设计竞赛（2）

零、背景

2021 年 TPC 腾讯程序设计竞赛 又开始了。

4 月 20 号，周二晚上，参加了 2021 年 TPC 腾讯程序设计竞赛第一季第二场比赛。

PS：这次在工位上作比赛。
比赛前5分钟风扇呼呼的响，我便想着重启下电脑。
第一次重启，鼠标键盘都没响应了。
第二次重启，重启前把所有外设拔了，启动后再插上，还是没响应。后来折腾了好久才恢复。

以后比赛前再也不比赛了，电脑又不卡。

一、奇怪的排序

题意：给一个长度为 n 的序列，可以对a[i] 与 a[(i+2)%n] 交换，问是否可以使这个序列最终有序。

思路：分析发现，这个题是群论相关的题目。

如果序列长度是奇数，则从0 开始，可以到达任意位置。
对应到群论上，就是划分为一个集合，集合内的元素可以使用冒泡法做到任意顺序。

如果序列长度是偶数，则按照偶数位置与奇数位置，序列被划分为两个无交集的集合。
由于两个集合没有交集，为了做到合并后的序列有序，那两个有序集合交叉合并后，必须是有序序列才行。

int base[111111];
int vec[2][111111];

bool check(int n) {
  for (int i = 1; i < n; i++) {
    if (base[i] < base[i - 1]) {
      return false;
    }
  }
  return true;
}



if (n % 2 == 1) {
  printf("Yes\n");
  continue;
}

int m = n / 2;
for (int i = 0; i < n; i++) {
  vec[i % 2][i / 2] = base[i];
}

sort(vec[0], vec[0] + m);
sort(vec[1], vec[1] + m);

for (int k = 0; k < n; k += 2) {
  for (int i = 0; i < 2; i++) {
    base[k + i] = vec[i][k / 2];
  }
}

if (check(n)) {
  printf("Yes\n");
} else {
  printf("No\n");
}
}

二、零的个数

题意：给一个生成数列a[n]=a[n-1]+a[n-2]，并给一个 n 和序列的前两个数字 a 和 b。
问 a[0] ~ a[n] 所有数字或运算后，二进制中 0 的个数。

思路：a 和 b 最大值是 1000。
分析可以发现，如果二进制中某一位有 1，通过若干次操作，之后的位置肯定都是 1。
所以二进制 第 10 位之后的肯定都是 1，只有前 10 位中间可能有 0。

中间的 0 会慢慢的被低位的 1 覆盖。
分析下覆盖的速度，发现操作一次或者两次可以减少一次中间的0。
因此最多 20 次，答案就固定不变了。

所以这道题只需要计算前 20 个数据就行了。

这道题我敲完后，迟迟没提交，在本地各种自测，浪费了 5 分钟。
最后提交后，发现一下就通过了。

ll forceCal(int n, ll a, ll b) {
  ll sum = a | b;
  for (int i = 2; i <= n; i++) {
    ll c = (a + b) % 1024; 
    sum |= c;
    a = b, b = c;
  }
  return sum;
}


int ans = 0;
ll sum = forceCal(min(n, 20), a, b);
while (sum > 0) {
  if (sum % 2 == 0) {
    ans++;
  }
  sum /= 2;
}

printf("%d\n", ans);

三、最小生成树

题意：给一个无向图，求最小生成树。

-）要求制定的几个顶点必须是叶子节点。
-）输入有自环
-）输入有重边

思路：首先输入的时候，去掉自环，重边取最小那条边。

然后优先处理选中的叶子节点，看是否可以找到一个非选中的叶子节点，可以了，取最小的，然后删除当前点（缩点）。
之后，剩下的顶点和边就是普通的图了，求最小生成树即可。

我曾在《2021 TPC 腾讯程序设计竞赛 热身赛》提到过，我很多年没做过几何体和图论题了。
最小生成树我现在只会O(E log(E))的并查集 和 O(n^2) 的 prime 算法。
我不想写并查集，便去我的算法模板里去找有没有其他算法。
复习了 SPFA 等一堆复习算法后，发现那个是求单源最短路的，浪费时间。
于是又去找 prime 算法怎么使用堆优化降低到 O(E log(E))。

学会低复杂度的 prime 后，发现既然要写堆了，那还不如写并查集简单。

于是，最后我又老老实实的去写并查集了。

写完还编译错误一次，原因是我的本地是 c++17编译的，使用了 auto [a, b] = ... 的语法，判题系统 OJ 不支持。
修改成普通的语法后，就通过了。

一个最小生成树敲了 80 分钟。
我明天有必要整理一个 prime 算法 O(E log(E))复杂度的最小生成树的模板。
以后遇到最小生成树，还是优先使用并查集的，简单高效，prime 算法还容易出错吧。

四、可整除连续子序列

题意：给一个序列，问是否存在一个连续子序列，使得子序列中任意两个元素都存在整除关系。
如果存在，返回最长的长度。

思路：起初看，暴力计算O(n^2)的复杂度，会超时。

但是分析一下，如果一个子序列满足题目要求，那么这个子序列排序后，从小到大是倍增的关系。
倍增代表数据增长的很快，而数据范围只有10^9​，这意味着子序列最长只有 32 位。
这样暴力计算的复杂度就是 O(n log(n))的复杂度，不会超时了。

由于最小生成树我浪费太多时间了。
这道题读题后，发现非常简单。

截图中可以看到时间。敲完代码后已经 21:02 了，比赛结束两分钟了，遗憾。

PS：复旦大学的同事提供了另一种思路，不需要暴力 check，不过复杂度还是 O(n log(n))。
如果新来的数字已存在双指针序列内，或者是最大值或者最小值，我们可以 O(1)判断是否满足。
其他情况，则可以假设 a[i] < val < a[i+1]，队列使用 map 或者 set 储存，理由红黑树的有序性，可以 upper_bound 在 log(n)的复杂度内找到这个位置。
然后只需要判断 a[i] 和 a[i+1] 是否满足即可。

vector<int> vec;
unordered_map<int, int> m;

bool OK(int v) {
  if (m.count(v)) return true;

  for (auto& p : m) {
    int u = p.first;
    if (u % v == 0 || v % u == 0) {
      continue;
    }
    return false;
  }
  return true;
}

int ans = 1;

int l = 0, r = 1;
int num = 1;
m.clear();
m[vec[0]]++;

while (l < n && r <= n) {
  while (r < n && OK(vec[r])) {
    num++;
    m[vec[r]]++;
    r++;
    ans = max(ans, num);
  }

  if (r == n) {
    break;
  }

  while (l < r && !OK(vec[r])) {
    num--;
    m[vec[l]]--;
    if (m[vec[l]] == 0) {
      m.erase(vec[l]);
    }
    l++;
  }


  num++;
  m[vec[r]]++;
  r++;
}

printf("%d\n", ans);

五、排列矩阵

题意：给 k 个矩阵，每个矩阵的行是 a[i]，列是 m。
k 个矩阵排列之后，可以组成 N * m的大矩阵，这个大矩阵存在一个最大的全 1 子矩阵。
求所有排列里面，最大的全 1 子矩阵。

思路：k 和 m 的数据范围很大，都是10^5。
但大矩阵的元素个数也不超过 10^5。

方法一：暴力枚举。

枚举大矩阵列的左边界和右边界，求最大的全1子矩阵。
此时，中间肯定都是全 1 的矩阵，上面取一个最大的非全1矩阵，下面取一个最大的非全1矩阵，求和即可。

复杂度：O(m^2 * N)

优化：我想的优化主要是枚举的过程中，利用上一次循环的信息，这样就少一次循环。
大家也已想想细节，怎么复用之前的信息。

六、最后

这次比赛又有点不理想了，第四题可以做出来，就差几分钟。
而第三题这么简单的最小生成树树，一开始我却不愿使用并查集去写，最后还是选择使用并查集写，中间上网一个小时去复习算法了。
PS：还学错了，一开始学的 SPFA 最短路。。。

后面写篇文章先分享下最小生成树吧，比赛期间上网一个小时，还是对最小生成树加深了不少印象的。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code