Loading...
题面 https://www.luogu.com.cn/problem/P3572 题解 首先，不难列出方程：$f[i]$ 代表跳到 $i$ 的最小疲劳值 时间复杂度为 $O(qn^2)$，不理想。但是不难发现，这道题可以用单调队列进行优化。为什么？ 如下状态一定是更优的：随着 index 递增 $f$ 不下降（第一维比较） $f$ 若相同，同时有 $a$ 不上升（第二维比较） 所以我...
Preface 三年前的四月，第一次接触 OI。初三下，小教室里听着 fcx 讲着滑动窗口单调队列，放学后去本部蹭了第一节斜率优化的课，随即拉开了我长达两年的竞赛摆烂之旅。 记忆犹新。第一个注册的 OJ 账户就是 POJ，第一道 AC 的题便是 POJ 2823 滑动窗口。 多年过去，今天再看这个基础中的基础，茫然。只能说这是究极摆烂的下场罢。总之就好好写一下题解。 题面 https://w...
Preface 好耶，少见的难题。 题面 https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/ 题解 大部分题解已经提到了：就是下面这个结论。 结论：最终构造出来的数列以 $k$ 为一个周期 证明： 由题设： 按照之前说的贪心，我们会选保留 $b, d$，然后第三列适应答案使得异或为 $0$...
题面 https://www.luogu.com.cn/problem/P2210 题解 一开始没反应出来是状压，看了少数题解才知道可以状压。今天姑且 A 掉状压的写法，明天写写看模拟退火。 首先，我们来设状压的状态方程： 好。赘述完关于状态的定义，我们来思考状态怎么转移。对于集合 $i$，我们可以枚举位于队列尾端的到底是哪头牛。每次转移我们只需要加上原来的集合中孤立朋友的数量即可。最终给...
题面 https://leetcode-cn.com/problems/reaching-points/ 题解 就是一道思维题。看一下数据范围：$1e9$，正做肯定是不行的。借鉴小升初时候的失败经验，这题必然是从后往前推。怎么从后往前推呢？很简单： 但是，如果直接这么做还是会 WA，因为最终结束的答案可能并不是 $x \bmod y$，而是 $x \bmod y + ny$，所以我们在计算...
Preface 被录取的喜悦冲昏了头脑，停了几天跳题，今天又开始跳了。 题面 https://leetcode-cn.com/problems/split-array-with-same-average/ 题解 一开始做的时候想假了，一眼就觉得是普通的子集和，就是说看能不能找到一个子集使得和为一个定值。写了一发才发现这题目说的是均值。 但是问题不大，因为 $n$ 很小，所以我们可以枚举所有的...