打模拟赛,顺便复习了ACAM,学习了全局平衡二叉树.
D7
T1
简单贪心题.
直接上正解.首先同时操作的线程只有两个,情况比较简单,只有两种情况,一种是两个线程同时工作,一种是只有一个线程工作.显然最大化同时工作的时间是最优的.
来个表面的简单假贪心,直接考虑在所有可行叶子里面摩尔投票.但是这样显然不成立,因为随着叶子消掉,可能有新叶子解锁.所以从下向上看不是很方便.考虑从上向下看.既然当前贪心的矛盾是贪心决策与依赖关系不确定性的矛盾,那就直接从依赖关系明确的方向看问题,也就是讨论从一个节点出发的儿子子树.子树间互不干扰,考虑摩尔投票.如果出现过半的一个子树,只有这个子树内部可能进一步增加双线程时间.在这个子树内考虑即可.
复杂度显然是 \(O(n)\) 挺简单的.
T2
数据结构题.
暴力:处理矩形覆盖一类问题,要么二位前缀和,要么扫描线.
二位前缀和显然必然 \(n^2\) ,没啥前途,但是好想.
直接二位前缀和把平面的操作结果跑出来,然后考虑把上连续和下连续分别讨论,然后排除同时连续的,同时连续这一块没啥好的 \(n^2\) 做法,直接上个线段树多个 \(log\).
期望30分(其实改一下可以到40) 但是MLE到10,警钟敲烂.
在这里扫描线的处理思路是类似的.
另外还有一种更有前途的统计方式,就是把扫竖排变成扫横排,对每个位置维护一下竖向连续1的个数,考虑元素之间互相贡献,贡献为:
\[\sum_{i }^{} \sum_{j} \max (len_i, len_j) \]这东西暴力是 \(n^3\) 的,考虑优化一下这个式子,显然地联想到统计每个 \(len\) 能贡献的次数,于是变成:
\[\sum_{i }^{} len_i \times rk_i \]其中 \(rk_i\) 为对 \(len\) 的严格排名(同值不同排名),这个东西可以简单sort拿到暴力分了.
这个方案比第一个更有前途一点,因为首先这个东西是对一整排整体操作的,加上 \(len\) 的变化与区间抑或1操作直接相关.此外,\(rk\) 这个东西也是可以数据结构维护的,相比第一个做法更简洁,也更少一些讨论.
因此虽然做法一也能推到正解,但是来自做法二的解法显然更自然一些,就从这里开始考虑.
正解:采取扫描线维护行,考虑维护 \(len_i\),分析区间异或时发生了什么.
对于 \(0\) 变 \(1\),\(len_i\)变成了 \(1\)
对于 \(1\) 变 \(0\),\(len_i\)变成了 \(0\)
其余没有经过操作的地方,是 \(1\) 的会 \(len++\)
发现这个 \(len++\) 直接导致 \(len\) 一行一变,没法用更高明的办法维护了.于是考虑转化为不变量,考虑 \(1\) 的起始点的绝对位置不变,变的是当前的线,考虑把 \(len_i\) 设为 \(n-pos\) 其中 \(pos\) 为最靠前 \(1\) 的位置,再除去贡献.答案用权值线段树维护,这是可以做到的.
考虑维护操作,\(1\) 变 \(0\) 是容易的,直接DS维护序列数区间 \(1\) 的个数然后取反调整贡献即可.考虑这个 \(0\) 变 \(1\) ,首先,要撤销过去的 \(0\) 变 \(1\) 的贡献,要在维护答案的线段树上调整的是过去这次操作所在的行,同理,新的贡献与当前行有关.看起来一个区间内可能有多种不同的贡献,复杂度爆炸,不过因为考虑区间内 \(1\) 的贡献情况,唯一的操作就是区间染色.因此存在颜色段均摊.事实上不必 set 维护,直接继承这个线段树思路就行,如果当前段颜色不一样就下放,贡献开个 map 统计一下,然后统一更新,就可以做到 \(nlogn\).
启发:首先对于平面问题,横行考虑和竖列考虑是典型的改换观察角度来发掘问题内部矛盾的,这展现了一个典型的改换角度来发掘/接近/利用性质,尤其是关键性质的时候.
其次就是平面扫描线,很有用,不要忘了.
然后就是转化成DS问题后的转化,大胆从操作,查询两方面解构区间需要维护的信息和更新方式,来寻找可靠的数据结构.
T3
感觉自己思路和题解差别极大,由于被细节卡麻,没有验证自己的想法.
场上思路:对于这个序列,硬套字符串算法显然没前途.考虑发掘性质.
首先对着 \(abba\) 手算了一下,发现如果把一个串约成一个规范的形式,是可以通过讨论和计算得出答案的.因此首先的思路是处理串 \(S\)
想到了缩串,感觉没想法,就直接去原串找性质了.题解是从缩串切入的,不过感觉中心思想是相似的.
发现每次倍增构造,相当于对当前串取反接在后面.再深入一步,把这个过程视作二叉树,奇数层的区间左右是相反对称的,区间中点的两个字符不同.偶数层的区间轴对称,区间中点的两个字符相同.有了这个性质,相当于任取一段序列,直接通过相邻字符的关系,就可以得到这棵树上非叶子节点的奇偶染色.
然后可以考虑直接还原这棵树,发现对于当前的叶子层考虑,也是类似的讨论,发现只有左右颜色都不同时,可能是叶子节点,其余的高层节点左右都有到叶子层的区间(边界除外),因此就可以找出上一层节点,依次类推,直到汇总到一个根节点.这时找到的就是最小的一棵能够用中序遍历的一部分描述当前串的二叉树.
至此第一问解决考虑第二问就是把所有的用这个树能维护而不能用更小的维护的情况算出来,其实就是树不退化,是可以计算方法得知的.
没有经过验证,但是感觉挺对的,就是不好实现.
正解:直接缩串＋dp,比较神秘.
D8
T1
被卡麻了.
简单题,直接上正解.这题就是算动态加边的边双上的信息.考虑树性质显然可以用常规树方法维护.而边bcc是可以缩成树的,把bcc大小设为权值,直接简单差分维护即可.
倍增LCA奇慢,加上,没有用tie(0)输入输出,导致被卡常,警钟敲烂.
T2
看着像背包,其实就是背包.
暴力:直接变成多重背包.
场上思路:既然有倍数关系,直接考虑用当前层的数补全 $m \mod a_{i+1} $ 的余数,然后多出来的物体 \(a_{i+1}\) 个一组直接扔到上一层.根据题目给的性质,每层点数不会太多.
但是想要用组合办法解决每层的统计问题,发现很复杂很不可做,就过掉了.
正解:直接在上述思路上直接用背包,套个卷积就完事.
但是还要实现一个高精度,有点烦人.