[USACO11MAR] Brownie Slicing G题解(二分+二维前缀和+矩阵分割)
[USACO11MAR] Brownie Slicing G
题目地址
P3017 [USACO11MAR] Brownie Slicing G
思路
二分最大化最小值
切割思路:
一行一行进行切割,如果这一行可以切割出b块大于等于mid的块,就开始切割下一行
如果无法切割出b块,就把正在切割的行与下一行拼起来一起切割
最后通过能切割出b块的水平块块够不够a条来判断m是否合适
代码
#include <iostream>using namespace std;int a[1010][1010], s[1010][1010];
int r, c, x, y;bool check(int m) {int lrow = 0;int rows = 0;for (int i = 1; i <= r; i ++) {int num = 0, sum = 0;for (int j = 1; j <= c; j ++) {if (sum + (s[i][j]-s[i][j-1])-(s[lrow][j]-s[lrow][j-1]) < m)sum += (s[i][j]-s[i][j-1])-(s[lrow][j]-s[lrow][j-1]);else {sum = 0;num ++;}}if (num >= y) {lrow = i;++ rows;}}return rows >= x;
}int main() {cin >> r >> c >> x >> y;for (int i = 1; i <= r; i ++)for (int j = 1; j <= c; j ++) {cin >> a[i][j];s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}int left = 0, right = s[r][c];//m 越小越容易成功while (left < right) {int m = left + right + 1 >> 1;if (check(m))left = m;elseright = m - 1;}cout << left;return 0;
}
相关文章:
[USACO11MAR] Brownie Slicing G题解(二分+二维前缀和+矩阵分割)
[USACO11MAR] Brownie Slicing G 题目地址 P3017 [USACO11MAR] Brownie Slicing G 思路 二分最大化最小值 切割思路: 一行一行进行切割,如果这一行可以切割出b块大于等于mid的块,就开始切割下一行 如果无法切割出b块,就把正在…...
【每日一题】—— B. Arrays Sum (Grakn Forces 2020)
🌏博客主页:PH_modest的博客主页 🚩当前专栏:每日一题 💌其他专栏: 🔴 每日反刍 🟡 C跬步积累 🟢 C语言跬步积累 🌈座右铭:广积粮,缓称…...
XTU-OJ 1328-数码和
题目描述 一个10进制数n在2∼16进制下可以得到的不同的数码和,求在这些数码和中出现次数最多的数码和。 比如20, 进制2345678910111213141516数码10100202110403226242220191817161514数码和2424586421098765 其中数码和2和4分别出现了3次,为…...
混入组件 (mixin)
1 什么是混入以及作用 *混入 (mixin) 提供了一种非常灵活的方式,来分发 Vue 组件中的可复用功能。一个混入对象可以包含任意组件选项。当组件使用混入对象时,所有混入对象的选项将被“混合”进入该组件本身的选项。作用:主要作用是继承和封装…...
ubuntu18.04 RTX3060 rangnet++训练
代码链接: https://github.com/PRBonn/lidar-bonnetal 安装anaconda环境为 CUDA 11.0(11.1也可以) anaconda环境如下 numpy1.17.2 torchvision0.2.2 matplotlib2.2.3 tensorflow1.13.1 scipy0.19.1 pytorch1.7.1 vispy0.5.3 opencv_python…...
HZOJ-72:猜拳
题目描述 在一次聚会中,每人拿着一张印有石头、剪刀、布的卡片,每个人具体拿得是哪种卡片不得而知。 现在告诉你某些人之间的胜负关系,并会询问某两个人之间的对战结果,人按照从 11 到 n� 编号。 对于每个…...
【Django 03】QuerySet 和 Instance应用
1. DRF QuerySet 和 Instance功能概述 1.1 QuerySet 从数据库中查询结果存放的集合称为 QuerySet。 Django ORM用到三个类:Manager、QuerySet、Model。每个Model都有一个默认的 manager实例,名为objects。Django的ORM通过Mode的objects属性提供各种数据…...
安装 mysql
gpt: 要在 Debian 11 上安装 MySQL 数据库服务器,您可以使用以下步骤: 1. **更新软件包列表**:在安装任何软件之前,始终建议首先更新软件包列表,以确保获取最新的软件包信息。在终端中运行以下命令: bash…...
文件管理系统的基本认识
1.文件的属性 文件的定义:一组有意义的信息的集合。 1.文件名: 由创建文件的用户决定文件名,主要是为了方便用户找到文件,同一目录下不允许有重名文件。 2.标识符: 一个系统内的各文件标识符唯一,对用户来说毫无可读性, 因此…...
Excel·VBA制作工资条
看到一篇博客《excel表头_Excel工资表怎么做?3分钟学会利用函数生成工资表》,使用排序功能、函数制作工资条。但如果需要经常制作工资条,显然使用VBA更加方便 VBA制作工资条 Sub 制作工资条()Dim title_row&, blank_row&, ws_new$,…...
【SA8295P 源码分析 (二)】10 - HQX Display(OpenWFD)qcdisplaycfg_ADP_STAR_LA.xml 配置文件解析
【SA8295P 源码分析】10 - HQX Display(OpenWFD)qcdisplaycfg_ADP_STAR_LA.xml 配置文件解析 一、HQX Display 介绍1.1 OpenWF Display Driver二、HQX Display 配置文件参数解析2.1 qcdisplaycfg.xml 配置文件2.1 配置两个 DPUs in QNX2.1.1 配置 graphics_ADP_STAR.conf : …...
git操作说明
SourceURL:file:///home/kingqi/桌面/git操作说明.doc 本地建立仓库 mkdir namebao cd namebao pwd git init 初始化 cd .git/ gedit config 本地存储 进入目录上传全部文件 git add . 提交 git commit -m “说明” 远程提交 复制gitee或者github仓库链接 可以直…...
数据结构——栈与队列
数据结构——栈与队列 文章目录 数据结构——栈与队列一、栈的定义二、队列的定义 一、栈的定义 栈(Stack)是一种具有特殊限制的线性数据结构,它只允许在表的一端进行插入和删除操作。这一端被称为栈顶(Top)ÿ…...
Redis入门到实战(四、原理篇)RESP协议
目录 2、Redis内存回收-过期key处理3、Redis内存回收-内存淘汰策略 Redis是一个CS架构的软件,通信一般分两步(不包括pipeline和PubSub): 客户端(client)向服务端(server)发送一条命令…...
c++屏蔽qq或者wechat的好友对局域网环境下的指定关键字
要使用C来屏蔽QQ或WeChat的好友对家庭网络或局域网环境下的指定关键字,你需要编写一个网络包过滤程序,该程序需要有能力拦截并分析网络流量,然后根据指定的规则(如关键字)来阻止或允许数据包的传输。然而,需…...
rviz中显示的点云与网格垂直,将保存的pcd文件转为点云在rviz中显示,并使用octomap_server将点云地图转化为八叉树地图和占据栅格地图
文章目录 问题:点云与网格垂直背景解决方法:对点云坐标做变换,绕x轴旋转90度,将z轴指向上方将pcd转成点云,在RVIZ中显示点云图创建launch rviz显示 问题:点云与网格垂直 用lego-loam建图时用rosbag录制相关…...
个人博客系统的总结
个人博客系统 1、项目背景: 个人博客系统的兴起和发展是与信息技术和互联网的迅猛发展密切相关的。随着互联网的普及和数字化时代的到来,越来越多的人开始使用互联网平台来表达自己的观点、分享知识和展示个人创作。个人博客系统作为一种在线的个人信息…...
小程序之实例会议OA的首页 (3)
⭐⭐ 小程序专栏:小程序开发专栏 ⭐⭐ 个人主页:个人主页 目录 编辑 一.前言 二.flex弹性布局 flex属性 2.1 display: flex 弹性布局属性 2.2 flex-direction属性 2.3 flex-wrap属性 2.4 flex-flow属性 2.5 justify-content属性 三.首页轮播…...
Gson 问题汇总
Gson 自定义TypeAdapter 使用Gsonspringboot中指定Gson为默认消息转换器自定义Gson实例解决方法设定日期类型的格式处理特殊格式数据解析serialVersionUID字段报错int类型,转换后变成了double类型 使用Gson gson是google推出的json解析框架,相较于其他json解析框架,它速度更快…...
css-水滴登录页
效果图: html <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title><link type"text/css" rel"stylesheet" href"login.css" /></head><body><…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
