模拟题1(考虑周全以及情况较多)

2024-06-16 06:12
文章标签 情况 模拟题 考虑 周全

本文主要是介绍模拟题1(考虑周全以及情况较多),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

牛客小白月赛96(重现赛)D题

题目解析以及注意事项

该题主要是找线路最多和最少的各种情况,从而达到整体连通图的构建代价最小的情况。
注意事项:a,b的正负影响着这个图的线尽可能的多还是少
思路图
{ a ≥ b { b < 0 a < 0 : 能连的线都连上 b < 0 a ≥ 0 :奇偶性不同线能连的的全连上 b > 0 :连奇偶性不同的点,而且线的数量要尽量小 a < b { a < 0 b < 0 : 能连的线都连上 a < 0 b ≥ 0 : 奇偶性相同的点互相之间能连的都连上,最后连一个奇偶性不同的点以形成连通图 a > 0 : 奇偶性相同的点互相之间连上,而且尽量少,最后连一个奇偶性不同的点 \begin{cases}a\geq b & \begin{cases}b<0 & a<0:能连的线都连上\\ b<0 & a\geq0:奇偶性不同线能连的的全连上\\ b>0 & :连奇偶性不同的点,而且线的数量要尽量小\end{cases}\\ a<b & \begin{cases}a<0 & b<0:能连的线都连上\\ a<0 & b\geq0:奇偶性相同的点互相之间能连的都连上,最后连一个奇偶性不同的点以形成连通图\\ a>0 & :奇偶性相同的点互相之间连上,而且尽量少,最后连一个奇偶性不同的点\end{cases}\end{cases} aba<b b<0b<0b>0a<0:能连的线都连上a0:奇偶性不同线能连的的全连上:连奇偶性不同的点,而且线的数量要尽量小 a<0a<0a>0b<0:能连的线都连上b0:奇偶性相同的点互相之间能连的都连上,最后连一个奇偶性不同的点以形成连通图:奇偶性相同的点互相之间连上,而且尽量少,最后连一个奇偶性不同的点
注意事项
当考虑n个点之间所有能连的都连上的时候,线的数量count为
n ∗ ( n − 1 ) 2 \frac{n*(n-1)}{2} 2n(n1)
注意n数据范围是
1 ≤ n ≤ 2 e 5 1\leq n\leq 2e^5 1n2e5
而count如果不开long long会超,(呜呜呜,因为这个又多WA了一发)
其他情况同理需要考虑,所以最好全开ll。

 #define ll=long long;

key代码实现

odd记录数组中奇数的个数,even记录数组中偶数的个数。

	if(odd==0||even==0){if(a>=0)cout<<(n-1)*a<<endl;else cout<<(odd*(odd-1)>>1)*a+(even*(even-1)>>1)*a<<endl;return;}if(b<=a){if(b>=0) cout<<(odd+even-1)*b<<endl;else if(a>=0) cout<<odd*even*b<<endl;else if(a<0) cout<<odd*even*b+(odd*(odd-1)>>1)*a+(even*(even-1)>>1)*a<<endl;return;}else {if(a>=0)cout<<(odd+even-2)*a+b<<endl;else if(b>=0) cout<<((odd*(odd-1)>>1)+(even*(even-1)>>1))*a+b<<endl;else cout<<((odd*(odd-1)>>1)+(even*(even-1)>>1))*a+b*odd*even<<endl;}

完整代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define For for (ll i = 1; i <= n; i++)
#define rFor for (ll i = n; i > 0; i--)
#define rep(i, sta, end) for (ll i = sta; i <= end; i++)
#define rrep(i, end, sta) for (ll i = end; i >= sta; i--)
#define ALL(x) for (auto item : x)inline void solve() {ll n,a,b;cin>>n>>a>>b;ll odd=0,even=0;ll tmp;For {cin>>tmp;odd+=(tmp%2==1);even+=(tmp%2==0);}if(n==1){cout<<0<<endl;return;}if(odd==0||even==0){if(a>=0)cout<<(n-1)*a<<endl;else cout<<(odd*(odd-1)>>1)*a+(even*(even-1)>>1)*a<<endl;return;}if(b<=a){if(b>=0) cout<<(odd+even-1)*b<<endl;else if(a>=0) cout<<odd*even*b<<endl;else if(a<0) cout<<odd*even*b+(odd*(odd-1)>>1)*a+(even*(even-1)>>1)*a<<endl;return;}else {if(a>=0)cout<<(odd+even-2)*a+b<<endl;else if(b>=0) cout<<((odd*(odd-1)>>1)+(even*(even-1)>>1))*a+b<<endl;else cout<<((odd*(odd-1)>>1)+(even*(even-1)>>1))*a+b*odd*even<<endl;}
}int	 main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);ll num = 1;cin >> num;while (num--) {//cout << "Main function execute properly before solve function " << endl;solve();//	cout << "Main function execute properly after solve function" << endl;}return 0;
}

这篇关于模拟题1(考虑周全以及情况较多)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1065665

相关文章

机试算法模拟题 服务中心选址

题目描述 一个快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置,并希望能够以此为依据为新的服务中心选址:使服务中心到所有区域的距离的总和最小。 给你一个数组positions,其中positions[i] = [left, right] 表示第 i 个区域在街道上的位置,其中left代表区域的左侧的起点,right代表区域的右侧终点,假设服务中心的位置为loca

分布式系统的主要考虑

异构性:分布式系统由于基于不同的网路、操作系统、计算机硬件和编程语言来构造,必须要考虑一种通用的网络通讯协议来屏蔽异构系统之间的禅意。一般交由中间件来处理这些差异。缺乏全球时钟:在程序需要协作时,它们通过交换消息来协调它们的动作。紧密的协调经常依赖于对程序动作发生时间的共识,但是,实际上网络上计算机同步时钟的准确性受到极大的限制,即没有一个正确时间的全局概念。这是通过网络发送消息作为唯一的通信方式

如何保证android程序进程不到万不得已的情况下,不会被结束

最近,做一个调用系统自带相机的那么一个功能,遇到的坑,在此记录一下。 设备:红米note4 问题起因 因为自定义的相机,很难满足客户的所有需要,比如:自拍杆的支持,优化方面等等。这些方面自定义的相机都不比系统自带的好,因为有些系统都是商家定制的,难免会出现一个奇葩的问题。比如:你在这款手机上运行,无任何问题,然而你换一款手机后,问题就出现了。 比如:小米的红米系列,你启用系统自带拍照功能后

Windows11电脑上自带的画图软件修改照片大小(不裁剪尺寸的情况下)

针对一张图片,有时候上传的图片有大小限制,那么在这种情况下如何修改其大小呢,在不裁剪尺寸的情况下 步骤如下: 1.选定一张图片,右击->打开方式->画图,如下: 第二步:打开图片后,我们可以看到图片的大小为82.1kb,点击上面工具栏的“重设大小和倾斜”进行调整,如下: 第三步:修改水平和垂直的数字,此处我修改为分别都修改为50,然后保存,可以看到大小变成63.5kb,如下:

postgres数据库中如何看查询是否走索引,以及在什么情况下走索引

在 PostgreSQL 中,可以通过 EXPLAIN 或 EXPLAIN ANALYZE 查看查询计划,以判断查询是否使用了索引。除此之外,了解索引的使用条件对于优化查询性能也很重要。 1. 如何查看查询是否使用索引 使用 EXPLAIN 查看查询计划 EXPLAIN 显示 PostgreSQL 如何执行查询,包括是否使用索引。 EXPLAIN SELECT * FROM users WH

linux 查看内存使用情况

Linux查看CPU和内存使用情况:http://www.cnblogs.com/xd502djj/archive/2011/03/01/1968041.html 在做Linux系统优化的时候,物理内存是其中最重要的一方面。自然的,Linux也提供了非常多的方法来监控宝贵的内存资源的使用情况。下面的清单详细的列出了Linux系统下通过视图工具或命令行来查看内存使用情况的各种方法。 1. /pr

Python 中考虑 concurrent.futures 实现真正的并行计算

Python 中考虑 concurrent.futures 实现真正的并行计算 思考,如何将代码所要执行的计算任务划分成多个独立的部分并在各自的核心上面平行地运行。 Python 的全局解释器锁(global interpreter lock,GIL)导致没办法用线程来实现真正的并行​,所以先把这种方案排除掉。另一种常见的方案,是把那些对性能要求比较高的(performance-critica

ubuntu内存资源使用情况监视

此处分享一个可以查看ubuntu系统中资源使用情况的指令,只需要在终端中输入一下这条指令即可: gnome-system-monitor

在不损坏数据的情况下给WIN7重新划分分区

小易接到个求助电话:我的机器上已经装好了系统,但是只有一个分区。我不想重装系统重新分区,能不能再分出一个分区?   这个故障可能是困惑很多网友的一个故障。一般,有一些第三方的软件可以实现这些功能。但是,现在在 Windows Vista/Windows 7 里允许你对现有分区大小进行一定范围的调整。   来看一下操作办法:   准备工作   这个操作必须要求你的文件系统是 N

关于Qt在子线程中使用通讯时发生无法接收数据的情况

在多线程应用中,串口通讯或TCP通讯的场景常常涉及到持续的读写操作,如果子线程处理不当,可能会导致信号阻塞问题。本文将通过串口通讯或TCP通讯为例,详细解释如何在多线程环境中避免信号阻塞,并提供代码示例。 1. 问题背景 假设我们在一个应用程序中使用多线程处理串口或TCP通讯,通常会在子线程中实现持续的数据读取。为了确保实时处理数据,常见的做法是在子线程的 run() 方法中使用 while