作业H5-简单数学与线性结构

30
AAABCDEFGHIJKLMNOPQRSTUVWXYZAA
5
1 26
2 27
3 28
4 29
5 30

NO
NO
YES
YES
NO

 详解：该题为线性结构习题，可以使用简单的前缀和快速解决。

对于字符串的每一个位置，如1,2...n用一个二维数组统计每个字母出现次数的前缀和，再查询时即可对于26个字母，第l个位置的前缀和值减去第r个位置的前缀和值，得到该区间内每一个字母出现了多少次

#include
using namespace std;
int a[27][500010],sum[27][500010];
int main(){
    int n,m;
    string str;
    cin>>n;
    cin>>str;
    cin>>m;
    for(int i=0;i>x>>y;
        for(int j=0;j<26;j++){
            if(sum[j][y]-sum[j][x-1]==0) flag=1;
        }
        if(flag==0) cout<<"YES"< 
2.有惊无险 
 
样例输入 
30
AABBCDEFGHIJKLMNOPQRSTUVWXYZZZ
 


 样例输出 
27
 
 详解：本题可以采用尺取法解决，但需要注意右指针和左指针的移动条件。
 
使用一个数组记录区间中每一个字母出现的次数。
 
当区间中出现的字母个数小于26时，右指针向右移动，若该位置的字母未出现过，则出现字母的个数cnt+1，区间中该字母个数减1。
 
当区间中出现的字母个数等于26时，或者右指针移动到字符串终点时，左指针向右运动，去除的那个字母在区间中的个数减1。
 
当区间中的字母个数等于26时，将该区间长度R-L+1与当前ans值取min，记录为新的ans
 
直到 L>=n-25 停止移动，因为再往后已经没有可能了。
 
#include
using namespace std;
int a[30];//记录区间中每个字母的个数
int main(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    int ans=n,cnt=0,low=0,high=-1;//cnt表示区间中出现了多少个字母，ans记录答案
    while(low 
3.天降甘霖 
 
样例输入 
8 3
1 3 -1 -3 5 3 6 7
 

 样例输出 
-1 -3 -3 -3 3 3
3 3 5 5 6 7
 
详解：
 
本题是一道经典的单调队列题，该算法也称为滑动窗口，是线性优化常用的一种算法。
 
其算法思想是维护一个单调队列，保证窗口的第一个元素为输出的值：如果找最大值就维护递减序列，找最小值就维护递增序列。
 
我们以找最大值为例：维护一个最大长度为k的单调队列，每当遇到一个新的值时，将该值与单调队列从后往前比较，比它大的数全部去除，然后把它放进去。如果队列中的元素个数大于k，则将队首元素去除。这个过程就相当于移动一个固定大小的窗口，就能保证队列的队首始终为该区间的最大值。
 
以上队列添加去除过程使用数组模拟。
 
#include
using namespace std;
int a[1000010];//数组
int q1[1000010],q2[1000010],p[1000010];//q1单调递减，处理最大值；q2单调递增，处理最小值
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i>a[i];
    int head=0,tail=-1;//head代表窗口的第一个元素，tail代表窗口的最后一个元素
    for(int i=0;ia[i]) tail--;//去除队列中所有大于该数的元素
        q1[++tail]=a[i];//将这个新数加入队列
        p[tail]=i;//记录队列位置与数组位置的对应关系
        if(i-p[head]>=k) head++;//窗口中元素数量大于k，去除第一个元素
        if(i>=k-1) cout<=k-1) cout< 
4. 终而复始
 
 
样例输入 
7
2 1 4 5 1 3 3 
 
样例输出 
8
 
 详解：
 
本题考察单调栈的用法。
 
由题意可知，如果选定某一块区域求矩形面积，则该区域的面积为最低的那个矩形块高度乘上矩形块数量，因此对于每个矩形块而言，以该方块的高度为整个矩形块的高，则需要找到左边和右边的第一个高度小于它的矩形块，然后求面积再找面积最大。
 
做法：以找每个矩形块的左边界为例。以每个方块为高的左边界记在left1中右边界记在right1中。
 
该方块记为A，它左边的方块记为B，判断A和B的高度大小关系，如果B>A，即A左边的方块比它高，则找到以B为高的矩形的左边界，将这个边界方块记为B，重复以上步骤，直到找到第一个高度小于A的矩形块跳出循环。然后将边界的方块记为A的左边界。
 
右边界的寻找过程同上。尤其注意，数组从h[1]开始记录小方块的高，h[0]和h[n+1]需要赋值为-1,否则会超时。
 
#include
#define int long long
using namespace std;
int left1[100010],right1[100010],h[100010];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    h[0]=-1,h[n+1]=-1;
    for(int i=1;i<=n;i++)//求左边界，递减栈
    {
        int j=i;
        while(h[j-1]>=h[i]){//直到有方块高度小于h[i]，跳出循环
            j=left1[j-1];
        }
        left1[i]=j;
    }
    for(int i=n;i>=1;i--){//求右边界，递增栈
        int j=i;
        while(h[j+1]>=h[i]){
            j=right1[j+1];
        }
        right1[i]=j;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int width=right1[i]-left1[i]+1;
        ans=max(ans,width*h[i]);
    }
    cout<