#589. 图图的游戏

news/2024/2/20 15:06:55
【题目描述】:
图图正在玩一个智力游戏:有一个n×n 的01 方格,图图要从中选出一个面积最大的矩形区域,要求这个矩形区域不能有超过k个1。这么难的问题图图当然不会做了,他想让你帮帮他,你能解决这个问题吗?【输入描述】:
第一行包含2 个正整数n,k。接下来n 行每行n 个整数,表示这个01方格。【输出描述】:
输出1 个整数,表示最大面积。【样例输入】:
5 4
1 0 1 0 1
0 1 0 0 0
1 0 1 0 0
1 1 1 1 1
0 0 1 0 1
【样例输出】:
12
【时间限制、数据范围及描述】:
时间:1s 空间:256M对于40%的数据,1≤n≤10;对于70%的数据,1≤n≤51;对于100%的数据,1≤n≤501,0≤k≤n×n。本题n^4的算法想必是人人都会写的,直接一个矩阵前缀和就行了,然后我就想到了二分第四维,结果还是90,最后没想到的是尺取大法居然比二分快得多.
只想说一句:尺取大法好!!!Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<deque>
using namespace std;
const int N=505;
int c[N][N],n,q,f[N][N];
int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;
}
int calc(int r1,int c1,int r2,int c2){return f[r2][c2]-f[r2][c1-1]-f[r1-1][c2]+f[r1-1][c1-1];
}
int main(){n=read();q=read();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){c[i][j]=read();f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+c[i][j];}}int ans=0;for(int i=1;i<=n;i++){for(int k=1;k<=i;k++){int l=1;for(int j=1;j<=n;j++){while(calc(k,l,i,j)>q){l++;}int x=i-k+1;int y=j-l+1;ans=max(ans,x*y);}}}printf("%d\n",ans);return 0;
}

转载于:https://www.cnblogs.com/ukcxrtjr/p/11577825.html


http://www.ppmy.cn/news/273996.html

相关文章

✿ISCC2021✿糊图图

致敬沐沐子 题目地址 链接&#xff1a;https://pan.baidu.com/s/1NvLzi1mM7AHK67j1xR0mxw 提取码&#xff1a;7aea 这里就不说思路了直接上完整解题流程 flag.rar解压后的文件附加了NTFS流&#xff0c;用软件提取出来 下图里面是真正的密码&#xff0c;压缩包为弱密码&#xf…

宋图图的PHP课程02

day02 apache的安装配置 如何公开服务器下的文件 1.找到配置文件 htttd.cong 2.将deny from all 改为 allow from all 配置根路径 默认的网站的根路径是我们的www子目录 如果不想使用该目录 可以配置根路径 1.找到配置文件 D:\develop\amp\bin\apache\Apache2.4.4\conf http…

纯css制作大耳朵图图

跟着教程学了用纯css做了大白之后&#xff0c;自己做了一个大耳朵图图。 html部分&#xff1a; <div id"tutu"><div id"hair"><div id"hair1"></div><div id"hair2"></div><div id"hai…

Android连接手机真机调试。(小米为例,其他品牌类似)

自己也是一个在学习中的小白&#xff0c;在用真机调试安装软件的过程中发生很多问题&#xff0c;耽误了很多时间和精力&#xff0c;下面根据我自己操作的实际经验&#xff0c;总结一下我的操作方法。亲测有效&#xff0c;希望能帮到大家。 1、我假设你已经搞定了前面gradle和b…

图图图图!!!

终于开始图了&#xff0c;我估计我已经想着复习图有好久时间了&#xff0c;4月24日开始了奥&#xff01;今天做了两个图的问题&#xff0c;不多BB&#xff0c;直接列出题干&#xff0c; 这道题&#xff0c;很简单&#xff0c;但是我用的方法有些麻烦了&#xff0c;我是一步一步…

图图图图图

某系统的进程可能占有和等待一些资源&#xff0c;现给出在某一时刻dump的这些进程占有和等待的资源信息。 请按照如下简化规则分析哪些进程发生了死锁&#xff1b; 请升序返回所有死锁的进程ID列表&#xff0c;或空列表[]。 简化规则如下&#xff1a; 如果某个进程P的任意等…

python画大耳朵图图_简笔画教程:怎么画大耳朵图图

大耳朵图图是一部比较有意思的动画片&#xff0c;很多小朋友都会比较喜欢看&#xff0c;图图是个小调皮&#xff0c;但是又非常的惹人喜爱&#xff0c;有个时候做出来的事情&#xff0c;常常会惹得人一阵大笑&#xff0c;所以也是我们生活中的开心宝。今天露西姐姐呢&#xff0…

不写代码也能年薪百万?Prompt+低代码开发实战

&#x1f449;腾小云导读 近期 AIGC 狂潮席卷&#xff0c;“前端走向穷途”“低代码时代终结”的言论甚嚣尘上。事实上 GPT 不仅不会干掉低代码&#xff0c;反而会大幅度促进低代码相关系统的开发。本文会介绍 GPT Prompt Engineering 的基本原理&#xff0c;以及如何帮助低代码…

Python数据使用HTTP代理

在Python中&#xff0c;使用HTTP代理可以通过设置环境变量HTTP_PROXY和HTTPS_PROXY来实现。具体步骤如下&#xff1a; 1. 打开终端或命令行窗口&#xff0c;输入以下命令设置HTTP代理&#xff1a; export HTTP_PROXYhttp://<proxy_host>:<proxy_port> 其中&#…

Java爬虫通用模板它来了

Java 爬虫在实际应用中有很多场景&#xff0c;例如&#xff1a;数据挖掘和分析、搜索引擎、电商平台、数据更新、监控与预测等行业都需要爬虫借入&#xff0c;那么在实际爬虫中需要注意什么&#xff1f;又该怎么样快速实现爬虫&#xff1f;下面的文章值得看一看。 单线程java爬…

Openwrt squafs文件系统及sysupgrade升级探究

Openwrt squafs文件系统及sysupgrade升级探究 https://blog.csdn.net/caofengtao1314/article/details/52957890 http://blog.chinaunix.net/uid-29767867-id-5606128.html 一位大神的文章膜拜一下 分类&#xff1a; LINUX 1.平台简介&#xff1a; 硬件平台: QCA9531 软…

360路由器插件_主打游戏加速 360安全路由P4C体验

360路由器从2013年和磊科的合作款之后&#xff0c;产品线已经涵盖P0一直到P4&#xff0c;当中包括了mini款、5G款、千兆款。而360安全路由P4在2017年中发布&#xff0c;到了同年7月&#xff0c;累计销量突破1000万台。在大半年之后&#xff0c;其更新了负责挖矿和游戏方向的P4G…

维和医疗分队患者信息管理系统的开发与研究

本文发表于《中国数字医学》2018.4 摘要&#xff1a;目的&#xff1a;为维和医疗分队定制一套贴合业务需求的患者信息管理系统&#xff0c;用信息化手段辅助维和医疗分队实现从粗放式管理向精细化管理的转变。方法&#xff1a;在南苏丹瓦乌任务区完成需求分析&#xff0c;结合任…

7628刷breed_路由器刷breed_Web控制台助手v5.9版本.7z

1 路由器刷breed_Web控制台助手v5.9版本 0 Bytes 2018/11/22 23:01:33 2 路由器刷breed_Web控制台助手v5.9版本\binbak 0 Bytes 2018/11/22 23:21:18 3 路由器刷breed_Web控制台助手v5.9版本\BreedEnter 0 Bytes 2018/11/22 21:43:23 4 路由器刷breed_Web控制台助手v5.9版本\My…

已解决:stability_selection模块报错got an unexpected keyword argument ‘normalize‘等问题

1.stability_selection模块问题 (1) 多余参数 got an unexpected keyword argument ‘normalize‘ got an unexpected keyword argument ‘penalty’(2)导库问题 (3)函数不收敛/数据标准化问题 (4)项目自带的示例跑不通问题 2.stability_selection模块问题解决 【问…

算法与数据结构(四)

一、哈希表 1、哈希表在使用层面上可以理解为一种集合结构 2、如果只有key&#xff0c;没有伴随数据value&#xff0c;可以使用HashSet结构(C中叫UnOrderedSet) 3、如果既有key&#xff0c;又有伴随数据value&#xff0c;可以使用HashMap结构(C中叫UnOrderedMap) 4、有无伴随数…

【javaScript】- 公共方法的封装

用于截取字符串 封装的方法 /*** 用于截取字符串* param {string} str - 需要截取的字符串* param {string} startStr - 字符串截取开始字符* param {string} endStr - 字符串截取结束字符* returns {string} 截取的字符串*/function interceptFun(str, startStr, endStr, msg…

Django新手必看:从入门到精通Web应用开发①【文末送书三本】

Django新手必看&#xff1a;从入门到精通Web应用开发① 1. Django是什么1.2 Django的由来1.3 Django的命名1.4 Django的版本发布1.5 Django框架的特点 2 Django的设计模式2.1 MVC设计模式2.2 MTV设计模式 3 Django安装与配置3.1 Python支持版本&#xff1a;3.2 Django 3.2与4.1…

对讲机的单工、双工介绍

对讲机的电路形式较多&#xff0c;从调制方式上可分为调幅式和调频式&#xff1a; 从收发功能上&#xff0c;可分为单工式和双工式。单工式对讲机在同一时间内&#xff0c; 只能工作在一种状态下、即&#xff1a;接收或者发射状态&#xff0c;而不能同时处于收发状态。单工对讲…
最新文章