8.12~8.24 总结

8.12

[ARC159B] GCD Subtraction

题意：没必要讲，就是题面。

按题目直接模拟会超时，考虑优化。

发现在 \(a,b\) 互质时特别慢，每次只能减一，因此应将减一的操作合并。

设会减 \(x\) 次一，则 \(\gcd(a-x,b-x) = c (c \ne 1)\)。

则 \(a-x \equiv b-x \pmod c\)， \(a \equiv b \pmod c\)

得 \(d\) 为 \(a - b\) 的因数。枚举 \(a - b\) 的因数即可算出 \(x\)。

Border

题意：可以使用 \(n\) 种数 \(a_1,a_2,\dots , a_n\) 任意次并相加，问 \(\bmod k\) 后有哪些可能的个位。

设每个 \(a_i\) 的个数为 \(x_i\)，则相加的和为 \(x_1a_1+x_2a_2+\dots+x_na_n=s\)。

根据裴蜀定理拓展可知，\(s\) 一定是 \(\gcd(a_1,a_2,\dots,a_n)\) 的倍数。不妨设为 \(x\) 倍。

得 \(x \cdot \gcd(a_1,a_2,\dots,a_n) \equiv s \pmod k\)

根据裴蜀定理，\(x\cdot \gcd(a_1,a_2,\dots,a_n)+ky=s\)

再次根据裴蜀定理可得 \(\gcd(k, \gcd(a_1,a_2,\dots,a_n))\) 为 \(s\) 的因数。

即答案为 \(\gcd(k, \gcd(a_1,a_2,\dots,a_n))\) 不超过 \(k\) 的所有倍数。

8.13 思维训练

[ABC216D] Pair of Balls

题意：没必要讲，就是题面。

拓扑拓扑拓扑拓拓扑扑拓扑拓扑拓拓扑扑拓扑拓扑

每种颜色的球的先置即为它的上一个。拓扑判环即可。

Walk

题意：没必要讲，就是题面。

矩阵快速幂模板。答案为矩阵 \(a^k\) 中所有元素的和。

8.14 CSPS模拟测

hugclose

正解是字典树，但暴力可过。

wayhome

有电往前走，没电回头充。

[ABC280F] Pay or Receive

预处理每个连通块，并查集判断 -1，有正环即为 inf，否则答案为 \(dis_y - dis_x\)。

8.15

Tree Painting

题意：没必要讲，就是题面。

换根 dp，最后加上 \(n\) 即可（每个点都还有为一的大小）。

宝物筛选

题意：这下小 FF 可发财了，嘎嘎。

有 \(n\) 个物品，每种物品的价值为 \(v_i\)，重量为 \(w_i\)，有 \(m_i\) 件。有一个容量为 \(W\) 的背包。现求物品总体积不超过背包容量时价值最大为多少。

直接多重背包会超时。

可以使用二进制优化。将每个 \(m_i\) 拆分成 $ \le m_i$ 的所有 \(2^x\) 以及 $ \le m_i$ 的所有 \(2^x\) 的和与 \(m_i\) 的差。

然后正常多重背包即可。

大师

题意：在数组 \(h\) 中选择 \(x(x \ge 1)\) 个数，使得这 \(x\) 个数按原顺序排列构成一个等差数列。问有多少种选法。

设 \(dp_{i,j}\) 为以第 \(i\) 个数结尾，公差为 \(j\) 的选法数。

\(j\) 可能是负数，因此需要数组偏移。

枚举到 \(i\) 时，将所有 \(j < i\) 的 \(dp_{i, h_i-h_j}\) 加上 \(dp_{i, h_i-h_j}+1\)，并将答案也增加 \(dp_{i, h_i-h_j}+1\)。

最后直接输出答案。

8.19

Ice Skating

题意：平面上有 \(n\) 个点，最少需要加几个点才能使得所有点都两两互通。当两个点处于同一行或同一列时，两个点互通。

并查集。

双重循环枚举两个不同的点，若两个点处于同一行或同一列，将两个点并为一个连通块中。

因为需要加的点最少，答案就是连通块数量 \(-1\)。

Almost Acyclic Graph

题意：给定一个 \(n\) 个顶点，\(m\) 条边的有向图。问是否能够删掉一条边后使图无环。

拓拓扑扑拓扑拓扑拓拓扑扑拓扑拓扑拓拓拓扑扑扑拓扑拓扑

枚举删去哪一条边，然后再跑拓扑。

8.20 思维训练

Shaass and Bookshelf

题意：没必要讲，就是题面。