日记

我需要复健。

大数定理# Link to

这破题。。。作为一道 NOIp T1 居然让我想了 2h。。。
唐的没边了。

观察（对，我就是观察了 2h）到：只需要选择两个数就可以删完整个数列。而且，对于 $i \in [1,\frac{n + 1}{2}]$，如果 chk(i,j) 为 true，那么 $i,j$ 就可以删完。

chk(i,j)：

1
2
3
4
5
6

bool chk(int x,int y)
{
    bool f1 = min(x - 1,y - x - 1) << 1 >= abs((n - y) - (y - 1));
    bool f2 = min(n - y,y - x - 1) << 1 >= abs((n - x) - (x - 1));
    return f1 || f2;
}

然后，我们发现对于一个 $i$，$j$ 的合法区间是 $[\frac{n + 1}{2},pos]$，而且对于一个单调递增的 $i$，$pos$ 也是单调递增的。于是我们可以双指针，复杂度 $O(n)$。

考试# Link to

我们发现，对于一个求 $|x - y|$ 最大的问题，我们可以钦定 $x \ge y$ 或者 $y \le x$，然后计算，因为不合法的情况一定不优。因为 $n$ 很小，所以我们枚举集合 $S \subseteq [1,n]$，钦定 $s$ 里的都是 $x_i \le r_i$ 的，然后把每道题的贡献拆出来，那么对于题 $j$，它的贡献就是 $p_j \times \sum_{i = 1}^{n}s_{i,j}(-1)^{[i \in S]}$。我们可以给每个 $j$ 赋一个等于 $\sum_{i = 1}^{n}s_{i,j}(-1)^{[i \in S]}$ 的权值，按照权值从小到大依次赋 $p_j$ 就是了。

串串# Link to

其实不难。

观察第二个限制发现要容斥。于是我们钦定有 $i$ 个不满足条件的方案数是 $f(i)$。答案就是 $\sum_{i = 0}^{n}(-1)^i f(i)$。

首先 $f(i)$ 肯定有系数：$\binom{n}{i}$。这剩下的 $n - i$ 个又能搞出 $2^{n - i}$ 种烤串，每种烤串取与不取就又有了 $2^{2^{n - i}}$ 种方案。所以我们得出 $f(i) = \binom{n}{i}2^{2^{n - i}}g(i)$。

考虑如何求 $g(i)$。我们考虑这 $i$ 个不合法的东西有 $j$ 个取了 $1$ 个。所以又有一个 $\binom{i}{j}$ 的因数。我们考虑把这 $j$ 个分到 $k$ 根烤串上，所以有 $\tiny \begin{Bmatrix}j \\ k\end{Bmatrix}$ 种（就是第二类斯特林数）。这 $k$ 个集合里还能包含那合法的 $n - i$ 个元素，所以我们有 $g(i) = \sum_{j = 0}^{i}\binom{i}{j}\sum_{k = j}^{i}2^{k(n - i)} \tiny \begin{Bmatrix}j \\ k\end{Bmatrix}$。

所以有：

就可以暴力求了，复杂度 $O(n^2)$，注意实现，注意常数。

后日谈 # Link to 后日谈

你要成为谁？