在哪个国家做垂直网站好,建设营销网站的目的,汕头潮南网站建设,写网站编程需要什么目录 1、矩形牛棚#xff08;usaco training 6.1#xff09; 思路#xff1a; 预处理的过程#xff1a; 判断左右边界的过程#xff1a; 代码#xff1a; 2、单调栈#xff08;单调栈模板#xff09; 思路#xff1a; 基本步骤#xff1a; 1、维护单调性 2、处理要求… 目录 1、矩形牛棚usaco training 6.1 思路 预处理的过程 判断左右边界的过程 代码 2、单调栈单调栈模板 思路 基本步骤 1、维护单调性 2、处理要求的操作 3、入栈 代码 3、滑动窗口单调队列模板 思路 基本步骤以求最大值为例 1、维护单调性在尾部做处理 2、入队 3、判断是否滑出窗口滑出则hh 4、做要求的处理 代码 4、子矩阵第十四届蓝桥杯省赛C C组、第十四届蓝桥杯省赛Java C组/研究生组、第十四届蓝桥杯省赛Python A组 思路 固定左右边界进行枚举的过程 实现得到滑动窗口最大值最小值的函数 代码 5、最大子序和《算法竞赛进阶指南》 思路 滑动窗口中维护前缀和的单调性的步骤 代码 6、烽火传递(NOIP2010提高组初赛、《信息学奥赛一本通》) 思路 维护单调性的步骤 代码 1、矩形牛棚usaco training 6.1 作为一个资本家农夫约翰希望通过购买更多的奶牛来扩大他的牛奶业务。 因此他需要找地方建立一个新的牛棚。 约翰购买了一大块土地这个土地可以看作是一个 R行编号 1∼RC列编号 1∼C的方格矩阵。 不幸的是他发现其中的部分方格区域已经被破坏了因此他无法在整个 R×C 的土地上建立牛棚。 经调查他发现共有 P 个方格内的土地遭到了破坏。 建立的牛棚必须是矩形的并且内部不能包含被破坏的土地。 请你帮约翰计算他能建造的最大的牛棚的面积是多少。 输入格式 第一行包含三个整数 R,C,P。 接下来 P 行每行包含两个整数 r,c表示第 r 行第 c 列的方格区域内土地是被破坏的。 输出格式 输出牛棚的最大可能面积。 数据范围 1≤R,C≤3000 0≤P≤30000 1≤r≤R1 1≤c≤C1 输入样例
3 4 2
1 3
2 1输出样例
6
思路
对于每行预处理好每个方块上面最多能用的方块的个数枚举其中的每列分别判断左右两边第一列比该行少的位置然后底乘高算出面积维护最大值即可
预处理的过程 for(int i1;in;i)for(int j1;jm;j){if(g[i][j]0){h[i][j]h[i-1][j]1;}}//记录这一位置上面能用的格子是多少
判断左右边界的过程
int work(int a[])
{a[0]-1,a[m1]-1;int tt0;//枚举左边第一个比这个位置上面能用的格子少的左边界 stk[tt]0;//把左边界加进去 for(int i1;im;i){while(a[i]a[stk[tt]])tt--;//栈顶元素大于等于当前元素的话弹出栈顶 l[i]stk[tt];stk[tt]i; } tt0;stk[tt]m1;for(int im;i1;i--){while(a[stk[tt]]a[i])tt--;r[i]stk[tt];stk[tt]i;}int res0;for(int i1;im;i){resmax(res,a[i]*(r[i]-l[i]-1));}return res;
}
代码
#includebits/stdc.husing namespace std;const int N3010;int n,m,p;int g[N][N],h[N][N];int l[N],r[N];int stk[N];int work(int a[])
{a[0]-1,a[m1]-1;int tt0;//枚举左边第一个比这个位置上面能用的格子少的左边界 stk[tt]0;//把左边界加进去 for(int i1;im;i){while(a[i]a[stk[tt]])tt--;//栈顶元素大于等于当前元素的话弹出栈顶 l[i]stk[tt];stk[tt]i; } tt0;stk[tt]m1;for(int im;i1;i--){while(a[stk[tt]]a[i])tt--;r[i]stk[tt];stk[tt]i;}int res0;for(int i1;im;i){resmax(res,a[i]*(r[i]-l[i]-1));}return res;
}int main()
{cinnmp;for(int i0;ip;i){int r,c;cinrc;g[r][c]1;//标记为破坏 }for(int i1;in;i)for(int j1;jm;j){if(g[i][j]0){h[i][j]h[i-1][j]1;}}//记录这一位置上面能用的格子是多少 int res0;for(int i1;in;i){resmax(res,work(h[i]));}coutres;return 0;
} 2、单调栈单调栈模板 给定一个长度为 N 的整数数列输出每个数左边第一个比它小的数如果不存在则输出 −1。 输入格式 第一行包含整数 N表示数列长度。 第二行包含 N 个整数表示整数数列。 输出格式 共一行包含 N 个整数其中第 i 个数表示第 i 个数的左边第一个比它小的数如果不存在则输出 −1。 数据范围 1≤N≤1e5 1≤数列中元素≤1e9 输入样例
5
3 4 2 7 5输出样例
-1 3 -1 2 2
思路
经典单调栈模板
基本步骤
1、维护单调性
while(tt0 s[tt]x)tt--;
2、处理要求的操作
if(tt0)cout-1 ;else couts[tt] ;
3、入栈
s[tt]x;
代码
#includebits/stdc.husing namespace std;const int N 1e5 5 ;int tt;
int s[N];int main()
{int n;cinn;while(n--){int x;cinx;while(tt0 s[tt]x)tt--;if(tt0)cout-1 ;else couts[tt] ;s[tt]x;} return 0;
} 3、滑动窗口单调队列模板 给定一个大小为 n≤1e6 的数组。 有一个大小为 k 的滑动窗口它从数组的最左边移动到最右边。 你只能在窗口中看到 k 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子 该数组为 [1 3 -1 -3 5 3 6 7]k 为 3。 窗口位置最小值最大值[1 3 -1] -3 5 3 6 7-131 [3 -1 -3] 5 3 6 7-331 3 [-1 -3 5] 3 6 7-351 3 -1 [-3 5 3] 6 7-351 3 -1 -3 [5 3 6] 7361 3 -1 -3 5 [3 6 7]37 你的任务是确定滑动窗口位于每个位置时窗口中的最大值和最小值。 输入格式 输入包含两行。 第一行包含两个整数 n 和 k分别代表数组长度和滑动窗口的长度。 第二行有 n 个整数代表数组的具体数值。 同行数据之间用空格隔开。 输出格式 输出包含两个。 第一行输出从左至右每个位置滑动窗口中的最小值。 第二行输出从左至右每个位置滑动窗口中的最大值。 输入样例
8 3
1 3 -1 -3 5 3 6 7输出样例
-1 -3 -3 -3 3 3
3 3 5 5 6 7
思路
经典单调队列模板
基本步骤以求最大值为例
1、维护单调性在尾部做处理
while(hhtt a[i]dq[tt])tt--;
2、入队
dq[tt]a[i];
3、判断是否滑出窗口滑出则hh
if(i-k0 dq[hh]a[i-k])hh;
4、做要求的处理
if(i1k)coutdq[hh] ;
代码
#includebits/stdc.husing namespace std;const int N1e65;int n,k;int tt-1,hh;
int dq[N],a[N];int main()
{cinnk;for(int i0;in;i)scanf(%d,a[i]);//求窗口最小值 for(int i0;in;i){while(hhtt a[i]dq[tt])tt--;dq[tt]a[i];//if(i-k0 dq[hh]a[i-k])hh;//队头一定是最小的if(i1k)coutdq[hh] ; } coutendl;//求最大值tt-1,hh0;for(int i0;in;i){while(hhtt a[i]dq[tt])tt--;dq[tt]a[i];if(i-k0 dq[hh]a[i-k])hh;if(i1k)coutdq[hh] ; } return 0;
} 4、子矩阵第十四届蓝桥杯省赛C C组、第十四届蓝桥杯省赛Java C组/研究生组、第十四届蓝桥杯省赛Python A组 给定一个 n×mn 行 m 列的矩阵。 设一个矩阵的价值为其所有数中的最大值和最小值的乘积。 求给定矩阵的所有大小为 a×b a 行 b 列的子矩阵的价值的和。 答案可能很大你只需要输出答案对 998244353998244353 取模后的结果。 输入格式 输入的第一行包含四个整数分别表示 n,m,a,b相邻整数之间使用一个空格分隔。 接下来 n行每行包含 m 个整数相邻整数之间使用一个空格分隔表示矩阵中的每个数 A[i],[j]。 输出格式 输出一行包含一个整数表示答案。 数据范围 对于 40%40% 的评测用例1≤n,m≤100 对于 70%70% 的评测用例1≤n,m≤500 对于所有评测用例1≤a≤n≤10001≤b≤m≤10001≤Ai,j≤1e9。 输入样例
2 3 1 2
1 2 3
4 5 6输出样例
58样例解释
1×22×34×55×6581×22×34×55×658。
思路
固定左右边界进行枚举这时候从上上边界往下边界枚举每次在每个区域中在每行的最小值中选出最小的在每行的最大值中选出最大的这个区域的最大值乘最小值就是该矩阵的价值
固定左右边界进行枚举的过程 for(int ib-1;im;i)//固定好列区间 {for(int j0;jn;j)A[j]maxr[j][i];//每行把每个窗口最大的数取出来getmax(A,B,n,a);//存到B中 for(int j0;jn;j)A[j]minr[j][i];//每行把每个窗口最小的数取出来 getmin(A,C,n,a);//存到C中 for(int ja-1;jn;j) {res(res(LL)B[j]*C[j])%MOD;}}
实现得到滑动窗口最大值最小值的函数
void getmin(int a[],int b[],int total,int lenth)
{int tt-1,hh0;for(int i0;itotal;i){//判断元素是否滑出窗口 if(hhtt q[hh]i-lenth)hh;//判断新元素和旧元素的大小关系确保队列单调while(hhtt a[i]a[q[tt]])tt--; //入队 q[tt]i;//把最值交给存储数组 队头一定是最小的 if(ilenth-1)b[i]a[q[hh]];//ik-1表示滑动窗口形成}
}void getmax(int a[],int b[],int total,int lenth)
{int tt-1,hh0;for(int i0;itotal;i){if(hhtt q[hh]i-lenth)hh;while(hhtt a[i]a[q[tt]])tt--;q[tt]i;//队头一定是最大的赋值给b if(ilenth-1)b[i]a[q[hh]];}
}
代码
#includebits/stdc.husing namespace std;const int N1010;int n,m,a,b; int g[N][N],minr[N][N],maxr[N][N]; int q[N];typedef long long LL;const int MOD998244353;void getmin(int a[],int b[],int total,int lenth)
{int tt-1,hh0;for(int i0;itotal;i){//判断元素是否滑出窗口 if(hhtt q[hh]i-lenth)hh;//判断新元素和旧元素的大小关系确保队列单调while(hhtt a[i]a[q[tt]])tt--; //入队 q[tt]i;//把最值交给存储数组 队头一定是最小的 if(ilenth-1)b[i]a[q[hh]];//ik-1表示滑动窗口形成}
}void getmax(int a[],int b[],int total,int lenth)
{int tt-1,hh0;for(int i0;itotal;i){if(hhtt q[hh]i-lenth)hh;while(hhtt a[i]a[q[tt]])tt--;q[tt]i;//队头一定是最大的赋值给b if(ilenth-1)b[i]a[q[hh]];}
}int main()
{cinnmab;for(int i0;in;i)for(int j0;jm;j)scanf(%d,g[i][j]);//for(int i0;in;i)//for(int j0;jm;j)printf(%d,g[i][j]);//预处理出来每一行中滑动窗口的最值 for(int i0;in;i){getmin(g[i],minr[i],m,b);getmax(g[i],maxr[i],m,b);}int res0;int A[N],B[N],C[N];for(int ib-1;im;i)//固定好列区间 {for(int j0;jn;j)A[j]maxr[j][i];//每行把每个窗口最大的数取出来getmax(A,B,n,a);//存到B中 for(int j0;jn;j)A[j]minr[j][i];//每行把每个窗口最小的数取出来 getmin(A,C,n,a);//存到C中 for(int ja-1;jn;j) {res(res(LL)B[j]*C[j])%MOD;}}coutres;return 0;
} 5、最大子序和《算法竞赛进阶指南》 输入一个长度为 n 的整数序列从中找出一段长度不超过 m 的连续子序列使得子序列中所有数的和最大。 注意 子序列的长度至少是 1。 输入格式 第一行输入两个整数 n,m。 第二行输入 n 个数代表长度为 n 的整数序列。 同一行数之间用空格隔开。 输出格式 输出一个整数代表该序列的最大子序和。 数据范围 1≤n,m≤300000 保证所有输入和最终结果都在 int 范围内。 输入样例
6 4
1 -3 5 1 -2 3输出样例
7
思路
前缀和滑动窗口
滑动窗口中维护前缀和的单调性的步骤
//s[q[tt]] 即将被减去当然是越小越好
//如果s[i](前i个数的和)小于s[q[tt]](前面的前缀和)
//那么s[i]更适合被减去来求后面的前缀和
while(hhtt s[q[tt]]s[i])tt--;
代码
#includebits/stdc.husing namespace std;const int N30000010;int n,m; long long s[N];int q[N],hh-1,tt;int main()
{cinnm;//前缀和 for(int i1;in;i){cins[i];s[i]s[i-1];}long long resINT_MIN;for(int i1;in;i){//判断是否滑出窗口 if(hhtt q[hh]i-m-1)hh;//保持单调性 //while(hhtt )resmax(res,s[i]-s[q[hh]]);//s[q[tt]] 即将被减去当然是越小越好 //如果s[i](前i个数的和)小于s[q[tt]](前面的前缀和)//那么s[i]更适合被减去来求后面的前缀和 while(hhtt s[q[tt]]s[i])tt--;q[tt]i;}coutres;return 0;
} 6、烽火传递(NOIP2010提高组初赛、《信息学奥赛一本通》) 烽火台是重要的军事防御设施一般建在交通要道或险要处。 一旦有军情发生则白天用浓烟晚上有火光传递军情。 在某两个城市之间有 n 座烽火台每个烽火台发出信号都有一定的代价。 为了使情报准确传递在连续 m 个烽火台中至少要有一个发出信号。 现在输入 n,m 和每个烽火台的代价请计算在两城市之间准确传递情报所需花费的总代价最少为多少。 输入格式 第一行是两个整数 n,m具体含义见题目描述 第二行 n 个整数表示每个烽火台的代价 ai。 输出格式 输出仅一个整数表示最小代价。 数据范围 1≤m≤n≤2×1e5 0≤ai≤1000 输入样例
5 3
1 2 5 6 2输出样例
4
思路
动态规划单调队列
f[i]表示第i个烽火台点燃需要的最小代价
维护单调性的步骤
//维护单调性
while(hhtt f[i]f[q[tt]])tt--;
代码
#includebits/stdc.husing namespace std;const int N2e510;int n,m; int a[N];int q[N];int hh,tt-1;
//dp
int f[N];int main()
{cinnm;for(int i1;in;i){cina[i];}//前0个烽火台的最小代价是0 f[tt]0;int res1e9;for(int i1;in;i){//f[i]表示第i个烽火台点燃需要的最小代价//超出i-m范围则不合法 if(q[hh]i-m)hh;f[i]f[q[hh]]a[i];//维护单调性while(hhtt f[i]f[q[tt]])tt--;q[tt]i; }for(int in-m1;in;i)resmin(res,f[i]);coutres;return 0;
}
/*
5 3
1 2 5 6 24*/
