李志自己做网站,番禺网站制作 优帮云,网站地图制作,wordpress 添加锚点首先就是运用了暴力的思路#xff0c;能够过个70%的数据#xff0c;剩下的直接时间超时了#xff0c;没办法优化了。
讲一下暴力的思路#xff1a;
其实就是模拟而已#xff0c;也就是看作想要找的矩阵为一个小窗口#xff0c;然后不断移动的事而已。
#includeios…首先就是运用了暴力的思路能够过个70%的数据剩下的直接时间超时了没办法优化了。
讲一下暴力的思路
其实就是模拟而已也就是看作想要找的矩阵为一个小窗口然后不断移动的事而已。
#includeiostream
#includestdio.h
#includecstring
#includecstdlib
#includecmath
#includevector
#includealgorithm
#includestack
#includequeue
#includesstream
#includemap
#includelimits.h
#includeset
#define MAX 1005
#define int long long
#define _for(i,a,b) for(int ia;i(b);i)
#define ALL(x) x.begin(),x.end()
using namespace std;
vectorintcunchu;
int arr[MAX][MAX];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int n, m;int a, b;cin n m a b;for (int i 1; i n; i) {for (int j 1; j m; j)cin arr[i][j];}int sum 0;//计算结果int left1 1;//这里代表的是对于上界的限制int left2 a;//代表对于下界的限制int right1 1;//代表对于左边的限制int right2 b;//代表对于右边的限制while (left2 n) {cunchu.clear();if (right2 m){right1 1;right2 b;left2;left1;continue;}for (int i left1; i left2; i) {for (int j right1; j right2; j) {cunchu.push_back(arr[i][j]);}}sort(cunchu.begin(), cunchu.end());sum (cunchu.front() * cunchu.back()) % 998244353;right1;right2;}cout sum;return 0;
}
接下来就是优化版本
这里用的是滑动窗口问题的解决方法也就是所谓数据结构中的单调队列这也是需要一些数据结构基础的才能接受的知识点。
思路单调队列讲究的就是一个单调我们可以先套用单调队列的模板可以参考一下y总的模板作者的模板也是跟y总学的建议首先理解然后自己敲出来。
我们想在给定的大矩阵当中我们从中随便选一块小矩阵的大小我们要求它的最大值最小值如果要是暴力的话复杂度肯定是n**2而单调队列可以降到n在求最值的时候我们尝试用单调队列进行求出。但是我们以往用的单调队列都是线性的也就是一维的但不是二维的怎么办这样我们可以换个思路可以从前面写的那个二维双指针可以知道我们可以把二维问题变成一维的也就是说首先固定两个相对的边界。
假设我们这里就首先固定了左右边界这个时候列数是不是就是小矩阵的长呢可以自己画图看一下。这个时候如果说我们先求出来每一行的最大值再来求每一列的最小值这两个过程是不是都是线性的呢是的这个时候我们的单调队列才派上用场。
对于每一行的最值求完之后我们还需要对于这些最值中再求最值这样才能是小矩阵的最值所以又需要用一次单调队列这样虽然麻烦但是效率却是很高的。OK核心思路就到这里
上代码
#includeiostream
#includestdio.h
#includecstring
#includecstdlib
#includecmath
#includevector
#includealgorithm
#includestack
#includequeue
#includesstream
#includemap
#includelimits.h
#includeset
#define MAX 1005
#define int long long
#define _for(i,a,b) for(int ia;i(b);i)
#define ALL(x) x.begin(),x.end()
using namespace std;
vectorintcunchu;
int arr[MAX][MAX];//存储的大矩阵
int rmax[MAX][MAX], rmin[MAX][MAX];//对于第i-1行的每一个长度为b的窗口求最大/小值
int q[MAX];//队列
int one[MAX], two[MAX], three[MAX];//用来存储列的最值的
void get_max(int a[], int b[], int total, int qujian) {int front 0;int rear -1;for (int i 0; i total; i) {if (front rear q[front] qujian i)front;//当前队头滑出窗口while (front rear a[q[rear]] a[i])rear--;//队尾元素比进来的元素小那么我们就开始更新q[rear] i;if (i qujian - 1)//滑动窗口已经完全在数组里面进行滑动了就开始统计每个窗口的最大值。b[i] a[q[front]];}
}
void get_min(int a[], int b[], int total, int qujian) {int front 0;int rear -1;for (int i 0; i total; i) {if (front rear q[front] i - qujian)front;while (front rear a[q[rear]] a[i])rear--;q[rear] i;if (i qujian - 1)b[i] a[q[front]];}
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int n, m;int a, b;cin n m a b;for (int i 0; i n; i) {for (int j 0; j m; j)cin arr[i][j];}for (int i 0; i n; i) {get_max(arr[i], rmax[i], m, b);//对于每一行的每一个长度为b的窗口求最大值get_min(arr[i], rmin[i], m, b);//对于每一行的每一个长度为b的窗口求最小值}int count 0;//用来统计积的和//这里的外循环是对于列的遍历内循环才是对于行的遍历for (int i b-1; i m; i) {//为什么初值是b-1呢这个时候窗口的队头才是i0初值不是b-1的话窗口是不满的for (int j 0; j n; j) one[j] rmax[j][i];//这个时候我们对于每一行的当前窗口的最大值进行存储get_max(one, two, n, a);//这里是对于这些行的最大值再进行求最大值也就是小矩阵的最大值了for (int j 0; j n; j)one[j] rmin[j][i];//同理求最小值get_min(one, three, n, a);for (int j a - 1; j n; j) {//为什么这里用a-1当初值呢其实也是窗口的问题如果纵向看窗口的宽就是a了如果初值不是a-1窗口也是不满的count (count two[j] * three[j]) % 998244353;//这样就是对于所有小矩阵的最值进行相乘然后相加取模了}}cout count;return 0;
}
