如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
大概应该改成第 inf 次学习笔记才对（
LuoguLOJ分析先考虑没有 $o$ 的限制怎么做。可以想到贪心，把房间按容量小到大排序、订单按人数从小到大排序，然后依次枚举每个房间，选择能容纳的租金最高的那个订单。正确性比较显然。现在加入这个限制，可以考虑 WQS 二分。设 $f(x)$ 表示接受 $x$ 个订单的最大收入，感性理解可以知道 $f(x)$ 是凸的。二分斜率 $m$，则我们要求最大的 $b=f(x)-mx$，而这个东西可...
Luogu分析不难看出一个最大权闭合子图的模型，然而直接求最大流显然过不了，于是可以考虑模拟最大流。首先把这个坐标系变换一下。如果警卫 $a$ 能看到手办 $b$，则应有于是可以把 $(h\times x+w\times y,h\times x-w\times y)$ 作为每个点的坐标，这样子警卫 $a$ 能看到手办 $b$ 当且仅当 $x_b\leq x_a,y_a\leq y_b$。考虑...
CodeforcesLuogu分析考虑一个贪心，即每次取贡献最大的一个，这里的贡献是 $k_i\times a_i+b_i$，其中 $k_i$ 表示前面选了的数量，$b_i$ 表示后面选了的 $a_i$ 的和。那么我们相当于要维护一些直线，支持区间斜率加、截距加和求全局最大值。考虑分块，对每块维护一个上凸壳，散块修改后重构、整块打标记即可。注意要把当前选出来的数删掉。代码// =======...
UVaLuogu分析其实写这篇只是为了纪念一下写的第一道大模拟（暴力模拟就好了，查询都直接暴力扫一遍，因为输入只有 10KB 所以根本不要担心 TLE。我是用 std::vector 维护的所有学生，这样子在删除时可以和最后的元素交换一下然后 pop_back。代码除了奇妙的换行之外也没啥细节。代码打表一时爽，一直打表一直爽// ===============================...
CodeforcesLuogu分析设 $dp_{i,j}$ 表示前 $i$ 个数，第 $i$ 位填 $j$ 的方案数，$s_i$ 表示 $\sum_{j=1}^k dp_{i,j}$，$len_{i,j}$ 表示第 $i$ 位往前最多有多少位为 $j$。转移时讨论一下。当 $len_{i,j}<l$ 时 $dp_{i,j}=s_{i-1}$；否则要减去超长的那一部分，即为 $dp_{i...
Luogu分析显然一个置换的步数就是它所有环长的 $\operatorname{lcm}$。于是问题变为求有多少个数 $n$ 的某个拆分中所有数的 $\operatorname{lcm}$。考虑 DP。设 $dp_{i,j}$ 表示 $i$ 拆成若干个最大质因子 $\leq p_j$ 且不为 $1$ 的数时的答案，不难得到转移答案即为 $1+\sum_{i=1}^n dp_{n,|\math...
CodeforcesLuogu分析考虑莫队，维护区间内每个数的出现次数，然后询问时建一棵 Huffman 树即可。然而暴力建树是 $\mathcal{O}(n)$ 的，显然过不了。考虑根号分治，并维护出现次数为 $i$ 的数的个数，这样子对于出现次数 $\leq B$ 的数，可以直接 $\mathcal{O}(B)$ 扫一遍合并；对于出现次数 $>B$ 的数，显然只有 $\frac{n...
Festival考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。考虑无解的情况。一种情况是出现负环，另一种情况是出现一个全是...
LuoguLOJ分析因为 IP 地址可以看做长度为 $32$ 的二进制串，所以可以考虑用 Trie 树维护。考虑查询。可以发现一个 IP 地址的匹配最大明确度是单增的，因此求出链上修改时间的单调栈即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.co...