首页/新闻资讯/正文详情

UVA-12265 贩卖土地 题解答案代码 算法竞赛入门经典第二版

发布时间:2026/9/27 1:57:45 来源:云帆数科 栏目:资讯中心
UVA-12265 贩卖土地 题解答案代码 算法竞赛入门经典第二版
GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版虽然算法竞赛入门经典书中标的是两个星号表示难度较高但是从方法和代码量上来看我觉得和两颗星的难度还差的比较远。当然或许是我直接看了书中的分析再做的缘故。参考书中的方式我的实现如下1. 首先计算每个格子向上连续的空地格数。一起计算的话只需要O(mn)即可。2. 然后是遍历每行再遍历每行中的每个元素计算最大的周长。3. 这里使用了一个链表存储这个元素前面元素的空地和格数根据一定规则调整和删除元素3.1. 如果当前格子是沼泽那么清空链表因为前面的所有元素都不能使用了。3.2. 如果当前元素的高度比之前的短那么之前的更长元素统一调整成当前元素的长度。因为如果要想组成矩形当前高度会作为之前元素的永远的限制。3.3. 如果某个元素的前面的元素要更高或者一样高那么这个元素没必要存在。即之前元素高度和你一样但是矩形长度比你更长因此不管后面走多少步都不会选择你。然后是遍历链表找到最大值并统计最后输出。AC代码#include stdio.h #include map #include list #define MAXMN 1005 using namespace std; int arr[MAXMN][MAXMN]; int m, n; // 当前格往上的连续最高格 int arrTop[MAXMN][MAXMN]; // 存放结果数据 mapint, int mp; void outputArr() { int i, j; for (i 0; i m; i) { for (j 0; j n; j) printf(%d, arrTop[i][j]); putchar(\n); } putchar(\n); } void getArrTop() { int i, j; for (i 0; i n; i) { arrTop[0][i] arr[0][i]; for (j 1; j m; j) { if (arr[j][i] 0) arrTop[j][i] 0; else arrTop[j][i] arrTop[j - 1][i] 1; } } } struct Node { int num, top; }; void printList(listNode ls) { for (auto ip ls.begin(); ip ! ls.end(); ip) { printf(top %d num %d\n, ip-top, ip-num); } } void computed(int line) { int i, j, maxV, value; listNode ls; auto ip ls.begin(), ipt ls.begin(); for (i 0; i n; i) { if (arr[line][i] 0) { // 清空list ls.clear(); continue; } Node no {i, arrTop[line][i]}; ls.push_back(no); // 统一调整限高 for (ip ls.begin(); ip ! ls.end(); ip) { if (ip-top no.top) ip-top no.top; } // 统一计算去掉的情况 ip ls.begin(), ipt ls.begin(); ip; while (ip ! ls.end()) { if (ip-top ipt-top) { ip ls.erase(ip); } else { ipt ip; ip; } } // 统一计算最大值 maxV 0; for (ip ls.begin(); ip ! ls.end(); ip) { value ip-top * 2 2 * (i - ip-num 1); if (maxV value) maxV value; } if (maxV ! 0) { if (!mp[maxV]) mp[maxV] 1; else mp[maxV]; } } } int main() { int t; int i, j; char c; scanf(%d, t); while (t--) { scanf(%d %d, m, n); for (i 0; i m; i) { getchar(); for (j 0; j n; j) { scanf(%c, c); if (c .) arr[i][j] 1; else arr[i][j] 0; } } getArrTop(); mp.clear(); for (i 0; i m; i) computed(i); for (auto ip mp.begin(); ip ! mp.end(); ip) { printf(%d x %d\n, ip-second, ip-first); } } return 0; }

相关推荐

选择语句练习避坑指南:从if-else到switch的实战技巧
选择语句练习避坑指南:从if-else到switch的实战技巧

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 1:57:39

fptw64实战:Intel主板BIOS救砖与固件刷写完整指南
fptw64实战:Intel主板BIOS救砖与固件刷写完整指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 1:57:39

STM32+FPGA架构下的分级存储方案:EEPROM、NOR Flash与SD卡的设计取舍与掉电保护
STM32+FPGA架构下的分级存储方案:EEPROM、NOR Flash与SD卡的设计取舍与掉电保护

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 1:57:32

[极客大挑战 2019]Havefun_CTF2
[极客大挑战 2019]Havefun_CTF2

靶场环境:一起来撸猫 页面展示 解题过程 步骤一: 右击查看源代码或Ctrl u 键,下翻发现在408---414行出现以下php代码。 步骤二: 分析代码,构造语句 ?catdog 步骤三: 回到原环境在url后面拼接语句 -… · 2026/9/27 2:34:33

识光CIOE亮相:SPAD-SoC三大产品线如何勾勒单光子感知的量产路径
识光CIOE亮相:SPAD-SoC三大产品线如何勾勒单光子感知的量产路径

在刚刚落幕的中国国际光电博览会(CIOE)上,苏州识光芯科技术有限公司(识光,Sophoton)携多款SPAD-SoC新品亮相。从单点、线阵到面阵,三条产品线并非孤立展示,而是呈现出一种清晰的技术逻辑:以全芯片化架构为底座,用不同形态的芯片去接住高度分化的产业需求。 统一技术… · 2026/9/27 2:34:03

3步搞定app开发人员网站被黑挂马怎么选安全方案
3步搞定app开发人员网站被黑挂马怎么选安全方案

3步搞定app开发人员网站被黑挂马怎么选安全方案 半夜三点,手机突然弹出短信:“您的网站www.yourapp.com存在恶意代码”。你慌了神,点开后台,发现首页被替换成了博彩广告,SEO收录瞬间归零。这种 网站被黑挂马不知道怎么办… · 2026/9/27 2:34:03

国企干部民主评议场景,衡识人才测评等360评估系统适配
国企干部民主评议场景,衡识人才测评等360评估系统适配

引文/摘要又到年终干部考核季。不少国企组织人事部门都在面对同一道题:民主评议怎么搞,才能既合规又高效,还能真正沉淀出有用的数据?传统纸票模式下,评议结果常常“评完就归档”,难以支撑干部选拔与梯队建设… · 2026/9/27 2:33:57

立创EDA安装全攻略:专业版与标准版选型及避坑指南
立创EDA安装全攻略:专业版与标准版选型及避坑指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 2:33:57

Vue 全局事件总线详解
Vue 全局事件总线详解

一、什么是事件总线 1.1 定义 事件总线(Event Bus)本质上就是一个居中转发消息的"邮局":发送方不直接找接收方,而是把消息丢给总线,总线再帮转给所有订阅了这个消息的人。 在 Vue 里,它用来解决任意两个组件之间通信的问题,不限于父子,不限于兄弟,只要挂在同一条总线… · 2026/9/27 2:33:57

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码