P4559:「JSOI2018」列队 – 题解

主要思路

一开始想了一个假的,后面写完了之后才意识到哪里错了,就很傻逼。

首先贪心的知道,肯定是第 \(i\) 小的数位于 \(K + i – 1\) 的位置上。我们算答案的时候会发现无非就是把贡献根据绝对值的拆法进行分开处理,一部分是 \((a_i – rk_i) – (k – 1)\),还有一部分是 \((k – 1) – (a_i – rk_i)\)。所以我们需要一个数据结构来拆分这两个部分。

首先我们知道这两个部分肯定是连续的两段,因为前后的 Delta 都至多为 \(1\)。知道这个性质之后,我们其实可以尝试用主席树来搞区间内的段。考虑用势能线段树的那一套,我们可以把段一直下传,直到段完整为止。

对于完整的段,发现其实就是给上面那个贡献式子套 \(\sum\),而且发现套 \(\sum\) 的时候要记录这一段和的左端点,这样就可以用等差数列直接搞了。

继续阅读P4559:「JSOI2018」列队 – 题解

P4428:[BJOI2018]二进制 – 题解

主要思路

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

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

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

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

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

继续阅读P4428:[BJOI2018]二进制 – 题解

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

主要思路

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

首先这个题求的就是 \(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)\),因为这个其实用一个反着的(从右到左)单调栈就行了。

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

继续阅读P4425:[HNOI/AHOI2018]转盘 – 题解

HNOI 2018 省队集训 Day 8 – 解题报告

A – 杀毒软件

这套题里面质量最好的题(虽然跟 BZOJ 的某题比较像)。

我们先考虑把所有的病毒串加到 AC 自动机里去,然后再考虑一个 DP 转移,设 \( dp[i][j] \) 为当前第 \(i\) 个字符匹配于自动机节点 \(j\) 上的方案数。发现数据范围很小,所以其实这个可以矩阵优化。建完 AC 自动机之后,我们针对 \(a_i = 0, 1, -1\) 算三个矩阵。算完这个之后用线段树来维护就可以了。(复杂度上天了)

实测矩阵乘法的时候剪枝可以快 10s 的样子。

继续阅读HNOI 2018 省队集训 Day 8 – 解题报告