题目链接 大意：给你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(LL ...

题目链接 大意：给你两个字符串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; LL gcd(...

题目链接 大意：给你一个矩形区域，     (   (   0   ,   0   )   −   (   n   ,   m   )   )    ((0,0)-(n,m))   ((0,0)−(n,m))，现在有k条直线，每条直线都是从一个点出发到上下左右四个方向之一。 问你这个区域被分成了多少块。 思路：稍微观察即可发现，分成的区域等于直线交点个数+1。 我们对     L   ,   R    L,R   L,R方向的对纵坐标分开离散化建立主席树（横坐标放一起离散化），然后每次遍历     U   ,   D    U,D   U,D方向的直线来在主席树上查询。 设当前横坐标为x 方向...

题目链接 大意：给你一系列的数字，让你用若干个10,20,50,100的某个组合，可以组合出任意一个数字 思路：      x   y   q    xyq   xyq聚聚说这个是签到题，但是自闭一场我都不会做，呜呜呜 分析一下，给你数字若个位数非零则显然无解。 然后对有解的情况进行判断一下： 我们来枚举10 20 50分别使用多少个。 题解如下：  然后就暴力判断是否可行，然后整百的部分直接用1美元代替即可 细节见代码： #include<bits/stdc++.h> #define LL long long #define fi first #define se second ...

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 + (1 << (i - 1))][i...

题目链接 思路： 设     f   [   i   ]   [   j   ]    f[i][j]   f[i][j]为范围在1-800内 模i为j的所有答案 然后对每个修改操作直接改，然后如果x<=800的话直接更新一下f。 对于每个询问操作，小范围直接输出f[x][y]，大范围直接暴力即可 因为每次操作处理最多是800的 所以复杂度可以保证 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair #define LL lon...

题目链接 大意：给你一个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 #define pb p...

题目链接 大意：给你n条鱼每条鱼需要煮的时间，和抓一条鱼的时间k， 你每次只能抓一条鱼，煮一条鱼，问你最少多久煮完所有的鱼。 思路：显然我们必须花k的时间抓第一条鱼，而且煮鱼的时间是不能减少的，问题就是我们需要浪费多长时间， 那么如果煮鱼的时间可以抓完所有的鱼，那么我们就不需要浪费时间，煮鱼时间内我们可以抓     ∑     a   i    k     \sum\frac{a_i}{k}   ∑kai​​ 如果     ≥   n   −   1    \geq n-1   ≥n−1，那么我们不需要浪费时间，否则少一条我们就要浪费一点时间去抓，那么我们把煮鱼时间对k取模从大到小排序取就行了...

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

题目链接 大意：给你一棵树，让你求出多少对     (   l   ,   r   )    (l,r)   (l,r)，使得存在两条长度为     l   ,   r    l,r   l,r的链且他们不相交 思路:我们直接枚举边，每条边将一棵树分成两颗，求出两棵树的分别直径即可。 具体操作是： 先以1为根，记录每个节点的最长向下延申长度x，和子树内前三大的x,然后就可以计算出过当前节点的最长链了， 每个节点记录子树内前三大的最长链。 然后就直接换根统计答案即可，把旧根的贡献给新根，更新新根的信息，注意一点就是旧根的最长链(不包含新根)也要传递给新根。剩下就没什么坑了 #include&lt...

题目链接 大意：两个人玩游戏，每回合一方可以放另一方没有放过的卡，谁最后没卡放谁输 思路：每回合，出卡的人肯定要出场上最多的卡，这样可以使自己尽量多或者别人尽量少 细节见代码： #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(LL a...

题目链接 大意:让你求满足题意的区间个数 思路：先跑一遍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 pii...

题目链接 大意：给你一个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 pair&...

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