2021.02.06

$\texttt{Location:HNOI2021}$

得分:$\texttt{230/300,Rank1}$。

[02.06]-错误

$\texttt{T3}$ 完全不会做,对生成函数不够熟悉。

[02.06]-部分正解

$\texttt{T1}$

直接区间 $\text{dp}$,设 $\text{dp}_{l,r}$ 为区间 $[l,r]$ 的最优解。

考虑枚举一个断点 $k$,令他是 $[l,r]$ 最后一个被吃掉的位置。于是有转移:

$$ \text{dp}_{l,r}=\max_k\{\text{dp}_{l,k-1}+\text{dp}_{k+1,r}+w_{k,l,r}\} $$

其中 $w_{k,l,r}$ 表示被 $[l,r]$ 包含,且一定包含 $k$ 点的区间中最大的权值,这是很好算的。

直接转移,时间复杂度 $\mathcal{O}(n^3)$。

$\texttt{T2}$

十分显然的结论:子树所代表的 $\text{dfn}$ 区间只有不交、完全包含两种相对关系。

考虑上面的结论,发现如果我们需要更新一棵子树,那么需要先撤销其子树内的所有操作。

直接记录 $c$ 个 $\text{set}$,里面存所有已经被染了 $c$ 这种颜色的区间。每次加入新区间,就暴力在 $\text{set}$ 里找被其完全包含的,在线段树上撤销操作。

如果新操作的子树区间已经被包含了,显然跳过即可。

时间复杂度 $\mathcal{O}(n\log n)$。

$\texttt{T3}$

考虑计数恰好 $k$ 个逆序对的排列可以怎么做:

假设现在已经得到了一个 $1$ 到 $i-1$ 的排列,那么我们可以通过在左边/右边插入一个数字,再修改相对的值,使逆序对个数添加 $[1,i-1]$ 中的任意数字。

所以可以 $\text{dp}$,设 $\text{dp}_{i,k}$ 为 $1$ 到 $i$ 的排列,逆序对个数为 $x$ 的方案数,直接 $\mathcal{O}(nk)$ 转移。

但是我们发现,一次转移可以看做乘一个多项式 $1+x+x^2+...+x^{i-1}$。

再考虑原题。发现一个点的深度可以拆成一个点的祖先个数,所以只需要计数某点 $y$ 成为节点 $x$ 的祖先的次数,这当且仅当:

$$ \min_{k=\min(x,y)}^{\max(x,y)}\{p_k\}=p_y $$

考虑先从 $x$ 向 $y$ 一侧走,依次填数。然后再向反方向,依次填数。显然可以构造出所有情况。

需要注意的是,$y$ 这个位置比较特殊。如果 $y<x$,则这个位置贡献为 $0$;若 $y>x$,则这个位置贡献为 $y-x$。发现只有 $y-x$ 重要了,所以不需要枚举 $x,y$ 了,而只需要枚举 $y-x$。

用类似多项式的方法,预处理优化,可以做到 $\mathcal{O}(nk)$。


2021.02.07

$\texttt{Location:HNOI2021}$

得分:$\texttt{147/300,Rank2}$。

[02.07]-错误

$\texttt{T2}$ 少乘了一个阶乘,于是炸了。
$\texttt{T3}$ 不会做。

[02.07]-部分正解

$\texttt{T1}$

若 $\max\{p_i\}\ge \dfrac{1}{2}$,直接输出。

概率是:

$$ P=\sum_{i=l}^r p_i\prod_{j=l}^r[j\ne i] (1-p_j) $$

令 $\text{mul}_x=\prod_{i=1}^x (1-p_i)$,$\text{sum}_x=\sum_{i=1}^x \dfrac{p_i}{1-p_i}$。那么概率是:

$$ P=\dfrac{\text{mul}_r}{\text{mul}_{l-1}}(\text{sum}_r-\text{sum}_{l-1}) $$

推推柿子可以发现单峰,于是可以二分。观察发现可以双指针,于是变成 $\mathcal{O}(n)$。

$\texttt{T2}$

发现路径可以很长,但是 $k$ 很小,所以考虑算出所有长度小于 $k$ 的路径和,然后减一下。

可以把每棵树都写成一个生成函数,表示两两之间路径的长度,全部卷起来就可以了。

$\texttt{T3}$

首先,每次走出一个矩形是最优的。那么若按照 $x$ 从小到大排序,那么首先要求一个 $\text{LIS}$(最长上升子序列),同时,要求这个 $\text{LIS}$ 使得相邻两点之间构成的矩形面积的和最小。

设以其结尾的 $\text{LIS}$ 长度为 $i$ 的位置组成的集合为 $L_i$,$\text{dp}_i$ 表示已经考虑到 $i$ 的最优解,令其 $\text{LIS}$ 长 $l$。那么有:

$$ \text{dp}_i=\min_{p\in L_{l-1}, x_p<x_i,y_p<y_i} \text{dp}_p+(x_i-x_p)(y_i-y_p) $$

那么可以考虑按 $\text{LIS}$ 长度分层 $\text{dp}$。

观察到,对于同一个集合 $L_x$ 中的元素,横坐标递增,纵坐标递减。再考虑优化上述 $\text{dp}$。

无法斜率优化,因此考虑决策单调性:

若不考虑 $x_p<x_i,y_p<y_i$ ,那么若 $j$ 优于 $k$($k<j$),那么:

$$ \text{dp}_j+x_jy_j-x_iy_j-x_jy_i\le \text{dp}_k+x_ky_k-x_iy_k-x_ky_i $$

$$ (y_k-y_j)x_i+(x_k-x_j)y_i\le \text{dp}_k+x_k y_k-\text{dp}_j- x_j y_j $$

而根据上述结论,$y_k-y_j$,$x_k-x_j$ 一正一负,所以这是一个斜率为正的半平面。其将下一层的点划分为两部分,因此具有决策单调性。

对于限制 $x_p<x_i,y_p<y_i$,发现在同一层中,这样的节点是连续的。所以把询问挂在线段树上,每次对线段树上每个节点,取出其询问节点,跑决策单调性即可。

线段树+决策单调性,时间复杂度 $\mathcal{O}(n\log^2 n)$。


2021.02.19

$\texttt{Location:HNOI2021}$

得分:$\texttt{210/300,Rank1}$。

[02.19]-错误

$\texttt{T3}$ 有分可拿,但是没有去拿......

[02.19]-部分正解

$\texttt{T1}$

首先有十分 $\text{naive}$ 的 $\text{dp}$,可以划分每一层的点的个数,然后向上一层连边即可。复杂度 $\mathcal{O}(n^4)$ 的样子,无法通过。

考虑到只需要深度为奇数的点数为 $k$,因此深度具体是多少并不重要,重要的是奇偶性。

注意到树是二分图,且恰好可以根据深度的奇偶性黑白染色,因此不妨将其化成二分图的形式。发现只有二分图两边连边,一边点有 $k$ 个,另一边 $n-k$ 个。

这就是生成树计数问题了,所以考虑 $\text{Matrix-Tree}$ 定理。先将二分图两侧的点之间两两连边,然后画出其基尔霍夫矩阵。直接消元跑不过,且发现矩阵十分有规律,所以考虑手动消元一下。

消完之后发现其代数余子式的行列式为 $k^{n-k-1}(n-k)^{k-1}$,再组合一下,除了 $1$ 之外的标号需要分配。因此答案为:

$$ \binom{n-1}{k-1}k^{n-k-1}(n-k)^{k-1} $$

$\texttt{T2}$

直接考虑最大权闭合子图。

考虑到最小值不好弄,所以所有值取反得到数组 $a_i$ 来求最大值。源点连药,权值为 $+\infty+a_i$,药与药材连边,权值为 $+\infty$,药材与汇点连边,权值为 $+\infty$。

直接跑最小割就可以了。

需要证明的是,为什么这样一定可以保证药和药材数量相同。首先由于原二分图有完美匹配,所以至少需要割去 $n$ 条边,而又如果把与 $S$ 相连的所有边都割去,恰好为 $n$ 条。由于其他的边的边权远大于权值,所以一定割去 $n$ 条,更多一定不优。

同时,割中间的边一定不优,所以 $n$ 条边一定从与 $S,T$ 相连的边中选。又割去与 $S$ 相连的边,表示选择这个点,割去与 $T$ 相连的边,表示不选这个点。所以,若与 $S$ 相连的边割去 $a$ 条,那么表示选择了 $a$ 种药,此时与 $T$ 相连的割去了 $n-a$ 条,表示有 $n-a$ 个药物不选,则恰好也是 $a$ 种药材选择,满足限制。

$\texttt{T3}$

考虑到实际上是区间问题,区间加+区间第 $k$ 大,因此分块。

在每块中,建立前缀和数组,区间加时整块加 $\text{tag}$,零散的部分加上之后重构整个块的前缀和数组。

区间第 $k$ 大,直接二分答案即可。

但是考虑到维护前缀和数组,其复杂度可能高达 $\mathcal{O}(n\times \text{len})$,这明显是无法接受的。然而单块维护可以变为 $\mathcal{O}(\max-\min)$,所以我们希望一块的 $\max-\min$ 在可控范围。

那么按照两个限制分块:

  • 块大小不超过 $\sqrt{n}$。
  • 块元素的 $\max-\min\le \sqrt{n}\times \text{len}$。

可以证明这样分块,总块数是 $\mathcal{O}(\sqrt{n})$。

同时,由于每次加法可能会破坏这个性质,所以我们需要定期重构序列,证明可得大概在 $\mathcal{O}(\sqrt{m})$ 次修改后进行一次重构。

时间复杂度 $\mathcal{O}((n+m)\sqrt{n}(\log n+\text{len}))$。


2021.02.20

$\texttt{Location:HNOI2021}$

得分:$\texttt{210/300,Rank1}$。

[02.20]-错误

$\text{T2}$ 细节处理得不好导致挂分。

[02.20]-部分正解

$\texttt{T1}$

如果不强制在线,直接先建树,然后再模拟直径合并就可以了。

强制在线,上 $\text{LCT}$ 即可。

$\texttt{T2}$

$01$ 背包问题是 $\text{NPC}$ 的,所以考虑从特殊的角度出手:$C\le 300$。

因此考虑按照售价分类,然后每一类都先从大到小排序,显然只会选前缀,那就前缀和。

按照售价来分类转移,发现对于一个 $c$,相当于在模 $c$ 意义下进行转移。接着发现这个东西具有决策单调性,所以直接套就可以了。

$\texttt{T3}$

把 $A,C$ 均看做 $n$ 个列向量,那么向量 $C_j$ 是由若干 $A_i$ 异或而来的,这个恰好可以用 $B_{i,j}$ 的值来表示。那么一定有:$C$ 的每个向量必然可以被 $A$ 的向量所组成的线性空间张出。

首先有结论:

对于秩一定的矩阵 $C$,其答案相同。

两个 $01$ 向量取交对于异或具有交换律,因此当对 $A$ 做线性变换的时候,$C$ 也在相应做线性变换。显然线性变换不改变秩大小,$A,C$ 可以看做具有对应关系。

那么考虑将所有秩为 $|C|$ 的矩阵的答案加起来,最后除以秩为 $|C|$ 的矩阵个数即可。

设计 $\text{dp}_{i,j}$ 表示,前 $n\times i$ 的矩阵中,秩为 $j$ 的方案数。那么可以得到:

$$ \text{dp}_{i,j}=\text{dp}_{i-1,j}\times 2^{j}+\text{dp}_{i-1,j-1}\times(2^n-2^{j-1}) $$

也就是考虑这一个新的向量是否使秩增大,由于是异或矩阵,所以只需要考虑之前的 $j$ 个矩阵是否加入。

那么对于一个秩为 $x(x\ge |C|)$ 的矩阵 $A$,考虑计算其贡献。

首先,一个秩为 $x$ 的矩阵 $A$,考虑有多少秩为 $|C|$ 的矩阵 $C$,使得其每一个列向量都可以用 $A$ 线性变换来得到。考虑直接用一个 $x$ 维向量表示,那么这个 $n\times x$ 的矩阵的秩要是 $|C|$,根据行秩等于列秩可得,这恰好是 $\text{dp}_{x,|C|}$ 的值。

再考虑在这个情况下,有多少 $B$ 合法。可以得到是 $2^{n(n-x)}$ 个。因为对于一个固定的 $A$ 与 $C$,有不同的 $B$ 均是合法的。对于 $C$ 中一列,他是 $A$ 中某些列的线性组合,而 $A$ 中有 $n-x$ 个自由元,所以 $B$ 的一行有 $2^{n-x}$ 中表达方法。又需确定 $n$ 行,所以系数是 $2^{n(n-x)}$。

所以答案是:

$$ \dfrac{1}{\text{dp}_{n,|C|}}\sum_{i=|C|}^n \text{dp}_{n,i}\times \text{dp}_{i,|C|}\times 2^{n(n-i)} $$

在求 $C$ 的秩的时候,需要 $\text{bitset}$。

时间复杂度为 $\mathcal{O}(n^2+\dfrac{n^3}{\omega})$。


2021.02.22

$\texttt{Location:HNOI2021}$

得分:$\texttt{250/300,Rank1}$。

[02.22]-错误

$\texttt{T1}$ 花费过长时间......

[02.22]-部分正解

$\texttt{T1}$

首先,一定先要围出凸包。在凸包内部,三角剖分一定最优。

考虑设三角形个数为 $F$,凸包上点个数=边个数=$k$,恰好是有界面的个数,那么一个三角形贡献 $3$ 条边,除了凸包上的边以外,所有边两侧有两个三角形。因此可以得到柿子:

$$ 2E=3F+k $$

又根据欧拉定理,有:$V+F-E=1$(注意这里 $F$ 是有界的面)。考虑到 $F$ 不是很好求,所以可以考虑通过两个柿子消去 $F$。

最后可以得到柿子:

$$ E=3V-k-3 $$

需要注意的是,这只在有点出现的时候成立。$V$ 期望很好算,主要求 $k$。

根据期望的线性性,考虑计算每一条边出现的期望。只需要枚举一个端点,以其为原点将其他点极角排序,再双指针就可以了。时间复杂度 $\mathcal{O}(n^2\log n)$。

$\texttt{T2}$

无向图四元环计数。

考虑三元环计数的方法:给每一条边定向——从度数小的往度数大的定向,度数相同则标号小指向标号大。直接暴力枚举一个点 $u$,枚举其所有新图出边到 $v$,再枚举 $v$ 在新图中的所有出边到 $w$。由于新图显然是 $\text{DAG}$,所以第三边的指向是一定的,直接判定即可。

考虑证明其复杂度,首先枚举一条边是 $\mathcal{O}(m)$ 的,接着枚举 $v$ 的出边时,可以根号分治地来看:若 $v$ 度数 $\le \sqrt{m}$,那么最多枚举 $\mathcal{O}(\sqrt{m})$ 个出点;若 $v$ 度数 $>\sqrt{m}$,由于只会连向度数更大的点,这样的点显然最多 $\mathcal{O}(\sqrt{m})$。因此复杂度是 $\mathcal{O}(m\sqrt{m})$。

考虑四元环。也先用上面的方法定向,接着观察四元环的所有可能形态,发现一定有一个点,满足两条边均连向他。可以先枚举一条原图中的边 $u-v$,再在新图中枚举 $v-w$,在 $w$ 上加一个计数器统计一下即可。随便证下就知道和上面三元环一个复杂度。

$\texttt{T3}$

考虑分块,定期重构。

首先,对于 $2$ 操作进行分块,令 $\text{v2}_{i,j}$ 表示第 $i$ 个块中所有 $2$ 操作对 $j$ 的影响的最小值。同时对 $1$ 操作进行分块,令 $\text{v1}_{i,j}$ 表示第 $1-i$ 个块中,最近的可以影响到 $j$ 的操作。这两个操作要建立反向边,朝着反向边的方向更新上去。

那么一次询问的答案,一定是上一个距离他最近的影响他的 $1$ 操作,与该 $1$ 操作和询问之间的所有影响他的 $2$ 操作的 $\min$。由于我们进行了分块,所以这个东西可以在 $\mathcal{O}(\sqrt{q})$ 的时间内完成。

但是在处理边角料的时候,我们需要判断一个操作是否可以到达特定的节点。如果直接用 $\text{bitset}$ 维护连通性,则空间是 $\mathcal{O}(\dfrac{n^2}{\omega})$ 的,开不下。

因此,再考虑对节点分块,块大小 $\sqrt{n}$。每次,只维护每一个节点,到这个块内所有节点的连通性,同时也只求这个块内的点的询问的答案,然后每 $\sqrt{n}$ 个点重构。这样空间就压到 $\mathcal{O}(n^{\frac{3}{2}})$,可以通过。

时间复杂度 $\mathcal{O}(q^{\frac{3}{2}}+\sqrt{n}(q+n))$。

[02.22]-总结

$\texttt{T1}$

本题第一步中的三角剖分应该是易于想到的,围出凸包也是可以想到的。关键点在于对于欧拉定理的运用——将欧拉定理与本题中的凸包模型相结合以得到更为简单的柿子。

对于平面上关于面、边、点个数的题目,可以朝着欧拉定理进行思考。特殊地,对于网格图,也是可以使用欧拉定理解决部分相关问题的。本题中,关键要想到列出关于凸包大小、边、面个数的等式,再消去对于面的计算。

也就是说,对于此类欧拉定理计数问题,若存在某一个数字特别不好计算,同时可以列出类似的其他等式,可以考虑使用数学方法消去这样不好算的数字。

$\text{key observation:}$ 关于凸包的等式与欧拉定理的结合。

$\texttt{T2}$

无向图四元环计数问题。

本题是板子,但是十分巧妙。复杂度的保证基于对无向图的合理定向,从而使得点的度数得到限制。也就是说,将无向图转变为度数从小到大连边的有向图,在度数上存在十分好的性质,需要牢记。

同时,三元环与四元环的复杂度一致,其本质在于在定向后的有向图中,枚举一条长度为 $2$ 的链的复杂度上限从 $\mathcal{O}(m^2)$ 降低为 $\mathcal{O}(m\sqrt{m})$。

也就是说,如果环大小增加,变成五元环及以上,则或许无法使用这样的方法进行计算——因为他们都需要枚举长度更长的链。但或许枚举长度为 $k$ 的链可以认为是 $\mathcal{O}(m^{\frac{k+1}{2}})$ 的复杂度?实际上应该跑不满,因为很难构造很多长度为 $k$ 的链使得链上每个点的定向后度数都为 $\mathcal{O}(\sqrt{m})$ 级别。

同时,本做法基于无向图可随意定向的性质,随意定向还在混合图欧拉回路中有出现,但混合图欧拉回路中定向的意义在于建立网络流模型,做到入度、出度平衡。而本题定向的意义在于限制度数。也就是说,定向在控制与度数相关的内容上或许是不错的选择。

那么如果是有向图四元环计数,并且要求一定是一个环,而不是只是四条边连接,则无法使用该方法。如果只是四条边连接,则与无向图无异。

$\text{key observation:}$ 无向图的定向、复杂度分析。

$\texttt{T3}$

分块+分块+分块

首先,由于不是序列上或树上问题,所以常规的 $\text{polylog}$ 数据结构是难以维护的。若考虑相关 $\text{DAG}$ 的链剖分应该在大多数题上没什么前途......但如果是链与反链的话就要斟酌一下。

因此,对于这类很数据结构的题,却无法用常规的 $\text{polylog}$ 数据结构进行维护,则考虑分块/莫队。莫队的优势在于其擅长于解决“相似状态相互转化的复杂度极低”的问题,而相对来说分块的运用更为广泛。

那么对于操作 $1,2$ 的分块维护就是很 $\text{trivial}$ 的了。

下一个关键点在于对于 $\text{bitset}$ 空间的压缩,也就是再对于点进行一次分块。需要切记的是,分块不仅可以用来优化时间复杂度、相应劣化空间复杂度,他同样可以优化空间复杂度、相应劣化时间复杂度。本题中每 $\sqrt{n}$ 次就需要重构就是劣化了时间,却压下了空间。

分块的运用十分广泛,最常见的是对:序列、节点、树、甚至时间的分块,如果没有 $\text{polylog}$ 做法,分块或许是另一种选择。

$\text{key observation:}$ 分块、对于 $\text{bitset}$ 的空间优化。


2021.02.24

$\texttt{Location:HNOI2021}$

得分:$\texttt{190/300,Rank1}$。

[02.24]-错误

$\texttt{T3}$ 为什么挂分了???

[02.24]-部分正解

$\texttt{T1}$

考虑圆反演

由于答案圆一定过原点,所以提示我们以原点为反演中心反演一下。

接着就变成了这个问题:

给定若干圆,求一条直线使其经过尽量多的圆。

根据调整法,我们总可以将直线移动到某两个圆的公切线而答案不变,从而减少枚举量。因此可以考虑枚举公切线,再进行判定,复杂度 $\mathcal{O}(n^3)$。

发现如果只是枚举公切线,复杂度不会更优了。所以考虑先枚举一个圆,把其他圆与其公切线全拿出来,排序。然后使用指针扫过去,只要经过一个切线就让答案 $+1$ 或 $-1$,这样就可以做到 $\mathcal{O}(n^2)$。

$\texttt{T2}$

暴力就可以跑过去

考虑斐波那契通项公式:

$$ \text{fib}_n=\dfrac{\Big(\dfrac{\sqrt{5}+1}{2}\Big)^n-\Big(\dfrac{\sqrt{5}-1}{2}\Big)^n}{\sqrt{5}} $$

首先可以知道 $5$ 在 $\bmod(10^9+9)$ 意义下是有二次剩余的。所以设:

$$ a=\dfrac{\sqrt{5}+1}{2},b=\dfrac{\sqrt{5}-1}{2} $$

那么有:

$$ a^n-b^n\equiv \sqrt{5}k\pmod{10^9+9} $$

这仍然不好做,但是观察到 $ab=-1$,因此写成:

$$ a^n-(-1)^n a^{-n}\equiv \sqrt{5}k\pmod {10^9+9} $$

再推一推变成:

$$ a^{2n}-\sqrt{5}ka^n-(-1)^n a^{-n}\equiv 0\pmod {10^9+9} $$

这是二次方程,求根公式可得:

$$ a^n\equiv \pm\sqrt{(-1)^n+\dfrac{5k^2}{4}}+\dfrac{\sqrt{5}k}{2}\pmod {10^9+9} $$

然后考虑 $\text{BSGS}$ 。但是由于右边 $n$ 不确定,所以需要分类讨论一下。考虑到 $(-1)^n$ 只有两种取值,所以只要按照 $n$ 的奇偶性分分类即可。

时间复杂度 $\mathcal{O}(\sqrt{10^9+9})$。

$\texttt{T3}$

竟然自己的一个小脑洞用上了?

随便用脚化化柿子可以得到答案是:

$$ \sum_{d|n}\binom{d}{m}\varphi\Big(\dfrac{n}{d}\Big) $$

把组合数拆掉,$\dfrac{1}{m!}$ 挪出来,变成:

$$ \dfrac{1}{m!}\sum_{d|n} d^{\underline{m}} \varphi\Big(\dfrac{n}{d}\Big) $$

发现下降幂指数固定为 $m$,考虑使用第一类斯特林数转为普通幂:

$$ \dfrac{1}{m!}\sum_{d|n} \sum_{i=0}^m \begin{bmatrix} m \\ i \end{bmatrix} (-1)^{m-i} d^i \varphi\Big(\dfrac{n}{d}\Big) $$

交换和式:

$$ \dfrac{1}{m!}\sum_{i=0}^m \begin{bmatrix} m \\ i \end{bmatrix} (-1)^{m-i} \sum_{d|n} d^i \varphi\Big(\dfrac{n}{d}\Big) $$

观察发现后面是狄利克雷卷积的形式。同时两个函数都是积性函数,所以其狄利克雷卷积也是积性函数,在 $i$ 一定时,令其为 $f_i(x)$,那么只需要求出所有素数的 $k$ 次幂位置的值即可把柿子变成:

$$ \dfrac{1}{m!}\sum_{i=0}^m \begin{bmatrix} m \\ i \end{bmatrix} (-1)^{m-i} \prod_{p^k} f_i(p^k) $$

考虑求 $f_i(p^k)$,有:

$$ f_i(p^k)=\sum_{j=0}^k p^{ij}\varphi(p^{k-j}) $$

又 $\varphi(p^k)=(p-1)p^{k-1}$

所以:

$$ f_i(p^k)=p^{ik}+(p-1)\sum_{j=0}^{k-1} p^{ij+k-j-1} $$

至于质因数分解,上 $\text{Pollard-Rho}$ 即可。时间复杂度 $\mathcal{O}(\sqrt[4]{n}+m^2+m\log^2 n)$。

[02.24]-总结

$\texttt{T1}$

跟随部分分提示,从直线的情形开始思考。

接着考虑如何使得圆的情形变得简单。如果要转变为类似部分分的做法,那么圆反演是可行的。

因此,本题的目标是通过变换,使正解向类似部分分的做法靠拢。同时,对于计算几何问题,尤其需要注意交点、切线等特殊图形,因为在计算几何中,枚举量实际上是无穷的,因此通过特殊图形的性质,减少枚举量或许是做“与枚举相关的计算几何题”的必经之路?

$\text{key observation:}$ 圆反演,最优直线一定是一条公切线。

$\texttt{T2}$

对于斐波那契数列,有以下思考方向:

1.矩阵快速幂优化递推
2.斐波那契循环节(纯循环、循环节最长 $\mathcal{O}(6\text{mod})$)
3.斐波那契数列与其他数列的关系(例如与组合数的关系)
4.斐波那契通项公式

等......

本题与斐波那契的下标有关,若与上述 $1$ 相关,则需要类似二分等操作,但不具单调性;若与 $3$ 相关,则或许会将问题转变为求另一个数列的某一个下标,这也不太好考虑。

与 $2$ 相关,则跑出循环节是最 $\text{naive}$ 的做法。事实证明这样已经足够通过了。若希望优化,可以根据纯循环的性质来减少枚举量。

与 $4$ 相关,看起来是更为有前途的方向,因为通项公式恰好是将下标与值连接的一种方法。那么便可以考虑列方程求解。

本题与 $\text{WC2021}$ 斐波那契一题的区别,较为关键的一点在于模数的大小。由于本题模数过大,所以在很多情况下,考虑循环节确实没有前途(。

$\text{key observation:}$ 考虑到下标与值可以通过通项公式连接。

$\texttt{T3}$

本题最开始的推柿子是十分套路的。

对后面的柿子:

$$ \sum_{d|n}\binom{d}{m}\varphi\Big(\dfrac{n}{d}\Big) $$

这是一个非积性函数与积性函数的狄利克雷卷积,这种情况下是没有什么优秀的性质的。

考虑到本题由于存在 $\gcd$,所以或许与整除密不可分。因此狄利克雷卷积似乎是无法避免的。那么就往狄利克雷卷积的方向思考,也就是朝将非积性函数变为积性函数的方向去。

那么拆掉组合数是不可少的了。写成下降幂之后,需要对下降幂进行一定的观察,发现指数一定且并不是很大,这指引我们将其转变为一个积性函数:某一个数字的 $m$ 次幂。从这个方向构造积性函数,可能是想到斯特林数的好角度。

接着写出积性函数之后,对于其快速求值,则直接引导我们使用 $\text{Pollard-Rho}$ 将其分解为互质的部分,剩下的就很 $\text{trivial}$ 了。

因此:

  • 对于无法避免的狄利克雷卷积,应尽量考虑构造出积性函数使得狄利克雷卷积的结果仍然是积性函数。
  • 对于积性函数的求值,有时可以先考虑经典的狄利克雷卷积结果;若不是很经典、常见,那么应自然想到分解为互质的部分。这就直接到了 $\text{Pollard-Rho}$。
  • 组合数=阶乘逆元 $\times$ 下降幂!下降幂有利于解决裂项、转变为组合数的问题,或者直接可以通过预处理阶乘做到很优秀的复杂度;而普通幂擅长解决积性函数卷积等问题。具体题目具体分析。

2021.02.25

$\texttt{Location:HNOI2021}$

得分:$\texttt{160/300,Rank1}$。

[02.25]-错误

$\texttt{T1}$ 写挂了,但是考场没有去检查!
$\texttt{T3}$ 的决策单调性复杂度写假了......导致挂了 $\text{40pts}$,同时主席树开小了数组。

[02.25]-部分正解

$\texttt{T1}$

考虑网络流。

普通的网络流无法满足我们的要求,主要原因是流量无法平衡......那么可以考虑另外的网络流模型。

考虑最大费用循环流的模型。具体来说,对于树边 $(x,y)$,其中 $x$ 深度较浅。连接 $(x,y)$,费用为 $0$,流量为 $d$。对于匹配 $(x,y)$ 其中 $x$ 深度较浅,连接 $(y,x)$,费用为 $c$,流量为 $1$。

不难发现,最优解一定是一种网络流,使得流在边上循环进行。那么满流的匹配便是被选择的。

解决这个问题,可以首先令所有费用为正的边满流,将费用加入答案 $\text{Ans}$,然后利用普通网络流模型模拟退流操作,来保证流量的平衡。令 $\text{deg}_i$ 表示在所有正费用的边满流的情形下,$i$ 点的入度-出度的值。

  • 若 $\text{deg}_i>0$,说明 $i$ 点流入更多却没有足够流出,那么与 $T$ 相连,流量为 $\text{deg}_i$,费用为 $0$。
  • 若 $\text{deg}_i<0$,说明 $i$ 点流出更多却没有足够流入,那么与 $S$ 相连,流量为 $-\text{deg}_i$,费用为 $0$。

由于我们希望退流的费用尽量小,所以最后对以上普通网络流做一遍最小费用最大流,答案是 $\text{Ans}-\text{mincost}$。

$\texttt{T2}$

首先有结论:

随机抽取,若抽取到之前抽到过的物品便重新抽,令 $P1_{i,j}$ 表示 $j$ 是第 $i$ 个被抽到的物品的概率;随机抽取,抽取到一个物品便将其删除,同时将其他的物品概率等比例放大,令 $P2_{i,j}$ 表示 $j$ 是第 $i$ 个被抽到的物品的概率。那么 $P1_{i,j}=P2_{i,j}$。

考虑先求出第一问的期望,令 $P_{i,c},E_{i,c}$ 分别为第 $i$ 轮抽到 $c$ 这面的概率、期望和。

首先根据上述结论,若上一轮抽到 $a$,这一轮抽到 $b$ 的概率是:

$$\dfrac{p_b}{1-p_a}$$

那么有:

$$ P_{i,c}=\sum_{a\ne c} P_{i-1,a}\times \dfrac{p_c}{1-p_a} $$

$$ E_{i,c}=P_{i,c}\times c + \sum_{a\ne c} E_{i-1,a}\times \dfrac{p_c}{1-p_a} $$

最终第一问答案为:

$$ \sum_{i=1}^6 E_{n,i} $$

再考虑求方差的期望,有:

$$ V=E(\text{Ans}^2)-2E(\text{Ans})\times \text E(\text{Ans})+E(\text{Ans})^2 $$

又 $\text{Ans}$ 的期望就是 $E(\text{Ans})$,因此:

$$ V=E(\text{Ans}^2)-E(\text{Ans})^2 $$

这就是十分经典的问题了,首先可以令每个点的权值减去 $\text{tag}=\dfrac{\sum_{i=1}^6 E_{n,i}}{n}$,令 $E2_{i,c}$ 表示第 $i$ 轮抽到 $c$ 时,答案的和的平方的期望值。

考虑到 $(a+b)^2=a^2+2ab+b^2$,所以有:

$$ E2_{i,c}=P_{i,c}\times (c-\text{tag})^2+2E_{i,c}(c-\text{tag})+\sum_{a\ne c} E2_{i-1,a}\times \dfrac{p_c}{1-p_a} $$

注意由于修改了每个面的权值,因此其中的 $P$,$E$ 也需要重新算。

最后答案为:

$$ \sum_{i=1}^6 E2_{n,i} $$

时间复杂度 $\mathcal{O}(36n)$。

$\texttt{T3}$

首先,对于一对鞋子 $(a,b)$,鞋柜放在 $\dfrac{a+b}{2}$ 一定是最优的。现在考虑将鞋子对进行排序,从而使得存在一种最优方案,使得共用同一个鞋柜的鞋子对是一个区间。

那么设 $\text{dp}_{k,i}$ 表示考虑前 $i$ 对鞋子,用了 $k$ 个鞋柜的最优答案,那么:

$$ \text{dp}_{k,i}=\min_{j<i} \text{dp}_{k-1,j}+w(j+1,i) $$

这个 $w(l,r)$ 表示,把 $[l,r]$ 中的鞋子对放进同一个鞋柜,其最小距离和。这是具有决策单调性的,考虑按照 $k$ 分层,然后直接套决策单调性分治即可。

考虑求 $w(l,r)$,由于放进同一个鞋柜,所以鞋子和谁配对不重要了,重要的只有距离。这就有结论——放在最中间的点的位置最优。

那么开一棵主席树,然后拿出 $[l,r]$ 这段区间,二分找到中点,然后左边右边分别求一下点的下标和,减一下即可。

时间复杂度 $\mathcal{O}(nk\log^2n)$。

[02.25]-总结

$\texttt{T1}$

本题是区间覆盖问题的树上版本。

由于链直上直下的性质,所以应该自然地想到划分为链的情况。在链上,即区间情况,是经典的网络流模型。

$\text{key observation:}$ 考虑序列的简化问题,再拓展到树。

$\texttt{T2}$

简单的套路题,关键在于区分“平方的和的期望”,和“和的平方的期望”。

$\texttt{T3}$

本题首先利用排序,将不确定的选择变成相对确定的区间。观察到该性质并不容易。

因此对于此类看起来较为“$\text{dp}$”的题目,在无法得到优秀的转移复杂度时,可以考虑对枚举项的顺序进行改变,从而使其满足若干性质。这与[USACO20DEC] Sleeping Cows P中类似,但是两者不同在,本题关键在于通过排序使得最优转移项从“零散的”变为“一个区间”,而后者关键在于通过排序消除 $\text{dp}$ 状态中无法考虑到的限制。

$\text{key observation:}$ 将区间排序从而大幅度降低了转移的复杂度。


2021.02.27

$\texttt{Location:HNOI2021}$

得分:$\texttt{200/300,Rank2}$。

[02.27]-错误

$\texttt{T2}$ 想法假了但是没有及时意识到,直到写了 $\text{7k}$ 后才发现......因此以后想到做法尽可能先手玩几种情况而不是仅仅口胡。
$\texttt{T3}$ 实际上是可以拿到更高的分数的,但是没有走到正确的优化方向。

[02.27]-部分正解

$\texttt{T1}$

大力 $\text{bitset}$ 可以做 $\mathcal{O}(\dfrac{Tn^2}{\omega})$,应该随便写。

$\texttt{T2}$

将序列差分,那么一个等差数列变成一段连续的相同的数字,一次修改变成两边单点加与中间的区间加。

考虑分块。首先可以求出每个块中的最优解,那么就只需要处理跨过块的情况,尝试是否能够让两个属于不同块的相邻区间拼起来。

首先,若存在一种块内的最优方案使得最后留下一个零散的点,那么他一定是很优的。因为这样我们可以认为他有更大的概率与后面的块拼接。接着就只需要考虑这个零散点是否可以接到后面,那么只需记录“第二个块中的最优答案”与“第二个块中去除第一个点后的最优答案”。

若零散点直接可以拼,那就直接拼;否则,若“第二个块中的最优答案”与“第二个块中去除第一个点后的最优答案”相等,那么说明存在一种最优方案使得第一个点是孤立的,若是如此,那么上个块的零散点与下个块的零散点可以组成一个等差数列,这样就可以使答案 $-1$。

细节很多,时间复杂度 $\mathcal{O}(n\sqrt{n})$。

貌似使用线段树大力分类讨论就可以直接 $\mathcal{O}(n\log n)$ 了。

$\texttt{T3}$

首先令 $d_i=a_{i+1}-a_i$,那么现在需要做的是把 $d$ 做分裂,使得最后 $\sum (d_i-L)^2$ 最小。

显然地,若给 $d_i$ 分配 $k$ 次分裂,那么一定全部平均分裂。令 $\text{delta}(i,k)$ 为给 $d_i$ 从分配 $k$ 次分裂变为分配 $k+1$ 次的贡献变化量。那么就可以直接拿堆贪心了。时间复杂度是 $\mathcal{O}(m\log n)$。

但是 $m$ 极大,所以考虑如何使得 $m$ 减小从而使用上述算法。

要减小 $m$,就要预先分配一些分裂的次数给每一个 $d$。经过大力推导,$d_i$ 的最优解 $k_i$ 大概在 $\dfrac{m|s_i|}{\sum_j |s_j|}$ 的位置,最优解下界为 $\left\lfloor\dfrac{m|s_i|}{\sum_j |s_j|}\right\rfloor-1$。

那么就先给每个点分配这样的值,剩下的分裂次数计算可知在 $\mathcal{O}(n)$ 级别,于是就可以重复上述做法了。时间复杂度 $\mathcal{O}(n\log n)$。

[02.27]-总结

本套题几乎都是基于等差数列的题,可以给出一些小总结:

  • 等差数列一般可以考虑差分形式,那么较为困难的区间加等差数列、判断等差数列就变为较为简单的区间加+单点加、判断相等段。
  • 等差数列有一种类似对称(?)的既视感,在统计等差数列的时候是否可以考虑从最中间入手?

然后就憋不出来了

$\texttt{T1}$

本题貌似有复杂度更为正常但是十分困难的做法,但是两种做法均基于排列的性质与长度为 $3$ 的等差数列的性质。值域小使得 $\text{bitset}$ 复杂度正确。由于长度为 $3$ 的等差数列若从中间枚举,那么左右恰好只有一个元素,这使得枚举变得相对容易,同时这种从中间枚举的思路值得借鉴。

是否可以将 $3$ 变为 $4,5...?$ 貌似很难通过类似的思路进行考虑,因为 $3$ 恰好中间元素左右恰好只有一个元素,从 $4$ 开始就无法满足这样的情况。同时由于是子序列而不是子区间,所以使得差分变得不可行。目前的思路没有用到排列的性质,也就是可以存在重复元素,但是复杂度中带有值域。大概思路是暴力枚举公差,然后做若干次判断,使用树状数组维护类似前缀和的操作,从而看某一个元素是否可以成为一个等差数列的第 $i$ 项。

$\texttt{T2}$

本题很好地运用了关于等差数列差分的优异性质。本题的关键点在于对等差数列的判断以及连接,他们在转化之后均有更为方便的做法,同时需要清楚:由于等差数列的最小划分实际上方案不唯一,所以在查询区间的时候,其划分方案或许会存在较大的差异,这是考场上做法错误的原因。

其关键在于对于分块后等差数列划分的零散块的处理,最优化方案的选择,这依靠贪心的策略,让零散块尽量出现使得后面的合并变得更为灵活与方便。这都需要在口胡的时候进行充分的考虑,或者应积极从对拍中找寻问题,从而找到解决各种情形的方法。

$\text{key observation:}$ 差分,对于零散点的处理。

$\texttt{T3}$

贪心是 $\text{trivial}$ 的,而关键点在于对于操作的预先分配。

本题同样从部分分来,回归部分分去。即应先考虑简单的部分分,接着考虑如何拓展到正解,或如何使得正解转变为几乎一致的问题上。在这个方面的思考不够深入,导致一直在考虑利用要求精度很低的性质。

从 $m\le 10^6$ 到 $m\le 10^{18}$ 基于对最优解分布的精确分析,即有时一些题目可以通过非数学方法得到较为优秀的解法,但是最后仍然需要通过数学推导来得到更为简明的柿子,从而进一步降低复杂度。

$\text{key observation:}$ 平均分配的最优性与最优解的下界,观察到其柿子对 $m$ 的减小作用。

标签: none

添加新评论