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

每日刷题(二分查找,匈牙利算法,逆序对)

目录

1.Saruman's Army

2.Catch That Cow

3.Drying

4.P3386 【模板】二分图最大匹配

5. Swap Dilemma


1.Saruman's Army

3069 -- Saruman's Army (poj.org)

这道题就是要求我们在给的的位置放入 palantir,每个 palantir有R大小的射程范围,要求求出最少需要安装多少个 palantir,才能将让所有的军队在射程范围内。

思路:

先将军队的位置排序,为二分做准备。

先枚举第一个位置,二分找到小于等于这个位置+R的位置,在此位置安装一个 palantir。

再从这个位置开始重复上述操作。直到索引i>n。

#include<iostream>
#include<algorithm>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x) 
using namespace std;
const int N = 1500;
const int M = 1e9 + 2;
int base1 = 131, base2 = 13311;
ll a[N];
void solve()
{ll n,k;while(cin>>k>>n){if(k==-1) break;for(int i=1;i<=n;i++) cin>>a[i];ll ans=0;sort(a+1,a+1+n);int i=1;while(i<=n){ans++;//找安装的位置int pos=upper_bound(a+1,a+1+n,a[i]+k)-a-1;pos=upper_bound(a+1,a+1+n,a[pos]+k)-a;i=pos;}cout<<ans<<"\n";}
}
int main()
{solve();return 0;
}

2.Catch That Cow

3278 -- Catch That Cow (poj.org)

给出我们起点和终点,要求我们求出从起点到终点最少需要几个操作。

操作1:当前位置+1

操作2:当前位置-1

操作3:传送到当前位置*2的位置

思路:

用bfs算法去搜索答案。注意不能乱搜索:

当当前位置大于终点位置,不能入队操作1和3

当当前位置小于0,不能入队操作3

当当前位置大于终点位置,才能入队操作2

#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x) 
using namespace std;
const int N = 1500;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll a[N],v[M];
struct node
{ll v,st;
};
void solve()
{ll n,k;cin>>n>>k;queue<node>q;node start,nextt;start.st=0,start.v=n;q.push(start);while(!q.empty()){node t=q.front();q.pop();if(t.v==k){cout<<t.st<<"\n";return;}if(t.v>0&&!v[t.v-1])nextt.v=t.v-1,nextt.st=t.st+1,q.push(nextt),v[t.v-1]=1;if(t.v<k&&!v[t.v+1])nextt.v=t.v+1,nextt.st=t.st+1,q.push(nextt),v[t.v+1]=1;if(t.v>0&&t.v<k&&!v[2*t.v])nextt.v=t.v*2,nextt.st=t.st+1,q.push(nextt),v[2*t.v]=1;}
}
int main()
{solve();return 0;
}

3.Drying

3104 -- Drying (poj.org)

要求求出全部衣物都干的最短时间。

二分答案去求解,L为1,R为最湿的衣服的湿润度。

如何判断mid可行?

对衣服的湿润度排序,找到大于mid的衣服,将它减去,再除以烘干片每分钟可以减少的湿润度,向上取整。最后这个值要是小于mid,则这个值可行。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 150000;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll n, k, a[N];
bool check(ll x) {ll ans = x;int pos = upper_bound(a + 1, a + 1 + n, x) - a;for (int i = pos; i <= n; i++) {ans -= (a[i] - x + k - 2) / (k - 1);if (ans < 0) return false;}return true;
}
void solve() {scanf("%lld", &n);for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);scanf("%lld", &k);sort(a + 1, a + 1 + n);if (k == 1) {cout << a[n] << "\n";return ;}ll l = 1, r = a[n], mid;while (l < r) {mid = l + r >> 1;if (check(mid)) { //这段时间可以烘干,再试试更短的时间r = mid;} else {l = mid + 1;}}cout << r << "\n";
}
int main() {solve();return 0;
}

4.P3386 【模板】二分图最大匹配

P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

匈牙利算法的板子题。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 100010;
const int M = 16000101;
int base1 = 131, base2 = 13311;
ll colour[N], head[N];
struct Node {int u, v, net;
} e[N << 2];
ll n, m, cnt = 0;
ll v[N];
vector<vector<ll> >f;
bool dfs(int x, int co) {if (v[x] == co) return false;v[x] = co;for (auto k : f[x]) {if (!head[k] || dfs(head[k], co)) {head[k] = x;return true;}}return false;
}
void solve() {cin >> n >> m >> cnt;f.resize(n + m + 1);for (int u, v; cnt; cnt--) {cin >> u >> v;f[u].push_back(v);}ll ans = 0;for (int i = 1; i <= n; i++) {if (dfs(i, i)) ans++;}cout << ans << "\n";
}
int main() {solve();return 0;
}

5. Swap Dilemma

Problem - D - Codeforces

先将两个数组排序,再判断这两个数组是否相同,相同再进行下一步,反之直接输出NO。

求逆序对,分别讨论两个逆序对的奇偶性,奇偶性相同则输出YES,反之输出NO。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<map>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 100010;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll n, rak1[N], rak2[N];
struct Node {ll v, id;
} e1[N], e2[N];
map<ll,ll>f1,f2;
bool cmp(Node a, Node b) {if (a.v == b.v) return a.id < b.id;return a.v < b.v;
}
void add1(int pos) {for (int i = pos; i <= n; i += lowbit(i)) f1[i]++;
}
void add2(int pos) {for (int i = pos; i <= n; i += lowbit(i)) f2[i]++;
}
ll ask1(int pos) {ll ans = 0;for (int i = pos; i >= 1; i -= lowbit(i)) ans += f1[i];return  ans;
}
ll ask2(int pos) {ll ans = 0;for (int i = pos; i >= 1; i -= lowbit(i)) ans += f2[i];return  ans;
}
void solve() {scanf("%lld", &n);f1.clear();f2.clear();for (int i = 1; i <= n; i++) {scanf("%lld", &e1[i].v), e1[i].id = i;}for (int i = 1; i <= n; i++) {scanf("%lld", &e2[i].v), e2[i].id = i;}sort(e1 + 1, e1 + 1 + n, cmp);sort(e2 + 1, e2 + 1 + n, cmp);for (int i = 1; i <= n; i++) {if (e1[i].v != e2[i].v) {cout << "NO\n";return;}rak1[e1[i].id] = i;rak2[e2[i].id] = i;}ll ans1 = 0, ans2 = 0;for (int i = 1; i <= n; i++) {int pos1, pos2;pos1 = rak1[i];pos2 = rak2[i];ans1 += ask1(n) - ask1(pos1);ans2 += ask2(n) - ask2(pos2);add1(pos1);add2(pos2);}if (abs(ans1 - ans2) % 2 != 0) {cout << "NO\n";} else {cout << "YES\n";}
}
int main() {TESTsolve();return 0;
}

相关文章:

每日刷题(二分查找,匈牙利算法,逆序对)

目录 1.Sarumans Army 2.Catch That Cow 3.Drying 4.P3386 【模板】二分图最大匹配 5. Swap Dilemma 1.Sarumans Army 3069 -- Sarumans Army (poj.org) 这道题就是要求我们在给的的位置放入 palantir&#xff0c;每个 palantir有R大小的射程范围&#xff0c;要求求出最少…...

LLM应用构建前的非结构化数据处理(三)文档表格的提取

1.学习内容 本节次学习内容来自于吴恩达老师的Preprocessing Unstructured Data for LLM Applications课程&#xff0c;因涉及到非结构化数据的相关处理&#xff0c;遂做学习整理。 本节主要学习pdf中的表格数据处理 2.环境准备 和之前一样&#xff0c;可以参考LLM应用构建前…...

如何从数码相机恢复已删除的照片

照片恢复是恢复已删除照片的最佳工具&#xff0c;它带有恢复 RAW 照片的选项。在本文中&#xff0c;我们将解释如何恢复已删除的照片。 不仅对于专业摄影师&#xff0c;对于像我们这样喜欢捕捉回忆的人来说&#xff0c;瞬间相机都是重要的数码设备。遗憾的是&#xff0c;就像智…...

设计模式使用场景实现示例及优缺点(创建型模式——单例模式、建造者模式、原型模式)

创建型模式 单例模式&#xff08;Singleton Pattern&#xff09; 单例模式&#xff08;Singleton Pattern&#xff09;在Java中的使用场景与在其他编程语言中类似&#xff0c;其主要目的是确保一个类只有一个实例&#xff0c;并提供一个全局的访问点。以下是单例模式的一些常…...

LAMP万字详解(概念、构建步骤)

目录 LAMP Apache 起源 主要特点 软件版本 编译安装httpd服务器 编译安装的优点 操作步骤 准备工作 编译 安装 优化执行路径 添加服务 守护进程 配置httpd 查看 Web 站点的访问情况 虚拟主机 类型 部署基于域名的虚拟主机 为虚拟主机提供域名解析&#xff…...

金南瓜科技SECS/GEM:引领智能制造新潮流

引言 在当今快速发展的半导体行业中&#xff0c;智能制造和自动化生产已成为提升效率和降低成本的关键。金南瓜科技凭借其先进的SECS/GEM解决方案&#xff0c;正成为这一变革的先锋。 SECS/GEM&#xff1a;智能制造的核心 SECS/GEM&#xff08;SEMI Equipment Communications …...

昇思训练营打卡第二十一天(DCGAN生成漫画头像)

DCGAN&#xff0c;即深度卷积生成对抗网络&#xff08;Deep Convolutional Generative Adversarial Network&#xff09;&#xff0c;是一种深度学习模型&#xff0c;由Ian Goodfellow等人在2014年提出。DCGAN在生成对抗网络&#xff08;GAN&#xff09;的基础上&#xff0c;引…...

东方通Tongweb发布vue前端

一、前端包中添加文件 1、解压vue打包文件 以dist.zip为例&#xff0c;解压之后得到dist文件夹&#xff0c;进入dist文件夹&#xff0c;新建WEB-INF文件夹&#xff0c;进入WEB-INF文件夹&#xff0c;新建web.xml文件&#xff0c; 打开web.xml文件&#xff0c;输入以下内容 …...

spring xml实现bean对象(仅供自己参考)

对于spring xml来实现bean 具体代码&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <beans xmlns"http://www.springframework.org/schema/beans"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaL…...

MiniGPT-Med 通用医学视觉大模型:生成医学报告 + 视觉问答 + 医学疾病识别

MiniGPT-Med 通用医学视觉大模型&#xff1a;生成医学报告 视觉问答 医学疾病识别 提出背景解法拆解 论文&#xff1a;https://arxiv.org/pdf/2407.04106 代码&#xff1a;https://github.com/Vision-CAIR/MiniGPT-Med 提出背景 近年来&#xff0c;人工智能&#xff08;AI…...

如何判断ip地址在同一个网段:技术解析与实际应用

在网络世界中&#xff0c;IP地址就像每个人的身份证一样&#xff0c;是识别和定位网络设备的关键。然而&#xff0c;仅仅知道IP地址还不足以完全理解其背后的网络结构和通信方式。特别是当我们需要判断两个或多个IP地址是否位于同一网段时&#xff0c;就需要借助子网掩码这一概…...

linux高级编程(TCP)(传输控制协议)

TCP与UDP: TCP: TCP优点&#xff1a; 可靠&#xff0c;稳定 TCP的可靠体现在TCP在传递数据之前&#xff0c;会有三次握手来建立连接&#xff0c;而且在数据传递时&#xff0c;有确认、窗口、重传、拥塞控制机制&#xff0c;在数据传完后&#xff0c;还会断开连接用来节约系统…...

【常见开源库的二次开发】一文学懂CJSON

简介&#xff1a; JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式。它基于JavaScript的一个子集&#xff0c;但是JSON是独立于语言的&#xff0c;这意味着尽管JSON是由JavaScript语法衍生出来的&#xff0c;它可以被任何编程语言读取和生成…...

点云下采样有损压缩

转自本人博客&#xff1a;点云下采样有损压缩 点云下采样是通过一定规则对原点云数据进行再采样&#xff0c;减少点云个数&#xff0c;降低点云稀疏程度&#xff0c;减小点云数据大小。 1. 体素下采样&#xff08;Voxel Down Sample&#xff09; std::shared_ptr<PointClo…...

AutoHotKey自动热键(六)转义符号

转义符号 符号说明,, (原义的逗号). 注意: 在命令最后一个参数中的逗号不需要转义, 因为程序知道把它们作为原义处理. 对于 MsgBox 所有参数同样如此, 因为它会智能的处理逗号.%% (原义的百分号) (原义的重音符; 即两个连续的转义符产生单个原义字符);; (原义的分号). 注意: 仅…...

第16章 主成分分析:四个案例及课后习题

1.假设 x x x为 m m m 维随机变量&#xff0c;其均值为 μ \mu μ&#xff0c;协方差矩阵为 Σ \Sigma Σ。 考虑由 m m m维随机变量 x x x到 m m m维随机变量 y y y的线性变换 y i α i T x ∑ k 1 m α k i x k , i 1 , 2 , ⋯ , m y _ { i } \alpha _ { i } ^ { T } …...

股票分析系统设计方案大纲与细节

股票分析系统设计方案大纲与细节 一、引言 随着互联网和金融行业的迅猛发展,股票市场已成为重要的投资渠道。投资者在追求财富增值的过程中,对股票市场的分析和预测需求日益增加。因此,设计并实现一套高效、精准的股票分析系统显得尤为重要。本设计方案旨在提出一个基于大…...

.gitmodules文件

.gitmodules文件在Git仓库中的作用 .gitmodules 文件是 Git 版本控制系统中用来跟踪和管理子模块的配置文件。子模块允许你将一个 Git 仓库嵌套在另一个仓库中&#xff0c;这样可以方便地管理多个项目之间的依赖关系。 在 .gitmodules 文件中&#xff0c;通常会记录每个子模块…...

STM32 SPI世界:W25Q64 Flash存储器的硬件与软件集成策略

摘要 在嵌入式系统设计中&#xff0c;选择合适的存储解决方案对于确保数据的安全性和系统的可靠性至关重要。W25Q64 Flash存储器因其高性能和大容量成为STM32微控制器项目中的热门选择。本文将深入探讨STM32与W25Q64 Flash存储器的硬件连接、软件集成以及SPI通信的最佳实践。 …...

【计算机网络仿真】b站湖科大教书匠思科Packet Tracer——实验17 开放最短路径优先OSPF

一、实验目的 1.验证OSPF协议的作用&#xff1b; 二、实验要求 1.使用Cisco Packet Tracer仿真平台&#xff1b; 2.观看B站湖科大教书匠仿真实验视频&#xff0c;完成对应实验。 三、实验内容 1.构建网络拓扑&#xff1b; 2.验证OSPF协议的作用。 四、实验步骤 1.构建网…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...