P3515 [POI2011] Lightning Conductor
此处主要记录不用决策单调性的做法。
- 我们发现根号的取值是 \(O(\sqrt{n})\) 级别的。于是在每一个位置枚举根号取值然后在对应前后缀中查询 \(a_j\) 最值，这样算法是 \(O(n\sqrt{n})\) 的。
- 使用贡献法，对于每一个位置 \(i\) 考虑对别的位置的贡献，只需要在每一个根号值发生变化的地方打上标记即可。
- 优化:我们发现一个位置能对之后产生贡献的必要条件为这个位置的值大于之前的所有位置。这么一来在随机数据的情况下复杂度又下降为 \(O(n+\sqrt{n}\log{n})\)。
- 其实能产生贡献的位置更少，设序列最大值为 \(max\)，那么只有值域落在 \([max-\sqrt{n},max]\) 之间的数才能产生贡献。而且该数必须是第一次出现。这就把能产生贡献的规模降到了 \(O(\sqrt{n})\)，总复杂度为 \(O(n\sqrt{n})\)。
【PR #1】删数
其实数列是可以从左往右按顺序删除的，我们发现每次删除保留的是两边的数，也就是一个区间删完之后剩下的是左右端点，所以并不能通过左右各删一部分，使得左右边的某个数跨过了屏障相遇。这题还有区间平均数的不变性，所有剩下两个端点平均数为区间平均数不过好像没用。
部分分 \(a_i=i\)，直接奇偶删即可。部分分，\(a_i \le 3\) 挺有意思的，其实我们发现本来是不能遇到能删就删，但是这个部分分策略就是能删就删，因为如果有连续的三个不同的数可以被操作，也就是 \(1~2~3\)，我们发现左或右边的数无法被更左或更右的数删，因为它们已经是极值了。
部分分 \(n \le3000\)，其实虽然 \(\sum n \le 10000\)，但是单组数据 \(n\) 并不大，所有可以 \(O(n^2\log n)\)。易知区间删到最后就是两个端点，所以区间结果具有唯一性。于是设 \(dp_{l,r}\) 表示区间 \([l,r]\) 能否被操作，中间的分治点需要满足 \(a_{m}=\frac{a_l+a_r}{2}\)。观察性质，发现区间 \([l,r]\) 是单调的，二分寻找即可。
正解是考虑差分，这样就是合并相同差分并乘以 \(2\)。固定右端点，发现可以满足条件的左端点级别在 \(O(\log n)\)。这里有一个小技巧，我们发现呈 \(2\) 倍关系的差分值 \(\frac{d_i}{lowbit(d_i)}\)。
【NOIP Round #6】抉择
感觉这种优化到尽头还无法解决的 \(dp\) 就是要挖掘一下
部分分挺简单的，但是正解思路其实和特殊性质最后一档很想，二者的思想都其实是选更多的大概率会更优一点。我们来分析一下为什么不多选，比如选了 \(a_j\) 和 \(a_i\)，我们非要在其中插入的一个 \(a_k\)，那么可能 \(a_k\) 的很多位都为 \(0\)，导致我们损失了一些高位。这里给出一个结论也就是只要 \(a_i~and~a_j\) 与 \(a_i~and~a_k\) 的最高位相同即可，很明显最高位大于其他位之和。所以我们只需要对于每一位保存最近的即可。注意别忘记考虑按位与为 \(0\) 的情况。