洛谷-算法2-2-常见优化技巧2
P4147 玉蟾宫
题目背景
有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
题目描述
这片土地被分成 N×M 个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的最大的土地面积为 S，它们每人给你 S 两银子。
输入格式
第一行两个整数 N，M，表示矩形土地有 N 行 M 列。
接下来 N 行，每行 M 个用空格隔开的字符 F 或 R，描述了矩形土地。
输出格式
输出一个整数，表示你能得到多少银子，即 3×S 的值。
输入输出样例
输入 #1复制
5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F
输出 #1复制
45
说明/提示
对于 50% 的数据，1≤N,M≤200。
对于 100% 的数据，1≤N,M≤1000。
实现代码：
#include<iostream>
#include<stack>
#include<cstring>
#define N 1010
using namespace std;
int n,m,f[N][N],maxx;
char c;
struct node
{
int len,h;
}a[N];
stack<node> S;
void ask(int x)
{
memset(a,0,sizeof(a));
a[1].h=f[x][1],a[1].len=1;
while(S.size()) S.pop();
S.push(a[1]);
for(int i=2;i<=m;i++)
{
int w=0;
while(S.size()&&f[x][i]<=S.top().h)
{
w+=S.top().len;
maxx=max(maxx,w*S.top().h);
S.pop();
}
a[i].h=f[x][i],a[i].len=w+1;
S.push(a[i]);
}
int w=0;
while(S.size())
{
w+=S.top().len;
maxx=max(maxx,S.top().h*w);
S.pop();
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>c;
if(c=='F') f[i][j]=f[i-1][j]+1;
}
for(int i=1;i<=n;i++) ask(i);
cout<<maxx*3<<endl;
return 0;
}
P2866 [USACO06NOV] Bad Hair Day S
题目描述
农夫约翰有 N 头奶牛正在过乱头发节。
每一头牛都站在同一排面朝右，它们被从左到右依次编号为 1,2,⋯,N。编号为 i 的牛身高为 hi。第 N 头牛在最前面，而第 1 头牛在最后面。
对于第 i 头牛前面的第 j 头牛，如果 hi>hi+1,hi>hi+2,⋯,hi>hj，那么认为第 i 头牛可以看到第 i+1 到第 j 头牛。
定义 Ci 为第 i 头牛所能看到的牛的数量。请帮助农夫约翰求出 C1+C2+⋯+CN。
输入格式
输入共 N+1 行。
第一行为一个整数 N，代表牛的个数。
接下来 N 行，每行一个整数 ai，分别代表第 1,2,⋯,N 头牛的身高。
输出格式
输出共一行一个整数，代表 C1+C2+⋯+CN。
输入输出样例
输入 #1复制
6 10 3 7 4 12 2
输出 #1复制
5
说明/提示
数据规模与约定
对于 100% 的数据，保证 1≤N≤8×104，1≤hi≤109。
实现代码：
#include<bits/stdc++.h>
using namespace std;
int n,t;
long long ans;
stack <int> a;
int main() {
cin>>n;
for (int i=1; i<=n; i++) {
cin>>t;
while (!a.empty()&&a.top()<=t)
a.pop();
ans+=a.size();
a.push(t);
}
cout<<ans;
return 0;
}
P1950 长方形
题目描述
小明今天突发奇想，想从一张用过的纸中剪出一个长方形。
为了简化问题，小明做出如下规定：
（1）这张纸的长宽分别为 n,m。小明将这张纸看成是由 n×m 个格子组成，在剪的时候，只能沿着格子的边缘剪。
（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。
（3）剪出来的长方形的大小没有限制。
小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？
输入格式
第一行两个正整数 n,m，表示这张纸的长度和宽度。
接下来有 n 行，每行 m 个字符，每个字符为 * 或者 .。
字符 * 表示以前在这个格子上画过，字符 . 表示以前在这个格子上没画过。
输出格式
仅一个整数，表示方案数。
输入输出样例
输入 #1复制
6 4 .... .*** .*.. .*** ...* .***
输出 #1复制
38
说明/提示
【数据规模】
对 10% 的数据，满足 1≤n≤10,1≤m≤10
对 30% 的数据，满足 1≤n≤50,1≤m≤50
对 100% 的数据，满足 1≤n≤1000,1≤m≤1000
实现代码：
#include<bits/stdc++.h>
using namespace std;
char ch;
long long l[1020],r[1020],h[1020],k[1020],n,m,top;
int d[1020][1020];
long long ans;
void ddzl(){
top=0;
for(int i=m;i>=1;i--){
while(top!=0&&h[i]<=h[k[top]]) l[k[top]]=i,top--;
top++;
k[top]=i;
}
while(top) l[k[top]]=0,top--;
}
void ddzr(){
top=0;
for(int i=1;i<=m;i++){
while(top!=0&&h[i]<h[k[top]]) r[k[top]]=i,top--;
top++;
k[top]=i;
}
while(top) r[k[top]]=m+1,top--;
}
void work(){
ddzl();
ddzr();
for(int i=1;i<=m;i++){
ans+=(i-l[i])*(r[i]-i)*h[i];
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ch;
if(ch=='*') d[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){h[j]++;if(d[i][j]) h[j]=0;}
work();
}
cout<<ans;
}
P2032 扫描
题目描述
有一个 1×n 的矩阵，有 n 个整数。
现在给你一个可以盖住连续 k 个数的木板。
一开始木板盖住了矩阵的第 1∼k 个数，每次将木板向右移动一个单位，直到右端与第 n 个数重合。
每次移动前输出被覆盖住的数字中最大的数是多少。
输入格式
第一行两个整数 n,k，表示共有 n 个数，木板可以盖住 k 个数。
第二行 n 个整数，表示矩阵中的元素。
输出格式
共 n−k+1 行，每行一个整数。
第 i 行表示第 i∼i+k−1 个数中最大值是多少。
输入输出样例
输入 #1复制
5 3 1 5 3 4 2
输出 #1复制
5 5 4
说明/提示
对于 20% 的数据，1≤k≤n≤103。
对于 50% 的数据，1≤k≤n≤104。
对于 100% 的数据，1≤k≤n≤2×106，矩阵中的元素大小不超过 104 并且均为正整数。
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,k;
struct node{int v,id;}a[N];
deque<node> qmin,qmax;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i].v,a[i].id=i;
for(int i=1;i<=n;i++)
{
while(!qmax.empty()&&qmax.back().v<=a[i].v)qmax.pop_back();
qmax.push_back(a[i]);
if(qmax.front().id==i-k)qmax.pop_front();
if(i>=k)cout<<qmax.front().v<<endl;
}
return 0;
}
P2216 [HAOI2007] 理想的正方形
提交答案加入题单复制题目
题目描述
有一个 a×b 的整数组成的矩阵，现请你从中找出一个 n×n 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入格式
第一行为 3 个整数，分别表示 a,b,n 的值。
第二行至第 a+1 行每行为 b 个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
输出格式
仅一个整数，为 a×b 矩阵中所有“ n×n 正方形区域中的最大整数和最小整数的差值”的最小值。
输入输出样例
输入 #1复制
5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2
输出 #1复制
1
说明/提示
矩阵中的所有数都不超过 1,000,000,000。
20% 的数据 2≤a,b≤100,n≤a,n≤b,n≤10。
100% 的数据 2≤a,b≤1000,n≤a,n≤b,n≤100。
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;
int A[MAXN][MAXN];
int B[MAXN][MAXN];
int C[MAXN][MAXN];
int M[MAXN][MAXN], N[MAXN][MAXN];
int main(){
int n, m, k;
cin >> n >> m >> k;
for(int i = 0;i < n;++ i){
for(int j = 0;j < m;++ j){
cin >> A[i][j];
M[i][j] = 1e9;
N[i][j] = -1e9;
}
}
for(int i = 0;i <= (n - 1) / k;++ i){
for(int j = 0;j <= (m - 1) / k;++ j){
int u = i * k, v = min(n - 1, u + k - 1);
int l = j * k, r = min(m - 1, l + k - 1);
vector <tuple<int, int, int, int, int, int> > T = {
{ u, v, l, r, - k + 1, - k + 1 },
{ u, v, r, l, - k + 1, 0 },
{ v, u, l, r, 0, - k + 1 },
{ v, u, r, l, 0, 0 }
};
for(auto [l1, r1, l2, r2, d1, d2]: T){
int t1 = 0, t2 = 0;
t1 = r1 > l1 ? 1 : -1;
t2 = r2 > l2 ? 1 : -1;
for(int a = l1;a != r1 + t1;a += t1){
for(int b = l2;b != r2 + t2;b += t2){
B[a][b] = C[a][b] = A[a][b];
if(a != l1)
B[a][b] = min(B[a][b], B[a - t1][b]),
C[a][b] = max(C[a][b], C[a - t1][b]);
if(b != l2)
B[a][b] = min(B[a][b], B[a][b - t2]),
C[a][b] = max(C[a][b], C[a][b - t2]);
if(a + d1 >= 0 && b + d2 >= 0)
M[a + d1][b + d2] = min(M[a + d1][b + d2], B[a][b]),
N[a + d1][b + d2] = max(N[a + d1][b + d2], C[a][b]);
}
}
}
}
}
int ans = 1e9;
for(int i = 0;i < n - k + 1;++ i){
for(int j = 0;j < m - k + 1;++ j){
ans = min(ans, N[i][j] - M[i][j]);
}
}
cout << ans << endl;
return 0;
}
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
7
0- 0
已为社区贡献12条内容
所有评论(0)