BZOJ4716 假摔

Posted by yjjr's blog on January 1, 2018

标签:STL,贪心

题目

题目传送门

假摔(flopping.pas/c/cpp/in/out) 【题目背景】 小Q最近喜欢上了一款游戏,名为《舰队connection》,在游戏中,小Q指挥强大的舰队南征北战,从而成为了一名dalao。 在游戏关卡的攻略中,可能由于作战过程中某艘船受到严重损伤,为避免沉没而被迫进行返航,这种情况大家称为这艘船“假摔”。小Q最喜欢使用的一艘战舰代号为P01,但是最近这艘船总是用各种不同的姿势假摔,于是小Q打算研究一下原因。 【题意描述】 P01的装甲可以近似看作一个nm的矩阵,每个位置上的数字代表这个位置装甲的强度。当受到炮击时,防御力为被炮击的部分的所有位置强度之和。 最近小Q发现,敌方有一种船只被称为ENE,它可以发射不同形状的炮弹,以达到攻击装甲最薄弱处的目的。P01已经被连续k次用不同方式打成了严重损伤(假摔),于是小Q打算分析一下ENE的攻击力。 为了简单起见,我们作如下假设: 1、ENE的炮弹形状无论如何变化,火力值都为一个定值(整数,未知) 2、ENE的炮弹形状只能是长方形(ENE:呵呵),且由于口径的限制,炮弹不能太小(具体来说,对于每一发炮弹长xi宽yi,有xmin<=xi<=n,ymin<=yi<=m) 3、当ENE的炮击命中P01的某处装甲时,被命中部分的强度之和为P01的防御力,此时,ENE的火力必须严格大于P01的防御力,才能将其击穿并造成严重损伤(假摔)。 然而,小Q并没有得到详细的中弹数据,只知道P01用k种不同的方式假摔过。两种假摔方式不同,当且仅当受到炮击的位置不完全相同。因此,不同形状的炮弹击穿护甲时必定可以造成不同的假摔方式,而相同形状的炮弹在不同的位置击穿护甲也能造成不同的假摔方式。 现在,小Q想估计ENE的火力最低是多少。于是,这个任务被交给了你。 举例而言,假设P01的护甲为34: 0 1 3 7 1 1 5 5 7 6 9 6 如果ENE的口径至少为22,那么直接使用22的炮弹攻击左上角22的装甲时,只要火力>=4即可造成一种假摔。如果想造成k=3种不同的假摔方式,至少要拥有12的火力,此时可以造成如下三种假摔方式: 1、22炮弹,攻击有数字的部分,装甲值为3 0 1 - - 1 1 - - - - - - 2、22炮弹,攻击有数字的部分,装甲值为10 - 1 3 - - 1 5 - - - - - 3、23炮弹,攻击有数字的部分,装甲值为11 0 1 3 - 1 1 5 - - - - - 可以证明,火力小于12时,无法造成3种不同的假摔方式,所以ENE的火力至少应为12。 【输入格式】 第一行,五个数n, m, xmin, ymin, k,空格分隔。 接下来n行,每行m个数,空格分隔,表示P01的装甲。 【输出格式】 仅一行,一个数,表示ENE的火力最低值。 【样例输入】 3 4 2 2 3 0 1 3 7 1 1 5 5 7 6 9 6 【样例输出】 12 【数据规模和约定】 对于100%的数据,1<=n,m<=1000,1<=xmin<=n, 1<=ymin<=m, 1<=k<=250000,装甲值为不超过2000的非负整数。 对于100%的数据,保证火力为无穷大的ENE可以造成k种不同的假摔方式。 本题共计20个测试点。 对于1,2,3,4号测试点,1<=n,m<=50。 对于5,6,7,8号测试点,1<=n,m<=100。 对于9,10,11,12,13,14号测试点,1<=n,m<=300。 标程使用了读入优化。 【时间和空间限制】 时间限制以标程在评测环境下的最大数值2倍向上取整为准。 空间限制以标程在评测环境下的最大数值2倍向上取整至2的整次幂为准。 如标程在所有测试点的最大耗时为2.4s,最大空间消耗为160MB,则时间限制应为5s,空间限制应为512MB。 如有需要,该数值应在考试前测出并向选手公示。

分析

题面那么长qwq,早上模拟赛看题时间1h++

简要题意:给定一个n*m的矩阵,求所有长>=xmin,宽>=ymin的子矩阵中,元素和第k小的子矩阵的元素和+1

我只会敲20分的暴力,40分都不知道该怎么卡常qwq

感觉全世界都A了这题,我果然还是弱省菜鸡选手

正解:

使用STL库里的优先队列,先把xmin*ymin大小的矩阵扔进去

然后每次取出最小的进行扩展操作,然后将扩展的矩形扔进优先队列

判重的话可以使用map,出题人想卡map+queue可是没卡掉

由于每次抽出最小矩形最多放入4个矩形,所以总复杂度$O(n^2+k\log(n^2+k))$

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map> 
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1006;
int sum[maxn][maxn],n,m,lx,ly,k,a[maxn][maxn],ans,cnt;
struct node{int a,b,c,d,v;};
bool operator < (node a,node b){//重载运算符
	if(a.v!=b.v)return a.v>b.v;
	if(a.a!=b.a)return a.a>b.a;
	if(a.b!=b.b)return a.b>b.b;
	if(a.c!=b.c)return a.c>b.c;
	if(a.d!=b.d)return a.d>b.d;
	return 0;
}
inline int get(int a,int b,int c,int d){
	return sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1];
}
priority_queue<node> que;
map<node,int>mp;
int main()
{
	n=read(),m=read(),lx=read(),ly=read(),k=read();
	rep(i,1,n)
		rep(j,1,m)a[i][j]=read();
	rep(i,1,n)
		rep(j,1,m)sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
	rep(i,1,n-lx+1)
		rep(j,1,m-ly+1)que.push((node){i,j,i+lx-1,j+ly-1,get(i,j,i+lx-1,j+ly-1)});//将xmin*ymin大小的矩阵扔进去
	while(!que.empty()){
		node x=que.top();que.pop();
		if(mp.find(x)!=mp.end())continue;
		mp[x]=1;++cnt;ans=x.v;
		if(cnt==k)break;
		if(x.c+1<=n)que.push((node){x.a,x.b,x.c+1,x.d,get(x.a,x.b,x.c+1,x.d)});
		if(x.d+1<=m)que.push((node){x.a,x.b,x.c,x.d+1,get(x.a,x.b,x.c,x.d+1)});
	}
	printf("%d\n",ans+1);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr