链接 & 题目大意 算法 & 数据结构 差分、单调队列 思路 & 推导过程 暴力 1 注意到我们可以直接模拟，但是这样的话复杂度很难优化，没有前景，需要考虑换一个暴力。 暴力 2 注意到我们需要统计每秒牛奶的浪费，所以可以想到一个奶牛在 $k$ 秒后传入的牛奶是前 $k$ 个奶牛容量的最小值，而只有当这个最小值大于当前奶牛容…

链接 & 题目大意 P6146 Help Yourself G 算法 & 数据结构 计数，DP 思路 & 推导过程 首先可以考虑如果把一个线段加进去会出现什么事情。 我们先想到可以考虑 dp[i] 为包含第 i 个线段的答案为多少，但是发现这样会算重，很难处理。 那只能换个思路，也就是令 dp[i] 表示加了这个线段后的答案…

思路 90pts 注意到 $O(n^2)$ 的暴力的能得到 90pts，不妨先考虑一下这个该怎么写。 我们可以考虑 dp，令 dp[i] 为到 i 的时候的最少的答案。 我们可考虑要从 dp[j] 扩展到 dp[i] 只有两种方法，第一种方法也就是在最后一次买东西的时候把羊毛都没买好，后面的直接走到目的地就行了。 第二种方法，就是在走到 j 后走回…

思路 发现这道题时一个 RMQ 区间求最值的题目，我们可以求出每个位置的左边 $D$ 包括的数的区间，和右边的区间，注意如果 $D = 4$，$5$ 和 $9$ 其实是在一个区间内的，然后可以算出区间最大值，再用这个最大值和 $2 \times h$ 去比较。 区间最值可以用 ST 表去做，也可以用单调队列去做。 代码 /* problem : b…

思路 这道题其实就是一个暴力模拟，但是细节极其的多，很**。 我们可以把每个奶牛编码为一个混进制，这样如果我们要获取第 $x$ 个，我们就可以直接把 $x$ 从十进制转换为混进制，然后记录每一位的每个数对应的单词，就可以得出答案了。 注意由于题目给定了不能出现的奶牛，那么我们需要对输入的 $k$ 进行处理，算出 $k$ 实际上时编号为多少的奶牛。 …

根号分治的本质就是结合两个暴力，使得复杂度得到了均摊。 题目：Problem - 1207F - Codeforces 现在有两种暴力，第一种是根据题目模拟，修改操作时间复杂度 $O(1)$，查询操作时间复杂度 $O\left( \frac{n}{x} \right)$。 第二种暴力是针对查询操作优化的，也就是定义 $b$ 数组为下标模 $i$ 的…

思路 由于题目中给出了所有 $x$ 都不相同，所有的 $y$ 也不相同，那么我们发现，只有两个不同方向的奶牛才有相交的可能。 所以，我们为了方便，在输入的时候直接把奶牛给分成两组，然后两层循环遍历一下，记录所有有可能发生的路径相交。 由于奶牛只往右或者上走，所以对于一直奶牛，最靠左下的那一次相交时最先发生的。 然后就可u有直接计算了。 代码 #in…

思路 由于确定一个矩形后这个矩形里面有哪些奶牛是确定的，而且如果确定矩形的上下左右的边的位置，这个矩形就是确定的，所以这道题就改为计算有多少个不同矩形，使得每个矩形里面至少有一个一个奶牛，而且每个奶牛是在矩形的边上的（用来防止多个矩形内的奶牛一样）。 那么，我们可以先枚举两个奶牛确定两个奶牛作为上下两条边。然后可以计算出靠左边的奶牛的左边有多少奶牛…

思路 我们可以想到，每次在一个点翻倍到足够把子节点都覆盖的时候传播到子节点，至于传播后多余的有两种情况，一种情况是传输到子节点，使得子节点的翻倍数量减少。但是实际发现这样是不现实的，因为传输需要用的时间比翻倍需要用的时间更多（可以感性的理解一下，因为具体的证明我也不会） 代码 #include <bits/stdc++.h> using…

题目描述 思路 我们第一步应该想到优先做截止时间靠前的任务，所以我们按截止时间从小到大为第一关键字，收益从大到小为第二关键字。 但是这个时候，有一类型的样例有可能会 hack 掉这个做法： 7 1 2 1 3 2 5 2 7 3 10 3 11 3 12 33 我们会发现我们可以舍弃所有的截止时间为第一天的任务，而去做第二天和第三天的。 所以我们可…