wo2011qwq

摘要： 四月做题记录 5.3 AT_arc218_b 比较简单的博弈题，其实样例把所有情况都告诉你了。（除了初始的 \(0\)）。 先看开始的 \(0\)，如果有多个，则 Alice 可以任选先后手（留 \(0/1\) 个 \(0\)），则 Alice 必赢。 否则如果有一个，交换先后手。（后面就都说先后手 阅读全文

摘要： 数列分块入门 1 其实线段树和树状数组都可以做，但是毕竟是在练习分块。 分块，顾名思义把数组分成若干块，这里特指分成 \(\sqrt n\) 块，每块长 \(\sqrt n\)。 分块的修改非常暴力，如果一整块都在要修改的区间里，那就一起打个 tag，否则暴力单点修改。 对于整块的修改，一次最多 \ 阅读全文

摘要： 三月做题记录 4.4 P8251 比较显然的是一个数在整个序列里能把前面的弹到哪里，在子串中也可以，要是子串不包含到那里那就肯定可以弹到头。单调栈预处理一下，离线 + 树状数组。 AT_abc452 D DP，写成史了。 E 推式子，把 \(a\bmod b\) 换成 \(a-\lfloor\fra 阅读全文

摘要： 二月做题记录 3.1 CF2171H 神秘 DP 题。令 \(f_{i,j}\) 表示填到第 \(i\) 个点，填的是 \(i+j\) 时的最大值。那么显然有 \(f_{i,k}=\max_{j=0}^{k}f_{i-1,j}+v(i,i+k)\)。 先枚举 \(i\)，然后枚举 \(i+j\)。\ 阅读全文

摘要： 一月做题笔记 2.1 P4556 复习线段树合并。 P4979 复习珂朵莉树。 P3605 依旧线段树合并板子。 2.2 P4097 李超线段树板子。 P3224 线段树合并板子，但是多了个并查集。（猜猜我为什么以前没用平衡树写过这题） P5494 线段树分裂板子，和合并差不多。 CF1009F* 阅读全文

摘要： 区间问题的一种暴力方法就是从一个区间到另一个区间时，把左右端点分别一个点一个点地挪过去，但是这样显然是 \(\text{O}(n^2)\) 的。莫队就是通过离线这些区间然后用特别的排序方式使得这个暴力的复杂度降至根号级别。 建议边看边画图，便于理解。 普通莫队 把数组分成 \(\sqrt{n}\) 阅读全文

摘要： 老师给的数据结构题单里出现的，会的同学教了一下。没有想象中的难。 思路 基础的珂朵莉树其实就是用 set 维护一个数组上的连续相同区间，每一个区间用一个结构体表示。 struct node { int l, r; //区间左右端点 mutable int v; //区间里每个数的值 friend b 阅读全文

摘要： 12 月做题记录 1.2 CF1638E 新年第一题。发现第一种操作和珂朵莉树的 assign 很像，考虑用珂朵莉树维护。 对于第二种操作，可以打懒标记，表示某种颜色加了多少。 那么在做第一种操作时，我们就需要把原来的懒标记给处理了再变色，并且变色后还需要减去这个颜色的懒标记以保证答案正确。 处理懒 阅读全文

摘要： 11 月做题记录 12.2 P14636(NOIP T2) 补一下 NOIP T2。 首先观察样例加推一推我们会发现题中人物的贪心不对的情况只有一种，他选了一个 \(w=1\) 的原价 \(a_i\) 的物品，然后在选 \(w=2\) 的原价为 \(a_k\) 的时候只剩 \(1\) 元，只能选 \ 阅读全文

摘要： 10 月链接 11.1 CSP，炸了。 S-T1(P14361) 先让每个人选自己最大的，然后在人数最多的那个选项中，选择一些人换选项。把换选项造成的损失放在一起排序，选最小的若干个。记录一下一个人的两种损失不同时选。 S-T2(P14362) 错解（CCF 没卡），洛谷上能过：先把所有边扔到数组里 阅读全文