3rd ucup 做题笔记

· · 个人记录

不知道为什么从十月才开始训这个赛季的 ucup，实在是太摆了。

不对我好像其实知道为什么来着的，哈哈，哈哈。

Stage 12. Qinhuangdao

三排，11 题 rk5，赢麻了。但是我做的 I 题复杂度错了后来被 hack 了，搞笑。

感觉我做的除了这个 I 其他题都没啥含金量，主播每天有效思考只有一小时.jpg。

考虑如何刻画一个三角剖分：我们下凸壳开始逐渐扩展至上凸壳，每次加入一个点，维护当前的上边界。

所以考虑设计一个状压 dp：设 dp_{S} 表示目前上边界为 S 的最小代价。枚举加入哪个点，以及他和上边界上的哪条边连边，连出来的三角形内部不能有点。这样做就是 \mathcal O(2^nn^2) 的了，可以求出最小代价。

考虑计数。这东西肯定是会算重的，我们想办法钦定一个转移顺序使得每种方案只被算一遍。考虑将整个上边界以上的平面根据上边界的所有线段划分成若干个区域，每个区域内的点只能用其对应线段转移。可以用这个图来理解：

这个时候先转移红色的三角形是不合法的，因为选了之后左边还会连出其他三角形，所以应该先转移左边的三角形。

这样再记录一维表示目前转移到第几条线段，限制一下转移顺序就不会重复了。时间复杂度还是 \mathcal O(2^nn^2) 的，赛时可以通过，赛后被卡了。好像可以通过一些手法搞成 \mathcal O(2^nn)，但是我懒得搞了。

Stage 13. Sendai

和 z 宝双排，12 题 rk8，又赢麻了。z 宝非常结实强壮，把题目都给干爆了。

观察到一个合法的网格应该长这样：

所以你考虑枚举最左下和最右上的 1，然后对这两条轮廓线计数，就和所有合法网格一一对应了。对轮廓线计数是一个显然的 LGV 引理，这样可以做到 \mathcal O(n^2)。式子写出来之后应该是可以 FFT 优化的，时间复杂度 \mathcal O(n\log n)。

这我都会，感觉开了。

考虑一些比较基本的操作。我们发现可以在 2n 次操作内实现循环位移三个点 A(x,y),B(x,v),C(u,v)。大概就是只要你玩过魔方或者玩过 patrick's parabox 忘了第几关了你就知道怎么操作了，正好需要 2n 次操作（行列分别转了一圈）。

接着你发现由于值域是 2，所以循环位移三个位置实际上就可以任意交换两个点了。总的次数就是 \frac{n^2}{2}\cdot 2n=n^3 恰好可以通过。需要特判交换的两个点在一行一列上的情况，这时候要从其他列 / 行借一个过来循环位移。

先问一个菊花图，按照 (1,x) 之间的边的颜色分成两个点集 S,T。接下来想让两边的点连起来。

考虑双指针，每次询问一下目前 S_1,T_1 之间的边，如果是 S 的颜色那就把 T_1 扔掉，否则把 S_1 扔掉。容易发现这样最后一定有一个集合组成生成树，询问次数 2n-3。

感觉不是我很会做的那种题，但是我做出来了，我好牛。

首先有个单次 \mathcal O(n) 的暴力：直接容斥，枚举 \operatorname{mex}\ge i，容斥 [0,i-1] 中有多少个没有出现过。

最后答案应该可以被表示成这个样子：

\sum\limits_{i=1}^{m}\sum\limits_{j=0}^{i}(-1)^j\binom{i}{j}(m-j)^n

把 i=0 也算进去，最后减去 m^n。

考虑用 EGF 来表示这东西，大概就长成这么个东西：

\sum\limits_{i=0}^{m}n![x^n](e^{(m-i)x}(e^x-1)^{i})

理解一下为什么是对的：j 相当于在枚举多少个 e^x-1 取了 -1。

那么你可以把 e^{mx} 拎出来，剩下等比数列求和一下。设 P(x)=e^x,Q(x)=e^x-1，得到：

[x^n]n!P^m\frac{1-(\frac{P}{Q})^{m+1}}{1-\frac{P}{Q}}=[x^n]n!(P^{m+1}-Q^{m+1})

然后把后面这东西展开爆算一下。P 的这项显然是 \frac{(m+1)^{n}}{n!}，Q 这项其实就是对着 n^m=\sum\limits_{k=0}^{m}S(m,k)\binom{n}{k}k! 做二项式反演。所以最后答案就是 (m+1)^{n}-(m+1)!S(n,m+1)-m^n，其中 S 是第二类斯特林数。

经过 z 老师指导发现这一坨根本就不需要这么推，交换求和号之后是个显然的组合恒等式，省掉一百万个步骤。

考虑设计一个容斥，对于 K 步的路径，实际上就是 K-1 步转移过来的容斥，减去选一条边作为最后两步走两遍的 K-2 步的路径。

所以设邻接矩阵为 A，度数矩阵为 D，单位矩阵为 I，我们可以得到这样一个递推：

对着这个矩阵套一个矩阵做矩阵快速幂就行了，时间复杂度还是 $\mathcal O(n^3\log K)$。 ### Stage 15: Chengdu 三排，11 题 rk18。前期有点倒闭，后期还算稳定。 - D $n$ 为偶数时最优方案唯一：把 $2k-1$ 和 $2k$ 配对，权值为 $n$；$n$ 为奇数时最优方案有 $n-1$ 种：选择 $2k-1,2k,2k+1$ 做一次置换，剩下的和偶数一样两两配对，权值为 $n+1$。 既然最优方案数量很少，我们可以直接全部拿出来排序。现在问题变成如何比较两个排列的字典序。 首先，被置换的位置只有 $\mathcal O(1)$ 个，剩下的部分分成三段：第一段两个排列都是一样的配对方式，第二段两个排列的配对方式恰好交叉 $1$（奇偶交错了），第三段又是一样的配对方式。而第二段必定每个位置都不相同，所以只要找到第一个位置就行了（比较字典序一定会直接分出胜负），所以最多只有 $6$ 个位置要比较。求出这些位置可以用 ST 表，支持查询值在 $[l,r]$ 的，最早出现的数。时间复杂度是优秀的 $\mathcal O(n\log n)$。 ### Stage 17: Jinan 三排，10 题 rk15，又是前期倒闭。后期直接连续 1A H C L，打赢了。 - E 巨大无比分类讨论，真是 XCPC 特色美味啊。 分成 $D\le X,X<D\le X+Y$ 和 $D>X+Y$ 三种情况考虑。 然后发现要么是尽量坐 A，要么是尽量坐 AB，要么是尽量坐 C，总之分讨很多种情况就行了。然后可能最后一段没坐满可以回退前面的一段，要特殊处理。 用 python 就行了。 - L 考虑用线段树维护这个过程，那么一次弹幕相当于在线段树上二分出一个前缀，把这个子树扣掉。删除一个人的弹幕相当于把这棵树拼回去。于是用线段树合并分裂维护即可。 但是有个问题是询问怎么处理，因为我们是动态开点的，没法定位到对应的叶子然后往上跳。有个很简单的处理方法是离线，把这些点作为关键点先建出来，然后就很好处理了。 代码有点难写，但是 1A 了，这是好的。 ### Stage 18: Southeastern Europe 11 题 rk11，感觉被队友带飞了，我一直在做签到并帮忙调代码。 - H 可以贪心，因为较大的数更有可能让下一列有机会完成一行的限制，所以每列先排个序，先尽可能满足还没满足的行，可以双指针做。容易调整证明是最优的。 ### Stage 20: Kunming 10 题 rk16。其实感觉 A I 都不是完全没思路，但是就是没做出来，尴尬了。借 F 题这个机会复习了一下 min25 筛，理解得更深刻了一些。 - G 发现答案不超过 $2\log a$，直接爆搜即可。 - H 极角排序之后双指针。 不会写极角排序了，计算几何水平为幼儿园级别。 - F 容易发现答案为 $\prod\limits_{i=2}^{n}\omega(i)$。数据范围和式子形式启发我们 min25 筛，但是这又不是积性函数，也不是求和，不能直接套板子。 回顾一下 min25 筛的原理：设 $S(n,i)$ 表示所有 $[1,n]$ 中的，最小质因子 $\ge pr_i$ 的数的答案。转移的时候，分成质数和合数考虑（还有可能要算 $1$）。 如果是质数，会提前预处理；如果是合数，枚举最小的质因子 $pr_{k}$，显然需要满足 $pr_k^2\le n$，并从 $S(\frac{n}{pr_k^e},k+1)$ 转移，其中 $e$ 是枚举的幂次。 但是问题是我们要求 $\prod$，每次把一些东西 $+1$ 很不好处理。好在 min25 筛的复杂度分析就是基于直接搜索的状态数正确，不需要记忆化，所以我们干脆把目前的质因子个数也给记录进去，即设 $S(n,i,x)$ 表示所有 $[1,n]$ 中的，最小质因子 $\ge pr_i$ 的数的 $(\omega +x)$ 的乘积。 那么直接转移就行了。质数处的点值就是前缀质数个数，容易预处理出来。注意还要处理一下，$e=1$ 的时候下一层不能把 $1$ 算进去。 直接做复杂度多一个 $\log $。不过 $\omega$ 很小，所以不需要算快速幂，直接把个数记下来最后求答案即可。