2021.03.07

$\texttt{Location:HNOI2021}$

得分:$\texttt{50/300,Rank3}$。

[03.07]-错误

开题顺序有问题,导致最为简单的 $\texttt{T1}$ 没有做出来且只有最暴力的分数。
$\texttt{T3}$ 数据范围看得不仔细,导致暴力分都没拿到。

[03.07]-部分正解

$\texttt{T1}$

这个问题可以转变为一个更为容易理解的问题:

现有总长 $n$ 的序列 $\{a_n\}$,被划分成 $m$ 段。每段有一个参数 $h_i$,还有参数 $X,A$。
现在需要你选取若干位置。一个选取方案合法,当且仅当对于序列的每一个前缀,都有 $A-c\times X+s\ge 0$,其中 $c$ 是前缀中没有被选择的数字个数,$s$ 是前缀中被选择的位置的权值 $a$ 的和。
一种选取方案中,若第 $i$ 段没有被选择的数字 $\ge h_i$,那么这一段是有效的。求一种合法选取方案,使得有效段尽量多,并输出方案。

我们在后面称 $A-c\times X+s$ 为一个前缀的权值。

转化为这样就变得简单很多了,可以考虑 $\text{dp}$,设 $\text{dp}_{i,j}$ 为前 $i$ 段中,前缀的权值为 $j$ 的时候,有效段数的 $\max$。

但是这样设置,第二维值域很大。观察到 $m\le 50$,所以考虑 交换第二维与存储值,也就是将状态设定为:$\text{dp}_{i,j}$ 表示前 $i$ 段中,有效段数为 $j$ 时,当前前缀的最大权值。

由于在 $i,j$ 一定的情况下,我们并不在意前面的段里的具体情况,而前缀权值越大,则后面就越为自由。

然后就只要分:是否要让当前段有效,进行分类即可。

如果希望当前段无效,那么显然所有数字全部选上是可以让前缀权值最大的:

$$\text{dp}_{i,j}=\text{dp}_{i-1,j}+\text{sum}_i$$

其中 $\text{sum}_i$ 是第 $i$ 段的所有数字的权值和。

如果希望当前段有效,只需要在段内贪心即可。也就是你能够选择 $\text{len}-h_i$ 个数。能不选就不选,不能不选了就在前面找一个最大的 $a$ 选上。最后如果有多余的次数,再贪心地选择最大的 $a$ 即可。

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

$\texttt{T2}$

观察柿子:

$$ A_n=xA_{n-1}-yB_{n-1} $$

$$ B_n=xB_{n-1}+yA_{n-1} $$

观察后容易发现 这两个函数貌似和 $\sin,\cos$ 有些相似的地方,除以一个 $\sqrt{x^2+y^2}$ 类似辅助角公式。

那么题解告诉我们,容易观察到:$(x+yi)^n=a_n+ib_n$,因此 $(x+y_i)^{2n}=a_n^2-b_n^2+2a_n b_ni$。

令 $\mathcal{I}(z)$ 表示取复数 $z$ 的虚部的话,原柿子可以变成:

$$ \sum \dfrac{a_nb_n}{C^n} $$

$$ = \dfrac{1}{2}\sum \dfrac{\mathcal{I}((x+yi)^{2n})}{C^n} $$

$$ = \mathcal{I}\Big(\dfrac{1}{2}\sum \dfrac{(x+yi)^{2n}}{C^n}\Big) $$

可以等比数列求和。至于在 $+\infty$ 的时候,判断是否收敛的话,在判断完答案为 $0$ 的情况之后,虚部收敛等价于级数收敛,那么就只需要 $\dfrac{(x+yi)^2}{C}$ 的模长 $<1$ 即收敛。

$\texttt{T3}$

考虑分块。

看到计数满足 $a_x+a_z=a_y$ 的三元组 $(x,y,z)$,其中 $x$ 是 $y$ 的祖先,$y$ 是 $z$ 的祖先,那么对于等式 $a_x+a_z=a_y$,可以想到使用卷积的方法进行计数。

考虑在序列上的情形,首先暴力枚举一个块,维护该块前面、后面的块的权值的桶,分类讨论。

若三个点都在块内,可以枚举一个节点,对块内其前面的节点建立桶,然后枚举块内后面的节点,在桶中查询个数。

若有两个点在块内,暴力枚举这两个点,然后在该块前面/后面的桶中查询。

若只有一个点在块内,那么把两边的桶进行 $\text{FFT}$ 即可。

再拓展到树,那么先对树进行分块,保证每块都是一个完整的联通块。

对于有三个点、两个点在块内的情况,可以同样照上面的方法暴力地做。至于只有一个点在块内的情况,可以先把每个子树块都和祖先链的桶卷积一次,然后对于当前块内的每个节点 $x$,取出那些以 $x$ 为祖先的子树块 与祖先链的卷积结果即可。

令分了 $k$ 块,块大小为 $L$,那么时间复杂度是 $\mathcal{O}(\dfrac{n^2}{k}+km\log m)$。

[03.07]-总结

$\texttt{T1}$

这道题没有做出来是十分可惜的,主要是因为柿子比较长,加上对题目难度的评估出现了差错。

本题一开始给了一个十分晦涩难懂的柿子,很长很恶心。但是通过足够的观察,可以对该柿子建立一个相应的组合意义的问题。

例如观察到 $b_i<b_{i+1}$,应该想到按照 $b$ 对 $a$ 划分区间。接下来的就是简单的贪心。

这类题目出现的并不算很多,很多情况是代数推导和组合意义均可行。但是本题中明显转化为组合意义之后变得简单了很多。

同时,本题中还有一个十分有效的 $\text{trick}$:交换 $\text{dp}$ 数组的一维与储存值。当 $\text{dp}$ 某一维值域极大,但是存储值十分小,同时有合理的意义解释交换后的 $\text{dp}$ 的话,交换往往是一种很好的优化时空的方法,需牢记。

$\text{key observation:}$ 代数直观和组合意义之间的转化。

$\texttt{T2}$

本题的关键在于对柿子的足够观察,看到其与 $\sin$ 与 $\cos$ 之间相似的关系。这一点十分困难。

观察到分母中的 $C^k$,因此考虑将分子部分也转变为某数的幂。其核心在于将不是很容易求解的递推公式转变为通项公式,从而利用等比数列的方式简化运算。因此,对于整数域上的数列,其通项公式可能拓展到实数域、复数域,应该拓宽自己的思维。

同时,本题在判断收敛的角度上也值得思考。只有在通过等比数列的转化之后,才可以更为简单地判断级数是否收敛。

$\text{key observation:}$ 对于递推公式与通项公式的转化、级数收敛的判断。

$\texttt{T3}$

本题在做题思路方向上是十分套路的:先考虑对于序列的问题,再拓展到树上。

本题很容易可以想到之前考的一道关于等差数列的题,而思考发现本题的序列版本严格不弱于前者,而又由于本题的信息并不传统,因此应该要朝着分块的方向去思考。

若想到了进行分块,那么对于块内关键点个数的分类便是 $\text{trivial}$ 的。三个点、两个点在块内的情况容易想到,但是一个点在块内的话,必须联想到等式 $a_x+a_z=a_y$ 隐含的信息——卷积。也就是说,当对于权值求和=另一权值的计数问题,多项式往往可以更好地解决。同时,分块中有很多暴力的想法、做法实际上都有正确的复杂度,因此应大胆想、大胆写,积极调块长。

$\text{key observation:}$ 序列到树的拓展,分块,$a_x+a_z=a_y$ 与卷积的转化。


2021.03.13

$\texttt{Location:HNOI2021}$

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

[03.13]-错误

$\texttt{T1}$ 竟然是搜索,考场上一直在考虑高维前缀和、莫比乌斯反演等。或许应该打个表,观察发现答案增长不快的性质。
$\texttt{T2}$ 明明是可想的题,但是却直接放弃了。不能因为题面很长、时限很长等原因而被吓跑了......

[03.13]-部分正解

$\texttt{T1}$

高维前缀和、莫比乌斯反演都是什么东西,搜索天下第一!

考虑先把数字挂到桶里,然后求出所有满足条件的二元组 $(A,B)$,再进行组合。

对于一个完全平方数 $D$,质因数分解他:

$$D=\prod p_i^{a_i}$$

那么若 $\text{lcm}(A,B)=D$,那么每一个质数的幂,有至少有一个数字顶到 $a_i$。首先可以 $\mathcal{O}(2^{\omega(D)})$ 地暴力把每一个 $p_i^{a_i}$ 分到 $A$ 或 $B$ 中。注意这里需要保证 $A,B\le 10^6$,可以剪去很多枝。

接着再考虑对于每一个 $p_i$,另外一个数字中,其指数是多少。这个再写一个搜索即可,为了保证不算重,我们这样规定:若 $p_i^{a_i}$ 被分配到 $B$ 中,那么 $A$ 中 $p_i$ 的指数可以在 $0$ 到 $a_i$ 枚举;但若 $p_i^{a_i}$ 被分配到 $A$ 中,那 $B$ 中 $p_i$ 的指数只能从 $0$ 到 $a_i-1$ 枚举。

这样就解决了指数相同导致的算重,同样的,需要保证 $A,B\le 10^6$,注意剪枝。

因此,先暴力枚举一个完全平方数,然后质因数分解他,最后再爆搜,即可通过本题。???

时间复杂度玄学,别问这怎么能过,出题人说能过就能过。

$\texttt{T2}$

被 $\text{9s}$ 时限吓到了......

看到奇怪的条件 $P\bmod K=1$,考虑从这个地方出发。发现这等价于 $K|(P-1)$,也就是说在 $\bmod P$ 的意义下,存在 $K$ 次单位根。

具体来说,求出一个原根 $g$,那么 $\omega_{K}=g^{\frac{P-1}{K}}$。

继续从这个角度往下想,求出单位根的意义是什么?当观察到满意指数要对 $K$ 取模,每次查询满意指数是 $[0,K-1]$ 中一个数的方案数。这引导我们思考多项式。

先对每个节点维护一个多项式,那么把所有操作写成多项式的形式:

1.给一个点的多项式乘上 $(1+x^a)$。
2.给一个点的多项式乘上 $(1+x^a+x^b)$。
3.把 $u$ 的多项式乘到所有与 $u$ 相邻的点的多项式上。
4.给 $(u,v)$ 把 $u$ 的多项式乘到删掉 $(u,v)$ 这条边之后,$v$ 所在的子树的所有点的多项式上。
5.给 $(u,v)$,求切断 $(u,v)$ 后,两棵子树分别的所有多项式的循环卷积

$\bmod K$ 的循环卷积,可以 $\mathcal{O}(K^2)$ 求解一次,但是这太慢了。由于是循环卷积,所以指引我们思考类似 $\text{FFT}$ 的方式:直接考虑点值形式,然后每次就只需要点值对应相乘了。

至于求一个多项式的点值,直接带入 $w_K^0$ 到 $w_K^{K-1}$ 即可。而单点修改的多项式也十分简单,系数很少,所以也可以直接带入。

再考虑 $3,4$ 两个操作。显然的,$3$ 操作可以直接使用 $\text{bfn}$ 解决,而 $4$ 可以通过 $\text{dfn}$ 解决。

如果只需要用其中一种编号方式,那么我们就把对应操作需要修改的位置转变为若干区间,这就可以考虑线段树了。具体来说,线段树一个节点上维护 $K$ 个值,表示当前多项式带入 $w_{K}^0$ 到 $w_{K}^{K-1}$ 的点值表示。

那么需要维护区间乘积、区间整体乘。需要注意的是,区间整体乘法的时候,若每个点需要乘 $v$,那么长度为 $l$ 的区间需要乘 $v^l$,但如果直接快速幂,会多一个 $\log$。但由于我们求出了原根,同时模数并不大,所以可以先求每个值的离散对数,然后借助预处理原根的次幂来做到单次 $\mathcal{O}(1)$。

再考虑如果两种操作同时存在要怎么办。我们仍然希望维护区间信息,同时又要保证 $\text{dfn,bfn}$ 和谐共存。

不妨考虑这样的编号方式:对当前点 $x$,先对每一个儿子标号,再递归进入子树内部继续编号。

不难发现,这样编号的话,一个节点 $x$ 的儿子编号连续、$x$ 的子树节点编号连续、但是 $x$ 本身的标号并不一定会与他们连续在一起。

这样就可以同时维护这两种操作了,注意查询的区间被各种区间、单点划分成若干段的情况。

至于 $5$,先可以求出两棵子树的点值多项式。若当前询问 $\text{sat}$ 处的系数,那么只需将 $\omega_K^{-\text{sat}}$ 带入,最后除以 $K$ 即可。

时间复杂度 $\mathcal{O}((n+q)K\log n+P)$,代码长度相当。也就只有 8k 而已

$\texttt{T3}$

提交答案题,主要是乱搞,懒得写了......


[03.13]-总结

$\texttt{T1}$

本题考到了一个几乎想不到的算法:搜索。

如果要想到搜索,首先需要通过打表等方式观察到答案并不大;同时由于 $\text{lcm}$ 的增长较快,所以在 $10^6$ 的值域限制内合法对数较少。

本题提示我们,对于一些看似需要优秀理论复杂度做法的题目,也有可能是搜索剪枝。对于一些增长较快的值,类似 $\text{lcm}$,若其值域被限制,那么应该去思考其真正数量有多少。

同时本题如果只是写一个搜索,是无法通过的,相反,需要写两个搜索,先对顶满的幂进行分配,进行第一轮剪枝;再分配未分配的位置,进行第二轮剪枝。这可以尽量快地剪去不合法的状态,如果只有一个搜索,可能有一种不合法状态在很深的位置才会被剪掉。其本质在于加大搜索树的深度,相应地减小搜索树的宽度,这在某些时候或许也是剪枝的一种方式。

$\text{key observation:}$ 合法二元组的数量级。

$\texttt{T2}$

本题的第一个关键点在于把题目向多项式方向转化。

本题的询问是计数,同时他对 $K$ 取模同样在暗示循环卷积。因此可以考虑转换为多项式的形式。同时 $P\bmod\ K=1$ 这个条件的运用同样十分的关键。他有很多等价的形式,都可以暗示 $K$ 次单位根的存在。只有通过一次 $\text{DFT}$,才可以将不好处理且复杂度高的多项式卷积转变为相对快速且好算的多项式点值相乘。

转化为点值相乘之后,问题变成了维护点值数组。线段树是 $\text{trivial}$ 的,关键在于如何让每一种操作的操作范围能够尽量在数量尽量少的区间内,从而使线段树可以发挥其作用。

操作分别需要调用子树、一级儿子。而这两个可以分别使用 $\text{dfn, bfn}$ 解决。而题解的标号方式巧妙地将两种编号方式结合,使得两种询问都变得快速。

$\texttt{T3}$

随机化赛高!随机化万岁!


2021.03.14

$\texttt{Location:HNOI2021}$

得分:$\texttt{55/300,Rank4}$。

[03.14]-错误

$\texttt{T1}$ 考场上朝着不对的方向推导了很久,导致浪费了时间且只拿到了 $\text{20pts}$。
$\texttt{T2}$ 暴力写得好可以拿满分???但是没有尽量优化暴力。

[03.14]-部分正解

$\texttt{T1}$

考虑从部分分中获取一些提示。

首先观察到必须拆分出一个奇数的条件,那么奇数只能拆分为奇数 $+$ 偶数,偶数只能拆分为奇数 $+$ 奇数。

那么考虑全是奇数的情况,这只与砖块数的奇偶性相关。

证明:

当前砖块数为 $0$,则后手必胜。若 $A$ 选择删除一个砖块,那么 $B$ 同样删除一个砖块,奇偶性不变。而 $A$ 选择拆分一个砖块,则拆为一个奇数,一个偶数,则 $B$ 立马拆分偶数砖块为两个奇数砖块,则奇偶性不变。因此若初始有偶数个砖块,后手必胜。若有奇数个,则先手可以删除一个砖块变为偶数的情况,从而使自己变成后手,必胜。

接着考虑全是偶数的情况:

偶数只会拆分出两个奇数,所以奇数长度奇偶性不变($\text{SG}$ 不变)。又根据上面全是奇数的情况,后手可以保证奇数砖块数奇偶性不变,因此奇数、偶数可以看做两个独立的游戏。

而同样可以发现,一个偶数砖块是不会影响其他偶数砖块的,因为一个偶数砖块被拆分后就变成了奇数砖块中的部分。因此又可以看做独立的若干游戏。若长度为 $x$ 的砖块有 $n$ 个,其 $\text{SG}$ 满足:

  • 若 $n\equiv x\pmod {x+1}$,则 $\text{SG}=2$。
  • 若 $n\bmod\ (x+1)\equiv 1\pmod 2$,则 $\text{SG}=1$。
  • 若 $n\bmod\ (x+1)\equiv 0\pmod 2$,则 $\text{SG}=0$。

证明待补

那么只需要把偶数看做若干游戏,奇数看做一个游戏,将其 $\text{SG}$ 异或起来即可。

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

$\texttt{T2}$

咕咕咕

$\texttt{T3}$

首先有以下等式:

$$ \varphi(ij)=\dfrac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} $$

$$ \mu(ij)=\mu(i)\mu(j)[\gcd(i,j)=1] $$

$$ \sigma_0(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1] $$

那么根据一系列推导,令 $F(x)=\sum_{p|x} \dfrac{p}{\varphi(p)}\mu(\dfrac{x}{p})$,那么可以得到极长的柿子:

$$ \sum_{w}\mu(w)\sum_{x}F(x)\sum_{w|y}\sum_{w|z}\sum_{d}\mu(d)\sum_{\text{lcm}(x,d)|i}\sum_{\text{lcm}(x,y)|j}\sum_{\text{lcm}(z,d)|k}\varphi(i)\varphi(j)\mu(i)\mu(k) $$

这也忒长了

狄利克雷前缀和,再枚举可以做 $\mathcal{O}(n^2\log\log n)$。

继续推导的话,令:

$$ A(x)=\sum_{x|i} \varphi(i)\mu(i) $$

$$ B(x)=\sum_{x|i} \varphi(i) $$

$$ C(x)=\sum_{x|i} \mu(i) $$

都可以 $\mathcal{O}(n\ln n)$ 进行预处理。

那么答案变为:

$$ \sum_{w}\mu(w)\sum_{x}F(x)\sum_{w|y}\sum_{w|z}\sum_{d}\mu(d)A(\text{lcm}(x,d))B(\text{lcm}(x,y))C(\text{lcm}(z,d)) $$

令:

$$ B_2(x,w)=\sum_{w|y} B(\text{lcm}(x,y)) $$

$$ C_2(d,w)=\sum_{w|z} C(\text{lcm}(z,d)) $$

答案为:

$$ \sum_{x}\sum_{d}\sum_{w} F(x)\mu(d)\mu(w)A(\text{lcm}(x,d))B_2(x,w)C_2(d,w) $$

暴力 $\mathcal{O}(n^2)$,可以得到 $\text{70-90pts}$。

先考虑快速计算 $B_2,C_2$。把 $(x,w),(x,y)$ 看做图上两条边,固定 $x$,枚举边 $(x,y)$,以及 $y$ 的约数 $w$,在 $w$ 上进行记录,最后枚举 $(x,w)$ 统计答案即可做到 $\mathcal{O}(n\sqrt{n})$。

观察柿子,这和 [SDOI2018]旧试题 很像,$x,d,w$ 类似一张图中的一个三元环!根据之前一道题中三元环计数的复杂度,优化即可做到 $\mathcal{O}(n\sqrt{n})$。

[03.14]-总结

$\texttt{T1}$

本题同样是通过部分分得到提示从而求解题目,因此若没有思路,真的应该对着部分分一个一个推。

本题在将游戏划分为若干独立的部分一方面是十分巧妙的,首先从全奇数的情况得出奇数的意义,然后发现偶数只会指向奇数,从而导致每一种偶数均独立。因此,对于博弈论题,应该大胆猜测游戏中的独立部分,从而使用更加简单的方法求解其 $\text{SG}$ 函数。

同时,观察题目关键性质同样是本题的重点。由于必须拆分出一个奇数,因此奇数、偶数的划分方案唯一。从这个角度,才可以保证每一个偶数独立的优秀性质。这启发我们,在题目给出较为奇怪的条件时,应该尝试朝着特殊性质的方向进行思考,得到的求解方法尽量要完美匹配所有的性质,这才可能是出题人的思路方向。

且在考试图中,遇到博弈论题,若自己十分有思路则可以进行推导,否则可以尝试打表,因为 $\text{SG}$ 值若要快速计算,则其一定满足一定性质,这是在打表中就有可能发现的。

$\texttt{T2}$

咕咕咕

$\texttt{T3}$

首先本题第一个难点是对于公式的推导。由于本题中求和符号十分多,导致变量繁多,因此尤其需要注意在交换和式的时候,每一个变量枚举范围的变化情况。

同时,对于此类很长的公式推导,应敢于设新函数、新变量,从而尝试让题目变得简单。同时,本题启发了我们什么时候加入新的 $\sum$。一般来说,在进行反演的时候需要增加,在对繁杂的柿子进行拆解的时候可能需要加(例如本题中拆分 $\sigma_0(ij)$),总而言之,增加新的求和符号的意义在于要将更为复杂,或者不够好算的信息变为好算的信息,其代价是加入求和符号。

同时,如果一个求和符号加入后,不进行和式的交换,那么这极大概率是没有意义的。因为一般而言,求和顺序的调换是此类数论题中精髓所在,就像枚举约数 $\mathcal{O}(n\sqrt{n})$,枚举倍数 $\mathcal{O}(n\ln n)$ 一样,枚举的方式有可能极大地改变柿子计算的复杂度。因此,在遇上以上情况时,大胆加入求和符号,大胆交换和式,不失为一种十分优秀的思路。


2021.03.17

$\texttt{Location:HNOI2021}$

得分:$\texttt{20/300,Rank7}$。

[03.17]-错误

考试策略出现错误,对题目难度估计出错,导致浪费了时间。

[03.17]-部分正解

$\texttt{T1}$

把原先 $1$ 的位置看做左括号,那么一次操作相当于找到最左边的空白位置,补充右括号。接下来一轮相当于把当前右括号全部替换为左括号,然后再进行括号匹配。

对于一组括号,令 $a_i$ 表示嵌套层数为 $i$ 的括号对数。嵌套层数表示该组括号内部最多叠加了多少层括号。那么可以证明,一次操作之后,序列 $\{a_i\}$ 不变。简略证明如下:

考虑相邻的两轮,把前一轮的右括号——同样是后一轮的左括号,所在的位置看做关键点。然后就只需要证明,把关键点看做左括号/右括号,匹配后嵌套序列不变。考虑 $a$ 的计算过程,返回原来的 $01$ 序列,若向右补充,则一次括号匹配相当于删除一个 $"10"$,然后将左右拼起来,继续匹配。向左匹配则是删除 $"01"$。那么由于右侧有无数个 $0$,可以看做左侧也有无数个 $0$,那么对于一段连续的 $000011110000$,他们可以产生相同的 $a$。

因此只需要求出原先的 $a$,然后就必然是括号嵌套层数依次递增了。时间复杂度 $\mathcal{O}(n\log n)$。

$\texttt{T2}$

考虑分治计算,每次只考虑跨过枚举中线的矩形。具体来说,维护每一个位置可以往上下左右延伸多少,枚举上边界,然后看能往下延伸多少,则对下边界产生一个贡献。但是,如果上边界能够向左/右延伸的长度比下边界的要长,就会出锅。因此从上往下、从下往上依次做一遍,取 $\min$ 即可。

但是如果每次只是按照某一位划分,那么复杂度不对,因为另一维太大了。因此交替划分即可。

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

$\texttt{T3}$

考虑枚举直径中心,可能在边上,因此先倍长。

显然只会在连接叶子的边上加,因为他们会对尽量少的路径产生贡献。假设我们知道了半径 $R$,那么就可以计算最多可以加多少次了,具体来说,记叶子到中心的距离和为 $s$,这个可以换根 $\text{dp}$,叶子个数为 $x$,那么最多可以加:$\left\lfloor\dfrac{xR-s}{2}\right\rfloor$,除 $2$ 是因为倍长。

设 $\text{dp}_i$ 为半径是 $i$ 的时候,最多可以加多少次。这个可以通过上述枚举直径中点,然后做前缀 $\max$ 得到。同时,这个数组只需要维护到 $n$ 即可,因为 $n$ 以上,则任意叶子上面都可以再加,可以直接数学推导。

那么同样还有 $\text{chkmax}(\text{dp}_{i+2},\text{dp}_i+2x)$,然后太大的部分就直接分一下 $\text{dp}$ 下标的奇偶性,从 $n$ 和 $n-1$ 两个地方推导到半径之后取 $\min$ 即可。

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

[03.17]-总结

$\texttt{T1}$

本题首先将较为难懂的问题转变为更为人熟知的括号匹配问题,接着提出了关于括号匹配层数相关的结论,从而从动态过程中的不变性解决了问题。

对于很多一一对应的问题,括号匹配问题都具有极其广泛的普适性,他有助于我们将新问题转变为老问题。同时,对于本题括号匹配层数的结论,需要极其细致的观察与推导才可以发现。

$\texttt{T2}$

对于一类较难直接 $\text{dp}$ 求解的计数问题,有一个十分好的方法是进行分治。本题中,本来需要计数一个封闭图形的个数,但是当我们分治之后,就变成了只和某线段上两个点相关的计数问题。因此,对于看似较为复杂的模型,如果在枚举了“跨过”某点/某边之后,可以转变为较为简单的问题,则可以考虑通过花费一个 $\log$ 的代价,将问题转变为分治。同时,这类问题在枚举的划分位置上,很多时候可以使用 $\text{bitset}$ 进行优化,但一般用于可信性问题而非计数问题。

同时,本题是二维问题,若只是对一维进行划分,时间复杂度同样无法接受。但是通过对两维交替的划分,保证了两个维度大小比值相对保持稳定,从而进一步优化时间复杂度。这个思路值得借鉴、思考与拓展。

$\texttt{T3}$

本题的关键词在于“浪费”操作。暴力每次模拟每个操作显然是不可行的,因此题解通过一步转化,转变为求使得答案为某一个值,所可以接受的操作次数的 $\max$,接着通过二分+数学计算得到本次询问的操作次数处于哪个区间。这启发我们在答案增长不快的时候反向考虑某一个答案的适配范围,这和某些 $\text{dp}$ 中交换储存值和状态中一位异曲同工。

最为关键的是枚举一个点作为直径的中点,然后通过枚举半径来计算出每一个点、每一种长度的半径,最多能够加多少次操作。因此,对于直径相关的问题,不仅直径的两个端点是极其特殊的,同时直径的中心或许也是考虑问题的不错方向。


出于某些原因 写不过来了,暂时搁置 $\text{2021.03.18-2021.03.24}$ 中的考试总结。

会补上的。


2021.03.26

$\texttt{Location:HNOI2021}$

得分:$\texttt{30/300,Rank7}$。

吉老师的神仙场

[03.26]-错误

题目的难度较大,导致完全失去了考试的状态。
$\text{T1}$ 的正解需要一步看似十分简单的结论,但是考场一直在考虑打表。因此考试中不能够一味地依赖打表来找规律,能列柿子还是列一下......

[03.26]-部分正解

$\texttt{T1}$

考虑这个相同的后缀,由于 $2^k|10^k$,因此如果在一个数字上加 $10^k$,那么不论在 $10$ 进制还是 $2$ 进制,最低 $k$ 位都是不会变的。因此,这指引我们考虑在合法状态上加入 $10^k$ 来判断新数是否可行。

对于一个已经合法的数字 $x$,若 $x+10^k$ 合法(当然 $x$ 一开始 $10$ 进制下 $k+1$ 位为 $0$),则说明 $2$ 进制上第 $k+1$ 位也是 $1$。这个判断可以通过写一个 $2$ 进制的高精度,同时查询这个大数的某一位来实现。

因此我们可以通过枚举合法数字,在其高位上加入一个 $10^k$,然后判断 $2$ 进制下 $k+1$ 位是否为 $1$。同时可以剪枝:若当前已经不合法了(当前 $2$ 进制已经有 $1$,但是我不再往相应的位置的 $10$ 进制加 $1$,那么之后这个位置就永远不会相等),那么再往上加也不合法。

同时,关于维护高精度数组,由于我们需要维护加法、乘 $10$、查询 $2$ 进制下某一位,不妨按照 $2$ 进制压位。令一个数字中压最多 $2^a-1$ 大小的数字,那么时间复杂度可以做到 $\mathcal{O}(\dfrac{kL}{a})$。

如果只是记录一个数组表示当前合法数字可不可能向后拓展,复杂度可能有些假 但题解就这么过的,但是如果开一个链表,就可以严格做到上述复杂度了,因为一个数字除了最后一次不合法的被遍历之外,都会产生新数,而有最多删除一次。

$\texttt{T2}$

首先很快可以考虑到一个 $\text{dp}$:设 $\text{dp}_{i,j,0/1}$ 表示 $i$ 个节点,最大独立集为 $j$,根节点选/不选的方案数。但是,由于实际上你很难知道到底选/不选根对答案有啥影响。

由于树的最大独立集=点数-最大匹配,所以令 $f_i$ 表示 $i$ 的子树内选了 $i$ 的最大匹配,$g_i$ 表示不选的最大匹配。观察到 $0\le f_i-g_i\le 1$,因此令 $F_{i,j}$ 表示 $i+1$ 个点,根节点 $f$ 值为 $j+1$,$g$ 值为 $j$ 的树的个数;$G_{i,j}$ 表示 $i+1$ 个点,根节点 $f,g$ 都是 $j$ 的树的个数。

那么可以得到方程:

$$ G_{i,j}=\sum_{a=1}^i \sum_{b=0}^j G_{i-a,j-b}\times F_{a-1,b-1}+[i=0,j=0] $$

$$ F_{i,j}=\sum_{a=1}^i \sum_{b=0}^j F_{i-a,j-b}\times(G_{a-1,b}+F_{a-1,b-1})+G_{i-a,j-b}\times G_{a-1,b} $$

第二重循环是个卷积,可以优化一下,但是还是 $\mathcal{O}(n^3\log n)$。可以先 $\text{DFT}$,然后在点值上直接乘,最后 $\text{IDFT}$,就做到了 $\mathcal{O}(n^3)$。

同样可以把 $F,G$ 看做节点数 $x$,根节点 $g$ 值 $y$ 的形式幂级数,那么:

$$ G=xyFG+1 F=xFG+xyF^2+xG^2 $$

而第二维 $y$ 不会超过 $\left\lfloor\dfrac{n}{2}\right\rfloor$,因此可以令 $x=y^{\left\lfloor\frac{n}{2}\right\rfloor+1}$,然后就变成一元的卷积了。

$\texttt{T3}$

首先考虑啥都没有的时候,要怎么求本质不同的子序列个数。考虑在一个子序列最早出现的时候计入答案,即组成这个子序列的下标的字典序最小的时候计入。那么令 $\text{nxt}_{i,c}$ 表示 $i$ 后第一个 $c$ 出现在哪里,那么 $i$ 的答案就可以向任意 $\text{nxt}_{i,c}$ 转移。

考虑使用数据结构对这个东西进行优化。建立线段树,设 $\text{dp}_{x,i,j}$ 表示线段树节点 $x$ 所代表的区间中,子序列第一个值是 $i$,且转移到区间外的一个 $j$ 的方案数。这个 $j$ 实际上只是为了方便进行区间的合并,相当于在区间的最后接上一个 $j$,这样就可以从 $x\rightarrow y\rightarrow z$ 来进行转移。

这就是一个矩阵乘法,然后就可以用线段树维护矩阵来做到了。

再考虑区间加,观察发现在 $\bmod\ k$ 的意义下,加法相当于一个置换,那么只需要把修改的区间的矩阵的行、列进行一些置换即可。

区间乘有一些区别:若 $\gcd(v,k)=1$,那么必然仍然是置换,和加法没有本质区别。若 $\gcd(v,k)=k$,表示他们全都变成了同一个值,只需要重新赋值即可。其他的情况,容易发现仅有 $k=4$ 的时候可能发生,也就是在 $\gcd(v,k)\ne 1,\gcd(v,k)\ne k$ 的时候。这种时候,只需要维护 $k$ 的约数的答案,然后从 $k$ 的约数的答案更新到 $k$ 的答案即可。

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

[03.26]-总结

$\texttt{T1}$

本题第一步是十分关键的,需要观察到 $2^k|10^k$,这对应的二进制下后 $k$ 位不变一性质十分重要。

同时本题最后维护一个高精度数的方式也是值得借鉴的,通过维护 $2$ 的次幂的值来实现快速求二进制某一位,同时通过压位高精来加速(这和 $\text{bitset}$ 的方式或许有些类似)。

$\texttt{T2}$

首先需要记住:树是二分图。这样就通过将最大独立集转移为最大匹配,将 $\text{dp}$ 的第二位的数值降到一半。

接着,通过 $\text{dp}$ 套 $\text{dp}$ 的方式(也就是把 $\text{dp}$ 值作为状态),再优化状态,得到二元形式幂级数形式的答案。$\text{dp}$ 套 $\text{dp}$ 一般可以用于求解最优解为某值的计数问题,同时一般要求最优解状态较少,从而将最优解加入 $\text{dp}$ 数组,通过转移最优解问题的方式去计算此时的方案数。

对于二元形式幂级数,处理方法有多种:可以考虑使用多维卷积进行优化,这个方式较为普适;可以仅将一个元看做形式幂级数,仅处理一维度上的卷积问题,这可能会使时间复杂度不太优秀;在本题中,还有第三种方式,即将两个元合并为一个,这需要一定题目性质的支撑,同时这可能使形式幂级数的上限到达平方级别,其本质就是用某一个元足够大的幂去表示另一个元,使得他们在进行卷积的时候,处在下面的元没有办法乘到被代换的元的位置,从而将两维划分开来。

$\texttt{T3}$

本题思路方向实际应该是较为清晰的:首先考虑没有任何操作的时候如何计算序列问题,接着考虑区间查询,再加入加法、乘法。这体现了一种逐步扩大适用范围的思想,也就是从最为简单的情形开始思考,也是一种好的思维方向。

同时本题中 $k$ 值极小这个性质,启发我们设立 $\text{dp}$ 状态,并支持我们使用较为暴力的方式进行合并。状态中“在区间后面加入一个值”的想法是很有趣的,这才支持我们进行区间的状态合并。


2021.03.28

$\texttt{Location:HNOI2021}$

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

为啥写暴力都可以第一

[03.28]-错误

题目的难度较大,导致完全失去了考试的状态。
$\texttt{T1}$ 提问的形式已经具有很强的提示性了,但是完全没有意识到。
$\texttt{T2}$ 又开始找规律了......还啥都没发现。
$\texttt{T3}$ 有部分分却只写了暴力。

[03.28]-部分正解

$\texttt{T1}$

由于题面直接把区间询问当做了一个二维表格,不妨直接顺着他的思路向下走。

考虑修改一个位置会让答案发生什么变化:把赋值变为加减,修改 $p$ 会使得满足 $l\le p,r\ge p$ 的区间 $[l,r]$ 的答案发生变化。这就是一个二维平面。

因此先离线下来,对所有询问点建立 $\text{K-D Tree}$,然后每次暴力修改,维护平面历史最小值即可。关于维护平面历史最小值,可以通过维护 $\text{val, hval, tag, htag}$ 四个值,即:当前值,历史最小值,当前加法标记,从上一次 $\text{pushdown}$ 到现在为止的加法标记的历史最小值。

$\texttt{T2}$

之前就说过这个思路,考虑将异或转变为加法、减法。对于 $m$ 是 $2$ 的整次幂的情况,特判一下。剩下任何情况中,不论我们加/减了任何 $2$ 的次幂,这个 $2$ 的次幂必然不会是 $m$ 的倍数。

那么把所有 $2^k$ 在 $\bmod\ m$ 意义下分组,那么如果一个数字 $\bmod\ m=s$,若存在一个二进制位 $k$,满足数字二进制第 $k$ 位为 $0$ 且 $2^k\bmod\ m=m-s$,或存在一个二进制位 $k$,满足数字二进制第 $k$ 位为 $1$ 且 $2^k\bmod\ m=s$,那么这个数字就是合法的。

那么可以把数字的每一位 $\bmod\ m$ 的值看做物品,做 $01$ 背包。那么对于背包的一个位置,其中或许有一些值实际上是不合法的,但是我们算多了:因为他们可能上述每一个可能使其合法的二进制位都不合法。考虑减去,相当于把二进制这些位钦定取什么,这只需要把背包中那些位置的值给删除即可。

删除 $01$ 背包中的一个物品,实际上类似于在解方程且每个方程只有两个未知数系数不为 $0$。在 $m$ 为奇数的时候这么解是没有问题的,$m$ 是偶数的情况下只需要判断后面的位上是否放一个 $1$,先把这些情况计数,然后把约数 $2$ 给除掉即可。

$\texttt{T3}$

考虑钦定哪条边作为第 $k$ 条边,那么相应地,若钦定边权为 $w$,那么将边权 $\ge w$ 的减去 $w$,剩下的变为 $0$。跑一遍最短路,假设最短路解为 $d$,那么 $\text{Ans}_k\leftarrow \min(\text{Ans}_k,d+k\times w)$。对每条边这样跑,就可以得到答案。

但是首先需要钦定一条 $w=0$ 的边,给每个答案赋一个初值。

考虑证明:如果当前边的边权小于第 $k$ 条边,那么任意应该非 $0$ 的边在图中都非 $0$,答案不会更优;如果当前边的边权大于第 $k$ 条边,那么大于他们两者的边实际上没有变化,但是经过的 “$0$” 边实际上会被看做边权为当前的 $w$,而这个 $w$ 偏大,所以答案也不会更优。

[03.28]-总结

$\texttt{T1}$

历史最小值是套路,但是我不会。本题中最重要的一点在于把区间信息看做二维平面的信息,然后使用数据结构维护二维平面信息。

$\texttt{T2}$

同样考到了关于将位运算看做加减法的问题。而且本题中由于要整除 $m$,所以启发我们将问题丢在同余系下进行求解。而本题中不合法的数字,需要每一个特殊的位置都不合法,而不是存在一个特殊位置不合法。因此只能考虑先算所有的数字,然后删除每一个位置都不合法的数字。

同时,由于在同余系下,很多二进制位都是相同的,所有考虑使用 $01$ 背包进行计算。这体现背包问题十分广泛的运用。同时,删除背包中某一个物品的 $\text{trick}$ 是值得记住的。但是是否可以快速对完全背包进行物品删除?方程估计就会变得更为复杂了。

$\texttt{T3}$

本题中首先观察到 $n,m$ 同阶且并不大,所以应该考虑枚举边来进行求解。通过枚举之后进行分层图最短路,可以拿到 $\text{60pts}$。

而本题的关键在于对边权进行重新设置之后,如果选中错误的边,对答案没有影响这一点。对边权重新设置之后,答案可以分为两部分:最短路的边权和 $+$ 加上的 $k\times w$。在选中不优的边时,这两部分中有一部分变大,另一部分不变(体现一种平衡?)。这种题或许需要一些脑洞来进行猜想,如果要总结一些方法,那么在这类不好找到合法的最优关键点的题目中,把每一个点都“假装”是合法的关键点,然后证明非合法关键点处必然取不到最优解即可。


2021.03.30

$\texttt{Location:HNOI2021}$

得分:$\texttt{0/300,Rank7}$。

抱灵了/kel

[03.30]-错误

暴力都写挂......
$\texttt{T1}$ 堆了很多时间,但是事实上没有搞到什么结论。
$\texttt{T2}$ 距离正解很近了,但是把自己叉掉了......

[03.30]-部分正解

$\texttt{T1}$

直觉告诉我们可能这个答案并不会很小,因为和直径端点很近的那些点很难都让 $\text{Bob}$ 选到。

而部分分中有一个 $\text{subtask}$ 中写到:保证答案不会小于直径长度-1,那么朝着直径的方向思考。根据关于树的直径的瞎扯中所提,本题和直径与距离相关,首先考虑将直径中点 $c$ 当做根节点再考虑。

那么令 $c$ 为根的时候子树分别为 $T_1...T_k$,设直径长 $l$。令集合 $S_i$ 表示子树 $T_i$ 中,深度为 $\dfrac{l}{2}$ 的点组成的集合,那么任意两棵不同子树中两个在各自集合中的点,都可以组合成一条直径。这意味着,当 $\text{Alice}$ 选到了两个子树中集合中的点,他必然“输”了,即长度为 $l$。

接着需要确定一个性质:当 $n$ 是偶数时,$\text{Alice,Bob}$ 取数的个数是相同的,而奇数时 $\text{Alice}$ 最后会多选一个,这不太有利。

(以下用先手、后手分别代表 $\text{Alice}$、$\text{Bob}$)

考虑子树和子树集合需要满足什么条件才能让答案顶满:

首先直觉告诉我们,当子树很多的时候,几乎不可能取不到这些点。不妨根据 $S$ 非空的子树个数进行讨论。

以下情况答案为 $l$。

若非空的 $S$ 有至少 $4$ 个。

先手必然至少在两个 $S$ 中取点。

若非空的 $S$ 有 $3$ 个,且 $n$ 为奇数。

先手最后还需要选择一个,后手必然可以留一个点使得先手取得两个 $S$ 中的点。

若非空的 $S$ 有 $3$ 个,且其中至少有一个 $|S|\ge 2$。

这个大小大于 $1$ 的集合中,先手必然取到点,且剩下两个集合中必然选到一个。

若非空的 $S$ 有 $2$ 个,且 $\forall |S|\ge 2$。

两个集合中,先手都必然会选点。

若非空的 $S$ 有 $2$ 个,且至少一个 $|S|\ge 2$,$n$ 是奇数。

同理,后手一定可以把大小为 $1$ 的 $S$ 留给先手选择,剩下一个必然两边都选到点。

排除以下,还剩下:

1.若非空的 $S$ 有 $3$ 个,$n$ 为偶数且 $\forall |S|=1$。
2.若非空的 $S$ 有 $2$ 个,$n$ 为偶数且存在一个 $|S|=1$。
3.若非空的 $S$ 有 $2$ 个,$n$ 为奇数且 $\forall |S|=1$。
4.若非空的 $S$ 有 $2$ 个,$n$ 为偶数且 $\forall |S|=1$。

实际上 $1,2,3$ 答案均为 $l-1$。可以令一个 $|S|=1$ 的 $S$ 中加入一个深度为 $\dfrac{l}{2}-1$ 的节点,就会完全转化为以上的某种情况,而又因为加入了一个 $\dfrac{l}{2}-1$ 的节点,所以可以证明先手必然有方法使得答案为 $l-1$。

那么只需要考虑:

4.若非空的 $S$ 有 $2$ 个,$n$ 为偶数且 $\forall |S|=1$。

这个情况答案必然不会大于 $l-1$,再来考虑是否能更小?考虑一下 $l-2$ 的情况。

把 $|S|$ 非 $0$ 的当做 $1,2$ 号子树,接着考虑深度为 $\dfrac{l}{2}-1$ 的节点。设 $S_1,S_2$ 中的点分别为 $v_1,v_2$,那么先后手一定最后分别选走其中一个。那么使得答案为 $l-1$ 的方法只有:

1.先手在 $T_i(i>2)$ 中选择了一个深度为 $\dfrac{l}{2}-1$ 的节点。
2.先手在 $T_1,T_2$ 中都选择了深度为 $\dfrac{l}{2}-1$ 的节点。

那么令 $T_i$ 中深度为 $\dfrac{l}{2}-1$ 的点构成集合 $H_i$,然后把其他的 $H_i(i>2)$ 累加到 $H_3$ 上,就只需要讨论 $H_1,H_2,H_3$ 了。

若 $|H_3|\ge 2$,则先手必然在里面选到一个,答案为 $l-1$。

若 $|H_3|\in\{0,1\}$。

若 $|H_3|=1$,那么先手尽量不选这个点,则后手必然在倒数第三步选走这个点。则后手必然需要先手在 $H_1,H_2$ 中同时选点,这就很类似 $S$ 的讨论了。按上面的推法即可求出什么情况答案为 $l-1$,什么情况是 $l-2$。

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

$\texttt{T2}$

考虑对 $y$ 坐标分治。仔细观察下那个查询的柿子,实际上红点蓝点的独立性是极强的,他们之间只有 $y$ 的限制。

那么每次考虑枚举 $y$ 的划分点,考虑下方红点对上方蓝点的贡献。观察发现,只有红点蓝点至少有一个取到当前可取的最大值,这个值才有可能成为最优解,因此一次分治中合法的点对个数只有 $\mathcal{O}(n)$ 级别。则一共只有 $\mathcal{O}(n\log n)$ 级别。

接下来直接扫描线+树状数组求 $\max$ 即可。

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

$\texttt{T3}$

怎么可以搬题!!!

现在还不是很会写等到时候会解释了再回来重新写一下所以目前扔一个写得很好的博客放这里凑合一下也就是说我咕咕咕了但是没有关系因为我迟早会回来补的!

[03.30]-总结

$\texttt{T1}$

本题考到了自己不是很擅长的博弈论,但是整体思想实际上是有可能想到的。

首先需要观察到本题与树上大多数点的关系并不大,而只和接近直径端点的节点有密切联系,这点应该在很多与树上最长路径的题目中都有可能遇到。接着关于直径节点个数、节点总数的一些讨论,主要是基于对“先手是否不得不选择两个子树的集合中的点”的思考。前面的几种讨论是较为常规的,而最后的讨论实际上是把 $\dfrac{l}{2}-1$ 的点与 $\dfrac{l}{2}$ 的节点做一个类比,然后使用之前已经证明的结论来解决新的问题。

这种思路似乎在博弈论中是十分常见的。在非 $\text{SG}$ 函数题中,尤其是分类讨论的博弈论中,经常需要推出若干结论之后,通过一些近乎等价的转化,将问题转变为已经解决过的较为简单的情形。同时,博弈论实际上就是在逼迫对方选择最劣的方案的过程,有时候题目中一些必然发生的事情(例如本题中有些情形中先手必然选择到两个子树中的端点)往往是十分具有启发性的,在做博弈论的时候,应该从这些角度出发。

同时,一个博弈论的结束状态同样是十分重要的,哪一边赢了之后会是什么样的局面,这个问题往往可以让我们从结尾倒推出一些策略,从而更好地解决问题。

$\texttt{T2}$

实际上分治是很套路的了,本题中最主要需要发现的就是查询形式对点对个数的影响。如果直接考虑分治,点对个数不会有任何变化,但是由于查询形式,所以使得点对个数骤降至 $\mathcal{O}(n\log n)$。这又一次体现了一种简化的思想,有时候我们不仅可以考虑优化求解的复杂度,优化状态数也是必不可少的思维方向。

例如本题中,如果考虑到分治结构,就必然会发现这个东西完全无法改变点对的个数。但我们明显不能接受 $\mathcal{O}(n^2)$ 级别的点对个数。因此,走到这个位置之后就应该思考状态数的化简。

同时,题目的询问形式也是十分重要的。尤其是一些比较非常规的询问方法,是否可以考虑手玩一些最优解的情况,然后逐步寻找规律。

$\texttt{T3}$

神题,没啥总结的。但是一类组合问题,若问题在划分部分解决,同时带有一些组合数的限制,折线法或许是一种思考方向。

标签: none

添加新评论