九月杂题选做

· · 个人记录

LOJ#6495. 「雅礼集训 2018 Day1」树

这个题训练的时候做了，结果只有两个人过，而且还有一个写的是状压DP……

令 dp_{n,d} 表示n个点，最大深度为d的二叉树个数.

转移分为两种情况:

1、1号节点只有1个子树。此时的DP值为 dp_{n-1,d-1}.

2、1号节点有多于一个子树。由于2号节点的父亲一定是1，我们考虑枚举2号节点所在子树的大小和最大深度然后暴力转移，复杂度\Theta(N^4).

精细实现应该可以做到 \Theta(N^3).

至于求答案下取整的问题，可以考虑使用long double或__int128.

代码见 : my solution

LOJ#6496. 「雅礼集训 2018 Day1」仙人掌

这个题训练的时候做了……然后……我圆方树对方点儿子排序的部分写错了……

建出圆方树，然后考虑DP.

对于每个方点x，我们需要知道儿子节点(圆点)还剩下度数为0/1/2的方案数，用来DP。

对于每个圆点x，我们需要知道儿子节点会用掉x的多少度数以及对应的方案数，不难想到把它们写成一个多项式,卷积起来即可得到。这个点还剩下度数为0/1/2的方案数。

观察到不管是圆点还是方点，会用掉父亲节点的度数一定 \leq 2 ，所以直接分治FFT，复杂度不超过 \Theta(n\log^2 n)

代码见 : my solution

LOJ#6497. 「雅礼集训 2018 Day1」图

考虑 dp_{i,a,b,0/1} 表示当前DP到第i个，目前有a个黑色的奇数点,b个白色的计数点的方案数，转移直接暴力即可。

可以发现状态里的a/b的值实际上没意义，如果没有，那么显然当前点必然是奇数;如果有，那么就是 \frac{1}{2} 的情况用偶数转移， \frac{1}{2} 的情况用奇数转移即可.

\Theta(n).

代码见 : my solution

P5502 [JSOI2015]最大公约数

解法1：

考虑分治解决这个问题。

维护当前的合法区间，如果扩展区间不会让 \texttt{gcd} 变小的话就直接扩展。

然后考虑往两边走即可。

左右各做一遍，然后取max即可。

\Theta(n\log n \log A_i)

解法2：

对于同一个L,gcd只有\log(A_i)种，那么对R记录这\log个区间即可.

\Theta(n\log^2 A_i)

LOJ#6038. 「雅礼集训 2017 Day5」远行

在并查集上维护每个联通块的直径，同时用 LCT 维护树形态即可。

\Theta((n+m)\log n)

代码见 : my solution

[JSOI2007]合金

首先，材料的前两个属性可以唯一确定一个材料，合金的前两个树形也可以唯一确定一个材料。

那么材料和合金都可以被看成平面上的点 (a_i,b_i) 或 (d_i,e_i)

不难发现，一些材料能表示出一种合金当且仅当这个合金（在平面上的点）在选取的材料（在平面上的点）组成的凸包内。

不难发现，选取的点凸包上的边一定满足：所有的合金代表的点都在这条边的某一侧，或者在这条线段上（不是直线上）

那么我们直接求个最小环就行了。

复杂度 \Theta(n^3+mn^2).

注意特判答案为 1 或 2 的情况。

代码见 : my solution

LOJ#6507. 「雅礼集训 2018 Day7」A

直接线段树上打 tag 即可，如果遇到打tag之后存在不同的值的区间，那么就往下递归。

复杂度分析 :

记一个节点的势能 f(node) = \sum\limits_{i=0}^{31} g(node,i) ,其中 g(node,i) 表示 node 节点内部的所有数字中，第 i 个二进制位上是(1)/否(0)有不同的值。

一开始势能是 \Theta(n\log n \times 31) 的。

每次修改最多增加 \Theta(\log n \times 31) 的势能，过程中如果暴力递归了一次那么势能必然也会减去1，所以复杂度为 \Theta((n+m) \log n \times 31).

代码见 : my solution

LOJ#6513. 「雅礼集训 2018 Day10」足球大战

首先判掉 p=0/1 或者 q=0/1 的情况。

记 x = \frac{p}{1-p} , y = \frac{q}{1-q} ,不难发现主场进 i 个球的概率为 \binom{n}{i} \times x^i , 客场进 i 个球的概率为 \binom{n}{i} \times y^i

那么直接计算概率就可以了。

实现的时候，由于空间是 64MB 所以我们只能开一个 O(n) 的数组。

可以发现我们只需要预处理阶乘的逆元。

实现要注意常数和空间。

代码见 : my solution

LOJ#6510. 「雅礼集训 2018 Day8」A

不难发现题目要求一个不定根的最小树形图。

那么直接套板子即可。

\Theta((n+m)\log n)

代码见 : my solution

LOJ#6501. 「雅礼集训 2018 Day4」Cube

答案为 \binom{n}{m} \times 2^{n-m}

证明1 :

考虑枚举m维作为超立方体，令剩余的n-m维在0/1中任意选择，方案即为选出m维的方案和n-m维选择0/1的方案的乘积即\binom{n}{m} \times 2^{n-m}

证明2 :

首先 f_{1,1} = 1,f_{1,x(x>1)} = 0.

对于 f_{n(n>1),m} ,我们尝试寻找其递推式。

不难发现我们要么是当前一维拿来确定，即在两个n-1维超立方体中找出m-1维超立方体的方案数，为 f_{n-1,m-1} .

或者我们直接递归到两个子超立方体中，此时的答案为 2f_{n-1,m} .

不难发现答案即为 [x^m](x+2)^n = \binom{n}{m} \times 2^{n-m} .

代码见 : my solution

LOJ#6502. 「雅礼集训 2018 Day4」Divide

考虑把数列w_i重新排列，使得新数列 w_i 满足对于任意 i , 所有的 w_{j(j<i)} + w_i \geq m 或者所有的 w_{j(j<i)} + w_i < m ,然后 O(n^2) DP 就容易了。

如何构造？

先把 w_i 从小到大排序。一开始答案序列 ans 为空。

如果 w_1+w_n \geq m ,那么对于所有 w_{i(i<n)},w_{i(i<n)}+w_n \geq m ,可以把 w_n 放到 ans 的末尾，并删去 w_n

否则，对于所有 w_{i(i<n)},w_{i(i<n)}+w_n < m ,可以把 w_1 放到 ans 的末尾，并删去 w_1

那么就可以 \Theta(n\log n) 构造了。

复杂度 \Theta(n^2)

代码见 : my solution

LOJ#6498. 「雅礼集训 2018 Day2」农民

不难发现，一条父亲到左儿子的边相当于一个\texttt{<}限制，一条父亲到右儿子的边相当于一个\texttt>限制。

考虑用树链剖分维护这些限制，2操作直接线段树上打tag，把\texttt<限制和\texttt>限制交换一下即可。

\Theta(n\log^2 n)

代码见 : my solution

LOJ#6499. 「雅礼集训 2018 Day2」颜色

考虑分块，设块大小为S。每个块用一个bitset记录块中颜色，整块之间打st表，查询的时候整块st表查，零散部分暴力即可。

时间复杂度\Theta(\frac{nS\log S}{w}) - \Theta(\frac{n}{w}+S)

空间复杂度\Theta(n+\frac{nS\log S}{w})

代码见 : my solution

LOJ#6503. 「雅礼集训 2018 Day4」Magic

对每个 a_i, 建出一个多项式 F(x) = \sum\limits_{j=1}^{a_i} x^j \binom{a_i-1}{j-1}, j次项系数表示这些卡牌被分成j段的方案数，也表示它们有a_i-j处强制为魔术对的方案数。

对它们进行EGF卷积，最后的结果G(x)的n-i次项系数 [x^{n-i}]G(x) 即为强制有i处为魔术对的方案数。

最后二项式反演即可得到答案为 ans = \sum\limits_{i=k}^{n} (-1)^{i-k} \binom{i}{k} [x^{n-i}]G(x).

怎么求出把m个长度之和=n的多项式的卷积的结果呢？

用一个堆记录当前多项式，每次找长度最短的那两个卷积起来即可，可以证明复杂度不超过\Theta (n\log^2 n)

代码见 : my solution

LOJ#6035. 「雅礼集训 2017 Day4」洗衣服

首先把两个过程分别贪心，然后对应匹配一下即可。

\Theta(l \log n).

代码见 : my solution

LOJ#6738. 王的象棋世界

一个 R \times C 的棋盘，你有 Q 组询问，每次询问国王走 R-1 步从 (1,x) 到达 (R,y) 有多少种方案。你只需要输出答案对 998244353 取模的结果。

首先不难有一个每组询问\Theta(C^3 \log R)的做法，即设转移矩阵 T 满足 T[i][j] = [ |i-j| \leq 1 ],然后矩阵快速幂。

因为转移是向量乘矩阵的形式，所以在C固定的情况下，对于任意的x,y,答案都是一个关于R的线性递推，并且有相同的特征多项式。

\begin{bmatrix} \lambda - 1 & -1 & & \ -1 & \lambda - 1 & -1 & \ & -1 & \lambda - 1 & \ddots \ & & -1 & \ddots \ \end{bmatrix}$

不难发现行列式/特征多项式满足递推式 : F_C = (\lambda - 1)F_{C-1} - F_{C-2}

可以通过矩阵乘法在\Theta(\log C)的时间内求出F_C的一个点值，那么求出所有单位根的点值然后再IDFT,就可以在\Theta(C\log C)的时间内获得F_C的系数了。

记x^R对特征多项式F_C取模之后的每一项系数为r_0,r_1,..r_{C-1},那么ans_R = \sum\limits_{i=0}^{C-1} ans_i \times r_i.

考虑翻折容斥，因为i<C,所以上下界不会同时越界，因此可以把有边界的ans转化成3个无边界的查询。

对于无边界的情况，我们要求\sum\limits_{i=0}^{C-1} r_i (x^{-1} + x^0 + x^1)^i,分治FFT即可。

然后就可以\Theta(1)查询了。

\Theta(C\log C \log R) - \Theta(1).

代码见 : my solution

LOJ#6045. 「雅礼集训 2017 Day8」价

首先把价值取反，然后问题转换为求最大权值。

考虑一个最小割模型:

S连向药，容量INF+权值，割掉这条边相当于不选这个药；

药连向药材，容量INF；

药材连向T，容量INF，割掉这条边相当于选这个药材；

不难发现在最小割方案中，割掉药连向药材的边是不优的。

因为有完美匹配，所以对于任意左部点集合 S , |N(S)| \geq |S|, 因此至少会割掉n条边。

又因为边权加上了 INF ,所以不会割掉 >n 条边。

因此不选的药的个数 + 选的药材个数 = n，所以可以得到选的药材个数 = 选的药的个数。

然后跑一个最小割即可。

O(Dinic(n,n^2))

代码见 : my solution

双倍经验 : CF103E Buying Sets

洛谷P4585 [FJOI2015]火星商店问题

直接线段树套Trie即可。

\Theta(n\log n \log a_i).

代码见 : my solution

IOI2020Day1T2 连接擎天树

IOI2020题解-洛谷博客 IOI2020题解-cnblogs

题目链接-LOJ 题目链接-洛谷

首先，如果存在 p_{i,j}=0 ,那么就分成了多个联通块，这些联通块分开做即可。

由于 p_{i,j} \leq 3 所以一个联通块当中不能出现多于一个环，否则必然会有两个点之间有 4 条路径。

没有环的情况(联通块内 p_{i,j} 均为 1 )先判掉，那么这个联通块正好有一个环。

不难发现，如果两个点 x 和 y 之间的路径需要经过多于一个环上的节点，那么 p_{x,y} 就等于 2 ,否则 p_{x,y} 为 1 , 因此如果存在 p_{x,y} = 3 那么也无解。

把所有的 p_{x,y} = 1 的 x 和 y 合并到一个联通块中，把这些块之间连成一个环， check 是否合法即可。

\Theta (n^2)

code见我的题解 solution-洛谷博客 solution-cnblogs

IOI2020Day1T3 嘉年华奖券

IOI2020题解-洛谷博客 IOI2020题解-cnblogs

题目链接-LOJ 题目链接-洛谷

首先我们考虑如何求出最大值。

不难发现这个抽奖的过程中，工作人员必然会取中位数来最小化当前轮次的奖励。

因为n是偶数，不难发现我们能获得的奖励为：

设当前轮次使用的奖券上的数值为 a_{1,2...n} 并且已经从小到大排序，那么

\large ans=\sum\limits_{\frac{n}{2}+1\leq i\leq n} a_i -\sum\limits_{1\leq i\leq \frac{n}{2}} a_i

也就是说，有 \large \frac{n}{2} 个数对答案的贡献为 a_i ,另 \large \frac{n}{2} 个数对答案的贡献为 -a_i , 并且所有负贡献的数字都不大于正贡献的数字。

可以发现，经过 k 次过程获得的最大值，相当于我们在 n 种颜色的奖券上的数字中，每种颜色选取 k 个数字，并在其中选 \large \frac{nk}{2} 个数字，使其对答案的贡献为正数 ，令另外一半的数字的贡献为负数 ，然后求和即为答案。

不难发现如果我们获得了这个取数问题的最优解，那么必然存在一种方案把这 nk 个数分成 k 组使得每组中有 n 个颜色两两不同的数，一半取负贡献，一半取正贡献，并且负贡献的数都不大于正贡献的数字。即有对应原问题的合法方案。

证明：如果不存在合法方案，那么对于任何一种方案，必然存在同一组数字中有一个取负贡献的数大于一个取正贡献的数。这时候交换一下它们的符号就可以获得一个更优的解，所以如果取得了最优解的取数方案，必然有一个对应了原问题的合法方案。

取数问题的贪心：先默认都取负数，然后再贪心的做 \large \frac{nk}{2} 次把负数换成正数的操作即可。

然后我们考虑如何构造方案。

递归构造，考虑从当前的 nk 个数字中取出 n 个颜色两两不同的成为一组，保证它合法后再对剩下的 n(k-1) 个数字继续构造。

从每种颜色中取出一个最大的正数和一个最小的负数并将正数和负数分别排序，枚举正数和负数之间的边界，two-pointers 的同时维护可用的正/负数数目即可。

因为正数和负数分别取到了最大和最小，所以在整个取数问题有对应方案的时候这个子问题必然能找到一组解，可以继续递归。

由于递归的时候保证了选数方案一直是当前的最优解，所以一直都能保证当前的选数方案有一组对应原问题的解。

\Theta(nm\log n)

code见我的题解 solution-洛谷博客solution-cnblogs

LOJ#6500. 「雅礼集训 2018 Day2」操作

首先考虑一个 \Theta(nm) 的暴力。

一次操作对差分数组的影响是把两个距离相差k的位置都异或上1,那么我们只需要保证对于模 k 的每个余数的位置上的1的总数为偶数即可，并且答案为相邻两个的位置差的和 / k。

那么对于每组询问，我们只需要做一个差分即可。判断是否有解可以考虑哈希。需要注意细节。

\Theta(n+m+k)

代码见 : my solution

IOI2020Day1T1 植物比较

IOI2020题解-洛谷博客 IOI2020题解-cnblogs

题目链接-LOJ 题目链接-洛谷

首先我们考虑构造出一个符合题意的数列。

每次选择一个 前面 k-1 个位置上都是 0 或者已经选过，并且当前位置为 0 的位置，然后把它的值置为这个序列的最大值。不难发现这样做一定能构造出一个符合要求的排列。

这个构造的过程可以用线段树+set优化到 \Theta(n\log n)

不难发现，一个排列符合条件相当于它的每连续 k 位的相对大小关系和我们构造出来的排列相同。

那么，不难证明在 2k>n 的时候只有唯一的一个排列，所以不判 0 直接比较可以获得子任务 2/3/4 的分数。

现在排列不唯一怎么办？

考虑对于每个点，求出它往左/右 k 个位置中，比他小的最大的数字的位置，分别记为 pre_i 和 nxt_i ，然后对 pre/nxt 做一个倍增。

对于每组询问，假定我们构造的排列 A 满足 A_x>A_y 。

我们从 x 开始，通过 nxt 和 pre 往左右跳，保证跳的时候仍然满足当前位置的值 >A_y . 如果跳到的区间包含了 y ，那么就输出 1 ，否则不能确定，输出 0 .

$\Theta((n+q)\log n)

code见我的题解 solution-洛谷博客solution-cnblogs

[NOI2013]小Q的修炼

提交答案题。

data1-2 是直接暴力\Theta(n \times 2^k ) 其中 k 为条件跳转操作的数目。

data3 是分块暴力。

data4-6 都是直接DP.

data7-8 是分块讨论然后DP.

data9-10 和data7-8基本差不多，但是有一些不符合规律的点要特殊考虑。

[HNOI2015]落忆枫音

首先如果不加入边 (x,y) 那么方案数为所有点入度的乘积。

我们要计算的是强制选取边 (x,y) 的情况下,能形成树形图的方案数

方案数为除去y的所有点入度乘积 - 形成环的方案数。

形成环的方案数可以在 DAG 上 DP 解决。

\Theta (n+m)

LOJ#6051. 「雅礼集训 2017 Day11」PATH

注意:本题解数组下标从 1 开始

不难发现概率为可行方案数/总方案数。

总方案数显然为 \large \frac {(\sum\limits_{i=1}^{n} a_i)!}{\prod\limits_{i=1}^{n} a_i!}

可行方案数如何计算？

考虑记 t_{i,j} 表示第 i 维 x_i 的值刚好加到 j 的时间。

不难发现只有 i \leq n 且 j \leq a_i 的时候, t_{i,j} 才有意义, 并且 t_{i,j} < t_{i,j+1}(如果存在) , t_{i,j} < t_{i+1,j}(如果存在)

那么这就是一个给定形状的杨表计数问题。

杨表计数问题的答案为 \large \frac {(\sum\limits_{i=1}^{n} a_i)!}{ \sum\limits_{i\leq n,j \leq a_i} Cnt(i,j)} , 其中 Cnt(i,j) 为 (i,j) 这个格子的钩长+1.

记 b_x = \sum\limits_{i=1}^{x} [a_i \leq x] , 不难发现如果 (i,j) 在杨表内部,其 Cnt(i,j) = (a_i - j) + (b_j - i) + 1 ,否则 (a_i - j) + (b_j - i) + 1 会小于 0 .

那么直接把式子拆成 (a_i - i) + (b_j - j) + 1 即可,可以直接 NTT 或者 FFT 解决，最后乘上 \prod\limits_{i=1}^{n} a_i! , 而 (\sum\limits_{i=1}^{n} a_i)! 这个巨大的阶乘在两个方案数相除的时候已经被消掉了，不需要处理。

\Theta(N\log N)$ , 其中 $N$ 为 $(n+\max\limits_{i=1}^{n} a_i)

代码见 : my solution

LOJ#6102. 「2017 山东二轮集训 Day1」第三题

记斐波那契数列的第 n 项为 F_n .

结论1 : \gcd(F_n,F_m) = F_{\gcd(n,m)}

这个应该是经典结论了。

大概就是,首先有 F_{n+m} = F_{n-1}F_{m} + F_{n}F_{m+1} 且 \gcd (F_n,F_{n-1}) = 1

那么不难发现 \gcd(F_{n+m},F_m) = \gcd(F_n,F_m) .

结论2 : \texttt{lcm}(S) = \prod\limits_{T ∈ S,T \neq ∅} \gcd(T) ^ {(-1)^{|T|+1}}

不难发现这个式子和对每个质因数进行 min-max 容斥等价，于是得证。

考虑计算出每个 F_{gcd(T)} 的次数，那么直接 Dirichlet 前缀和 一下即可。

因为最后需要快速幂，所以复杂度为 \Theta (n \log n) . 如果不想写 Dirichlet 前缀和 , 也可以写 \Theta(n \ln n) 的暴力，但还是跑的飞快？

代码见 : my solution

LOJ#6059. 「2017 山东一轮集训 Day1」Sum

考虑记 F_{n,m,r} 表示有多少个 n 位数 , 满足各位数之和为 m ，且对 p 取模的结果为 r .

不难发现我们只需要支持 F_{n} -> F_{n+1} 和 F_{n} -> F_{2n} 就可以了。

F_{n} -> F_{n+1}$ 可以直接枚举下一位数是什么,暴力转移,单次复杂度 $\Theta(10pm) F_{n} -> F_{2n}$ 需要卷积，实现的时候注意不要用过多的 NTT , 3p 次就够了 , 单次复杂度 $\Theta(p^2m+pm\log m)

总复杂度 \Theta (pm(10+p+\log m)\log n)

代码见 : my solution

LOJ#6068. 「2017 山东一轮集训 Day4」棋盘

考虑把一段连续的空地缩起来，形成一些"行"和"列"。

考虑一个网络流模型。

S -> 行，流量无限制，费用 f(flow) = \frac{flow (flow+1)}{2} , 列 -> T , 流量无限制，费用 f(flow) = \frac{flow (flow+1)}{2}

对于每个非障碍点，所在行 -> 列，流量为 1 ，费用为 0。

至于这个 f(flow) = \frac{flow (flow+1)}{2} , 我们把它拆成一堆流量为 1 , 费用分别为 0,1,2,3,4,...,5 的边。

最后因为 S -> 行不会用超过这一"行"里的点数的流量，列 -> T 类似，所以我们只会连 \Theta (n^2) 条边。

然后直接増广即可，注意到询问很多，要从小到大排序之后增加流量。

复杂度 O(EK(n^2,n^2)) , 实测 ZKW 跑的很慢，因为询问可以覆盖满 1 \cdots n^2，这时候显然比 EK 慢。

代码见 : my solution

LOJ#6062. 「2017 山东一轮集训 Day2」Pair

对每个数 a_i 求出它能匹配的 b_j 的数目，记为 c_i 。

考虑 Hall 定理，对于 c_i 的一段长度为 m 的连续子段，记 s_i 为 \leq i 的 c_i 的数目，因为 Hall 定理所以有 s_i \leq i , 并且如果满足 s_i \leq i 那么一定有完美匹配。

那么直接线段树上维护 s_i - i 的 \min 即可。

\Theta (n\log m)

代码见 : my solution

LOJ#6065. 「2017 山东一轮集训 Day3」第一题

枚举 \Theta(n) 种正方形的边长 L , 不难发现在选的 6 条边中只可能有 2 条 / 3 条 边的长度为 L .

有 2 条边长为 L :

另外两条边分别由两个比 L 小的数拼接而成。枚举拼成 L 的方式 ( 即 L = x + y ，(x \leq y) 的 x 和 y ) , 不难发现每种方式之间相互独立，然后分别考虑一下只用这种方式 / 使用两种不同方式 的方案数并求和即可。

有 3 条边长为 L :

剩下的一条边由三个加起来 =L 的数字拼接而成，不妨设 L = x + y + z(x\leq y\leq z) , 先 \Theta(n) 处理 x = y = z 或者 x = y < z 或者 x < y = z 的三种情况。

最后 x < y < z , 枚举 z 之后变成查询前 i 种数拼成 L-z 的方案数 , 这个可以离线下来做。

\Theta(n^2)

代码见 : my solution

LOJ#6039. 「雅礼集训 2017 Day5」珠宝

因为物品的价格不超过 300 , 所以考虑每种体积的物品一起处理，然后按照对 % m 的余数分类并 DP.

不难发现由于 DP 转移的权值满足四边形不等式，所以对于 % m 同余的 DP 状态满足决策单调性，因此直接分治解决即可。

\Theta (Cn\log n)

代码见 : my solution

LOJ#6033. 「雅礼集训 2017 Day2」棋盘游戏

把每个非 '#' 的格子当成点，共用边的格子所代表的点之间连一条边，不难发现这是个二分图。

不难发现这个二分图上的博弈，先手必胜当且仅当起始点一定会被包含在最大匹配中，否则后手只要一直走匹配边就赢了。

那么我们判断每个点是否可以成为这样的起始点即可。

求最大匹配的部分可以使用匈牙利算法也可以直接网络流，复杂度为 \Theta(n^2m^2) 或 \Theta((nm)^{1.5})

代码见 : my solution