「Summary」CQ 2023 省选前考试记录

I hope it was enough to be the way you are when everything’s falling apart.

2023-03-27

我是 🤡 。

飞鸟和蝉 (fly)

4h 都没发现一个显而易见的错误是什么水平？

第一眼看起来很简单阿，直接线段树优化建图，从前往后 dp 顺着做就好了，是 $n\log n$ 的。
觉得只给了 $3e5$ 的数据范围有点奇怪，这个按理来说是 $n \log^2n$ 的才对阿。
但是还是打完了，发现第五个大样例没过，查了一下小细节，改了就过了，恩，那这个做法肯定是对的 (flag) 。

考完之后， flower_sang 问我这个往回跳的情况怎么处理，我经过 $114514 \mu s$ 发现我是小丑，完全没有考虑这个 case ，心脏骤停.jpg。

---

于是把回跳这个情况考虑进去还是很好做，因为从每个点出发走 $d$ 步能到达的点存在于一个区间里面，记作 $[l_i, r_i]$，现在去二分这个 $d$，满足条件的 $(u, v), u < v$ 当且仅当 $r_u < v, l_v > u$ 。
但是这样每次 check 是 $n \log^2 n$，发现可以不用二分，直接倍增这个 $d$ 就可以了，最后的复杂度是 $n \log^2 n$，注意一下常数优化。

智巧灵蕈大竞逐 (fungus)

2.5h 激情 6.5k code 拿到 16pts 好成绩

首先看到 $k = 0$ 的情况，非常好做阿，直接点对点换就好啦。思考为啥这个好做，因为这样有解的局面只在 $s$ 和 $t$ 的每种字符相等的情况下出现。
延续上面这个想法，我们首先用 预置 把 $s$ 里面每种字符的数量调的和 $t$ 一样就好做了。
于是我开始乱搞，首先记录每种字符在两个图里面的差值，然后先用一遍预置，在每次都在预置过的矩阵里面交换一个，又预置回去，这样每次就能修掉一个。
于是我写不出来了 🤡

---

正解非常妙阿，代码相当好写。
你把整个过程倒过来，把初始的局面看成一个预置。
经过这样的转化后，再看这个预置操作，发现这样的操作的意义在于把一个和预置图形一样的矩形内的所有符号替换成通配符，而最后的目标就是把终止局面全部消成通配符。
做法就很明显了，每次挑一个能够被消掉的预置矩阵放在左上角，通过交换把需要的字符挪过去就可以了，重复这个操作即可。

筛法 (sieve)

暴力能写 WA 的也没几个了

暴力写挂了，虽然也没几个人写了。
一个很脑瘫的思路是在每个右端点记录上能和它匹配上的左端点，这个玩意就很好二分了，随便搞搞应该就有二十分，然而我写挂了。

---

正解是根号分治，非常复杂，out of my ability 。

2023-03-28

自闭 自闭 自闭， 2.5h 写 t1 的我十分坚定阿。

braca

origin link

这个 *2700 怎么做的这么艰难 😢 。
假设已经拿到了原来的染色方案，很简单地就能构造出一定不变的解，因为每一个极长连续的颜色段可以移动的区间是固定的，那么我们让这个颜色段在其中运动起来，放在最左边和最右边时重合的部分就是一定不变的位置。
反向构造也很简单，考虑这样一个 $mid$ 表示将所有有颜色的段全部挪到左边的时候末尾剩下的没有颜色的块的个数，那么一定染色的格子 $+k$ 就能对应 $p_i$。
这个 $k$ 不一定要很大，因为我们只需要长度为 $2,3$ 的连续段就可以处理大于 $2$ 的连续空白，所以 $k \in [0, 3]$ 就可以解决问题了。
有一些细节，写得有点慢，幸好没错。

bayern

origin link

*3400 放 t2 属于是省选 day3 难度对吧 😅 。

我考场根本就没想到从 $s,t$ 的长度入手。
考察这两个字符串变得相同这个过程，发现 $s, t$ 必定是由一个长度为 $\gcd(\mid s \mid, \mid t \mid)$ 的串循环拼接出来的。

设上下差了 $a$ 个 $A$，$b$ 个 $B$，于是要求是 $a \mid B \mid = b \mid A \mid$。

从没有 ‘?’ 的情况开始讨论。

$a = b = 0$

可以直接枚举 $\mid A \mid, \mid B \mid$ ，于是答案是

$$ \begin{aligned} &\sum_{i = 1}^n \sum_{j = 1}^n 2^{\gcd(i, j)} \\ =&\sum_{d = 1}^n 2^{d} \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i, j) = 1] \\ =&\sum_{d = 1}^n 2^d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) \lfloor \frac{n}{di} \rfloor^2 \end{aligned} $$

$a,b > 0$

如果 $a$ 和 $b$ 不互质就可以同时除以 $\gcd(a, b)$ ，于是现在只考虑 $a,b$ 互质的情况，现在 $\gcd$ 一定在 $[1, \lfloor \frac{n}{\max\{a, b\}} \rfloor]$ ，则答案为 $\sum_{i = 1}^{\lfloor \frac{n}{\max\{a, b\}} \rfloor} 2^i$ 。

现在加入有 ‘?’ 的情况。
定义 $f(a, b)$ 表示在差为 $a, b$ 的情况下的方案数，令 $cnt_a, cnt_b$ 分别表示 $s, t$ 中 ‘?’ 的个数。

$$ \begin{aligned} &\sum_{i = 0}^{cnt_a} \sum_{j = 0}^{cnt_b} \binom{cnt_a}{i} \binom{cnt_b}{j} f(a + i - j, b + (cnt_a - i) - (cnt_b - j)) \\ =&\sum_{t = -cnt_b}^{cnt_a} f(a + t, b + cnt_a - cnt_b - t) \sum_{j = 0}^{cnt_b} \binom{cnt_b}{j}\binom{cnt_a}{cnt_a - t - j} \\ =&\sum_{t = -cnt_b}^{cnt_a} f(a + t, b + cnt_a - cnt_b - t) \binom{cnt_b + cnt_a}{cnt_a - t} \end{aligned} $$

最后的复杂度是 $\Theta(n \log n)$

psg

origin link

你放道计算几何真以为我会做吗？
再见

2023-03-29

rectangle

origin link

良心签到题，可以先建出来小根笛卡尔树，然后对于一个矩形区域计数，记下面一层高度为 $hi$，当前层高度为 $h$，宽度为 $wid$ ，方案数是 $((h - hi) \times hi + \frac{(h - hi + 1)\times (h - hi)}{2}) \times \frac{(wid + 1) \times wid + 1}{2}$ 。

于是 $\Theta(n)$ 统计即可。

tree

origin link

我是脑瘫，这个要用矩阵快速幂很明显，但是问题在于我没想清楚这个答案最根本和啥有关，构建不出来转移矩阵。

从 $d = 1$ 开始考虑，发现换根就可以了， @lydd 问我这个换根怎么写，其实可以很无脑，只是常数非常大，贴个代码。

inline void update(int u) {
  tag[u] = 0;
  if (sg[u]) { if (cnt[u][0] == 1) tag[u] = dp[u][0]; }
  else tag[u] = dp[u][1];
}

void dfs1(int u, int fath) {
  for (int v : G[u]) if (v != fath) {
    dfs1(v, u);
    cnt[u][sg[v]]++;
  }
  if (cnt[u][0]) sg[u] = 1;
  for (int v : G[u]) if (v != fath) {
    dp[u][1] += tag[v] + (sg[v] == 0);
    if (!sg[v]) dp[u][0] += tag[v] + 1;
  }
  update(u);
}

void dfs2(int u, int fath) {
  int tsg, ttag, tcnt[2], tdp[2];
  tsg = sg[u], ttag = tag[u];
  memcpy(tcnt, cnt[u], sizeof(tcnt));
  memcpy(tdp, dp[u], sizeof(tdp));
  tot += tsg, sum[tsg] = (sum[tsg] + ttag) % Mod;
  if (!tsg) sum[tsg] = (sum[tsg] + 1) % Mod;
  for (int v: G[u]) if (v != fath) {
    --cnt[u][sg[v]];
    if (!sg[v]) dp[u][0] -= tag[v] + 1;
    dp[u][1] -= tag[v] + (sg[v] == 0);
    sg[u] = cnt[u][0] != 0;
    update(u);
    ++cnt[v][sg[u]];
    if (!sg[u]) dp[v][0] += tag[u] + 1;
    dp[v][1] += tag[u] + (sg[u] == 0);
    sg[v] = cnt[v][0] != 0;
    update(v), dfs2(v, u);
    sg[u] = tsg, tag[u] = ttag;
    memcpy(cnt[u], tcnt, sizeof(tcnt));
    memcpy(dp[u], tdp, sizeof(tdp));
  }
}

简单来说在第一遍 dfs 时计算 $v$ 对 $u$ 的贡献，在第二遍 dfs 时首先撤销 $v$ 对 $u$ 的贡献，然后加入 $u$ 对 $v$ 的贡献，最后还原。

然后记录 $dp_{0, 1}$ 表示在下一棵树上有多少点为根可以对当前根是产生贡献，发现这个东西可以传递下去，矩阵快速幂即可，复杂度 $\Theta(n \log d)$ 常数很大。

sort

origin link

考试的时候没什么时间做了，但是发现了要卡满这个下界的条件是不存在长度大于等于 3 的下降子序列。

那么记 $dp_{i, j}$ 表示前 $i$ 个数中最大的为 $j$ 的方案数，如果第 $i + 1$ 个数比 $j$ 小，那么当前一定是取可行的最小数，此时 $dp_{i, j} \rightarrow dp_{i + 1, j}$ ，否则 $\sum_{k < j}dp_{i, k} \rightarrow dp_{i + 1, j}$ 。

然后把这个过程扔到坐标系上，表示从 $(0, 0)$ 走到 $(i, j)$ 且始终只经过 $(i \le j)$ 的格子 $(i, j)$ 的方案数，可以参照数位 dp 的计算方式去算。