Week5 W（A - 最大矩形）（B - TT's Magic Cat）（C - 平衡字符串）（D - 滑动窗口）

A-最大矩形

题意

思路

维护一个递增单调栈，从左到右遍历矩形，空栈或者矩形高大于栈顶矩形的高，入栈，否则计算栈内矩形各自的最大面积（设当前栈顶的高为最高的高度）

代码

#include<iostream>
#include<stack>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
using namespace std;

const int maxn = 100005;

int n, cnt;
llong a[maxn];
llong s[maxn];
llong ans;

int main(){
	ios::sync_with_stdio(0);
    while(cin>>n){
    	if(n==0) break;
	    For(i,1,n) cin>>a[i];
	    ans = 0; cnt = 0;
	    For(i,1,n+1){
	    	a[n+1] = 0;
	    	if(!cnt || a[i]>a[s[cnt]]){
	    		s[++cnt] = i;
	    	}
	    	else{
	    		while(cnt && a[i]<=a[s[cnt]]){
	    			int t = s[cnt--];
	    			int l = 1;
	    			if(cnt) l = s[cnt]+1;
	    			int r = i-1;
	    			ans = max(ans, a[t]*(r-l+1));
	    		}
	    		s[++cnt] = i;
	    	}
	    }
	    cout<<ans<<endl;
	}
    return 0;
}

B - TT’s Magic Cat

题意

给你一组数据，n个数，q次操作，每次操作对l到r之间的数都加上c。
输出操作后的n个数。

思路

经典的差分题， 这ppt极好

代码

#include<iostream>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
using namespace std;

const int maxn = 200005;
llong n, q;
llong a[maxn], b[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    For(i,1,n){
    	cin>>a[i];
    	b[i]=a[i]-a[i-1];
    }
    For(i,1,q){
    	llong l,r,c;
    	cin>>l>>r>>c;
    	b[l]+=c, b[r+1]-=c;
    }
    For(i,1,n){
    	b[i]+=b[i-1];
    	cout<<b[i]<<" ";
    }
    cout<<endl;
    return 0;
}

C - 平衡字符串

题意

思路

尺取。
先遍历一下字符串，检查一下QWER哪个字符多了（每一个字符的数量应该是n/4），然后我们尺取字符串，在尺取范围内的字符包含了所有多余的字符即是符合要求的，记录答案，左界++；否则，右界++。

代码

#include<iostream>
#include<map>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
using namespace std;

const int maxn = 100005;

string str;
map<char, int> M{{'Q',0},{'W',1},{'E',2},{'R',3}};
int over[4], sv[4]; //Q:0 W:1 E:2 R:3
int ans;

int jg()
{
	int flag = 1;
	For(i,0,3)
		if(sv[i]>0)
			flag = 0;
	return flag;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>str;
    int len = str.length();
    ans = len;
    int a = len/4;
    For(i,0,len-1) {
    	over[M[str[i]]]++;
    }
    For(i,0,3){
    	over[i] -= a;
    	over[i] = (over[i]>0)?(over[i]):0;
    }
    int flag = 1;
    For(i,0,3){
    	sv[i] = over[i];
    	if(over[i])
    		flag = 0;
    }
    if(flag){
    	cout<<0<<endl;
    	return 0;
    }
    int l=0, r=0;
    while(l<=r && r!=len){
    	int t = M[str[r]];
    	int tt = M[str[l]];
    	if(jg()){
    		if(over[tt]) sv[tt]++;
    		ans = min(ans, r-l);
    		l++;
    	}
    	else{
    		if(over[t]) sv[t]--; 
    		r++;
    	}
    }
    cout<<ans<<endl;
    return 0;
}

D - 滑动窗口

题意

思路

单调队列
这题用deque和list都可以。（需要对前(front)和后(back)的操作）
维护一个最大值的队列和一个最小值的队列两个单调队列
先单独处理前m个的最大和最小值，然后 l++，r++处理。

处理单调队列：
????最小值：遍历新值(更新r)。空队或者大于队尾的值则从后面入队；否则一直将队尾弹出直到空栈或者队尾的值小于它。记录一个vMin表示是否已经将其弹出（失去当最小值的资格）。在更新左端点 l 的时候，如果已经弹出过，则不操作，反之则将队首弹出（此时左端点 l 肯定是最小值）。

最大值同理

每次处理完记录两个队列的队首元素（最大和最小值）

代码

#include<iostream>
#include<queue>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
using namespace std;

const int maxn = 1000005;
int n, m, cnt;
int A[maxn];
int vMax[maxn], vMin[maxn];
int ans[3][maxn];
deque<int> dmax;
deque<int> dmin;

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    For(i,1,n) cin>>A[i];
    For(i,1,m){
    	if(dmax.empty()){
    		dmax.push_back(i);
    	}
    	else{
    		int t = dmax.back();
    		while(A[i]>=A[t]){
    			dmax.pop_back();
    			vMax[t] = 1;
    			if(dmax.size())
    				t = dmax.back();
    			else break;
    		}
    		dmax.push_back(i);
    	}
    	if(dmin.empty()){
    		dmin.push_back(i);
    	}
    	else{
    		int t = dmin.back();
    		while(A[i]<=A[t]){
    			dmin.pop_back();
    			vMin[t] = 1;
    			if(dmin.size()) 
    				t = dmin.back();
    			else break;
    		}
    		dmin.push_back(i);
    	}
    }

    ans[1][++cnt] = A[dmax.front()];
    ans[2][cnt] = A[dmin.front()];
    int l = 1, r = m;
    while(r!=n){
    	l++, r++;
    	if(!vMax[l-1]) dmax.pop_front();
    	if(!vMin[l-1]) dmin.pop_front();
    	if(dmax.empty()) 
    		dmax.push_back(r);
    	else{
    		int tmax = dmax.back();
	    	while(A[r]>=A[tmax]){
	    		dmax.pop_back();
	    		vMax[tmax] = 1;
	    		if(dmax.size())
	    			tmax = dmax.back();
	    		else break;
	    	}
	    	dmax.push_back(r);
	    }
	    if(dmin.empty())
	    	dmin.push_back(r);
	    else{
	    	int tmin = dmin.back();
	    	while(A[r]<=A[tmin]){
	    		dmin.pop_back();
	    		vMin[tmin] = 1;
	    		if(dmin.size()) 
	    			tmin = dmin.back();
	    		else break;
	    	}
	    	dmin.push_back(r);
	    }
    	ans[1][++cnt] = A[dmax.front()];
    	ans[2][cnt] = A[dmin.front()];
    }
    For(i,1,cnt){
    	cout<<ans[2][i]<<" ";
    }
    cout<<endl;
    For(i,1,cnt){
    	cout<<ans[1][i]<<" ";
    }
    cout<<endl;
    return 0;
}