Codeforces Round #574 (Div. 2)

E. OpenStreetMap

题意: 给定一个 $n\ast m$ 的棋盘，棋盘中每一个格子都有一个数字。现在再给出一个 $a\ast b$ 的窗口，用这个窗口去覆盖棋盘中的区域，每一次覆盖的区域不相同，每一次覆盖区域中的最小值累加到答案中，最后输出答案。$(1\le n,m\le 3000,1\le a\le n,1\le b\le m)$

思路: 当拿到这题之后，马上出现的思路就是如何查询区域最小值…然后立刻想到了二维RMQ和二维线段树，然后开始了网络搜索板子的过程…历时半小时之后，确认空间开不下，除非动态开点的二维线段树可能可以卡过去…然后认定此题为难题…进入放弃阶段。顺便看着这题通过人数达到300，开始感叹CF人均实力越来越强…

不得不说，我真是过于愚蠢。下面开始思路讲解?

首先，解决区域最小值的通用方法就是二维RMQ和二维线段树，但是这两者的空间会达到 $n\ast m\ast 16$ ，因此大多数情况下均不适用。但是考察二维最值的题目却层出不穷，主要原因在于每道题都对题目进行了限制，从一开始的任意区域查询最值、任意区域修改，限制成了不修改、固定区域大小或者固定区域某一点等操作。

如此题，将任意区域的最小值，限制成了固定窗口大小的区域最小值，既然是固定窗口大小，那必然能考虑到预处理。

本题关键突破点在于长度固定，长度固定，长度固定！长度固定的最小值，最应该想到的就是单调队列！对于固定窗口的某一行求出该行区间长度为 $a$ 的最小值，再用求出的最小值对于每一列长度为 $b$ 的区间求取最小值即可得到区域 $a\ast b$ 的最小值，由此此题结束。

反思:

1. 今后的CF比赛务必摒弃网络搜索板子的过程，不要丢失少的可怜的思考时间。
2. 比赛结束后，通过人数为200左右的题目，难度仅为 2100-2300；通过人数为100以内的题目，难度为2500+。
3. 在比赛还剩 $50min$ ～ 比赛结束的这一段时间中，后几道题的通过人数会翻倍！
4. 一道题目，可能是一个难的题目进行了条件限制，也可能是为了考察某个算法进行的包装。一定要充分利用题目的条件限制，思考为什么要这样限制，如果不这样限制或者换一种限制方式会发生什么，毕竟这些限制条件才是题目关键突破点。
5. 固定长度的区间最值，是单调队列的核心标签！！！

代码:

#include <bits/stdc++.h>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 3000+10;
const int M = 1e5+100;
const db EPS = 1e-9;
using namespace std;

int n,m,a,b;
ll g0,x,y,z,mp[N][N],c1[N][N],g[N*N],q[N],head,tail,ans;

void solve1(int row){
	head = 1, tail = 0;
	rep(i,1,m){
		while(tail >= head && mp[row][i] <= mp[row][q[tail]]) tail--;
		while(tail >= head && i-q[head] > b-1) head++;
		q[++tail] = i, c1[row][i] = mp[row][q[head]];
	}
}

void solve2(int col){
	head = 1, tail = 0;
	rep(i,1,n){
		while(tail >= head && c1[i][col] <= c1[q[tail]][col]) tail--;
		while(tail >= head && i-q[head] > a-1) head++;
		q[++tail] = i, mp[i][col] = c1[q[head]][col];
	}
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&a,&b);
	scanf("%lld%lld%lld%lld",&g0,&x,&y,&z);
	g[0] = g0;
	rep(i,1,(n-1)*m+m-1) g[i] = ((ll)g[i-1]*(ll)x+(ll)y)%(ll)z;
	rep(i,1,n)
		rep(j,1,m){
			int xp = (i-1)*m+j-1;
			mp[i][j] = g[xp];
		}
	rep(i,1,n) solve1(i);
	rep(i,1,m) solve2(i);
	rep(i,1,n)
		rep(j,1,m){
			if(i >= a && j >= b) ans += mp[i][j];
		}
	printf("%lldn",ans);
	return 0;
}

最后

以上就是小巧小刺猬为你收集整理的Codeforces Round #574 (Div. 2)的全部内容，希望文章能够帮你解决Codeforces Round #574 (Div. 2)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。