杂记

Rusalka · 2021-09-02 17:58:20 · 个人记录

「2020-02-14 省选模拟赛」同桌与室友 (mate)

• 注意到每个人最多连出两条边，因此形成的图要么是环，要么是链。链分两端颜色是否相同讨论即可。

「2020-02-14 省选模拟赛」传送 (teleport)

• 有显然的差分约束模型。实际上 dp 可以求出每个点的合法区间，最后若区间非空即有解。
• 注意到每花费 1 的代价即可使答案区间左右各扩大 1，因此花费可简单计算。

「2020-02-14 省选模拟赛」生成树 (tree)

• 将绿边权值设为 x，蓝边权值设为 y，红边权值设为 1，矩阵树定理之后的形式是关于 x, y 的二元多项式。答案即为系数的二维前缀和，二元插值即可求出。

「2020-02-17 省选模拟赛」序列 (seq)

• 倒序考虑 q 的组成。最后加入的数对可以通过分奇偶性区间极值得出。这样可以把原区间分为三个子区间，递归下去即可。子区间的数对必须在当前区间的数对之前选择，这样可以得到数对之间的偏序关系，求字典序最小的拓扑序即可。

「2020-02-17 省选模拟赛」进制 (hex)

• 第一问，注意到十六进制数的长度不超过 15，预处理每种长度的数在序列中占多少长度可以判断位数。之后通过数位之间的整除、取模即可求得。

• 第二问，求出第一问后相当于小于某个数的所有数做数位统计，数位 dp 即可。

「2020-02-17 省选模拟赛」矩阵 (matrix)

• 设 f_{i,j} 表示有 i 行 j 列，其中每行都有涂黑的方案数。

• \text{ans} = \sum \dbinom{n}{i}f_{i,m}

• 考虑两种转移：

  1. 新增一列。f_{i,j} \xleftarrow{+} (\dbinom{j}2+j+1)f_{i,j-1}；

  2. 新增一列，以及若干行。考虑原来某列第一个位置的上一个，和最后位置的下一个位置，和新增的 i-k 个位置一共形成 i-k+2 个位置。那么相当于在 i+2 个位置中选出 i-k+2 个位置填数。 f_{i,j} \xleftarrow{+} \dbinom{i+2}{i-k+2}f_{k,j-1}。转移是卷积的形式，NTT 即可。

「2020-02-18 省选模拟赛」小 D 的奶牛 (cows)

• 先考虑 2^n 做法。记录每个点连出的点集，状压 dp 每个集合是否可行。

• 折半搜索。前一半需要统计子集中有多少个合法，可以 FWT；在后半搜索的时候直接求出对应的集合最大能是多少。

「2020-02-21 省选模拟赛」城市破坏 (disconnected)

• 如何判断删去若干边之后，图能否被分成两个连通块？

• 每条边随机一个权值，点权为相邻的边的边权的异或和，满足所有点权为 0。若删去的边的边权异或和为 0，则被分成两个连通块；否则不是。

• 关于边权，dfs 树上，非树边随机，树边构造即可。