题意：一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。若目标位于爆破正方形的边上，该目标将不会被摧毁。就是找一个边长为R的正方形使得val最大思路：二维前缀和板子题1.出于习惯，可以把目标范围改为。2.维护二维前缀和，表示式为：3.要价值最大，则正方形的可以取价值的面积最大是。3.枚举每个正方形，取最大值，取每个正方形价值的表达式为：，其实...

思路：贪心1.n个整数，字典序最大的在前面，很容易想到这个策略，但是有一组反例：3 31 39结果应该是39331，而不是39313。2.所以我们要改变策略，还是假定AB前面和后面已经有序了，而且AB不影响后面和前面的结果。3.要A排前面更优，就要AB的字典序比BA的字典序大。4.总的策略可以按照3的规则排序，然后依次输出就行。Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef lon...

思路：出现的数字在之内，又要排序又要去重，桶排序最合适了。1.出现的数字赋值为1，不管出现几次都是1，这就完成了去重。2.统计第一次出现的数字的个数就是去重后剩余的个数。3.从枚举，如果它的值为1，就输出，完成了排序。Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; int a[1005],cnt; int main() { js; int n,x; ...

思路：能暴力就先先一下暴力，题目差不多就会一半了。1.每次输入左右区间就把数组对应位置+1表示这棵树被移走，重复的部分多次+1不要紧，我们的结果是有多少个元素值是0。2.，好像不会超时，考虑更优的做法。差分+前缀和1.给一个区间加上一个值，我们只要考虑两个端点，中间的元素不需要考虑。2.前缀和，理解为第位的值比第位大。3，接着考虑区间赋值的问题，区间加上1，那么第L个位置比第L-1个位置大1，第R+1个位置比第R个位置小1，所以可以先预处理，最后再一遍前缀和得到最终的数组，里面0的个数就是剩余树的个数。想过离散化，挺有意义的，数据也不大，懒得写了，鸽了。Code: #include<bi...

思路：每一组最多两个礼品，贪心。1.如果枚举最小的礼品，要去找是否有礼品和它组队，而且枚举下一个礼品时还要判断是否组队了，比较麻烦。2.如果枚举最大的礼品，升序排序，如果最前面的礼品可以和这个礼品放一组，那么去掉这两个礼品，继续枚举下一个礼品。3.比较简单，代码会好懂些。Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; int a[30005],ans; int...

思路：看到这题我有想过前缀和、差分，但是后来发现，这题其实是个思维题，贪心也行吧。从先存完数据，然后从后往前枚举，遇到第一个囊括询问的点时就输出是第几个毛毯接着退出程序。Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; struct node{ int x,y,shang,you; }q[10005]; int main() { js; int n,x,y; cin>>...

思路：贪心+快排假设除了序列中相邻的两个大臣AB，其它大臣的位置都已经排好了。而AB的先后对前面和后面的结果都不会有影响，这里考虑A排前面最优的条件：左手数值用，右手数值用，表示AB前面大臣左手数值的乘积。1.A排前面时：,。2.B排前面时，,。3.。4.因为，所以不等式3需要满足，即。5.所以只要按每个大臣的左手乘右手值从小到大排序就能保证获得奖赏最多的大臣，所获奖赏尽可能的少。6.再找全部人的最大值即可。7.大数乘法+除法，，所以我被迫用py取巧。Code： n = int(input()) a,b = map(int, input().split()) ret = [] for i in...

题意：一个自然数最多可以分解成多少个不同的因子。 思路： 枚举题，主要在暴力的基础上减去不必要的枚举。1.因为n(1除外)一定存在一个小于的因子，所以枚举到因子枚举到就可以了。2.每找到一个因子就从n分离出来：3.当时，有两个一样的未出现的因子，那么只能把这两个因子合并为算作一个因子。4.当时，（假设x是上一个分解的因子）表示没有比x还大的因子对了，就是比如，需要a和b都大于x，不然分解出b后分解a时一定会重，因为a小于分解出来的一些因子，说明a的因子包括a，前面已经出现过了。5.所以如果，把他算作一个因子，不能再分解了。 Code： #include<bits/stdc++.h...

戳我传送 题意： 思路 求两个不连续的区间的最大和，很容易想到前缀和，[l,r]的区间和是sum[r]-sum[l-1]。朴素方法一个指针枚举左区间的起点，另一个指针枚举右区间的起点，两层循环复杂度 （n^2）,应该会超时。枚举右区间的起点时，可以发现左区间的起点不需要从1开始找，此时的最优解一定是左区间最大，而此时右区间左边全部的左区间已经出现过了，只要一直保存最大的左区间起点，在枚举右区间的起点时就可以 （1）的找到最优左区间起点。总复杂度 （n）。 Code； #include<bits/stdc++.h> #define ll long long using...

题意：n个糖糖排成一排，每个糖糖有一个能力值，第i秒第i个糖糖就会杀死前面能力比他小的人，进行m次区间加的操作，每次输入ci，表示第ci秒1~ci的糖糖能力值加一，输出最后有多少糖糖存活。 思路： 1.前m次操作可以用前缀和模拟区间加，得到每个糖糖的新能力值后从后往前维护每个队伍的最大值，当前糖糖的能力值如果大于后面敌对队伍糖糖的最大值，也就是比后面的糖糖都强，那么他存活，反之白给。复杂度 (n)。2.如果从前往后判断第i糖糖能不能存活，还要搜索后面i-1个糖糖，复杂度 (n^2)。3.刚开始没看懂题目看大佬博客，整了一个后缀和，一下愣是没看懂，看了2个多小时才看懂，你信？，大佬还提到扩展...

题目 题目描述：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 输入描述： 第一行为两个正整数n和b ，第二行为1~n 的排列。对于 30% 的数据中，满足 n≤100；对于 60% 的数据中，满足 n≤1000；对于 1100% 的数据中，满足n≤100000,1≤b≤n。 输出描述： 输出一个整数，即中位数为b的连续子序列个数。 思路： 1.子串中大于等于中位数的个数比小于中位数的个数多1。2.通常的做法是把大于K的数赋值为1，小于K的数赋值为-1。3.如果把等于K的数赋值为0，做法就是找到题目要求的K的...

题意：有n个建筑，每个建筑有修复时间和截止时间，只有一个工人，建筑之间移动的时间不计，最多可以让多少个建筑在截止时间前修复好。 思路：典型的“给程序留一个后悔机会”的贪心。 贪心可以考虑下面三种种策略：1.我最先想到的是先修复修复时间短的建筑a，但是可能它的截止时间很晚，而有一件截止时间很早的建筑b，做了a会导致不能修复b，而如果先做b不会耽误修复a，这时这个贪心不成立。2.按照最晚开始修复的时间（截止时间减修复时间）早晚来做，可能有一件事最晚开始修复的时间很早，但是它的修复时间很长，在这之间完全可以做两件比他开始时间晚的事，这时这个贪心不成立。3.按截止时间早的先做，但是会有一个问题，这...

题意： 给n种货币，每个面值ai​，数量无限，是否能去掉几种货币，使得原本这几种货币能组成的数仍能组成是否能去掉几种货币，问最后最少能剩下多少货币。 思路： 1.打算化简一下货币系统，其实就是去掉几种货币，说明剩下的货币能表示被减去的货币。2.最小的不能去掉，因为其它的货币表示不了面值最小的货币，但是面值最小的可能表示其它面值的货币。3.能组成某一种某种值的一定是一种或多种面值比他小的货币共同组成他，一个或多个数的和能组成的数，这不就是01背包。3.所以接下来就是第二小的货币，如果他是第一小的货币的倍数就不需要，不是就存进背包里。4.接下来就是第三小的货币，如果他能由前面的货币组成就不需...

题意： 给定一个数列，找出这个数列中长度为偶数的连续子列的异或和并且要求长度为偶数的同时满足在到之间最后结果 思路： 异或一般是是枚举每一个数每个二进制位的贡献1.这道题需要考虑的是一个连续子列，我们可以维护一个前缀和 cin>>a[i],a[i]^=a[i-1];2.那么枚举每个前缀的二进制位，看在某一个二进制位上这个前缀前面的个前缀有多少个是与他相反的前缀，然后每一二进制位综合起来乘上权值就可以算出来不考虑偶数限制的结果。 c[(a[j]>>i)&1^1]*(1ll<<i)//不考虑偶数限制，也就是不考虑第一维表示右端点到左端点+1这个点（...