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$,我们可以枚举位于队列尾端的到底是哪头牛。每次转移我们只需要加上原来的集合中孤立朋友的数量即可。最终给...
Preface 被录取的喜悦冲昏了头脑,停了几天跳题,今天又开始跳了。 题面 https://leetcode-cn.com/problems/split-array-with-same-average/ 题解 一开始做的时候想假了,一眼就觉得是普通的子集和,就是说看能不能找到一个子集使得和为一个定值。写了一发才发现这题目说的是均值。 但是问题不大,因为 $n$ 很小,所以我们可以枚举所有的...
Preface 做了一道可靠大仙贝给的 SJTU 巴院的题。出题人 ****** 啊。题目表述不清。smallest to largest 不是 size 而是 index,所以这句话有什么说的必要吗😅。 题面 DescriptionIn modern data centers, people often use tape drives to store large amounts of d...