2023 China Collegiate Programming Contest Shenzhen Site-526互联

写在前面
A
F
G
L
I
E
M
K
写在最后

写在前面

补题地址：vjudge。

以下按照场上过题顺序排序。

首银。

比游记更早出来，没想到吧。

游记链接：留坑。

A

场上先开的这道。

直觉是考虑先全部区间加直到最小值，然后将非最小值全单点加，再重复上述过程。然而会被递增序列卡掉。

瓶颈在于单点加太多了。大神 dztlb 手玩了几分钟发现可以对目标的值域二分，对于某个值域区间，先对后一半每个位置先做单点加，然后对后一半区间加直到后一半的最小值，然后再递归处理前后两半。

然后我就上机开写了，调的时候慢了几分钟呃呃，幸好在 Nebulyu 指导下一发过了。

F

真签到。

枚举所有环边检查删边后节点度数，有度数大于等于 5 的点则贡献为 0，否则贡献为 \(n\) 减去度数为 4 的点。

我在写 A 的时候 dztlb 和 Nebulyu 出的思路，我下机之后 dztlb 上机开写，稍微调了下一发过了。

场下也是一发过了呃呃。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const int kM = 2e5 + 10;
//=============================================================
int n;
int edgenum, head[kN], v[kM], ne[kM];
int into[kN], into1[kN], num4, num5, num6;
bool incircle[kN];
LL ans;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Topsort() {
  std::queue <int> q;
  for (int i = 1; i <= n; ++ i) {
    if (into[i] == 1) q.push(i);
  }
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    incircle[u_] = false;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if ((--into[v_]) == 1) q.push(v_);
    }
  }
}
int check(int u_, int v_) {
  if (num6) return 0;

  if (into1[u_] == 5) -- num5, ++ num4;
  if (into1[u_] == 4) -- num4;
  if (into1[v_] == 5) -- num5, ++ num4;
  if (into1[v_] == 4) -- num4;

  int ret = num5 ? 0 : n - num4;

  if (into1[u_] == 5) ++ num5, -- num4;
  if (into1[u_] == 4) ++ num4;
  if (into1[v_] == 5) ++ num5, -- num4;
  if (into1[v_] == 4) ++ num4;

  return ret;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  n = read();
  for (int i = 1; i <= n; ++ i) incircle[i] = true;
  for (int i = 1; i <= n; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
    into[u_] ++, into[v_] ++;
    into1[u_] ++, into1[v_] ++;
  }
  for (int i = 1; i <= n; ++ i) {
    if (into[i] == 4) ++ num4;
    if (into[i] == 5) ++ num5;
    if (into[i] >= 6) ++ num6;
  }

  Topsort();
  for (int u_ = 1; u_ <= n; ++ u_) {
    if (!incircle[u_]) continue;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (u_ > v_ || !incircle[v_]) continue;
      ans += check(u_, v_);
    }
  }
  printf("%lld\n", ans);
  return 0;
}

G

dztlb 写 F 的时候开了这道，一看 \(k\le 10\) 给我笑烂了哈哈

首先预处理所有串的哈希值，对于每次询问都枚举所有串并检查，检查时不断地通过哈希+二分求得第一个不同的位置即可。

F 写完之后我上机开写，场上一发过了，写完直接怪叫了一声，太激动了。

现在才刚过去一个多小时，这个时候看了眼名次我草三十多，一发罚时都没有，感觉至少银是相当稳了，甚至还有希望——

真的如此吗？

L

那么问题来了，直到现在都是我和 dztlb 在写，Nebulyu 在干什么呢？

时间回到我在写 A 的时候，期间一直在看榜，发现 L 过的数量仅次于 A，并且全都是一发过的。然而是期望，我的数学一直是一拖四于是丢给了 Nebulyu。

Nebulyu 首先考虑求 \(f_{i, j}\) 表示第 \(i\) 次生长时还可以生儿子的深度为 \(j\) 的节点的数量，于是有了一个 \(O(k^2)\) 的 DP，然而优化不了，于是寄。一直推到我写完 G 的时候出了一个好像是斯特林数的思路，于是开始大力推式子，代码也很有思路了于是上机了。这个时候 I 过了不少也，我在写的时候他们开了 I 但是没什么想法于是我就去开了 I。

然后 L 就卡住了呃呃，又推了 1h 多发现斯特林数的思路是假的，跑出来的和手动打表出来的对不上，陷入僵局。这个时候 I 出来了，需要去抄一个 Pollard_Rho 于是我就先上去开写了。

在我写 I 的时候 dztlb 突然灵机一动相当了另一种思路，然后推了下发现超级可行而且比我那逼泼辣的肉好写多了，于是开冲！

大力写了一发发现被卡常了，改线性求逆元之后一发过了，赢！

此时距离封榜没多少时间了，这个时候的排名加上打星是五十多，还在银线内，而且手里还有一道题马上就出来了，感觉至少银是稳了，激动人心！

然后下面是补题。

考虑记第 \(i\) 轮加点后所有节点深度和为 \(f_i\)，显然每轮 \(f\) 的增量与树的实际形态是无关的，仅需考虑第 \(i\) 次添加的结点 \(D_i\) 的深度，即有：

\[f_k = f_{k-1} + M\times E(D_k) = M\times \sum_{i=1}^k E(D_i) \]

\(E (D_i)\) 取决于被选出的结点的深度。手玩发现另一个显然的性质是每轮中叶节点的数量是固定的，第 \(i\) 轮加点后的叶节点数量即为 \((M-1)\times i + 1\)。记第 \(i\) 轮加点后所有叶节点的集合为 \(P_i\)，则有：

\[E(D_i) = \dfrac{E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u)\right)}{(M-1)(i-1) + 1} + 1 \]

对于上式的分子考虑递推，即考虑从 \(P_{i-1}\) 中选出某个点进行生长来得到 \(P_i\)，设被选出的点深度为 \(d\) 则有：

\[\begin{aligned} E\left(\sum\limits_{u\in P_{i}} \operatorname{dep}(u)\right) &= E\left( \left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u)\right) - d + M(d + 1) \right)\\ &=E\left( \left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u)\right) +(M-1) d + M \right)\\ &=E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + (M-1)E\left( d\right) + M \end{aligned}\]

然后考虑 \(E(d)\) 的实际意义，即从 \(P_{i-1}\) 中选出一个节点的期望深度，则有：

\[\begin{aligned} E\left(\sum\limits_{u\in P_{i}} \operatorname{dep}(u)\right) &=E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + (M-1)E\left( d\right) + M\\ &= E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + \frac{M-1}{(M-1)(i-1)+1}E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + M\\ &=\dfrac{(M-1)i + 1}{(M-1)(i-1) + 1}E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + M \end{aligned}\]

记 \(g_i = E\left(\sum\limits_{u\in P_{i}} \operatorname{dep}(u)\right)\)，则有：

\[\begin{aligned} g_i &= \dfrac{(M-1)i + 1}{(M-1)(i-1) + 1}g_{i - 1} + M \end{aligned}\]

答案即：

\[f_k = M\times \sum_{i=0}^{k-1}\left( \dfrac{g_i}{(M-1)(i-1) + 1} +1\right) \]

预处理下逆元复杂度 \(O(K)\) 级别。

场上似乎不是这个推法，必须每次对分母再求个逆元，复杂度是 \(O(k\log p)\) 但卡了卡常之后也跑过去了。

I

时间回到 Nebulyu 在大战斯特林数的时候。

首先是 dztlb 发现 \(k>4\) 时 \(a\) 和 \(b\) 的上界很小，因为当 \(k\) 较大时非常容易出现 \(a^k - (a-1)^k >n\) 从而导致没有整数解，于是此时可以移个项变成 \(a^k = b^k + n\)，枚举 \(b\) 之后二分检查是否存在 \(a\) 使得方程有解。

对于 \(k=3\) 的情况，考虑立方差公式有 \(a^3 - b^3 = (a-b)(a^2 + ab + b^2) = n\)，考虑枚举 \(n\) 的因子 \(d\)，则有：

\[\begin{cases} a - b = d\\ a^2 + ab + b^2 = \frac{n}{d} \end{cases}\]

大力求根公式判断是否有正整数解即可。

对于 \(k=4\) 的情况考虑平方差公式，同样考虑枚举 \(n\) 的因子，有：

\[\begin{cases} a^2 - b^2 = d\\ a^2 + b^2 = \frac{n}{d} \end{cases}\]

同样大力求解判断是否有正整数解即可。

用计算器玩了下发现 \(n\le 10^{18}\) 的因数也就是 \(10^5\) 级别，然后问题是如何枚举 \(n\) 的所有因数。没想到什么很好的方法，然后我脑子一抽，那就大力 Pollard_Rho 质因数分解 + dfs 枚举质因数次数就好了哈哈我草

于是开始翻 OI-wiki，发现 Pollard_Rho 才 \(O(n^{\frac{1}{4}})\) 并且在 \(10^{18}\) 内可以保证是超大概率正确的，于是开抄！

此时是以 L 优先的双线开题，过了 L 之后也几乎写好了，写了将近两百行妈的。

调的时候送午饭来了，一人一瓶 500cc 的可口+双层鸡排堡我草，tama 的 Nebulyu 和 dztlb 在我旁边吃汉堡我他妈调题，这下成代码黑奴了，调到后面精神状态不太好了，甚至开始拆米浴了妈的。

发现 \(k=3\) 和 \(k=4\) 的情况都写挂了妈的，改完之后把所有 LL 全换成 __int128 之后过样例了，交了一发 CE 了，发现是 sqrt 不能传入 __int128，于是强制类型转换了下一发过了。

然后开始怪叫，开始吃汉堡！

后面就摆了，看了下罚时相当优秀估计是稳银了，口了一下 DEK 发现一时半会也写不完，然后开始玩电脑看榜鉴赏逆天队名。

玩麻酱连连看的时候我绷不住了旁边队也绷不住了哈哈。

结束！

E

你以为是数据结构？错误的其实是结论提。

设 \(x,y\) 分别为出现次数 \(\operatorname{cnt}\) 最多和次多的两种颜色。

考虑一种特殊情况，设它们出现次数的最高位分别为 \(m_x, m_y\) 并且 \(m_x = m_y=m\)，则答案的上界为 \(2^{m + 1} - 1\)，并且肯定存在一种方案使得答案可以取到这个上界。至于怎么取到，考虑先选中整个序列，然后不断地从两边缩小区间，则肯定存在某个时刻使得 \(\operatorname{cnt}_x, \operatorname{cnt}_y\) 中的某一方变为 \(2^{m} - 1\)，而另一方的最高位仍然为 \(m\)，此时即可达到这个上界。

然后考虑更一般的情况，显然答案的下界为 \(\operatorname{cnt}_x \operatorname{or} \operatorname{cnt}_y\)，然后同样考虑上述不断缩小区间的过程，显然在某一时刻可以使得答案包括 \(\operatorname{cnt}_x \operatorname{or} \operatorname{cnt}_y\) 中所有为 1 的位的同时，使某一方的 \(\operatorname{cnt}\) 中 \(0\sim \operatorname{log}_2 (\operatorname{cnt}_x \operatorname{and} \operatorname{cnt}_y) - 1\) 位上全为 1，则答案的上界为 \(\operatorname{cnt}_x \operatorname{or} \operatorname{cnt}_y \operatorname{or} (2^{\operatorname{log}_2 (\operatorname{cnt}_x \operatorname{and} \operatorname{cnt}_y) - 1} - 1)\) 并且一定可以取到。

综上，答案即：

\[\operatorname{cnt}_x \operatorname{or} \operatorname{cnt}_y \operatorname{or} \left(2^{\left\lfloor\operatorname{log}_2 (\operatorname{cnt}_x \operatorname{and} \operatorname{cnt}_y)\right\rfloor - 1} - 1\right) \]

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, cnt[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    for (int i = 1; i <= n; ++ i) cnt[i] = 0;
    for (int i = 1; i <= n; ++ i) {
      int x = read(); ++ cnt[x];
    }
    std::sort(cnt + 1, cnt + n + 1);
    int ans = (1 << (std::__lg(cnt[n] & cnt[n - 1]))) - 1;
    printf("%d\n", cnt[n] | cnt[n - 1] | ans);
  }
  return 0;
}