2022/03/27 做题记录

【51Nod1386】双马尾机器人

题意等价 $n$ 以内的每个质因子恰好在一个数内出现，考虑每个数最多有一个 $> \sqrt n$ 的质因子，所以对于它们我们必须每个选一个对应的数，这部分可以先记入答案，而 $\le \sqrt n$ 的质因子在本题只有 11 个，可以考虑状压下来，dp[s] 表示选的质因子状态为 s 的时候最少选几个最小质因子 $\le \sqrt n$ 的数，转移时对于最小质因子 $> \sqrt n$ 的数我们把它的质因子记入状态但并不计数（因为它们的贡献之前统计过了）。

error

不太明白为什么这样不会导致两个数出现同样的 $> \sqrt n$ 的质因子，也许可以通过类似调整的方法证明（？

code: /code/2022.3.27/10493.cpp

【BZOJ3261】最大异或和

转化为前缀和，然后就是可持久化 trie 模版

code: /code/2022.3.27/bz3261.cpp

【HEOI2013】Alo

我们设一个数左边第一个比它大的为 $l_1$, 第二个为 $l_2$，右边第一个比它大的为 $r_1$，第二个为 $r_2$，如果不存在设为 $0/n+1$。

那么一个数作为次大值的区间会覆盖 $(l_2,r_2)$ （这里一开始想多了，这个区间和 $l_1,r_1$ 是否存在无关）。

因为 $l_1$ 可能大于 $l_2$，所以它们并不是单调栈的前两个数，可以维护一个双向链表，每次删除最小的数，这样往前找的前两个就一定是 $l_1,l_2$，右边也同理。

最后可持久化 trie 查询即可。

code: /code/2022.3.27/P4098.cpp