思路 发现这道题时一个 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 我们会发现我们可以舍弃所有的截止时间为第一天的任务，而去做第二天和第三天的。 所以我们可…

题目描述 思路 我们可以把这道题的输入数据想象成一个一座山，有很多个山峰和山谷。 我们从左往右计算，如果正在上山，那么答案增加一。下山的时候，如果这个点在上山的时候已经出现过了，就不统计，只是消除比这个点高的点的记录（因外后面如果出现比这个点高的点，那么也不是这座山峰了），否则统计。 我们发现这个其实可以做成前缀和，如果想获得从第一个到第 $i$ …

题目链接：https://www.luogu.com.cn/problem/P11839 思路 由于我们看到了题目要求字典序最大，那么就是要求选的尽量大，宁愿抛弃一些，也要保证前面尽可能的大。 那么，我们可以想到把输入的数组按值从大到小为第一关键字，在原数组的位置从小到大为第二关键字，因为尽量靠前可以使得后面能接更多的数。 我们按照排序后的数组遍历…

货仓选址原题 给定在一个一维数轴上的多个点，请找出一个位置，使得这个位置和所有点的距离之和最小。 思路 这样的题目在学习数学数形结合的时候其实就学到了，也就是选择最中间的数。这个结论可以通过调整法证明。 证明 我们假设我们选择的数左边还有 $A$ 个数，右边还有 $B$ 个数。 一共有奇数个数 这个时候，由于我们选的数是最中间的数，也就是第 $\f…