训练记录PART5 2018.6.15~8.15-白红宇

训练记录PART5 2018.6.15~8.15

阅读量：5140 次

发布时间：2019-06-13

本文共 16950 字，大约阅读时间需要 56 分钟。

友情提醒：大部分题选自opentrains，以后有训练需要的同学慎重查看。

6.15 Petrozavodsk Summer 2013 - Comenius U Selection by Michal Forisek

　　题意：给出一个长度为 $N(\leq 10^5)$ 的 $DURL$ 操作序列。想想一只画笔在无限大的平面上画线，保证线可以相交但不会重合，且最终构成一个回路。问画出的图形最少需要用几种颜色染色（使得边相邻的区域颜色不同）？

　　题解：

　　题意：有一个圆形披萨，圆心在 $(0,D)(D > 0)$ 。桌面是 $x$ 轴上侧。将披萨等分切成$N$块（水平沿 $x$ 轴正方向是第一刀）。现在要一块一块取小披萨。没有被取过的披萨本来是粘成一个整体的。注意任意时刻，不能有一个整体的披萨掉下桌面（重心 $\leq 0$）。问可行的取用排列有几种。

　　题解：先用积分预处理出一段披萨是否能屹立在桌上。然后区间DP一下即可。

　　题意：在 $[10^6,10^6]$ 平面里随机撒 $N(2 \leq N \leq 10^5)$ 个点。求最近点对的距离。

　　题解：利用随机花式做。

6.20 2017 Multi-University Training Contest 3

6.22 Petrozavodsk Winter 2011 - Andrew Stankevich Contest 39

　　题意：有 $N (\leq 30)$ 个交易所和 $M$ 个可行交易方案 $(x,y,p,q)$ ，表示交易所 $x$ 里每单位的钱可以换成交易所 $y$ 里 $p$元前，且最多交易 $q$ 次。$|p|,q \leq 100$。求最多能挣多少钱。

　　待补。

　　题意：用 $N (\leq 500)$ 个边长是 $1 \times 1$的正方形拼出一个规则几何形状。求拼成最小周长的形状的方法有几种。（摆放位置已经确定，即四个角上轮换算不同方案）

　　题解：最终形状肯定是 $a \times b$ 的长方形抠掉一些。枚举每一组$(a,b)$统计答案。

　　研究一下“抠”的规则。设 $L_i,R_i$ 表示每行连续的正方形位置，显然要保证 $L_i$ 先递减再递增，$R_i$ 先递增后递减，且 $L_i$ 要取过 $1$ ，$R_i$要取过 $N$。可以直接根据这些规则从上到下进行DP。

　　题意：求 $N (\leq 500)$ 个点的排列中，能被分解成三个递增序列的排列有几种。

　　题解：待补。

6.24 2017 Multi-University Training Contest 6

　　题意：给出由 $N(\leq 10^5)$ 个单词的字典和 $Q(\leq 10^5) $个询问,每次给出两个串 $pre,suf$ ，问有多少个单词以 $pre$ 为前缀，以 $suf$ 为后缀，且它们不重叠。字符串总长 $\leq 5 \times 10^5$

　　题解：这两维的限制很难搞。因为一开始单词的顺序是无关的，我们可以先按字典序排序。这样，前缀是固定值的单词必然是连续的。我们倒着建立trie，每次按$suf$走一走，即询问：当前 $trie$ 子树下有多少个开头满足在区间 $[L,R]$ 中的。

　　注意还有棘手的限制：不能重叠。即询问串的长度必须 $\geq |pre|+|suf|$ 。为了破解这个限制，我就离线先按询问的长度排序，动态往dfs序里丢一个数，或者询问一段区间里里另一维权值在 $[L,R]$ 的数有多少个。这个是经典的2个log带修改主席树的做法。

　　其实只要容斥地减掉即可。不合法的一定是重叠的，我们直接暴力枚举重叠部分长度，用hash去全局判一判即可。

　　题意：一共有 $5 \times 10^5$ 组数据。给出圆里的两个点 $P$ 和 $Q$ ，保证$|OP|=|OQ|$。在圆周上找一个 $D$ ，使得 $|DP|+|DQ|$ 最小。

　　题解：数据组数很大，三分需要一点黑科技。 三分时其实没必要三等分点 。如果 $m_1$ 和 $m_2$ 每次都取在 $mid=\frac{l+r}{2}$ 的附近，它的效率就会接近二分了。考虑到一些精度问题，建议与 $mid$ 隔得稍微远一点。

　　考虑解析解怎么求，这里需要圆的反演的知识。分别对 $P$ 和 $Q$ 做圆的反演点，相似比为 $|OP|:r$。因为比例一样，所以等价于求$|DP'|+|DQ'|$的最小值。如果 $|P'Q'|$ 与圆有交，交点便是 $D$ ；否则可以假想一个以它们为焦点的椭圆，我们一点点放大这个椭圆，它第一次与圆的交点即为所求，此时就在中垂线位置。

　　题意：给出 $N(\leq 10^5)$ 个数的排列和 $M(\leq 10^5)$ 个询问。每次给出 $L,R$ ，求$\sum \limits_{i=L}^R \sum \limits_{j=i+1}^R \sum \limits_{k=j+1}^R [gcd(p_i,p_j)=p_k] \times p_k$。

　　题解：离线，枚举每一个右端点，维护此时左端点的答案。由 $p$ 是一个排列，每次加入 $i$ 后，我们可以暴力枚举 $p_i | p_j (j<i)$。

　　如果从右往左扫描，现在问题转化成：把一个数加入集合；或者问集合里与某个数互质的数有多少。这是个经典问题，只能暴力容斥。为了减少常数，每次加入一个数的时候，只在它 $mul \ne 0$ 的位置算贡献。

7.14 Petrozavodsk Summer 2016 - Petr Mitrichev Contest 14

　　题意：考虑这样一个题：把 $0$ 和 $1$ 填入 $N(\leq 60)$ 位的格子。还有 $m(\leq 100)$ 个进制串，表示它们不能是某个合法方案的子串。问合法的方案总数 $n$ 。现在给出这个 $n(\leq 10^9)$ ，要求构造一种合法方案。

　　题解：待补。

　　题意：有 $k(\leq 10000)$ 轮游戏。每一轮会独立地随机一个 $1$ ~ $n(\leq 10000)$ 之间的数，可以选择取这个数或者 $skip$ 。必须正好取 $3$ 个数，问最优决策下，取的 $3$ 个数是等差数列的概率。

　　题解：设 $f_{i}$ 表示一共玩 $i$ 轮成功的概率。转移显然为：$f_i=\frac{1}{n} \sum \limits_{j=1}^n \max(f_{i-1},g_{i-1,j})$。其中 $g_{i,j}$ 表示还剩下 $i$ 轮，之前已经取了一个数字 $j$ 的最优成功概率。然后 $g_{i,j}=\frac{1}{n} \sum \limits_{k=1}^n \max(h_{i-1,k,g},g_{i-1,j})$ 。其中 $h_{i,j,k}$ 表示剩下 $i$ 轮，已经选出两个 $j$ 和 $k$ 的成功概率。 $h$ 已经可以直接算了。且注意到，计算 $g$ 枚举的 $k$ ，本质不同的只有 $4$ 种（已经确定了两个数，符合要求的第三个数最多只有 $3$ 个），我们可以合并相同的情况。最后复杂度 $O(NK)$ ，滚一滚数组即可。

　　题意：给出一个 $n \times m(n,m \leq 1000)$ 的01网格。每次可以翻转一行，一列，或者任意一条（反）对角线。求打印一种能翻转成全1的方案。

　　题解：

7.15 Petrozavodsk Summer 2016 - Ural FU Dandelion Contest

　　题意：维护一个 $N(\leq 10^5)$ 个数的可重集（数字 $\leq 10^9$ ）。有 $Q(\leq 10^6)$ 种操作，分为两种：①问目前第 $k$ 小的数；②将所有 $> x$ 的数都减掉 $x$。

　　题解：要动态地求第 $k$ 小，相当于要实时地维护出这个集合。为了用上一些均摊的特性，我们把②操作要维护的数分类。

　　对于 $y \in [x+1,2x]$ 的这些数，其实我们是可以暴力找出来删掉它们，再暴力插回平衡树的。因为每操作一次，值必然小于原来的一半。

　　对于 $y > 2x$ 的这些数就不能暴力了。但注意到，它们减去了 $x$ 后依然大于 $x$ ，与之前所有数的相对大小保持不变！这样我们只需在这一段里打一个区间减标记即可。

　　题意：给出一个凸包 $N(\leq 10^5)$ 。问凸包上有多少个点对，满足以它们为直径画圆，该圆可以盖住凸包上的所有点。

　　题解：因为直径是圆里最大的弦，所以符合要求的圆的直径必然是凸包的最远点对的距离。

　　 首先介绍一个经典算法：求每一个点的最远点。

　　显然一侧绕着凸包走，另一侧是单调的。但注意这不是完全决策单调性，即最优点周围是不具备单调性的。

　　最简单的做法就是分治。具体地，将凸包倍长，定义

\[\begin{equation} cost_{i,j}=\left\{ \begin{aligned} dist(i,j) & i \leq j < i+n\\ -dist(i,j) & j < i , j \geq i+n\\ \end{aligned} \right. \end{equation}\]

　　直接对其做要求的点为 $[1,n]$ ，分治决策点为 $[1,2n]$ 的DP即可。（注意不合法那一段一定要取负，以保持分治的单调性）

　　这题我们会发现，如果一组点对合法，那么所有距离为直径的对踵点都合法。所以只需暴力check一组即可。

7.17 Lesnoe Ozero 2016 BSUIR Open 2016 Finals

　　题意：有一个 $N \times N(N \leq 1000)$ 个格子，每一个格子均匀随机一种 $[1,k](1 \leq k \leq N^2)$ 的颜色。一个矩阵的价值是里面不同颜色的数量。求所有子矩阵的价值之和。

　　题解：待补。

　　题意：一个数列前 $5$ 项是 $\{1,2,4,6,3\}$ ，之后每一个$a_i$ 满足：它是与 $a_{i-1}$ 不互质、且之前没出现过的最小的正整数。求它第 $N(\leq 3 \times 10^6)$ 项的值。

　　题解：直接对于每一个质数，维护 $f_i$ 表示含该质数的最小没出现过的数是多少。全局维护一个是否出现过的flag数组，每次枚举 $a_{i-1}$ 的质数，用 $f_i$ 更新，维护 $f$ 时暴力往上走即可。复杂度为 $O(N \log N)$。

　　题意：平面里有 $N(\leq 1000)$ 个点。问有多少条长度为 $6$ 的链，满足这 $6$ 个点互不相同，线段方向交替（第一条线段是向左转，第二条向右转……），且每次转向角都是钝角。

　　题解：待补。

7.19 XVI Open Cup - Grand Prix of Ekaterinburg

7.21 XVI Open Cup - Grand Prix of Siberia

　　题意：有 $k(\leq 10)$ 个寄存器，初始时 $0$ 号点里的值是 $x$ ，别的点都是$0$。给出$m(\leq 15)$操作，分为两种：①将一个寄存器的值加到另一个上。②某个寄存器里的值加一。所有操作都是在模域 $P$ 下进行的。再读入一个 $K$ 位的字符串表示对$P$ 的限制：每一位是 $0$~$9$ 中的一个数或者 $?$ （可以填任意数字）；第一位必然是确定的数字。

　　设所有操作做完后 $0$号点得到的值是 $y$ 。现在只给出 $y$ ，对于所有合法的pair $(x,P)$ ，求 $x$ 的和。注意要保证 $0 \leq x,y<P$，且一个 $x$ 如果有多个 $P$ 符合，答案算多次。

　　题解：这题特别复杂。首先前面的寄存器没啥卵用。题目转化成，$Ax+B=y(\mod P)$，给出 $P$ 的数码限制和 $y$ ，求所有合法解的 $x$ 之和。

　　 $P$ 有数码限制，应该要数位DP；但有取模运算在似乎不好搞。因为寄存器操作 $m \leq 15$， $A$ 和 $B$ 不会很大（几千）。我们可以枚举这个等式的商 $k$ ，将其改写成 $Ax+B=y+kP$ 。如果 $B<P$ （为了满足这个条件，$P$ 限制位数小的时候我们可以暴力枚举 $P$ 验证），又因为 $x < P$，所以 $k$ 的枚举范围为$[0,A]$。

　　再把式子写成 $\frac{Ax+B'}{k}=P$。这个式子必须要整除，设最小合法解为 $x0$ （对应的 $P $称为 $p0$ ）。 $x$ 每加一，分子增加 $A$ ，那么我们可以求一个$dx = \frac{k}{gcd(A,k)}$，表示 $x$ 至少增加这么多才能又一次整除；对应的 $dp = \frac{A}{gcd(A,k)}$。注意还要满足 $x < P$ ，所以第 $i$ 组解如果成立，要满足 $x0 + dx \times i < p0 + dy \times i$，由 $k \leq A$ ，合法的 $i$ 是一个后缀（要大于等于某个值）。

　　求 $\sum x$ 比较麻烦，考虑先求出 $\sum P$ ，最后式子转化一下即可。

　　问题变成了一个有下界要求的数位DP。因为合法的 $P$ 是一组等差数列，DP的时候我们还要再记一维 $mod$ 表示目前填的 $P$ 的前缀对 $dp$ 的模数（最后被统计进答案的 $P$ 需满足 $P \mod dp = p0 \mod dp $ ）。注意不光要记录目前之前填好的前缀所有合法 $P$ 的和，还要记合法 $P$ 的个数（这样才能帮助转移前者）。常数略大，需要卡常。

7.22 Petrozavodsk Winter 2015 - Wroclaw U Contest

　　题意：给出一个 $N(\leq 2 \times 10^5)$ 个点和 $M(\leq 5 \times 10^5)$ 条边的有向图。对于每一个都询问：如果删了这个点，这张图的强连通分量个数是否会增加。

　　题解：每一个SCC单独做。考虑固定一个点 $O$ 。如果点 $X(X \ne O)$ 是合法点，那么至少存在一个子SCC集 $B$ ，满足它和 $O$ 所在的子SCC集 $A$ 不能互相到达。先从 $O$ 点开始跑一个支配树。假设只存在 $B$->$A$ 的边，我们会发现， $X$ 是 $B$ 集合的所有点的支配点；反之 $A$ -> $B$ 有边，只需将所有边都反向，那么 $X$ 依然是它们的支配点。所以，我们跑正反各一次支配树，如果一个点至少一次成为某个点的祖先，就是合法点。最后还要特判 $O$ 点，直接删除它跑一遍tarjan即可。

7.22 FaceBook R1 T4

　　题意：有 $N(\leq 3000)$ 个院子排成一排，相邻两个院子有一个栅栏。每个栅栏的高度是 $(L_i,R_i)(R_i \leq 10^6)$ 里的一个随机整数。

　　还有 $M(\leq 3000)$ 个僵尸，给出它们初始所在的院子和最多能跳的高度。对于所有栅栏的可能局面，问“至少存在一个院子不可能被任何僵尸走到”的概率。答案对大质数取模。

　　题解：有点意识流的DP。设 $f_{i,j}$ 为前 $i$ 个院子都能被僵尸到过，且能走到院子 $i$ 的最强的僵尸是 $j$ 的概率；再设$g_{i,j}$为前$i$个栅栏不能全被僵尸到过，且必须有一个能力至少为 $j$ 的僵尸从右侧跳到第 $i$ 个院子来，能使前 $i$ 个院子都被到过。对于一个 $i$ ， $f$ 和 $g$ 显然是不交的，而且它们的概率和是 $1$ 。每次转移的时候，分情况讨论即可。转移 $g$ 的时候复杂度是 $O(N)$ 的，还需要一个前缀和优化。总复杂度 $O(N^2)$。

7.23 Petrozavodsk Winter 2015 - Jagiellonian U Contest

　　题意：有一个 $6 \times 6$ 的棋盘。现在打乱棋盘上棋子。每次可以对一行或者一列循环移动1格。构造一种能恢复成原来状态的操作序列。

　　题解：如果我们能做到交换两个格子，这题也就结束了。可惜我并没有搞出来。

　　对于一个点 $(x,y)$ ，如果对其执行了 $DRUL$ 的操作，别的数没有发生变化，而$(x,y),(x,y+1),(x-1,y)$这三个字符发生了循环位移。同理，我们也能发现 $(x,y),(x,y-1),(x-1,y)$ 的循环位移的方法。前 $4$ 行每次用三角置换把数字移动到目标位置。最后两行是一列一列填好的，最后还会剩下两个字符（即使是反的也没救了）。到这里也能说明，能互相到达的状态的等价类最多为 $2$ 。实测发现等价类为1，所以每次对于一个初始态，我们可以先随机shift一下，再按这个操作拼。每次正确率的期望是 $\frac{1}{2}$。

　　题意：给出 $b(\leq 5 \times 10^4)$ 进制下，数码 $1$~$b-1$ 分别对应的字符串（总长$\leq 5 \times 10^5$）。再给出一个很长的字符串 $S(|S| \leq 3 \times 10^5)$，找到它的一个子序列 $S'$，使得$ S'$ 能能不重不漏地分解成一些数码对应的字符串，且数码构成的数字最大。要求输出方案。

　　题解：求最长的数字长度还是比较好做的。设 $f_i$ 表示后缀 $i$~$n$ 中能拼成的最长长度，每次枚举从 $i$ 开始最小的能覆盖的子串 $[i,j]$，$f_i=\max(f_{j+1}+1, f_{i+1})$。还要求具体方案的话，因为数字一定是首位越大越优，增设 $g_i$ 表示在满足长度为 $f_i$ 的情况下，当前第一位最大是多少。转移时，找合法覆盖串 $[i,j]$ 的最大可能数码。注意 $j$ 还要满足，$f_{j+1}=f_i-1$。

　　以上是暴力转移的做法。在比赛时，想到了一个$naive$的分块做法。设一个阈值 $last(=100)$ 。把数字对应的串按长度排序，称后 $last$ 个为大串，剩下的为小串。dp转移的时候，分别考虑这两类串的贡献。对于小串，长度都是比较小的，我们直接暴力枚举 $j$ ，然后看一下给定子串是否存在一个对应数码（所以我们还能将小串的长度去重来枚举，减少常数）；对于大串，每次dp第 $i$ 位时直接扫描全集，hash值比对一下即可。复杂度是 $O(N(K+last))$ 的，其中 $K=min(\sqrt{5 \times 10^5 - l \times last},l)$， $l$ 是一个任意值（表示后 $last$ 个串的长度）。手写hash+64位自然溢出可以卡过。

　　事实上有很简单的做法。将所有数码串反向建 $trie$ 图。倒着枚举 $i$ 的时候，直接走 $S_i$ 这条边。这样当前节点 $p$ 的 $fail$ 树上的祖先都是能匹配的串。预处理一个点到根路径上最短匹配串，就可以支持对 $f$ 数组的转移了。 $g$ 数组的话，因为有一个长度限制，如果同时维护的话，需要在 $fail$ 树上询问某一段祖先的最大值。但其实，我们可以等 $f$ 数组做完后，从前往后逐位确定去确定具体方案。每次找到之后 $f$ 连续的那一段，从结尾出开始走 $trie$ 图，这样我们只会询问到根路径上最大匹配串的数码。

　　题意：多组数据。每次给出一个 $N(\leq 2000)$ 个整数的集合，数字范围为 $[0,10^9]$。找出一个长度最长的等差数列。

　　题解：开始想到的做法是：枚举任意两个数 $a_i,a_j$ ，将这个pair插入 $a_j-a_i$ 这个集合里。最后依次扫描每一个集合，每次贪心地跑一遍即可。但是如何划分这些集合呢？直接排序也是会TLE的，首先hash可能也会卡常。

　　事实上，排完序后，直接设 $f_{i,j}$ 表示结尾两个数是 $a_i,a_j$ 时的最长长度。然后找到一个 $k$ ，使得 $a_j-a_i=a_k-a_j$ ，转移到 $f_{j,k}$ 。注意到，枚举 $j$ 的时候，对应的 $k$ 是单调的，指针扫一扫即可。

7.25 XV Open Cup - Grand Prix of America

　　题意：给出一个二进制数 $R$，它是由01串 $S(|S| \leq 50)$ 重复 $K(\leq 10^5)$ 次得到的。要在 $[0,R)$ 里选择 $N$ 个互不相同的数，使得它们的xor值是0。求方案数模 $10^9+7$。

　　题解：还不会帅气的做法。

　　先写一个我搞出来的求允许相同的数的答案。考虑直接数位DP，对每一个数都开一个0/1表示是否已经严格小于 $R$ ，转移时枚举每个数这一位填0/1（都可以用一个二进制状态 $U$ 来描述）。这样复杂度是 $O(|S| \times K \times 2^N)$ 的。 $K$ 很大，考虑倍增 $K$ 。关于合并的话，我并不会特别优美的做法。只会设 $f_{S,T}$ 表示经过一段 $R $之后，原dp数组的状态$S$对新dp数组的状态 $T$ 的贡献的系数。预处理走一段的复杂度上界是 $(4^N \times |S|)$ （枚举子集的子集）。不停地把f合并来倍增。每次合并复杂度也是 $O(4^N)$。

　　题意：初始有一个字符串 $p$ 和空串 $S$ 。重复若干次操作，每次往 $S$ 里的随机一个位置插入一个 $p$ 。给出最终状态的 $S(|S| \leq 200)$，求长度最短（如果一样，字典序最小）的合法的 $p$。

　　题解：要长度和字典序最小，应该是枚举+check的套路。先枚举一个 $|S|$ 的约数 $len$ 。 $p$ 必然是 $S$ 的一个子串，我们再花 $O(N)$ 的时间，可以找到所有可能的 $p$ ，最后验证一下即可。

　　验证时，每次找到最靠前的 $p$ 并删掉是错的。比如$S=ababaa,p=aba$也是合法的。

　　注意到，虽然一块p可能被断成若干截，但夹在其中的每一段，必然是能独立消光的。我们可以 $f_{i,j}$ 表示区间 $[i,j]$ 是否能合法。注意 $j-i+1$ 不要求是 $len$ 的倍数。如果有余数，我们要求多余的部分正好是 $p$ 的前缀。转移时考虑第 $j$ 个字符。

　　一种情况是，它和之后的零碎字符会拼成一段，即 $f_{i,j}|=f_{i,j-1} and a_j = prefix_{(j-i) \mod len+1}$；

　　或者说，对于之后的零碎部分而言， $j$ 是属于夹在它之间的整块，那么 $f_{i,j}|=f_{i,j-k \times len} and f_{j-k \times len+1,j}$。

　　最终复杂度为 $\sum \limits_{k|N} (N-k+1) \times N^2 \times \frac{N}{k}=O(N^4)$

　　题意：一个坏的售货机有 $N(\leq 10^5)$个物品，每个物品有 $a_i(\geq 1)$ 个。还有 $N$ 个按钮，第$i$个按钮指向物品 $f_i$ 。每指定一次 $i$ 后，如果物品 $i$ 和物品 $f_i$ 都有货，要支付 $C_i$ 的代价，但会跳出物品 $f_i$ 。再给出每个物品卖掉的价格 $D_i$ ，问操作一通最多能赚多少钱。

　　题解：挺有趣才摘录的，不难。经典模型，构出来的一定是一棵基环内向树。如果只是树，从根开始直接向外贪心即可。

　　考虑环的话，环上指向一个点 $X$ 的边必须要大于 $X$ 子树朝它的边（否则删掉它即可做一遍树即可）。先全部取到 $1$ ，最后必须损失一个点，找一个最小的即可。

7.27 2018 Multi-University Training Contest 2

　　题意：给出 $N(\leq 15)$ 个整数区间。在每个区间里等概率随机一个实数，求总和的绝对值的期望。模大质数。

　　题解：待填坑。

　　题意：给出一张 $N(\leq 10^5)$ 个点， $M(\leq 10^5)$ 条边的无向图。问最少几条 $path$ 可以覆盖每条边正好一次。要输出方案。

　　题解：度数为奇数的点必然只有偶数个。将它们随意连接，就能得到一张欧拉图。跑一个欧拉路径，再把连接处断开即可。

　　题意：给出一个 $N \times M (N,M \leq 3000)$ 的棋盘。给每一个格子染黑色或白色的一种，问至少有 $A$ 行全黑，$B$ 列全黑的方案数。

　　题解：在一维情况下，算正好是 $x$ 个符合要求的答案，我们可以倒着来$DP$。即 $g_x=f_x-\sum \limits_{i=x+1}^n g_i \times C_i^x$ 。但是二维下，这个是$O(N^4)$的。

　　反思一下，一维的时候，其实我们还可以直接容斥算 $x$ 处的答案。 $g_x=\sum \limits_{i=x}^n f_i \times C_i^x \times (-1)^{i-x}$。

　　而且这个也是可以无伤拓展到二维的。所以现在我们会 $O(NM)$ 的复杂度算 正好有 $A$ 行 $B$ 列的方案数 了。

　　假想我们枚举所有$(A',B')(A' \geq A),B' \geq B)$分别做一遍容斥，这样依然是 $O(N^4)$ 的。

　　但我们可以反过来考虑，对于一组 $(x,y) (x \geq A,y \geq B)$，计算它对所有 $(A',B')$ 的贡献。系数是对一个组合数的式子求和，拆一拆可以用前缀和优化。最终效率是 $O(NM)$ 的。

8.6 XVIII Open Cup - Grand Prix of Peterhof

　　题意：要选出六边形网格（见下图）里的 $N(\leq 10^9)$ 个点，然后用连续围墙把它们围住。围墙也占据格子，且不能和选出的点重合。可以多围一些空的格子。问围墙经过的最少的格子数。

　　题解：若 $N$ 正好等于一个正六边形内部的点数，那么外面围一圈必然是最优的。之后每增加1的围墙，可以“拓宽”一条边界。假设六边形边长是 $e$，向外拓展六次后，能多围的点数分别为 $e-1,e,e+1,e,e,e$。所以一点一点模拟拓宽过程即可找到最优解。复杂度$O(\sqrt N)$。

　　题意：在 $N \times M(N \leq 6,M \leq 300)$的网格里放骨牌。每一个骨牌都是 $1 \times 2$ 的，且正好一端黑一端白。特别的，对于两种骨牌放置方案，如果其带来的染色结果相同，我们认为是同一种方案。求放满骨牌的方案数模一个大质数。

　　题解：很难直接统计骨牌放置的方案，因为处理不了等价的情况。

　　先考虑，如果给出一种染色结果，是否存在一种骨牌放置方案？可以一列一列状压DP过去判断。这样就不用考虑相同的骨牌放置方案了。那么我们可以在之前的DP中，额外开两维 $(i,j)$，表示目前颜色涂到 $(i,j)$，且目前的骨牌能放置的结构为 $S$的方案数。每次枚举这一格颜色是 $0$ 还是 $1$。最后把最终态里合法的颜色的方案数加起来即可。状态数不满 $2000$。

　　题意：在 $N \times N(4 \leq N \leq 100)$ 的国际象棋棋盘上有两颗子。选手操纵后，$judge$程序操纵马。要求在 $K (K \times N \leq 10000)$ 步之内把马吃掉。

　　题解：大概会了。待补。

　　题意：设 $f(x)=\prod \limits_{i=1}^n (1+a_i x)$，$g(x)=\prod \limits_{j=1}^m (1+b_j x)$。（直接给出 $f$ 和 $g$ 的系数）。

　　求 $h(x)=\prod \limits_{i=1}^n \prod \limits_{j=1}^m (1+a_i b_j x)$ 的前 $k$ 项系数，模NTT质数。$n,m,k \leq 10^5$

　　题解：用到一步精妙的泰勒展开（或许是多项式基本操作？）

　　$f(x)=exp(\sum \limits_{i=1}^n ln(1+a_i x))=exp(\sum \limits_{i=1}^n \sum \limits_{k=1}^{\infty} \frac{(-1)^{k+1}}{k} \times {a_i}^kx^k)=exp(\sum \limits_{k=1}^{\infty} \frac{(-1)^{k+1}}{k} (\sum \limits_{i=1}^n {a_i}^k) x^k)$

　　$g(x)$同理。

　　$h(x)=exp(\sum \limits_{i=1}^n \sum \limits_{j=1}^m ln(1+a_i b_j x))=exp(\sum \limits_{k=1}^{\infty} \frac{(-1)^{k+1}}{k} \times (\sum \limits_{i=1}^n a_i)(\sum \limits_{j=1}^m {b_j}^k) x^k )$

　　所以 $ln(h(x))$可以由这两个函数取对数后点乘起来再调一下系数得到。最后再 $exp$ 回去即可。

　　题意：给出一个$n(\leq 10^6)$位的高精度数。判断它是否是完全平方数。

　　题解：NOIP模域做法再现江湖！我们可以指定一些质数 $P$。如果 $n$ 是完全平方数，显然 $n$ 在模域 $P$ 下存在二次剩余，即$n^{\frac{P-1}{2}}=1$。多测试几次即可。

8.7 2017 Multi-University Training Contest 1

　　题意：经典题。给出一棵 $N$ 个点的树。设一条路径的权值是它上面的颜色数。求所有路径的权值之和。

　　题解：显然对于每一种颜色分开考虑。这就变成了一个虚树上DP的模型。

　　虚树上不是所有点都是关键点。直接算包含关键点的路径会比较困难。可以容斥一下，算不包含的数量。

　　虚树上也要额外统计原树里（且不在虚树上）的点。可以分类为“虚树上一条边里的点”和“虚树上的点的其它子树里的点”。

　　题意：给出一棵 $N(\leq 1000)$ 个点的仙人掌。求它前 $K(\leq 10^5)$ 小生成树的代价和。

　　题解：显然每一个环里必须删掉一条边。

　　问题转化成：给出$N$个集合，每个集合里有若干个数（数量总和 $\leq N$）。现在要在每个集合里各删一个数，求剩下数的和的前 $K$ 小解。

　　有一个经典的二分做法。二分答案，暴力去DFS构造。一旦超过 $K$ 可立即停止，复杂度上界 $O(NK \log V)$。

　　题解分析了一通，其实也可以暴力。考虑一个一个去合并这些集合。

　　一种显然的做法是，之前已经维护好了$K$个值。到目前这个集合 $S$ 时，往堆里加 $|S|$ 个元素，每个元素开个指针一步一步从 $1$ 推到 $M$。这样每一轮复杂度是 $O(K \log |S|)$，总复杂度是$O(K \log \prod_{S_i})=O(KN)$

　　题意：有 $N(\leq 5 \times 10^4)$ 个物品，大小为 $i$ 的物品有 $a_i$ 个（$a_i < a_{i+1}$）。求拼出体积为 $1$~$2N$ 的方案数。

　　题解：经典的分段背包。对于大小小于 $\sqrt N$的物品，直接应用队列优化的多重背包即可；对于更大的物品，可以视为无限背包，且最多只会放$\sqrt N$个，直接应用旋转体积背包即可（每次整体 $+1$ 或者加入新的一个点）。

　　注意这里体积要算到 $2N$。可以先将物品视为 $2N$ 个，做一遍旋转体积背包。然后再考虑减掉 “用到体积大于$N$的物品” 的方案数。直接枚举超过的物品体积（$N+1$~$2N$），剩下的调用直接的DP值即可。

8.9 2017 ICPC SWERC

　　题意：字符集为前 $k(\leq 26)$ 个小写字母，填 $N(\leq 500)$ 个格子。还有一个额外限制 $S(|S| \leq 60)$ 。$S=s1>t1|s2>t2|s2>t3 \dots$。其中 $s1,t1,s2 \dots$是字符串，且保证对于一组 $(s,t)$，不可能存在一个字母同时属于$s$和$t$。限制的含义是，若你填的方案里出现过 $s_i$ ，则最后一个 $s_i$ ，必须早于最后一个 $t_i$ 。求合法方案数。

　　题解：看上去很经典？是的。

　　注意到 $|S| \leq 60$，所以最多只有 $15$ 个限制。设直接对所有限制一起建立一个AC自动机。设 $f_{len,p,S} $ 表示填到第 $len$ 位，走到了自动机的第 $p$ 位，且目前对于限制的满足情况是 $S$ （$S$ 是一个二进制状态）的方案数。可惜的是，这样会TLE的。

　　主要还是 $S$ 太大了。考虑建立一种崭新的自动机，能完全刻画出满足的某些限制，而不用 $S$ 来描述。

　　由于不知道如何形式化地建立自动机，我们可以暴力建。具体地，一个自动机上的点是一个状态集合$S$，表示目前对于第$i$个限制它匹配到了哪里。（比如，如果还没匹配完 $s_i$ 就失配了，那从 $s_i$ 头开始匹配；超过 $s_i$ 但没匹配完 $t_i$，则从 $t_i$开头匹配；匹配完了 $t_i$，又可以从头开始搞。注意，由于 $s$ 和 $t$ 出现的字母都不一样，所以不用考虑$kmp$）。

　　可以证明，建出的自动机大小不超过 $10^6$，这样只需要两维DP了。

8.10 German Collegiate Programming Contest 2010

8.15 ICPC Europe NEERC Northern Subregional 2017

　　题意：给出 $m(\leq 20)$ 个层层嵌套的循环语句。设循环变量分别为 $i_1,\dots,i_m$。保证$i_p$的循环下界是$1$或$i_q(q<p)$，循环上界是$N$或$i_q(q<p)$。求$N \rightarrow +\infty$时，该循环复杂度的最高项的系数。结果用最简分数表示。

　　题解：首先，要产生复杂度，每一个循环的下界都要小于等于上界。如果某一层循环 $i_p$ 是从 $i_u$ 循环到 $i_v$ 的，那么 $i_u \leq i_p \leq i_v$。对于每一个 $A \leq B$ 的关系，我们从 $A$ 到 $B$ 连一条有向边。这样$m$个循环变量构成了一张图。

　　首先求出这张图的所有强连通分量。根据连边的意义，每个SCC里的循环变量的取值必须完全一样。

　　那么可以等价地把每个SCC缩成一个点，结果不变。现在获得了一张 $m'$ 个点的拓扑图。

　　因为循环的下界只能是$1$，上界只能是$N$，如果不考虑循环变量之间的大小限制，总遍历次数是 $N^{m'}$。现在，我们要额外考虑循环变量之间的限制，如果算出对应的实际遍历次数 $cnt$，那么答案就是 $\frac{cnt}{N^{m'}}$

　　一个显然但是重要的转化：在 $N \rightarrow +\infty$ 下，我们可以忽略新图中存在两个点取值相同的情况。即你可以认为，所有点的取值两两不同。

　　考虑给这 $m'$个点任意两个 $rk$ 的合法排列 $p_1,p_2$（合法的意思是，满足拓扑图的大小限制）。你会发现，$p_1$ 和 $p_2$ 遍历到的次数（对应的取值方案数）是完全一样的。然后你进一步会法案，一个合法排列 $p$ 与一个不合法排列 $p'$ 遍历到的次数也是完全一样的。

　　所以可以转化为这样一个问题：给出一张最多 $20$ 个点的拓扑图，问有多少种 $rk$ 分配的排列，使得满足拓扑图限制。合法分配数除以排列总数即是我们要求的答案。这个直接 $O(2^{m'} \times m')$ 的状压DP即可。

　　题意：给出 $N(\leq 50000)$ 个数 $a_i(a_i \ne 0)$。设 $A=\sum \limits_{a_i>0} a_i,B=-\sum \limits_{a_i<0} a_i$。

　　再设

$\begin{equation} w_i=\left\{ \begin{array}{rcl} \frac{a_i}{A} & & {a_i>0}\\ \frac{a_i}{B} & & {a_i<0}\\ \end{array} \right. \end{equation}$

　　再设 $sum_i$ 是 $w_i$ 的前缀和。求 $sum_i$最大的位置 $i$。有 $Q(\leq 50000)$ 次操作，每次修改一个数，然后回答一下。

　　题解：在一次单调修改后，后缀 $sum_x$都会变动，不利于维护。很容易想到分块的操作。

　　$sum_i$ 割裂成 “大于$0$”和“小于$0$” 两维（以下简称 $x$ 和 $y$ ）的前缀和，就可以看做一个点了。因为 $A$ 和 $B$ 变动也很频繁，没有规律，我们可以把 $A$ 和 $B$ 当做变量去查询。

　　具体地，对数列分 $\sqrt N$ 块。每块无视之前的前缀和，从头算出 $sum_x$ 和 $sum_y$。对于询问，本质是求 $(B,A)$ 和 $(sum_x,sum_y)$ 的最大点积值（其中前者在第一象限，后者在第四象限）。考虑点积的几何意义，我们只需对点集$sum$，在第四象限维护出一个凸壳即可。询问时，做一个垂直于 $(B,A)$ 的直线，从无穷远处移动过来，碰到的第一个点即为答案点。

　　上述要维护的东西可以用二分+点积做到。

　　每次回答时，枚举每一个块分别问一下。之前块对后面块的影响，相当于把凸壳平移了一段距离。其实最优点依然不变。

　　每次修改时，暴力重建对应块的凸壳即可。复杂度为 $O(Q \sqrt N \log N)$。

转载于:https://www.cnblogs.com/jiangshibiao/p/9348328.html

你可能感兴趣的文章