ICPC/CCPC 2024
SUNCHAOYI
·
·
生活·游记
2024.8.25 组队
由我 SUNCHAOYI 和两位大佬 oahgnail, Erusel 组成。
【说句闲话，由于组队有点匆忙，我和 Erusel 愣是花了一下午从新生群中的强省一个个人肉搜索找到的队友。】
好了，队名还是要乱搞的，于是就有了：
中文队名：仚屳屲冚(xiān xiān wā kǎn) \\
英文队名：Supercalifragilisticexpialidocious
2024.8.28 第一次训练
打的是今年的杭电多校（2），时间不太多只打了四个小时。
一人四题，我开的是最后四题毒瘤数据结构+模拟+字符串+神必图论。发现自己只会一题，不过还是 WA 了一发。把两题弱智模拟打过以后就到了口胡环节，反正就是一顿口胡后来不及写一点。
由于第一次打，四小时只干出了五题。
赛后补题：
- oahgnail在魔方这题写了一个超级大模拟，但被Erusel一语道破只需要处理六个角的情况，然后瞬间破防。
- 我把地牢这题订正了，简单来说就是状压处理后的情况搜索，细节很多感觉不太好写。
- 顺便订正了图计算，发现和 \texttt{CSP 2022 T3} 的思路相近，用字符串哈希的形式去判断是否相等，直呼好 trick。
2024.8.30 第二次训练
打的杭电多校（3），不过连四小时都没打满，仍然还是过了五题。
这次开题发现有一道比较裸的线段树和一道需要处理的图论，果断开写。
-
单峰数列
直接通过差分将信息进行转化，然后维护差分是否 >,<,= 以及单峰（可以由前面的信息进行转化）的状态，单点更新，区间查询，甚至不需要 pushdown(cur)。写完直接过样例，一发 AC。
-
比特跳跃 定义 x \to y 的代价是 k \times (x | y)，主要需要分析出什么情况下使用跳跃是更优的。先跑一遍最短路，然后用跳跃的代价去更新最短路即可完成。【彩蛋：本人把 dij 给写错了导致一直过不了样例（虽然最后还是一发 AC 了，但是显得很蠢）。】
队友这边，还一直卡在三分上，直接罚时一车（好在通过了）。
2024.8.31 哈希之自然溢出啥事没有？
万恶之源：不基本子串结构。
毒瘤数据竟然把这个给卡了，所以好好去研究了一下。
自然溢出相当于是取余 2^{64}，所以需要尝试构造出两个字符串，哈希值能够 \mod 2^{64} 一样即可。
构造 baaa ... a (a \times 64) 和 caaa...a (a \times 64)。对于第一个位置上字符的哈希值，hsh('b')\times p^{64} \mod 2^{64} 和 hsh('c')\times p^{64} \mod 2^{64}。由于 2 \mid p，则有 2^{64} \mid p^{64}，因此第一个位置上哈希值去模后的贡献均为 0，即会出现哈希碰撞的情况。
首先规定：
-
s_1 = 'a'
-
-
s_i = s_{i - 1} + \overline {s_{i - 1}}
-
f_i = hsh (s_i) - hsh (\overline {s_{i}})
显然 s_i 的长度为 2^{i - 1}，那么就可以得到：
hsh(s_i) = hsh(s_{i - 1}) \times p^{2^{i - 1}} + hsh (\overline {s_{i - 1}})\\
hsh(\overline{s_i}) = hsh(\overline{s_{i - 1}}) \times p^{2^{i - 1}} + hsh(s_{i - 1})
作差可知，f_i = f_{i - 1} \times (p^{2^{i - 1}} - 1)。有奇偶性可知，2^{64} \mid f_{64}，即 s_{64} 符合条件，可仍然可以缩减长度。
由因式分解可知 p^{2^{i - 1}} - 1 = (p^{2^{i - 2}} - 1) \times (p^{2^{i - 2}} + 1) = (p^{2^{i - 2}} + 1) \times (p^{2^{i - 3}} + 1) \times \cdots \times (p^{2^1 } + 1) \times (p^{2^1} - 1)，因此 2^{1 + 2 + \cdots (i - 1)} = 2^{\frac{i(i - 1)}{2}} \mid f_i。所以 i > 11 时均会冲突，即最小构造出 s_{12} 和 \overline{s_{12}} 便会冲突。
2024.09.06 网络赛模拟
VP 了去年网络赛的第一场，最后切了六道题。然而口胡出的是九题，但是没来得及实现，最后 1.5 小时没有过题，这是十分遗憾的。以及我们是超级无敌多的罚时，已经没救了……
我写的是 A,G,I，队友写的 D,J,L，反正只有 L 是一次过的。
然后再是 $D,J$，好像一个是并查集和连通块的题，还有一个数学签到（不过也分析了蛮久的样子）。
$I$ 是一道细节巨多的计数 DP（这种东西怎么老是丢给我），需要时间和空间上的双重优化。设 $dp_{i,j,k}$ 表示第 $i$ 位填 $j$，然后 $k$ 是一个状态，记录大小写以及数字是否出现过。由于相邻两个不能重复，所以我们可以用之前的总数减去相邻两个相同时的情况，从而优化复杂度到 $O(62 \times 8 \times n)$。然后又发现可以用滚动数组优化空间，变为 $O(62 \times 2 \times 8)$，于是做完了。但写的时候一个地方打错了，以及滚动数组清空写炸了，导致 WA 了好多好多次（没救了……）。
然后 $H$ 是我们快讨论出来的题目，但是被哈希如何快速判断 $p$ 是不是 $S_i$ 的周期的时候卡住了。后来最后想到了 border，但是显然没时间了。首先先想到了对于 $S_p$，显然 $p$ 是它的周期，然后发现可以二分 $w(w \ge p)$，从而找到 $S_p,S_{p + 1},\cdots,S_w$ 均满足 $p$ 是它们的周期。之后就是离线处理 $(k,l,r)$，分别按照 $k,w$ 从大到小排序，处理询问的时候利用双指针的想法将 $w \ge k$ 的均加入到线段树中，然后就可以区间查询得出答案了。
由于不太会字符串，自然也不懂 $\texttt{border}$ 的原理，于是恶补一下。
简单来说，若 $s$ 的一个子串（非原串）既是它的前缀又是它的后缀，则这个子串是它的 $\texttt{border}$。若 $s[1,p] = s[|s| - p + 1,p]$，则 $s[1,p]$ 为 $\texttt{border}$，可以推出 $|s| - p$ 是 $s$ 的周期。证明如下：
若一个字符串周期为 $p$，则 $\forall x \ |s| - p$，有 $s[x + p] = s[x]$。那么设 $t$ 为 $s$ 的 $\texttt{border}$ 所对应的长度，则 $\forall x \le t$，$s[x + (|s| - x)] = s[x]$，变形可得，$\forall x \le |s| - (|s| - t)$，$s[x + (|s| - t)] = s[x]$，符合周期定义。
MD 这提交了将近 $20$ 次，原来 `s = ch + s` 也会导致超时，但是 WA 又是怎么回事？？？改成双哈希也挂，取模又会超时？？？要红温了！！！！！！
### $2024.09.07$ 网络预选热身赛
测试设备，似乎都没啥问题，希望明天不要出锅。
总的来说，打得并不好。热身赛一共只有三道题，队友先想了第三题但是出锅了导致第二题在将近比赛结束的时候才过，还因为神必错误挂了两次，因此排名很靠后。哎不是今天怎么都是我在过题，人麻了……
$A$ 就是一个搜索，需要计算出形如 $1,0,8$ 这种 `#` 内部有 $0,1,2$ 个洞（用 `.`）的个数。没啥好说，不停 $\texttt{dfs}$ 去处理就好了，很快写完，一发过。
$C$ 是先写的，但是因为题目描述不清，口胡过于粗糙等原因写了好久但是 WA。
$B$ 就是给 $num_i$ 个 $i(i \in [0,9])$，然后从中取 $m$ 个使得组成的数最小。难点在于如何在构造大数的同时取模。我的想法是令 $f_{i,j}$ 表示有 $2^{j - 1}$ 个数字 $i$ 时取模的值，可以列出递推式，$f_{i,j} = f_{i,j - 1} \times 10^{2^{j - 2}} + f_{i,j - 1}$。在构造的时候需要特殊处理最高位（当然也就要特判 $m = 1$ 答案为 $0$ 的情况），然后按照进制为倒序循环 $30 \to 1$，计算即可。当然，赛后讲题发现有种更显然的做法，就是 $99 \cdots 9 = 10^k - 1$，好好好，要破防了……这题的锅还是队友检查（一眼）出来的，由此可见团队合作的重要性！（我自己检查 $15$ 分钟死活没看出来）
$D$ 应该就没尝试过，所以就先不说了。
明天加油！
### $2024.09.07$ CCPC 网络预选
省流：做题不在状态，做出 $5$ 题，打成屎了。
因为网络问题还延长了 $1$ 小时，但总归还有点影响。
很快地打完了 $B,L$ 签到，还被 $B$ 所有数都一样的情况给恶心了一发。然后我开始开 $K$，想到了一种自己认为很对的算法，没怎么和队友讨论就交了，还 WA 了两次才发现假，好在和队友讨论了一下醒悟了过来，最后在一大堆分类讨论中过了这题。赛后发现只需要考虑 `lowbit(n)` 与 $k$ 的大小即可。
然后就到了本场比赛问题最大的 $D,E$，$E$ 纯靠队友开题，然后一直处于一种想到了然后发现假了/复杂度超了的情况，而且还有两个小问。一直到了 $3.5$ 小时左右才过这题。
$D$ 题不知咋的我们三个都无思路，却发现榜上一大堆的人过了，于是我们都开始慌了。直到我无意发现时间限制是 $2$ 秒，才醒悟原来朴素的区间 $DP$ 就可过，然后才开写，期间队友写红温了，还换了个人来重构，总之在 $5$ 小时的时候才过，而且还因为初始化问题 WA 了两次。
$J$ 想了，题意顺利转换了，但是线性基不会，所以没法写。$I$ 想了，但是很复杂，先是 $O(n^4)$ 的算法，然后队友用一种我没怎么理解的算法写了，不过到结束也没有成功调出来（悲）。
赛后一顿反思、复盘……
第二天开始补题，嗯哼这个 $D$ 怎么这么简单？嗯哼这个 $C$ 怎么没看过题，但是这么可做？$I$ 想到了一种简单做法，那就实现一下？
枚举最短时间 $t$，对于一个真实存在的 $t$（可以通过预处理记录）。设 $dp_{i,j}$ 表示前 $i$ 个人拿了 $j$ 个行李的方案数（注意对答案的贡献还要乘上 $t$，我就是这里被卡了很久很久）。由于枚举的是最短时间 $t$，就需要这个时间 $t$ 一定得取到，对于一个人选择行李的坐标范围为 $[1,x - t]$（$x$ 表示当前的人所在的坐标，由于直接转移可能会因为 $x - t$ 都未取到而导致错误，所以我们通过两次 dp，分别处理 $[1,x - t]$ 和 $[1,x - t - 1]$ 的情况，作差得到答案。
转移方程（只写出一个，其中 $sum_i$ 表示坐标上 $[1,i]$ 的行李数）：
$$
\begin{cases}
dp_{0,0} = 1\\
dp_{i,j} = dp_{i,j}+dp_{i-1,j}\\
dp_{i,j + 1} = dp_{i,j + 1}+dp_{i - 1,j} \times \max (0,sum_{\max(0,b_i - t)} - j)\\
tot = tot+\sum_{i = 1}^{\min (n,m)} dp_{m,i}
\end{cases}
$$
最后的代码如下，还被 codeforces 的卡常整红温了。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 505;
const int MOD = 998244353;
inline int read ();
int n,m,a[MAX],b[MAX],vis[MAX],sum[MAX];
int dp[MAX][MAX],ans,tot1,tot2;
//dp[i][j] 前 i 个人选了 j 个行李的方案数
int main ()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
n = read ();m = read ();
for (int i = 1;i <= n;++i) a[i] = read ();
for (int i = 1;i <= m;++i) b[i] = read ();
sort (a + 1,a + n + 1);sort (b + 1,b + 1 + m);
for (int i = 1;i <= m;++i)
for (int j = 1;j <= n;++j)
if (a[j] < b[i]) vis[b[i] - a[j]] = 1;
for (int i = 1;i <= n;++i) ++sum[a[i]];
for (int i = 1;i <= 500;++i) sum[i] += sum[i - 1];
for (int t = 0;t <= 500;++t)
{
if (!vis[t]) continue;
tot1 = tot2,tot2 = 0;
if (!tot1)
{
for (int i = 1;i <= m;++i)
for (int j = 1;j <= n;++j) dp[i][j] = 0;
dp[0][0] = 1;
for (int i = 1;i <= m;++i)
for (int j = 0;j <= min (m,sum[b[i]]);++j)
{
dp[i][j] += dp[i - 1][j];dp[i][j] %= MOD;
if (j + 1 <= min (m,sum[b[i]])) dp[i][j + 1] += 1ll * dp[i - 1][j] * max (0,(sum[max (0,b[i] - t)] - j)) % MOD,dp[i][j + 1] %= MOD;
}
for (int i = 1;i <= min (n,m);++i) tot1 = (tot1 + dp[m][i]) % MOD;
}
for (int i = 1;i <= m;++i)
for (int j = 1;j <= n;++j) dp[i][j] = 0;
dp[0][0] = 1;
for (int i = 1;i <= m;++i)
for (int j = 0;j <= min (m,sum[b[i]]);++j)
{
dp[i][j] += dp[i - 1][j];dp[i][j] %= MOD;
if (j + 1 <= min (m,sum[b[i]])) dp[i][j + 1] += 1ll * dp[i - 1][j] * max (0,(sum[max (0,b[i] - t - 1)] - j)) % MOD,dp[i][j + 1] %= MOD;
}
for (int i = 1;i <= min (n,m);++i) tot2 = (tot2 + dp[m][i]) % MOD;
ans += 1ll * (tot1 - tot2 + MOD) * t % MOD;ans %= MOD;
}
printf ("%d\n",ans);
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
```
开始恶补线性基，看的是这个 [洛谷日报](https://www.luogu.com.cn/article/zo12e4s5)。
简单来说，线性基是一个集合，取线性基中若干个数异或起来可以得到原序列中的任何一个数。那么如果要插入一个数 $x$，只需要判断 $x$ 在二进制下的每一位非 $0$ 位在线性基中是否存在。
```cpp
for (int i = 60;~i;--i)
{
if (!((1ll << i) & x)) continue;
if (!p[i]) x^= p[i];
else p[i] = x;
}
```
求[序列中选若干个数异或的最大值](https://www.luogu.com.cn/problem/P3812)，只需要在求出线性基的基础上从高到低贪心看是否需要异或上 $p_i$ 即可。
求序列中选若干个数异或的最小值，若有元素无法插入线性基，则答案为 $0$，否则为最小的 $p_i$。
同样的，I 题经过题意转化后就是在维护出 $c_i = a_i \oplus b_i$ 的线性基后按高到低贪心去更新即可，部分代码如下：
```cpp
for (int i = 1;i <= n;++i)
{
int x = a[i] ^ b[i];
for (int i = 30;~i;--i)
{
if (!((1 << i) & x)) continue;
if (!p[i]) {p[i] = x;break;}
else x ^= p[i];
}
}
for (int i = 30;~i;--i)
if (max (suma,sumb) > max (suma ^ p[i],sumb ^ p[i])) suma ^= p[i],sumb ^= p[i];
```
不写 C 题真的后悔一万年。贪心的思路，从下往上，如果未遇到已种植的点，那就将子树大小向上传；否则以它为根处理其子树内的点。唯一需要注意的是，以某点为根处理时，可能会有多余的点可以向上传递至它的父亲。核心代码如下：
```cpp
void dfs (int u,int fa)
{
sz[u] = 1;
for (auto v : ve[u])
{
if (v == fa) continue;
dfs (v,u);
sz[u] += sz[v];
}
if (vis[u])
{
ans += max (sz[u] / 2,0);
if (sz[u] % 2 == 0) vis[fa] = 1;//有多余，向上传递至父亲节点
sz[u] = 0;//该子树内全部处理完
}
else if (u == 1) ans += max ((sz[u] + 1) / 2,0);//特判向上一直再无遇到 vis[i] = 1 的点
}
```
### 2024.09.15 ICPC 网络赛Ⅰ
笑死，队长报名只写了他一个人。于是乎，这场没打…
但赛后发现这场似乎挺难，那就还好！
### 2024.09.21 ICPC 网络赛Ⅱ
这场打地很顺，开场半小时过完 F,J,A 签到。
然后队友开 I 构造题，显然可以用高位弥补低位凑出解，又光速发现末位为 $00$ 时是无解的情况，于是做完了。然而，队友因为输出反了挂了一发。
然后和队友开始做 $L$，一开始搞错题意以为只能最多 refresh 操作一次，WA 了两发以后我直接高中列表法求期望但误以为临界点 $t$ 在 $\lfloor\frac{n}{2}\rfloor + 1$。
||$1$|$2$|$\cdots$|$t$|$E(x) + 1$|
|:--:|:--:|:--:|:--:|:--:|:--:|
|$P$|$\frac{1}{n}$|$\frac{1}{n}$|$\dots$|$\frac{1}{n}$|$\frac{n - t}{n}$|
求得 $E(x) = \frac{t ^ 2 - t + 2n}{2t}$。WA 了一发后队友通过解不等式以后过了这题。
接着开 G，怎么又是推式子，然后发现平局啥用没有。
我这时候开始读 E，冗长的题面，以为是不可做题。然后给队友翻译了一下，随口说了一句奇偶性分层图，结果被他给秒了，在此膜拜。
好了七题了，之后尝试了几题全都无果（我甚至还尝试数据结构来着，笑死这题只有一个队通过），一小时坐牢，最后喜提校 $\texttt{rk 3}$。
由于本人前一天脑抽打了一场掉分近 $100$ 的 CF，所以说又~~光明正大~~地水了这场比赛，全靠队友！！！
---
### 2024.xx.xx 选赛站
选了 $2024.11.2-11.3$ 的 $\texttt{ICPC}$ 南京站 和 $2024.11.9-11.10$ 的 $\texttt{CCPC}$ 重庆站。加油吧，争取拿牌！
---
### 2024.11.2-11.3 ICPC 南京
详见 [游记--ICPC 小白勇闯南京](https://www.luogu.com.cn/article/jyaia4h8)。
----
### 2024.11.9-11.10 CCPC 重庆
$5$ 题铁了，那道构造回去给室友讲题的时候突然顿悟，可惜晚了……打的太烂就不写游记了。
---
一些好文，留着看：
- [Some Simple Tricks](https://www.luogu.com/article/cqhi72t6)
- [一些 trick](https://www.luogu.com.cn/article/o0yp5tx3)