NOT GOOD

P5987 [PA 2019] Terytoria

给你一个网格，网格的左右是联通的，上下也是联通的。这个网格上有 \(n\) 个矩形，但你只知道每个矩形两个对顶点的坐标。你需要最大化这 \(n\) 个矩形的交。\(n \leq 5 \times {10}^5\)。3s / 256M。

首先，是矩形 交 而非并，所以每一维都是独立的，可以直接转成一维的。

将线段的端点在数轴上标记出来，这样，数轴被分成了若干段。如果你确定了任意一段属于最终的交，那么你就确定了所有线段的形态。你只需要对这些段扫描线，然后线段树维护最大值以及最大值数量即可。时间复杂度 \(O(n \log n)\)。

如果换成并怎么做？有待思考。感觉做不了。

P10367 [PA 2024] Żarówki

给你一张 \(n\) 个点 \(m\) 条边的图，每个点有黑白两种颜色，初始的颜色是给定的。你可以进行任意多次如下操作：选择图上的一条边，如果这条边的两个端点颜色相同，那么同时反转这两个点的颜色。你需要求出最后可以得到的颜色方案的数量。两种颜色方案被视为不同当且仅当存在一个点在一个颜色方案中是白色，另一个中是黑色。\(n \leq 2 \times {10}^5, m\leq 4 \times {10}^5\)。3s / 1G。

先考虑二分图的情况，对于二分图，通过二分图染色，我们可以很清晰地将点分成两类。

考虑两条边 \((u, v)\) 和 \((u, w)\)，如果 \(v\) 和 \(w\) 颜色不同，那么显然可以经过若干次操作，交换 \(v\) 和 \(w\) 的颜色。同时，\(v\) 和 \(w\) 是属于同一类点的。因此，对于同一类点来说，你可以任意重排它们的颜色。这告诉我们，我们不需要考虑颜色顺序，只需要考虑黑点（或白点）的数量。

同时，还有一个性质是，对于你每次操作选择的边来说，它的端点总是属于不同的两类点的，所以你每次操作不会改变两类点黑点数量的差。有了这两条性质后，统计答案就是容易的。

如果不是二分图呢？首先，不需要考虑颜色顺序的性质依旧存在。同时，每次操作实际上不会改变黑点数量的奇偶性，所以统计答案依旧是容易的。

对每个联通块分别考虑，最后将答案乘起来即可。

P9084 [PA 2018] Skwarki

你有 \(n\) 种糖豆，有 \(k\) 种颜色，每种糖豆都有一种颜色。现在要去购买糖豆，购买的糖豆需要包含所有 \(k\) 种颜色，且每种颜色购买的数量相同。对于在区间 \([0,m-1]\) 的每个整数 \(r\)，你都需要求出，满足购买的糖豆总重量对 \(m\) 取模为 \(r\) 的购买方案中最小花费是多少。或者报告无解。\(n,k,m \leq 7000\)。3s / 1G。

考虑求出 \(f_{0} \sim f_{m - 1}\) 表示每种颜色的糖豆只选一个时原问题的答案，然后同余最短路即可。

P11915 [PA 2025] 瞬间传送 / Teleport

你有一张 \(n\) 个点 \(m\) 条边的无向联通图，边权均为 \(1\)。你需要在图中加入一条边权为 \(0\) 的边，最小化图的直径。\(n \leq 400\)。5s / 1G。

设 \(d(s, t)\) 表示点 \(s\) 和点 \(t\) 在原图中距离。

考虑二分答案，设此次二分出的答案为 \(k\)。

考虑枚举加入的边 \((u, v)\)。对于两个点 \(x\) 和 \(y\)，它们在加边后的距离大于 \(k\) 当且仅当：

• \(d(x, y) > k\)。
• \(d(u, x) + d(v, y) > k\)，即 \(d(v, y) > k - d(u, x)\)。
• \(d(v, x) + d(u, y) > k\)，即 \(d(u, y) > k - d(v, x)\)。

再考虑枚举 \(x\)。显然，在 \(u, v, x\) 固定时，分别满足以上三个条件的 \(y\) 构成了三个集合，而这些集合的交即为同时满足这三个条件的 \(y\)。那么我们拿 bitset 来维护这些集合即可。

总时间复杂度 \(O(\frac{n^4 \log n}{\omega})\)。

P4931 [MtOI2018] 情侣？给我烧了！

记答案为 \(t(n, k)\)，那么有：

\[t(n, k) = {n \choose k} {n \choose k} k! 2^k t(n - k, 0) \]

也就是说我们只需要求出 \(t(i, 0)\)。

注意到：

\[\sum_{k=0}^n t(n, k) = {(2n)}! \]

所以有：

\[\begin{aligned} {(2n)}! &= \sum_{k = 0}^n t(n, k) \\ &= \sum_{k=0}^n {n \choose k} {n \choose k} k! 2^kt(n - k, 0) \\ &= \sum_{k=0}^n \frac{{(n!)}^2 2^kt(n - k, 0)}{{((n-k)!)}^2k!} \\ &= {(n!)}^2\sum_{k=0}^n \frac{2^kt(n - k, 0)}{{((n-k)!)}^2k!} \\ \end{aligned} \]

即：

\[\sum_{k=0}^n \frac{2^k}{k!} \times \frac{t(n - k, 0)}{{((n-k)!)}^2} = \frac{{(2n)}!}{{(n!)}^2} \]

注意到这是一个卷积的形式，记 \(f_i = 2^i / i!\)，\(g_i = t(i, 0)/{(i!)}^2\)，\(h_i = (2i)!/{{(i!)}^2}\)，记 \(F(x)\) 为 \(f\) 的 OGF，\(G(x)\) 为 \(g\) 的 OGF，\(H(x)\) 为 \(h\) 的 OGF。

注意到：

\[h_{i+1} = \frac{(2i+2)(2i+1)}{{(i+1)}^2} h_i \]

即：

\[(i+1)h_{i+1} = 4ih_i + 2h_i \]

对应到 OGF，有：

\[H^\prime(x) = 4xH^\prime(x) + 2H(x) \]

即：

\[H^\prime(x) = \frac{2}{1-4x}H(x) \]

解得：

\[H(x) = C e^{\int{\frac{2}{1-4x} \mathrm{d} x}} \]

注意到 \(F(x) = e^{2x}\)，则：

\[e^{2x} G(x) = H(x) \]

那么有：

\[G(x) = C e^{\int{\frac{2}{1-4x} \mathrm{d} x} - 2x} \]

两边求导，有：

\[G^\prime(x)=C e^{\int{\frac{2}{1-4x} \mathrm{d} x} - 2x} ({\int{\frac{2}{1-4x} \mathrm{d} x} - 2x})^\prime \]

即：

\[G^\prime(x) = G(x) (\frac{2}{1 - 4x} - 2) \]

即：

\[(1-4x)G^\prime(x) = 8xG(x) \]

还原到 \(g\)，有：

\[(i+1)g_{i+1}-4ig_i = 8g_{i-1} \]

直接做即可。

CF1156E Special Segments of Permutation

考虑在笛卡尔树上做。

对于每个点，你会发现 \(l\) 是属于一个区间，\(r\) 是属于令一个区间的，那么我们只需要枚举短的那个区间即可。

时间复杂度是对的。

CF1355F Guess Divisors Count

神仙题，这是真人类智慧。

根据代数基本定理，我们将 \(X\) 分解为 \({p_1}^{a_1}{p_2}^{a_2}{p_3}^{a_3}\dots{p_k}^{a_k}\)，那么答案为 \((a_1 + 1)(a_2 + 1)\dots(a_k + 1)\)。

先考虑如何用第二个条件。我们发现，\(X\) 的因数中最多包含 \(2\) 个大于 \(1000\) 的质数。那么如果我们分解出若干个小于 \(1000\) 的质数，再按上面的公式计算，设得到的答案为 \(t\)，那么真实答案只能为 \(t,2t\) 或 \(4t\)，利用第二个条件，猜测 \(2t\) 即可。也就是说，我们不需要考虑大于 \(1000\) 的质数，只需要考虑 \(1000\) 以内的质数。

现在，假设我们已经确定了 \(X\) 的这些质因数，如何求出幂次呢？首先，对于一个质因数 \(p\)，我们可以通过询问 \(p^{\lfloor \log_{p}{{10}^9} \rfloor}\) 来得到 \(p\) 的幂次。又因为询问的数的上界是 \({10}^{18}\)，而我们前面所说的数（即 \(p^{\lfloor \log_{p}{{10}^9} \rfloor}\)）不超过 \({10}^9\)，所以我们可以将两个质因数绑在一起询问。由于 \({10}^9\) 范围内一个数最多有 \(9\) 个质因数，所以这里我们最多需要询问 \(\lceil \frac{9}{2} \rceil = 5\) 次即可得到每个质因数的幂次，进而得到答案。

好的，现在问题变成了在 \(17\) 次询问内确定 \(X\) 的质因数。考虑将 \(1000\) 以内的质数分组，每组的乘积不能超过 \({10}^{18}\)，且每组的质数应该尽量多。例如：\(2,3,5,7,\dots,47\) 可以分为一组。每次询问时，我们只需要询问一组的乘积就能判断这一组里哪些数是 \(X\) 的质因数。但是这样询问 \(17\) 次后我们最多确定到 \(661\)，还剩一些质数，怎么办？这时候就需要利用第一个条件了。

设经过上面所有操作后得到的答案为 \(r\)，对 \(r\) 进行分类讨论：

• \(r \leq 2\)，此时 \(X\) 中大于 \(661\) 的质因数最多有 \(3\) 个。利用第一个条件，我们发现输出 \(x+7\) 是一定对的。
• \(r \geq 3\)，此时 \(X\) 中大于 \(661\) 的质因数最多有 \(2\) 个，我们输出 \(2r\) 即可。

做完了，真可恶。

CF1322B Present

按位考虑，设当前考虑到了第 \(k\) 位，那么我们只关心 \(a_i\) 对 \(2^{k+1}\) 取模后的结果。显然，对于两个位置 \(i,j\)，\(a_i + a_j\) 第 \(k\) 位为 \(1\) 需要满足 \(2^k \leq a_i + a_j \leq 2^{k+1}-1\) 或 \(2^k + 2^{k+1} \leq a_i + a_j \leq 2^{k+2} - 2\)。排序后双指针即可。

总时间复杂度 \(O(n \log n \log V)\)，能过。