D、 Duration

题意：给出在同一天的某个时刻，输出这两个时刻之间的差值。
思路：签到题。简单暴力，直接以00：00：00为起点，计算两个时刻离这个时间点的时间，输出两者差值绝对值即可。
代码：

#include<iostream>
using namespace std;
int main(){
    int hh,mm,ss;
    scanf("%d:%d:%d",&hh,&mm,&ss);
    int num1=hh*3600+mm*60+ss;
    scanf("%d:%d:%d",&hh,&mm,&ss);
    int num2=hh*3600+mm*60+ss;
    cout<<abs(num1-num2)<<endl;
    return 0;
}

F、 Fake Maxpooling

题意：给出一个矩阵，求出这个矩阵的所有k阶子矩阵中的最大值的和。
思路：至于那个求出这个矩阵的元素怎么求就不说了，我还以为直接求会超时呢！对于取某一个范围内的最值的问题，一般就是两种思路，一种就是DP，另一种就是单调队列来做。这题更适合用单调队列的做法，我们只要对这个矩阵的每行每列用单调队列来维护它的最大值就可。
如果单调队列还不会建议先去做一些基础题目。
传送门先看看这个再回来吧。
了解了单调队列的基本原理和实现之后。我们来说说怎么来维护行，其实很简单，只要对每行进行一个区间长为k维护最大值就行了，同时把最大值放在mmax数组里面。

for(int i=1;i<=n;i++){  //对每一行的各列进行一个单调队列维护区间为k的最大值
        int head=0,tail=0;
        for(int j=1;j<=m;j++){
            while(head<tail&&a[i][j]>a[i][que[tail-1]])  tail--;
            que[tail++]=j;
            while(head<tail&&que[tail-1]-que[head]+1>h)  head++;
            if(j>=h)  mmax[i][j]=a[i][que[head]];
        }
    }

同理，我们这样来维护列。这里我们直接更新的是行下标超过k或列下标超过k的那些位置，也就是可以作为一个k阶矩阵的右下角的那些位置。

for(int j=h;j<=m;j++){  //对每一列的各行进行一个单调队列的维护区间为k的最大值
        int head=0,tail=0;
        for(int i=1;i<=n;i++){
            while(head<tail&&mmax[i][j]>mmax[que[tail-1]][j])  tail--;
            que[tail++]=i;
            while(head<tail&&que[tail-1]-que[head]+1>h)  head++;
            if(i>=h)  sum+=mmax[que[head]][j];  //维护之后我们直接累加这个矩阵为k的最大值即可。
        }
    }

ac代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
typedef long long ll;
int a[maxn][maxn],n,m,h,mmax[maxn][maxn],que[maxn];
int gcd(int x,int y){
    if(y==0)  return x;
    else  return gcd(y,x%y);
}
int lcm(int x,int y){
    return x*y/gcd(x,y);
}
int main(){
    cin>>n>>m>>h;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;++j){
            a[i][j]=lcm(i,j);
        }
    }
    for(int i=1;i<=n;i++){  //对每一行的各列进行一个单调队列维护区间为k的最大值
        int head=0,tail=0;
        for(int j=1;j<=m;j++){
            while(head<tail&&a[i][j]>a[i][que[tail-1]])  tail--;
            que[tail++]=j;
            while(head<tail&&que[tail-1]-que[head]+1>h)  head++;
            if(j>=h)  mmax[i][j]=a[i][que[head]];
        }
    }
    ll sum=0;
    for(int j=h;j<=m;j++){  //对每一列的各行进行一个单调队列的维护区间为k的最大值
        int head=0,tail=0;
        for(int i=1;i<=n;i++){
            while(head<tail&&mmax[i][j]>mmax[que[tail-1]][j])  tail--;
            que[tail++]=i;
            while(head<tail&&que[tail-1]-que[head]+1>h)  head++;
            if(i>=h)  sum+=mmax[que[head]][j];
        }
    }
    cout<<sum<<endl;
    return 0;
}