首页 > 其他分享 >8.26下午二分与深搜测试

8.26下午二分与深搜测试

时间：2024-08-26 20:04:52浏览次数：4  
标签：二分 return int mid long cin 8.26 maxn 测试

8.26下午二分与深搜测试

比赛传送门

分数情况

P2249 【深基13.例1】查找 P1706 全排列问题 P8647 [蓝桥杯 2017 省 AB] 分巧克力 P2440 木材加工 B3624 猫粮规划 P2105 K皇后 P3853 路标设置 P3743 小鸟的设备
0 100 12 100 0 0 0 15

T1. P2249 【深基13.例1】查找

题目传送门

\(Wrong\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int n, m;
int a[maxn];
int chenlaoshi(int ans)
{
	int l = 1 - 1;
	int r = n + 1;
	a[l] = INT_MIN;
	a[r] = INT_MAX;
	int mid;
	while (l + 1 < r)
	{
		mid = (l + r) / 2;
		if (a[mid] < ans)
		{
			l = mid;
		}
		if (a[mid] > ans)
		{
			r = mid;
		}
		if (a[mid] == ans)
		{
			r = mid;
		}
	}
	if (a[r] == ans)
	{
		return r;
	}
	return -1;
} 
signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= m; ++i)
	{
		int x;
		cin >> x;
		cout << chenlaoshi(x) << ' ';
	}
	return 0;
}

错误原因

数组开小了

\(1 \leq n \leq 10^6\)

不能是 1e5 + 7

要到 1e6 + 7

问题分析

二分查找相等数值的左侧边界

  • 如果查找值在中间值的左边，需要继续查找左侧边界

  • 如果查找值在中间值的右边，需要继续查找右侧边界

  • 如果查找值和中间值相等，也是需要继续查找左侧边界

\(AC\) \(Code:\)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
int a[maxn];
int n;
int chenlaoshi(int x)
{
	int l = 1 - 1;
	int r = n + 1;
	a[0] = -1e9;
	a[n + 1] = 1e9;
	while (l + 1 < r)
	{
		int mid = (l + r) / 2;
		if (a[mid] > x)
		{
			r = mid;
		}
		if (a[mid] < x)
		{
			l = mid;
		}
		if (a[mid] == x)
		{
			r = mid;
		}
	}
	if (a[r] == x)
	{
		return r;
	}
	return -1;
}
int main()
{
	cin >> n;
	int m;
	cin >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	while (m--)
	{
		int x;
		cin >> x;
		cout << chenlaoshi(x) << ' ';
	}
	return 0;
}

T2. P1706 全排列问题

题目传送门

问题分析

深搜全排列问题

非常经典

\(AC\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
bool vis[maxn];
int ans[maxn];
int n;
void print()
{
	for (int i = 1; i <= n; ++i)
	{
		cout << setw(5) << ans[i];
	}
	cout << "\n";
	return ;
}
void dfs(int cur)
{
	if (cur == n + 1)//满足条件就输出
	{
		print();
	}
	for (int i = 1; i <= n; ++i)
	{
		if (vis[i] == false)
		{
			ans[cur] = i;// 代表填写的是第cur个格子，填写的数字是i
			vis[i] = true;//标记
			dfs(cur + 1);
			vis[i] = false;//标记
		}
	}
	return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	dfs(1);
	return 0;
}

T3. P8647 [蓝桥杯 2017 省 AB] 分巧克力

题目传送门

\(Wrong\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int n, k;
int h[maxn], w[maxn];
bool check(int x)
{
	int sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		sum += ((h[i] / x) + (w[i] / x));
		if (sum >= k)
		{
			return true;
		}
	}
	return false;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	int maxx = INT_MIN;
	for (int i = 1; i <= n; ++i)
	{
		cin >> h[i] >> w[i];
		maxx = max(maxx, max(h[i], w[i]));
	}
	int l = 1 - 1;
	int r = maxx + 1;
	while (l + 1 < r)
	{
		int mid = (l + r) / 2;
		if (check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	cout << l << "\n";
	return 0;
}

错误原因

错误地点：第 \(12\) 行

是 \(+\) 不是 \(\times\)

问题分析

考虑边长和切分的巧克力关系

如果边长越短，切分得到的巧克力越多

边长越长，切分得到的巧克力总数越少。

这里存在单调关系，根据这种二分关系直接进行二分答 案。

\(AC\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int n, k;
int h[maxn], w[maxn];
bool check(int x)
{
	int sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		sum += ((h[i] / x) * (w[i] / x));
		if (sum >= k)
		{
			return true;
		}
	}
	return false;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	int maxx = INT_MIN;
	for (int i = 1; i <= n; ++i)
	{
		cin >> h[i] >> w[i];
		maxx = max(maxx, max(h[i], w[i]));
	}
	int l = 1 - 1;
	int r = maxx + 1;
	while (l + 1 < r)
	{
		int mid = (l + r) / 2;
		if (check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	cout << l << "\n";
	return 0;
}

T4. P2440 木材加工

题目传送门

问题分析

典型的二分答案

二分长度

长度越长，切分的段数越少

长度越短，切分的段数越多

这里存在单调性关系。

\(AC\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int n, k;
int a[maxn];
bool check(int x)
{
	int sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		sum += a[i] / x;
		if (sum >= k)
		{
			return true;
		}
	}
	return false;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	if (n == 0)
	{
		cout << 0 << "\n";
		return 0;
	}
	int maxx = INT_MIN;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		maxx = max(maxx, a[i]);
	}
	int l = 1 - 1;
	int r = maxx + 1;
	while (l + 1 < r)
	{
		int mid = (l + r) / 2;
		if (check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	} 
	cout << l << "\n";
	return 0;
}

T5. B3624 猫粮规划

题目传送门

问题分析

在原来全排列的基础之上

添加一个剪枝方式，如果已经大于 \(r\) 的总和

后面这一段直接 return ;

\(AC\) \(Code:\)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;
int n, l, r;
int a[maxn];
int ans;
void dfs(int j, int k) 
{
	if (l <= k && k <= r)
	{
		ans++;
	}
	if (k > r || j == n) 
	{
		return ;
	}
	for (int i = j + 1; i <= n; i++) 
	{
		dfs(i, k + a[i]);
	}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin >> n >> l >> r;
	for (int i = 1; i <= n; i++)
	{ 
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++) 
	{
		dfs(i, a[i]);
	}
	cout << ans << "\n";
	return 0;
}

T6. P2105 K皇后

题目传送门

\(Wrong\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5005;
int n, m, k;
bool qi[maxn][maxn];
bool gongji[maxn][maxn];
void do_gongji(int x, int y)
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if ((i == x) || (j == y) || (i == j) || (i == j + 1))
			{
				gongji[i][j] = 1;
			}
		}
	}
	return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= k; ++i)
	{
		int x, y;
		cin >> x >> y;
		qi[x][y] = 1;
		gongji[x][y] = 1;
		do_gongji(x, y);
	} 
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (gongji[i][j] == 0)
			{
				cnt++;
			}
		}
	}
	cout << cnt << "\n";
	return 0;
}

\(_{_{本来想用暴力的}}\)

问题分析

考虑之前写的八皇后问题

因为本题存在多次标记的情况，直接采用深度优先搜索的方式会超时

所以切换思路，提前将行、列、对角线直接标记

然后一个个格子进行判断，最后剪枝操作如果这一行被标记了，这一行直接跳过

\(AC\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int hang[maxn];
int lie[maxn];
int zhu[maxn];
int fu[maxn];

signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	int x, y;
	for (int i = 1; i <= k; i++)
	{
		cin >> x >> y;
		hang[x] = true;
		lie[y] = true;
		zhu[n + x - y] = true;
		fu[x + y] = true;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		if (hang[i] == true)
		{
			continue;
		}
		for (int j = 1; j <= m; j++)
		{
			if (lie[j] || zhu[n + i - j] || fu[i + j])
			{
				continue;
			}
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

T7. P3853 [TJOI2007] 路标设置

题目传送门

问题分析

空旷指数越大，添加的路标数量越少

但是空旷指数越小，意味着路标的密度越大，数量越多

所以此处需要获取间隔最大值的最小，比较明显的二分答案

\(AC\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int a[maxn], n, m, l;
bool check(int x)
{
	int cnt = 0;
	for (int i = 1; i <= m; i++)
	{
		cnt += (a[i] - a[i - 1] - 1) / x;
	}
	cnt += (n - a[m] - 1) / x;
	if (cnt > l)
	{
		return false;
	}
	else
	{
		return true;
	}
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> l;
	for (int i = 1; i <= m; i++)
	{
		cin >> a[i];
	}
	int l = 1 - 1;
	int r = 1e9 + 1;
	int mid;
	while (l + 1 < r)
	{
		mid = (l + r) / 2;
		if (check(mid))
		{
			r = mid;
		}
		else
		{
			l = mid;
		}
	}
	cout << r;
	return 0;
}

T8. P3743 小鸟的设备

题目传送门

问题分析

所有设备运⾏的时间显然有单调性，若时⻓ \(x\) 可⾏，⼩于 \(x\) 的也可⾏，若 \(x\) 不可⾏，⼤于 \(x\) 的也不可⾏。

二分 \(x\) , 重点考虑如何设计 check(mid) 。

枚举每个设备，其运⾏ mid 时间需要 a[i] \(\times\) mid 的电量

依靠⾃身 的电量 b[i] 若不够

那么就需要⽤充电宝 充 a[i] \(\times\) mid \(-\) b[i] 的电量

统计充电宝的需要充电的总电量 sum

sum 不应该超过 p \(\times\) mid

\(AC\) \(Code:\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int n;
double eps = 1e-5;
double a[maxn], b[maxn], p;
bool check(double x)
{
	double sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (b[i] < x * a[i])
		{
			sum += (x * a[i] - b[i]);
		}
	}
	return sum <= x * p;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> p;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i] >> b[i];
	}
	double l = 0 - eps;
	double r = 1e10 + eps;
	while (l + eps < r)
	{
		double mid = (l + r) / 2;
		if (check(mid) == 1)
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	if (r == 1e10 + eps)
	{
		cout << -1 << "\n";
	}
	else
	{
		cout << l << "\n";
	}
	return 0;
}

\(The\) \(end\)

标签：二分,return,int,mid,long,cin,8.26,maxn,测试
From： https://www.cnblogs.com/yucheng0630/p/18381530

相关文章

  • jmeter性能测试之CSV 数据文件设置
    文章目录业务场景使用步骤步骤1：准备数据步骤二:编写csv文件步骤三:添加CSV数据文件设置步骤四:定义接口，选择文件上传，文件名称通过“浏览”添加即可业务场景有一个文件上传的接口，希望每个线程上传不同的文件（比如说开启十个线程，每个线程上传一个excel文件），就可以将1......
  • DISC性格测试，企业人才测评工具@Hr人力资源管理
    DISC性格测试，是一种常见的企业人才评定方法，用于测试求职者的人际沟通、行为方式和工作风格等。用于评定出一个人的支配性、影响性、服从性和稳定性。支配性也叫管理潜能，很多企业采用DISC来寻找大D型性格，用于人才选拔，团队优化，岗位晋升，无论是人才盘点，还是人才招聘，disc都是不错的......
  • x86 ubuntu20.04 ros:noetic-perception-focal 镜像测试
    https://hub.docker.com/_/ros/tags?page=&page_size=&ordering=&name=noetic1.启动容器：dockerpullros:noetic-perception-focaldockerrun-it--envDISPLAY=$DISPLAY--volume/tmp/.X11-unix:/tmp/.X11-unix--privileged--gpusall--volume/home/h/doc......
  • 8.26
    一、FineBI的简单介绍数据可视化的工具有很多，其中FineBI是其中的一个，相比与其他的工具，FineBI更容易上手。1介绍FineBI是帆软软件有限公司推出的一款商业智能（BusinessIntelligence）产品。FineBI是定位于自助大数据分析的BI工具，能够帮助企业的业务人员和数据分析师，开展以问......
  • 深信服安全服务认证工程师（SCSA-S）系列课程——渗透测试环境搭建与工具使用-Nmap
    Nmap简介Nmap是Linux下一款开源免费的网络发现(NetworkDiscovery)和安全审计(SecurityAuditing)工具，软件名字Nmap是NetworkMapper的简称。Nmap最初由Fyodor在1996年开始创建，随后在开源社区众多的志愿者参与下，该工具逐渐成为最为流行的安全必备工具之一。Nmap使用原始......
  • 探索你的脑力边界：了解智商测试的独到之处！
    智力测试就是对智力的科学测试，它主要测验一个人的思维能力、学习能力和适应环境的能力。现代心理学界对智力有不同的看法。所谓智力就是指人类学习和适应环境的能力。智力包括观察能力、记忆能力、想象能力、思维能力等等。智商测试的意义职业选择与发展：对于成年人，智商测试......
  • mPLUG-Owl3环境搭建&推理测试
    ​引子多模态的大模型也写了很多篇，阿里系的之前有一篇Qwen-VL的相关部署，感兴趣的童鞋请移步（Qwen-VL环境搭建&推理测试-CSDN博客）。今天这个mPLUG-Qwl3，更新换代也很快，这都第三代，据说，这个专门用来理解多图、长视频，OK，让我们开始吧。一、模型介绍论文作者来自阿里mPLUG团队，他们一直......
  • 《机器学习》—— 随机森林实现二分类问题
    文章目录一、什么是随机森林二、随机森林的主要特点三、随机森林参数四、案例的代码实现一、什么是随机森林随机森林（RandomForest）是一种集成学习方法，属于监督学习算法，主要用于分类和回归任务。它通过在数据集的多个子集上构建多个决策树，并输出这些树预测结果的众数（......
  • JMeter：性能测试利器全解析
    目录JMeter：性能测试利器全解析一、JMeter的基础概念（一）什么是JMeter（二）主要功能特点二、使用JMeter测试Web应用的步骤（一）安装与启动（二）创建测试计划（三）配置Web应用测试场景（四）运行测试（五）分析测试结果三、案例分析（一）案例背景（二）测试步骤（三）测试结果分析四、总结JMeter：性能测试利器......
  • pytest+allure生成测试报告
    1.安装allure-pytest插件allure生成报告是先生成结果再生成报告需要运行的代码：pytesttest_demo2.py--alluredir…report/tmp......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99