题目链接 大意：给你n个气球位置，现在你可以水平，竖直取至多三排，三列的气球，且每次相邻的行，距离不超过k，列也是如此 思路：我们按列(每个列号有三个列的贡献)建线段树，然后从小到大遍历最小的行，然后更新在这三行的列。然后查询直接查最大值即可。（注意要撤回更新操作） 细节见代码： #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; LL gcd...

题目链接 大意：给你两个字符串a,b.a是可以无限复制的，现在让你找到一个长度使得这个长度的a串存在一个b的子序列。 思路：如果a字符串包含所有的b中字符，那么必然有解。我们先跑一个a的序列自动机出来。然后每次贪心的匹配b串的字符，如果需要加上a串就加上，否则跳到下一个匹配的位置即可。 #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; ...

题目链接 大意：给你一个矩形区域， ( ( 0 , 0 ) − ( n , ...

题目链接 大意：给你一系列的数字，让你用若干个10,20,50,100的某个组合，可以组合出任意一个数字 思路： x y q xyq xyq聚聚说这个是签到题，但是自闭一场我都不会做，呜呜呜 分析一下，给你数字若个位数非零则显然无解。 然后对有解的情况进行判断一下： 我们来枚举10 20 50分别使...

int dp[N + 33][21]; void RMQ() { for (int i = 1; i <= n; i++) dp[i][0] = i; for (int i = 1; (1 << i) <= N; i++) { for (int j = 1; j + (1 << i) - 1 <= N; j++) { dp[j][i] = a[dp[j][i - 1]] >= a[dp[j + (1 << (i - 1))][i - 1]] ? dp[j][i - 1] : dp[j + ...

题目链接 思路： 设 f [ i ] [ j ] f[i][j] f[i][j]为范围在1-800内 模i为j的所有答案 然后对每个修改操作直接改，然后...

题目链接 大意：给你一个1-n的排列，然后支持两种操作 l ,给x这个位置加上1e7 l r,询问1-r位置上没出现过且大于等于r的最小值 思路：我们建一颗权值线段树，维护区间元素的最大位置； 首先答案肯定在1-n+1中，所以对于修改操作来说 直接单点修改成一个极大的值。 询问操作我们直接询问r-n+1的元素出现在>l位置中的最小元素即可。 因为是最小值所以我们在递归的过程中，先搜小的，搜到就直接返回即可，不然会超时。 细节见代码 #include<bits/stdc++.h> #define fi first #define se second #def...

题目链接 大意：给你n条鱼每条鱼需要煮的时间，和抓一条鱼的时间k， 你每次只能抓一条鱼，煮一条鱼，问你最少多久煮完所有的鱼。 思路：显然我们必须花k的时间抓第一条鱼，而且煮鱼的时间是不能减少的，问题就是我们需要浪费多长时间， 那么如果煮鱼的时间可以抓完所有的鱼，那么我们就不需要浪费时间，煮鱼时间内我们可以抓 ∑ a i ...

题目链接 大意：给你一张有向加权图，让你求出第k小的路径 思路：显然我们从大到小处理到最大的询问就可以了。 先对所有点的出边按权值从小到大排序，然后塞到优先队列中，每次取出队头最小的元素更新答案，但是如果直接遍历点所有出边的话是会tle的，我们需要一个multiset来记录优先队列中的答案，如果multiset的元素等于最大的询问的话，那么我们只要更新到一个出边，使得这个路径长度和大于multiset最大的元素的话，我们就直接break出去，不然就更新multiset。 细节见代码： #include<bits/stdc++.h> #define fi first #defin...

题目链接 大意：给你一棵树，让你求出多少对 ( l , r ) (l,r) (l,r)，使得存在两条长度为 l , ...

题目链接 大意：两个人玩游戏，每回合一方可以放另一方没有放过的卡，谁最后没卡放谁输 思路：每回合，出卡的人肯定要出场上最多的卡，这样可以使自己尽量多或者别人尽量少 细节见代码： #include<bits/stdc++.h> #define LL unsigned long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; LL gcd(LL a,LL b){return b?gcd(b,a%b):a;} LL lcm(...

题目链接 大意:让你求满足题意的区间个数 思路：先跑一遍rmq，记录区间最大值下标，预处理每个点最左到左边哪个点，最右到右边哪个点，使得这段区间没有重复。 然后就直接分治，每次分治的区间先求出最大值下标，然后对小的一边for扫一遍求出符合的区间然后更新答案即可。 细节见代码 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair #define LL long long #define SZ(X) X.size() #define p...

题目链接 大意：给你一个n*n的矩阵，让你求出面积最大的矩形，使得矩形内极差小于等于k 思路：我们枚举矩形上下界，然后遍历右边界，维护每列的最大最小值，同时维护两个个下标递增，值分别递增和递减的单调队列，每次弹出不合法的队头元素，然后更新答案即可。 细节见代码： #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair #define LL long long #define SZ(X) X.size() #define pii p...

题目链接 大意：给你一个数组，让你求出有多少个合法的区间。 合法区间定义为：每次选择两个元素同时减1，若能都减为0即为合法，特别的，如果区间和为奇数时，可以选择一个值最小的使他减1. 思路：转换一下问题就是，让你求多少个区间，使得区间的最大值不大于区间和的1/2，（向下取整）。 那么我们可以分治做，先跑一个rmq，记录最大值下标，然后分治一个区间，每次分治的区间，先求出他的最大值下标，然后扫小的那一边，再二分另一边的最大/最小范围，然后统计答案即可。 细节见代码： #include<bits/stdc++.h> #define fi first #define se secon...