这题的思路和https://ac.nowcoder.com/acm/problem/50439 类似在我们看来，每一段都存在一个截至区域，首先肯定是要把截至区域按从小到大的顺序排列，这样之前的选择会为后面的选择腾出更多的时间，这个贪心就是可行的。既然所选需要最多，有些我选择过后，如果当前总和小于截至日期，直接选择，但是后期选择的时候你会发现个问题，如果你选择当前的，结果后期的修理时间比他小的值可能无法在截至日期前完成，那么就会缩小选择区域，那么我们可以用后者替换当前已选择的最大修理时间那个，因为截止时间从小到大排列，把修理时间多的改为少的，可行性会更优。所以我们只需要弄个优先队列，每次找出已选...

写过括号匹配这种题就很容易想到用栈来解决此类问题首先要理解栈是什么，它是一种线性表你可以将它理解为一个容器 但他只能从栈顶出，栈顶入，后进先出实际定义（来自百度百科）：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 头文件：#include<stack>定义：stack<类型(例如int)>a删除栈顶...

题目大意：给定一个长度为n的序列，找出一个最短的子序列使其之和大于等于s我也就来摸摸鱼，尺取+前缀和弄一个双指针分别对前缀进行处理sum[i]代表前i项之和 要求i-j的子序列 只需要sum[j]-sum[i-1]即可接下来只要运用尺取法 在保证当前子序列之和大于等于s的情况下移动左指针一旦小于移动右指针，这样就可以比较每个满足的区间  #include <iostream> using namespace std; const int maxn=5e5+7; const int inf=0x3f3f3f3f;///防大数 int a[maxn]; int b[maxn]; int...

题解写重了 参考https://blog.nowcoder.net/n/62b1d5cfab0647cbae38a868fdd0e713本题图片说明按上图设置M[i][j]记录以（1，1）为左上角端点 以(i,j)为右下角端点的矩形大矩形=红色矩形+青色矩形-黑色重叠矩形+（i，j）点的数值不难发现 按M[i][j]=M[i-1][j]+M[i][j-1]-M[i-1][j-1]+a[i][j]前缀即可接下来直接枚举左上角(i,j)边长为k的正方形M[i+k-1][j+k-1]-M[i+k-1][j-1]-M[i-1][j+k-1]+M[i-1][j-1]注意细节 比如边界  #include...

由于存在区间包含的关系，被包含的小区间满足时大区间也一定满足。把所有区间按照右端点从大到小排序。如果右端点相等，按照左端点从大到小排不妨想想，取哪个点由于右端点是从小到大，可以取最上面那个区间的右端点1.如果后面区间的左端点小于该区间，那么就是包含，就一定取得到2.如果后面区间的左端点大于该区间，依然被取到此时取得的区间最多 #include <bits/stdc++.h> using namespace std; const int maxn=5e4+7; const int inf=0x3f3f3f3f; struct node { int x,y; }a[maxn]; boo...

这么经典的题目没人写题解（我来水一波）  题目大意：牧场有N头牛，每头牛都有它喜欢的放牧区间[si,Ei]大多数人都知道母牛很自私。没有牛愿意与其他人共享任何放牧区域。因此，如果Si> = Ej或Ei <= Sj，则两只母牛i和j只能同时放牧。FJ希望知道给定的一组奶牛可以同时放牧的最大奶牛数量及其偏好。  看得很清楚了，就是找到最多不重复子区间，在这之前就要好好想一下贪心策略我们可以首先让Ei按照从小到大的序列排序接下来只需要讨论Ei的情况  E1<E2 此时s1>s2 不难看出，第二个区间包含第一个区间 这样一来，我们肯定选取区间小的那个，这样会为后面的牛有更多的选...

这数据O(n^2) 模拟 ，我不想tle看区间，区间覆盖的贪心，多想想，人总是贪心的  思路： 不妨把左端点从小到大排序，此时就是把覆盖的区间进行合并 比如合并过后区间是[l1,r2]但要注意像下面这种情况 第一个区间包含第二个区间 此时我们就无需改变右指针所以right=max(a[i].r,right);  #include <bits/stdc++.h> using namespace std; #define ll long long const ll maxn=5e7+5; struct node { ll l,r; }a[maxn]; bool cmp(node p,n...

铺矩形地毯既然前一张会被后一张所覆盖 那么不如直接按照反方向的顺序直接找到最后一张地毯（一年前的代码，缩进比较尴尬） #include <iostream> using namespace std; int a[100000][4]; int main(){ int n; cin>>n; for (int i=0;i<n;++i) { cin>>a[i][0]; cin>>a[i][1]; cin>>a[i][2]; cin>>a[i][3]; } int x,y; cin>>x; cin>>...

很明显就是一道关于背包的贪心问题那么根据贪心策略 固定容量的背包，装多样物品，使得背包数最小首先把大的装入背包，如果能匹配到一个最小的，他们的和小于容量就是优解 因为之前的最小的，会为后面稍大的提供空间，否则剩余的会超出容量达不到最优（我记得紫书上有讲） #include <bits/stdc++.h> #define ll int using namespace std; ll a[30010]; bool vis[30010];///标记数组 int main() { ll we; cin>>we; ll n; cin>>n; for (int i=0;...

题目描述   给出1-n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元>素从小到大排列后，位于中间的数。  输入描述:  第一行为两个正整数n和b ，第二行为1~n 的排列。对于 30% 的数据中，满足 n≤100；对于 60% 的数据中，满足 n≤1000；对于 1100% 的数据中，满足n≤100000,1≤b≤n。输出描述:输出一个整数，即中位数为b的连续子序列个数。直接暴力o(n^3) 铁定tle可以想见应该是思维转化的题目 中位数在排序过后比他大的个数和比他小的个数相同具体数值对题目没有影响 所以将小于k的数值改为-1 大于k的数值改为1左...

不仔细理解，害，看了半天就是连通块（你会不会这个算法和你能不能凑看出来是两码事）3*3的规模 在大炮的外围一圈内如果也有大炮就会波及，此时就连通起来了既然如此可以用dfs找出各个连通块及其所含有的大炮数量当然由于小齐先手攻击 它所要面对的司令的连通块个数减一（当然最后小齐炮的个数为0，虽说他为先手，没炮怎么打（wawa大哭））所以只要小齐的连通块个数大于等于司令的就可以最后结果来贪心 小齐剩的的炮要多，则用含有少的炮的连通块抵消司令的连通块 #include<bits/stdc++.h> using namespace std; char a[10][105]; int l[8]=...

一道很经典的题目 每次想到是否能不能用前缀和，要考虑前缀和处理出来的数据怎么简化判断，或者能不能判断 既然该题解决的是0和1的有关问题 不难发现如果该正方形不存在1，则其总和为0 ，如此一来，就解决了判断的问题，使用二维前缀数组 按上图设置M[i][j]记录以（1，1）为左上角端点 以(i,j)为右下角端点的矩形大矩形=红色矩形+青色矩形-黑色重叠矩形+（i，j）点的数值不难发现 按M[i][j]=M[i-1][j]+M[i][j-1]-M[i-1][j-1]+a[i][j]前缀即可接下来直接枚举左上角(i,j)边长为k的正方形M[i+k-1][j+k-1]-M[i+k-1][j-1]-M[i...

一维数组不好储存先后位置 所以用二维数组nt[i][j]记录当前位置i后面最靠近字母j的位置后缀一下，从后往前记录 特例由于 nt[i][a[i]-'a']=i; 记录的是它本身的位置所以后面查找成功后位置加一 d=nt[d][b[j]-'a']+1;否则遇到相同连续字符会一直在该位置上逗留 #include <bits/stdc++.h> using namespace std; const int maxn=1e7+7; string a; int n; int nt[maxn][30]={0}; int main() { getline(cin,a); cin>>...

后缀数组写起来简单，理解也比较简单。如果在原来的基础之上发功，就算开始发功的人收益但当后续的发功结束后该来的终究会来，之前小于他的糖糖也会被灭掉，所以从后往前是可以的，还容易维护一些 #include <bits/stdc++.h> using namespace std; #define ll long long struct node { ll a,b; }m[50007]; ll c[1000007]={0};///后缀小数组 int main() { ll t; scanf("%lld",&t); while (t--) { ll n,w; memset(c,0,s...