Season 2022

#6299. Binary String

如果 \(0\) 的个数小于 \(1\) 的个数那么就反转 \(01\) 以及反转序列，接下来假设 \(0\) 的个数大于等于 \(1\) 的个数。

称有 \(11\) 的序列为”未完全展开的“，那么序列的种类数有两个阶段：展开过程中和展开之后的。

在展开之后如果知道序列那么用 KMP 算最小周期即可计算不同的方案数，展开过程中显然均是不同的，所以只需要求出展开时间和展开后长什么样即可。

考虑三个连续的 \(01\) 长度为 \(x,y,z\)，其中 \(x,z\) 是 \(1\)，\(y\) 是 \(0\)，如果 \(x>y\)，那么在 \(x\) 完全展开之前，\(z\) 就会和 \(x\) 接触，那么总展开时间就是 \(x+z\)，这相当于将 \(z,y\) 交换。因此可以用栈暴力模拟这个过程，然后首尾相消。这样得到的是若干段 \(0\) 和 \(1\)，满足所有 \(1\) 在展开之前都不会碰到另外的 \(1\)，那么展开时间和最终序列都是容易求的。时间复杂度 \(O(n)\)。

submission

#5503. Euclidean Algorithm

考虑 \(2a-b\) 这样的操作能造出啥数列。

手摸一下可以摸出结论：只会产生对于所有自然数 \(k\)，\((k+1)a-kb\) 或者 \((k+1)b-ka\) 中的自然数。证明不难，归纳就行。

设 \(g=\gcd(a,b)\)，则显然 \(g\leq a\)，所以只有 \((k+1)a-kb\) 能产生 \(g\)，解得 \(k=\frac{a-g}{b-a}\)，也即要求 \(b-a\mid a-g\)。

不妨先转化一下变成 \(b-a\mid b-\gcd(a,b-a)\)，用 \(a\) 代换 \(b-a\) 可以得到 \(a\mid b-\gcd(b,a)\)。枚举 \(g=\gcd(b,a)\)，设 \(a'=\frac{a}{g},b'=\frac{b}{g}\)，则要求 \(a'\mid b'-1\) 且 \(\gcd(a',b')=1\)。容易发现后面一个条件是废话，那么也就是要求 \(a'\mid b'-1\)，对于所有 \(b\) 的约数 \(g\)，总是有 \(d(\frac{b}{g}-1)\) 个 \(a\) 满足条件，那么枚举 \(\frac{b}{g}\)，计算式就变成 \(\sum\limits_{i=1}^{n}{\lfloor\frac{n}{i+1}\rfloor d(i)}\)。对 \(i\) 除法分块，\(\sqrt n\) 计算 \(d(n)\) 前缀和即可做到 \(O(n^{0.75})\)。

submission

#6308. Magic

假设我们选定了一些位置，钦定其和下一个位置不同，那么要怎么判定存在一种方案？

也就是说我们需要让两个点不同，那么所有将两个区间覆盖成相同的都不能作为这两个点的最后覆盖。只有以 \(i\) 为右端点和以 \(i+1\) 为左端点的区间可以，也就是说我们要求这两个中至少一个成立。

那么现在需要找到限制之间的矛盾关系。对于两个同是左端点的限制，让左端点靠右的区间后做，一定最优，因为这样可以让两个左端点都 win，两个右端点也是同理。那么矛盾只在左右端点之间。如果两个区间的限制都包含了对面的限制，那么肯定有一个不行，这会导致矛盾。其余情况可以归纳说明没有矛盾。

如果我们再将 \(i\) 是右端点，\(i+1\) 是左端点的连边，限制其不能同时选，那么最多能满足的限制个数就是最大独立集的个数，可以 bitset 优化匈牙利算法做到 \(O(\frac{n^3}{\omega})\)，常数很小，可以通过。

submission

#6410. Classical DP Problem

这个题和这场的 E 是一个题