越来越懒了，懒了几天没总结，原因是每天晚上都有讲知识点。

2024-08-07

欧几里得 (File IO) (gmoj.net)

这道题告诉要对拍。

打表找规律。

容斥原理 (File IO) (gmoj.net)

容易发现第一个元素和第二个元素必须要一样，不一样的话就一定会出现一个相匹配的情况（交换第一个和第二个元素，此时对方案数贡献为 \(2\)，没有贡献），所以把它们合并为一个大小为 \(2\) 的元素。第三个第四个也可以合并。然后这四个元素合并成的两个元素，也可以合并为一个大小为 \(4\) 的元素。然后就是要选择 \(popcnt(M)\) 个元素，每一个元素大小为 \(2\) 的幂。

设 \(f_{i,j}\) 表示选择 \(i\) 个和为 \(j\) 的元素的代价。答案就是 \(f_{M,S}\)。考虑转移，因为一个元素大小必定是二的幂，所以：

\[ f_{i,j}\gets \bigoplus_{k=1}^n f_{i-2^u,j-a_k2^u}\ \ \ \ (M_u=1) \]

我们可以枚举 \(k\) 进行转移，每次转移就是： \[ f_{i,j+a_k2^u}\gets f_{i-2^u,j} \] 这一个可以用 bitset 做。

题解没有说到的，就是 bitset 可能很大，所以考虑怎么优化掉。

一个显然的办法，就是处理到第 \(u\) 位时，\(1\sim u-1\) 位都处理完了。因为以后每次对 \(j\) 的贡献都会将 \(a_k\) 乘上至少 \(2^u\)，所以 \(1\sim u-1\) 位必定不会改变了，我们可以直接舍弃。

记舍弃后 bitset 为 \(f\)，舍弃前为 \(g\)。容易有转移： \[ f_i=\begin{cases} g_{2i+1} & S_i=1 \\ g_{2i} & S_i=0 \\ \end{cases} \]

注意这种 \(\bmod 2\) 的题目，有几个套路：

• 考虑怎么样会重复贡献。将会重复贡献的方案相匹配消除即可。
• 如果考虑二进制时低位已经确定了，可以将其去除。

同时有一个没有用上的发现：

• \(C_n^m\bmod2=[n\cap m=m]\)

2024-08-08

远古上帝 小X (File IO) (gmoj.net)

乱搞题。赛时失误感觉是因为状态不够好，思维混乱，越是做不出越混乱，考后几分钟就调出来了

送(soong) (File IO) (gmoj.net)

运用：点数等于边数加一

将点权赋值为 \(w\)，边数赋值为 \(-w\)，那么求一条路径上的权值每条链只会统计上一次！

2024-08-11

扔骰子 (File IO) (gmoj.net)

拉插板题。

容易推式子，考虑区间内的值。

然后就可以拉插了。

知识点：

• 拉插的 \(O(n)\) 写法（下标连续+幂预处理）
• 一定的卡常技巧（统计答案用 int）
• 但是实际上 ll 转 int 似乎没什么大作用，但这里就是突然跑到了 988ms，一方面是 gmoj 两倍常数的原因，但更是卡常的一次教训。
• 但是 int 容易写挂，例子就是写自己题目的 std 时转 int 挂掉了。
• 现在我的办法是先全 ll，最后被卡时用 int，同时使用 ll 版本对拍。

2024-08-13

这场比赛是真正的爆炸。

原因和 GDOI/THUWC/APIO 一样，卡在一道题不放。

感觉是时候反思一下了。

之后，一道题目不得超过 1h。

必须。

一定！

string (File IO) (gmoj.net)

这道题目学会了一个技巧，当我们要求两个不同的方案而使用 \(O(n)\) 的做法容易统计到同一个时，可以使用二进制拆位的方法：

• 假设两个方案为 \(i,j\)，当 \(i\neq j\)，则必有一个二进制位 \(i=0,j=1\) or \(i=1,j=0\)，我们钦定这个二进制位然后跑 \(2\log W\) 次即可。
• 尽管不是最优的，却是一个便利的思维入口！

染色（colour） (File IO) (gmoj.net)

这题纯傻逼。

观察 spj、大样例就可以发现，答案一定是一直操作一个点的。

所以我们缩点后答案就是这个点到所有点最大距离。

所以暴力枚举每一种点即可！

由于今天爆炸的缘故，我并没有看 t2，所以也没有大力猜想性质。