Monthly Archives

25 Articles

信息学奥林匹克竞赛

P4338:[ZJOI2018]历史 – 题解

Posted by kal0rona on

主要思路

ZJOI 的题质量都好高啊!真的都是很棒的题。

其实这个覆盖的东西就相当于在 LCT 上进行 Access 时轻重链切换的次数。我们考虑静态的问题,对于点 \(u\) 来说,如果子树内有多个来自不同儿子子树内的子代节点,那么就需要进行合理的分配来把这个轻重链切换次数搞到最大。

转换一下就是两两不同颜色的点进行配对的最大值。设 \(S_0 = a_u, S_i = [\text{第 } i \text{个子树内的 access 次数之和}]\)。那么答案其实就是 \(\max\{ \sum_{i = 0}^m S_i – 1, 2(\sum_{i = 0}^m S_i – \max_{i \in [0, m]} S_i) \}\),前者是啥都不考虑,后者是连接到一个子节点。后者成为最大值的条件其实就是要成为重儿子。我们考虑维护这个东西。

发现其实我们用贪心的分配方案进行轻重链剖分时,复杂度也是对的。因为被贪心选择的那个子节点确实也是个重儿子,根据树链剖分那一套理论这个复杂度是成立的。

当我们进行修改时,我们就需要用 Access 操作来进行判断和修改。我们需要判断是否存在虚子树中的点成为重儿子,然后进行切换。

信息学奥林匹克竞赛

P5327:[ZJOI2019]语言 – 题解

Posted by kal0rona on

主要思路

好题!好题!

这个题首先需要了解到一个性质:每个点所能到达的、进行贸易的国家的集合可以形成一个连通的生成子图。所以,我们最后需要求的就是每个国家对应的集合的大小。

如何去快速求这个东西呢?我们需要把 \(m\) 个路径中每个跨过当前点 \(u\) 的路径给拿出来,然后算这些路径的交集。这样是一种计算的方法,但是确实不快速。

信息学奥林匹克竞赛

P4428:[BJOI2018]二进制 – 题解

Posted by kal0rona on

主要思路

打个表发现合法的区间需要满足以下条件之一:

  • 如果区间内的 \(1\) 的个数为奇数,则至少要有 \(2\) 个 \(0\)。
  • 区间内的 \(1\) 的个数为偶数。

我们可以考虑维护不合法的区间,因为不合法的区间特征明显一点,只有这种:

  • 如果区间内的 \(1\) 的个数为奇数,且 \(0\) 的个数 \(< 2\)。

我们可以考虑用线段树来维护这个信息。大概就是需要固定左右端点的选择,然后再用分治的方法处理跨两个子树的区间即可。

信息学奥林匹克竞赛

P3349:[ZJOI2016]小星星 – 题解

Posted by kal0rona on

主要思路

怎么毫无头绪啊?(wtcl)不过有一说一,题目是真的挺好。

有一种接近正解的方式是设置 DP,设 \(dp[u][i][stat]\) 为当前在点 \(u\)、编号为 \(i\) 且被用过的编号集合为 \(stat\),然后做一个树形 DP。不难分析出这个东西的复杂度是 \(\Theta(n^3 3^n)\)。

这个肯定过不了的,考虑进行玄学优化。假设转移时能去掉第三个限制就好了。我们考虑抛弃这个第三维。抛弃之后必须要面对的一个问题就是非法状态。我们可以考虑硬点一个点集,使得整个 DP 的时候只能选点集内的编号。发现这样答案的意义是至少有 \(i\) 个重叠选择的点的方案数,所以我们可以愉快的套一个 \((-1)^{n – |S|}\) 系数就可以的出恰好为 \(0\) 个重叠选择的方案数了。

信息学奥林匹克竞赛

P4425:[HNOI/AHOI2018]转盘 – 题解

Posted by kal0rona on

主要思路

第一次做到线段树维护单调栈的题,来写一写博客。

首先这个题求的就是 \(ans = \min_{i \in [n, 2n)} \max_{j \in [i – n + 1, i]} a_j + i – j\),换一下就是 \(ans = (\min_{i \in [1, n)} \max_{j \in [i, i + n – 1]} a_j + i – j) + n – 1\)。

我们可以考虑做 \(B_i = a_i – i\),然后再去做 \(\min\) 值。然而这样复杂度还是很高。我们考虑静态的问题时,发现其实这题可以做到 \(\Theta(n)\),因为这个其实用一个反着的(从右到左)单调栈就行了。

放到动态问题上,可以尝试用线段树去搞搞:合并的时候,先保留右子树的内容,然后尝试在左子树里进行二分,找到队尾即可。

信息学奥林匹克竞赛

P4501:[ZJOI2018]胖 – 题解

Posted by kal0rona on

主要思路

可以比较显然的看出来是个区间扩展问题,单调的向两边进行扩展。

正常暴力可以考虑 \(n^2\) 进行扩展,然而这题显然有单调性,所以我们可以试着进行二分优化掉一个 \(n\)。二分出一个范围,然后再用 ST 表或者是线段树之类的东西去查一下区域内的最远距离然后就可以进行判断了。

代码有点长而且还有点复杂。