当前位置: 首页 > news >正文

P3141 [USACO16FEB] Fenced In P题解

题目

如果此题数据要小一点,那么我们可以用克鲁斯卡尔算法通过,但是这个数据太大了,空间会爆炸,时间也会爆炸。

我们发现,如果用 MST 做,那么很多边的边权都一样,我们可以整行整列地删除。

我们造一个样例解析一下:

+-+--+---+
| |  |   |
+-+--+---+
| |  |   |
| |  |   |
+-+--+---+

首先,我们删除第一列的栅栏:

+-+--+---+
| |  |   |
+ +--+---+
| |  |   |
| |  |   |
+-+--+---+

此时答案是 1 1 1

再删除第一排的栅栏:

+-+--+---+
|        |
+ +--+---+
| |  |   |
| |  |   |
+-+--+---+

此时答案是 3 3 3

我们继续删除第二列的栅栏:

+-+--+---+
|        |
+ +  +---+
| |  |   |
| |  |   |
+-+--+---+

此时答案是 5 5 5

我们继续删除第二行的栅栏:

+-+--+---+
|        |
+ +  +---+
|        |
|        |
+-+--+---+

此时答案是 9 9 9

我们把第三列的栅栏删除,由于之前删除的两行栅栏导致第三列栅栏少删除一个,不用删除。

你可以继续造更大的数据发现规律:

我们先把每一列,每一行的栅栏长度算出来,从小到达排序,然后用双指针算法,两个指针 i i i j j j,第一个记录统计到哪一行,第二个记录统计到哪一列,这两个变量的初始值应该为 2 2 2,然后把第一列,第一行栅栏删除。讨论时,如果我们当前讨论的行比列要短,就删除 m − j + 1 m-j+1 mj+1 个栅栏,因为之前删除的栅栏导致我们现在不用删除一些栅栏。反之,同理,就是 n − i + 1 n-i+1 ni+1 个栅栏。如果一个指针走完了,那么所有的都是联通的,就不用再循环了。时间复杂度 O ( n ) O(n) O(n),通过。

AC Code:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int h, w, n, m;
int a[300000], b[300000];
long long a1[300000], b1[300000];
long long ans;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> h >> w >> n >> m;for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 1; i <= m; i ++) cin >> b[i];sort(a + 1, a + n + 1);sort(b + 1, b + m + 1);n++;a[n] = h;m++;b[m] = w;for (int i = 1; i <= n; i ++) {a1[i] = a[i] - a[i - 1];}for (int i = 1; i <= m; i ++) {b1[i] = b[i] - b[i - 1];}sort(a1 + 1, a1 + n + 1);sort(b1 + 1, b1 + m + 1);
//	for (int i = 1; i <= n; i ++) {
//		cout << a1[i] << ' ';
//	}
//	cout << '\n';
//	for (int j = 1; j <= m; j ++) {
//		cout << b1[j] << ' ';
//	}
//	cout << '\n';int i = 2, j = 2;ans = a1[1] * (m - 1);ans += b1[1] * (n - 1);while (i <= n && j <= m) {if (a1[i] < b1[j]) {ans += a1[i] * (m - j + 1);i++;}else {ans += b1[j] * (n - i + 1);j++;}}cout << ans;return 0;
}

相关文章:

P3141 [USACO16FEB] Fenced In P题解

题目 如果此题数据要小一点&#xff0c;那么我们可以用克鲁斯卡尔算法通过&#xff0c;但是这个数据太大了&#xff0c;空间会爆炸&#xff0c;时间也会爆炸。 我们发现&#xff0c;如果用 MST 做&#xff0c;那么很多边的边权都一样&#xff0c;我们可以整行整列地删除。 我…...

Android Compose 一个音视频APP——Magic Music Player

Magic Music APP Magic Music APP Magic Music APP概述效果预览-视频资源功能预览Library歌曲播放效果预览歌曲播放依赖注入设置播放源播放进度上一首&下一首UI响应 歌词歌词解析解析成行逐行解析 视频播放AndroidView引入Exoplayer自定义Exoplayer样式横竖屏切换 歌曲多任…...

Nginx实战:安装搭建

目录 前言 一、yum安装 二、编译安装 1.下载安装包 2.解压 3.生成makefile文件 4.编译 5.安装执行 6.执行命令软连接 7.Nginx命令 前言 nginx的安装有两种方式&#xff1a; 1、yum安装&#xff1a;安装快速&#xff0c;但是无法在安装的时候带上想要的第三方包 2、…...

Qt之条件变量QWaitCondition详解(从使用到原理分析全)

QWaitCondition内部实现结构图&#xff1a; 相关系列文章 C之Pimpl惯用法 目录 1.简介 2.示例 2.1.全局配置 2.2.生产者Producer 2.3.消费者Consumer 2.4.测试例子 3.原理分析 3.1.源码介绍 3.2.辅助函数CreateEvent 3.3.辅助函数WaitForSingleObject 3.4.QWaitCo…...

OpenSource - 一站式自动化运维及自动化部署平台

文章目录 orion-ops 是什么重构特性快速开始技术栈功能预览添砖加瓦License orion-ops 是什么 orion-ops 一站式自动化运维及自动化部署平台, 使用多环境的概念, 提供了机器管理、机器监控报警、Web终端、WebSftp、机器批量执行、机器批量上传、在线查看日志、定时调度任务、应…...

【后端高频面试题--设计模式下篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 后端高频面试题--设计模式下篇 往期精彩内容设计模式总览模板方法模式怎么理解模板方法模式模板方…...

这才是大学生该做的副业,别再痴迷于游戏了!

感谢大家一直以来的支持和关注&#xff0c;尤其是在我的上一个公众号被关闭后&#xff0c;仍然选择跟随我的老粉丝们&#xff0c;你们的支持是我继续前行的动力。为了回馈大家长期以来的陪伴&#xff0c;我决定分享一些实用的干货&#xff0c;这些都是我亲身实践并且取得成功的…...

Ubuntu20.04 安装jekyll

首先使根据官方文档安装&#xff1a;Jekyll on Ubuntu | Jekyll • Simple, blog-aware, static sites 如果没有报错&#xff0c;就不用再继续看下去了。 我这边在执行gem install jekyll bundler时报错&#xff0c;所以安装了rvm&#xff0c;安装rvm可以参考这篇文章Ubuntu …...

AWK语言

一. awk awk&#xff1a;报告生成器&#xff0c;格式化输出。 在 Linux/UNIX 系统中&#xff0c;awk 是一个功能强大的编辑工具&#xff0c;逐行读取输入文本&#xff0c;默认以空格或tab键作为分隔符作为分隔&#xff0c;并按模式或者条件执行编辑命令。而awk比较倾向于将一行…...

精通Nmap:网络扫描与安全的终极武器

一、引言 Nmap&#xff0c;即NetworkMapper&#xff0c;是一款开源的网络探测和安全审计工具。它能帮助您发现网络中的设备&#xff0c;并识别潜在的安全风险。在这个教程中&#xff0c;我们将一步步引导您如何有效地使用Nmap&#xff0c;让您的网络更加安全。 因为Nmap还有图…...

Java 学习和实践笔记(11)

三大神器&#xff1a; 官方网址: http://www.jetbrains.com/idea/ 官方网址: https://code.visualstudio.com/ 官方网址: http://www.eclipse.org 装好了idea社区版&#xff0c;并试运行以下代码&#xff0c;OK&#xff01; //TIP To <b>Run</b> code, press &l…...

开发实体类

开发实体类之间先在pom文件中加入该依赖 <!-- 开发实体类--><dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><scope>provided</scope></dependency>我们在实体类中声明各个属…...

人工智能学习与实训笔记(十五):Scikit-learn库的基础与使用

人工智能专栏文章汇总&#xff1a;人工智能学习专栏文章汇总-CSDN博客 本篇目录 一、介绍 1. 1 Scikit-learn的发展历程及定义 1.2 理解算法包、算法库及算法框架之间的区别和联系 二、Scikit-learn官网结构 三、安装与设置 3.1 Python环境的安装与配置 3.2 Scikit-lea…...

插值与拟合算法介绍

在数据处理和科学计算领域,插值与拟合是两种极为重要的数据分析方法。它们被广泛应用于信号处理、图像处理、机器学习、金融分析等多个领域,对于理解和预测数据趋势具有至关重要的作用。本文将深入浅出地介绍这两种算法的基本原理,并结合C语言编程环境探讨如何在CSDN开发者社…...

下一代Windows系统曝光:基于GPT-4V,Agent跨应用调度,代号UFO

下一代Windows操作系统提前曝光了&#xff1f;&#xff1f; 微软首个为Windows而设的智能体&#xff08;Agent&#xff09; 亮相&#xff1a; 基于GPT-4V&#xff0c;一句话就可以在多个应用中无缝切换&#xff0c;完成复杂任务。整个过程无需人为干预&#xff0c;其执行成功…...

二.自定义头文件

一.Worker.h 1.1概述 - 类名&#xff1a;Worker - 继承关系&#xff1a;所有其他类&#xff08;Employee、Manager、Boss&#xff09;都继承自该抽象类 - 头文件保护&#xff1a;使用 pragma once 防止头文件重复包含 - 引入标准库&#xff1a;包含 <iostream> 和 <st…...

【AIGC】Stable Diffusion之模型微调工具

推荐一款好用的模型微调工具&#xff0c;cybertron furnace 是一个lora训练整合包&#xff0c;提供训练 lora 模型的工具集或环境。集成环境包括必要的依赖项和配置文件、预训练脚本&#xff0c;支持人物、二次元、画风、自定义lora的训练&#xff0c;以简化用户训练 lora 模型…...

探索未来科技前沿:深度学习的进展与应用

深度学习的进展 摘要&#xff1a;深度学习作为人工智能领域的重要分支&#xff0c;近年来取得了巨大的进展&#xff0c;并在各个领域展现出惊人的应用潜力。本文将介绍深度学习的发展历程、技术原理以及在图像识别、自然语言处理等领域的应用&#xff0c;展望深度学习在未来的…...

PTA | Wifi密码

下面是微博上流传的一张照片&#xff1a;“各位亲爱的同学们&#xff0c;鉴于大家有时需要使用 wifi&#xff0c;又怕耽误亲们的学习&#xff0c;现将 wifi 密码设置为下列数学题答案&#xff1a;A-1&#xff1b;B-2&#xff1b;C-3&#xff1b;D-4&#xff1b;请同学们自己作答…...

Linux中gdb使用说明书

首先我们要使用gdb&#xff0c;必须明白gdb使用范围&#xff1a; 要使用gdb调试&#xff0c;必须在源代码生成二进制程序的时候, 加上 -g 选项&#xff08;gcc/g) 其次&#xff0c;我们就要来学习gdb使用的一些命令了&#xff1a; list&#xff0f;l 行号&#xff1a;显…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...