2024.2.3 寒假训练记录（17）

补一下牛客，菜得发昏了，F搞了两个小时都没搞出来，不如去开H了

在这里插入图片描述
还没补完 剩下的打了atc再来

文章目录

  • 牛客 寒假集训1A DFS搜索
  • 牛客 寒假集训1B 关鸡
  • 牛客 寒假集训1C 按闹分配
  • 牛客 寒假集训1D 数组成鸡
  • 牛客 寒假集训1E 本题又主要考察了贪心
  • 牛客 寒假集训1G why买外卖
  • 牛客 寒假集训1H 01背包，但是bit

牛客 寒假集训1A DFS搜索

题目链接

看数据很小于是纯暴力解法

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;

void solve()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	bool flag1 = false, flag2 = false;
	for (int i = 0; i < n; i ++ )
	{
		if (s[i] == 'd')
		{
			for (int j = i + 1; j < n; j ++ )
			{
				if (s[j] == 'f')
				{
					for (int k = j + 1; k < n; k ++ )
					{
						if (s[k] == 's')
						{
							flag1 = true;
							break;
						}
					}
					if (flag1) break;
				}
			}
			if (flag1) break;
		}
	}
	for (int i = 0; i < n; i ++ )
	{
		if (s[i] == 'D')
		{
			for (int j = i + 1; j < n; j ++ )
			{
				if (s[j] == 'F')
				{
					for (int k = j + 1; k < n; k ++ )
					{
						if (s[k] == 'S')
						{
							flag2 = true;
							break;
						}
					}
					if (flag2) break;
				}
			}
			if (flag2) break;
		}
	}
	if (flag2) cout << 1 << ' ';
	else cout << 0 << ' ';
	if (flag1) cout << 1 << '\n';
	else cout << 0 << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t -- )
	{
		solve();
	}
}

牛客 寒假集训1B 关鸡

题目链接

我是分两种讨论，从左边出去和从右边出去，先把坐标按y从小到大排序，遍历每一个坐标，看下一个坐标是不是在当前坐标的下面或者右下面或者右上面，是的话当前这一端就封死了

答案最大是3（在鸡的左右下）

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;

bool cmp(PII a, PII b)
{
	if (a.second != b.second) return a.second < b.second;
	else return a.first < b.first;
}

void solve()
{
	int n;
	cin >> n;
	vector<PII> pos(n);
	int cnt = 0;
	for (int i = 0; i < n; i ++ )
	{
		cin >> pos[i].first >> pos[i].second;
		if (pos[i].first == 1 && pos[i].second == -1) cnt ++ ;
		if (pos[i].first == 1 && pos[i].second == 1) cnt ++ ;
		if (pos[i].first == 2 && pos[i].second == 0) cnt ++ ;
	}
	sort(pos.begin(), pos.end(), cmp);
	if (n == 0)
	{
		cout << 3 << '\n';
		return;
	}
	if (cnt == 3)
	{
		cout << 0 << '\n';
		return;
	}
	bool flag1 = false, flag2 = false;
	for (int i = 0; i < n - 1; i ++ )
	{
		int x = pos[i].first, y = pos[i].second;
		if (y < 0)
		{
			if (flag1) continue;
			if (x == 1)
			{
				if (pos[i + 1].first == 2 && (pos[i + 1].second == y || pos[i + 1].second == y + 1)) flag1 = true;
			}
			else
			{
				if (pos[i + 1].first == 1 && pos[i + 1].second == y + 1) flag1 = true;
			}
		}
		else
		{
			if (flag2) break;
			if (x == 1)
			{
				if (pos[i + 1].first == 2 && (pos[i + 1].second == y || pos[i + 1].second == y + 1)) flag2 = true;
			}
			else
			{
				if (pos[i + 1].first == 1 && pos[i + 1].second == y + 1) flag2 = true;
			}
		}
	}
	if (flag1 && flag2) cout << 0 << '\n';
	else if (flag1)
	{
		int x = pos[n - 1].first, y = pos[n - 1].second;
		if (y >= 0) cout << 1 << '\n';
		else cout << 2 << '\n';
	}
	else if (flag2)
	{
		int x = pos[0].first, y = pos[0].second;
		if (y <= 0) cout << 1 << '\n';
		else cout << 2 << '\n';
	}
	else
	{
		int ans = 0;
		int x1 = pos[0].first, y1 = pos[0].second;
		int x2 = pos[n - 1].first, y2 = pos[n - 1].second;
		if (y1 <= 0) ans ++ ;
		else ans += 2;
		if (y2 >= 0) ans ++ ;
		else ans += 2;
		ans = min((i64)3, min(ans, 3 - cnt));
		cout << ans << '\n';
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t -- )
	{
		solve();
	}
}

牛客 寒假集训1C 按闹分配

题目链接

不知道为啥赛时脑抽写二分，实际上 O ( n ) O(n) O(n) 处理一下前缀和就搞定了

鸡插到某一个人前面，那增加的不满意度就是 t c t_c tc​ 乘上在鸡后面的人数，根据这个就能算出鸡最优能站在第几个人前面，剩下的前缀和就搞定了

下面代码还是二分，懒得写qaq

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;

void solve()
{
	int n, q, c;
	cin >> n >> q >> c;
	vector<int> t(n + 1), pre(n + 1), tmp(n + 2);
	for (int i = 1; i <= n; i ++ ) cin >> t[i], pre[i] = pre[i - 1] + t[i];
	for (int i = 1; i <= n; i ++ ) pre[i] = pre[i - 1] + pre[i];
	sort(t.begin(), t.end());
	for (int i = 1; i <= n + 1; i ++ ) tmp[i] = tmp[i - 1] + t[i - 1];
	while (q -- )
	{
		int m;
		cin >> m;
		auto check = [&](int mid)
		{
			int pos = upper_bound(tmp.begin(), tmp.end(), mid) - tmp.begin() - 1;
			int time = pre[n] + (n - pos + 1) * c;
			if (time - pre[n] > m) return false;
			else return true;
		};
		int l = 0, r = pre[n];
		while (l < r)
		{
			int mid = l + r >> 1;
			if (check(mid)) r = mid;
			else l = mid + 1;
		}
		cout << r + c << '\n';
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t -- )
	{
		solve();
	}
}

牛客 寒假集训1D 数组成鸡

题目链接

这题又可以学到一个trick，m的范围在1e9之内，但是30个2相乘就已经超过了，所以n给那么大完全是吓唬人的，如果n很大，那只能说明有很多一样的数要变成1 or -1，所以枚举每一个数变成-1开始到更小，从1开始到更大，只要乘积超过1e9直接停就可以了，最后要注意，如果一个数是0，乘积就肯定是0，所以0是很容易达成的，直接在一开始把0加入到可以得到的集合中，之后询问时每次查找集合中有没有这个数就可以了

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;
const int maxn = 1e6;
const int mod = 1e9 + 7;

void solve()
{
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	sort(a.begin(), a.end());
	set<int> st;
	st.insert(0);
	auto check = [&](int x)
	{
		int res = 1;
		for (int i = 0; i < n; i ++ )
		{
			res *= a[i] + x;
			if (res > 1e9) return false;
		}
		st.insert(res);
		return true;
	};
	for (int i = 0; i < n; i ++ )
	{
		if (i != n - 1 && a[i] == a[i - 1]) continue;
		for (int j = -a[i] - 1; check(j); j -- ) ;
		for (int j = -a[i] + 1; check(j); j ++ ) ;
	}
	while (q -- )
	{
		int m;
		cin >> m;
		cout << (st.count(m) ? "Yes" : "No") << '\n';
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t -- )
	{
		solve();
	}
}

牛客 寒假集训1E 本题又主要考察了贪心

题目链接

数据范围很小，dfs就可以

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	vector<PII> op;
	for (int i = 0; i < m; i ++ )
	{
		int x, y;
		cin >> x >> y;
		if (x == 1 || y == 1) a[1] += 3;
		else op.push_back(make_pair(x, y));
	}

	int ans = n;
	m = op.size();
	function<void(int)> dfs = [&](int u)
	{
		if (u == m)
		{
			int cnt = 0;
			for (int i = 2; i <= n; i ++ )
			{
				if (a[i] > a[1]) cnt ++ ;
			}
			ans = min(cnt + 1, ans);
			return;
		}
		int id1 = op[u].first, id2 = op[u].second;
		a[id1] ++ , a[id2] ++ ;
		dfs(u + 1);
		a[id1] += 2, a[id2] -- ;
		dfs(u + 1);
		a[id1] -= 3, a[id2] += 3;
		dfs(u + 1);
		a[id2] -= 3;
	};

	dfs(0);
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t -- )
	{
		solve();
	}
}

牛客 寒假集训1G why买外卖

题目链接

优惠券按照a排序，遍历一遍即可，利用前缀和

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;

bool cmp(PII a, PII b)
{
	if (a.first != b.first) return a.first < b.first;
	else return a.second > b.second;
}

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<PII> info(n);
	for (int i = 0; i < n; i ++ ) cin >> info[i].first >> info[i].second;
	sort(info.begin(), info.end(), cmp);
	int pre = 0;
	int i = 0, ans = m;
	for (i = 0; i < n; i ++ )
	{
		pre += info[i].second;
		if (info[i].first - pre > m) continue;
		else
		{
			int used = info[i].first - pre;
			ans = max(ans, info[i].first + m - used);
		}
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t -- )
	{
		solve();
	}
}

牛客 寒假集训1H 01背包，但是bit

题目链接

按照题解思路写的，枚举m的二进制中的每一位1，让最后的总重量在该位为0，在这一位之后的可以随便取，在这一位之前的必须是m的子集（意思是m那一位不为1的，总重量的那一位也不能为1），取最大值即可

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;
const int maxn = 1e5 + 1;
const int mod = 1e9 + 7;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> v(n), w(n);
	for (int i = 0; i < n; i ++ ) cin >> v[i] >> w[i];
	int ans = 0;
	for (int j = 0; j < n; j ++ )
	{
		bool flag = true;
		for (int k = 0; k <= 30; k ++ )
		{
			if ((((w[j] >> k) & 1) == 1) && (((m >> k) & 1) == 0))
			{
				flag = false;
				break;
			}
		}
		if (flag) ans += v[j];
	}
	for (int i = 0; i <= 30; i ++ )
	{
		if ((m & (1 << i)) == 0) continue;
		int tmp = 0;
		for (int j = 0; j < n; j ++ )
		{
			bool flag = true;
			if (((w[j] >> i) & 1) == 1) continue;
			for (int k = i + 1; k <= 30; k ++ )
			{
				if ((((w[j] >> k) & 1) == 1) && (((m >> k) & 1) == 0))
				{
					flag = false;
					break;
				}
			}
			if (flag) tmp += v[j];
		}
		ans = max(ans, tmp);
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t -- )
	{
		solve();
	}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/368848.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

react 使用react-seamless-scroll实现无缝滚动

react 使用react-seamless-scroll实现无缝滚动

文章目录 1. 实现无缝滚动效果2. react-seamless-scroll 无缝滚动案例介绍3. react 项目集成3.1 项目引入 cssSeamlessScroll 滚动组件3.2 完整代码3.2.1 newBet.tsx 代码3.2.2 index.module.scss 1. 实现无缝滚动效果 实现单步向下滚动点击更多展开&#xff0c;收起&#xff0…
阅读更多...
Python爬虫urllib详解

Python爬虫urllib详解

前言 学习爬虫&#xff0c;最初的操作便是模拟浏览器向服务器发出请求&#xff0c;那么我们需要从哪个地方做起呢&#xff1f;请求需要我们自己来构造吗&#xff1f;需要关心请求这个数据结构的实现吗&#xff1f;需要了解 HTTP、TCP、IP 层的网络传输通信吗&#xff1f;需要知…
阅读更多...
Java八大常用排序算法

Java八大常用排序算法

1冒泡排序 对于冒泡排序相信我们都比较熟悉了&#xff0c;其核心思想就是相邻元素两两比较&#xff0c;把较大的元素放到后面&#xff0c;在一轮比较完成之后&#xff0c;最大的元素就位于最后一个位置了&#xff0c;就好像是气泡&#xff0c;慢慢的浮出了水面一样 Jave 实现 …
阅读更多...
RabbitMQ_00000

RabbitMQ_00000

MQ的相关概念 RabbitMQ官网地址&#xff1a;https://www.rabbitmq.com RabbitMQ API地址&#xff1a;https://rabbitmq.github.io/rabbitmq-java-client/api/current/ 什么是MQ&#xff1f; MQ(message queue)本质是个队列&#xff0c;FIFO先入先出&#xff0c;只不过队列中…
阅读更多...
Jmeter 基于Docker 实现分布式测试

Jmeter 基于Docker 实现分布式测试

基于Docker 实现分布式测试 制作Jmeter基础镜像制作工作节点镜像启动工作节点启动控制节点遇到的问题 使用Docker 部署Jmeter非常方便&#xff0c;可以省略软件的安装以及配置&#xff0c;比如jdk、jmeter。需要部署多个工作节点可以节省时间。 制作Jmeter基础镜像 下载jmeter…
阅读更多...
Kubernetes集群搭建

Kubernetes集群搭建

一、概述 Kubernetes是一个Google开源的全新的分布式容器集群管理系统&#xff0c;由于从第一个字母到字母s中间有8个字母&#xff0c;所以简称K8s。 二、准备 ip角色内存192.168.187.130master4G192.168.187.131node2G192.168.187.132node2G 小提示&#xff1a; 设置静态i…
阅读更多...
【课程作业_01】国科大2023模式识别与机器学习实践作业

【课程作业_01】国科大2023模式识别与机器学习实践作业

国科大2023模式识别与机器学习实践作业 作业内容 从四类方法中选三类方法&#xff0c;从选定的每类方法中 &#xff0c;各选一种具体的方法&#xff0c;从给定的数据集中选一 个数据集&#xff08;MNIST&#xff0c;CIFAR-10&#xff0c;电信用户流失数据集 &#xff09;对这…
阅读更多...
TCP TIME_WAIT 过多怎么处理

TCP TIME_WAIT 过多怎么处理

文章目录 1.什么是 TCP TIME_WAIT&#xff1f;2.为什么要 TIME_WAIT?3.TIME_WAIT 过多的影响4.解决办法4.1 调整短连接为长连接4.2 调整系统内核参数 5.小结参考文献 1.什么是 TCP TIME_WAIT&#xff1f; TCP 断开连接四次挥手过程中&#xff0c;主动断开连接的一方&#xff…
阅读更多...
ctfshow——文件包含

ctfshow——文件包含

文章目录 web 78——php伪协议第一种方法——php://input第二种方法——data://text/plain第三种方法——远程包含&#xff08;http://协议&#xff09; web 78——str_replace过滤字符php第一种方法——远程包含&#xff08;http://协议&#xff09;第二种方法——data://&…
阅读更多...
游戏被DDOS攻击无法访问时该如何处理

游戏被DDOS攻击无法访问时该如何处理

游戏行业随着时代的发展有着突飞猛进的变化&#xff0c;尤其是互联网时代智能手机的普及&#xff0c;让游戏行业发展上了一个新的台阶。因为游戏带来的巨大利润&#xff0c;游戏行业一直是DDoS攻击的首选目标。 DDoS是Distributed Denial of Service的缩写&#xff0c;即分布式…
阅读更多...
学习Android的第二天

学习Android的第二天

目录 Android User Interface 用户界面 UI Android View与ViewGroup的概念 Android View android.view.View android.view.View XML 属性 android:id 属性 Android ViewGroup android.view.ViewGroup ViewGroup.LayoutParams ViewGroup.MarginLayoutParams ViewGr…
阅读更多...
Redis核心技术与实战【学习笔记】 - 19.Pika：基于SSD实现大容量“Redis”

Redis核心技术与实战【学习笔记】 - 19.Pika：基于SSD实现大容量“Redis”

前言 随着业务数据的增加&#xff08;比如电商业务中&#xff0c;随着用户规模和商品数量的增加&#xff09;&#xff0c;就需要 Redis 能保存更多的数据。你可能会想到使用 Redis 切片集群&#xff0c;把数据分散保存到不同的实例上。但是这样做的话&#xff0c;如果要保存的…
阅读更多...
java社区养老年人服务系统springboot+vue

java社区养老年人服务系统springboot+vue

为了帮助用户更好的了解和理解程序的开发流程与相关内容&#xff0c;本文将通过六个章节进行内容阐述。 第一章&#xff1a;描述了程序的开发背景&#xff0c;程序运用于现实生活的目的与意义&#xff0c;以及程序文档的结构安排信息&#xff1b; 第二章&#xff1a;描述了程序…
阅读更多...
uniapp 高德地图显示

uniapp 高德地图显示

1. uniapp 高德地图显示 使用前需到**高德开放平台&#xff08;https://lbs.amap.com/&#xff09;**创建应用并申请Key   登录 高德开放平台&#xff0c;进入“控制台”&#xff0c;如果没有注册账号请先根据页面提示注册账号   打开 “应用管理” -> “我的应用”页面…
阅读更多...
Leetcode 85. 最大矩形

Leetcode 85. 最大矩形

题目信息 LeetoCode地址: 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目理解 该题是84题的升级版。84题给出了一个一维数组&#xff0c;即一行数据&#xff0c;每个元素是高度。而该题则是给出了二维数组&#xff0c;只需我们将每一行的高度…
阅读更多...
太强了，AI数字人从制作到变现一次搞定

太强了，AI数字人从制作到变现一次搞定

AI数字人从制作到变现 如果说GPT类大模型是我们人类的第二大脑&#xff0c;数字人就是我们人类在互联网上的第二个身体。随着 AI 的迅速发展&#xff0c;2024 年 AI 模型开始从大型语言模型向大型视觉模型转变。数字人技术作为其分支之一&#xff0c;正日益成为科技、娱乐、教…
阅读更多...
【GAMES101】Lecture 14 15 辐射度量学

【GAMES101】Lecture 14 15 辐射度量学

目录 辐射度量学 Radiant flux&#xff08;光通量&#xff09; intensity&#xff08;发光强度&#xff09; irradiance radiance 辐射度量学 主要讲述了物理学中的Basic radiometry (辐射度量学)&#xff0c;就是我们在之前的计算光照中没有用具体的物理单位去衡量和描述…
阅读更多...
C++新特性 协程

C++新特性 协程

本篇文章我们来讲述一下C协程 协程&#xff08;Coroutine&#xff09;是一种能够挂起个恢复的函数过程 是一种轻量级的并发编程方式&#xff0c;也称为用户级线程。它与传统的线程&#xff08;Thread&#xff09;相比&#xff0c;具有更低的开销和更高的执行效率。 协程通常运…
阅读更多...
爬虫学习笔记-scrapy爬取汽车之家

爬虫学习笔记-scrapy爬取汽车之家

1.终端运行scrapy startproject scrapy_carhome,创建项目 2.接口查找 3.终端cd到spiders,cd scrapy_carhome/scrapy_carhome/spiders,运行 scrapy genspider audi https://car.autohome.com.cn/price/brand-33.html 4.打开audi,编写代码,xpath获取页面车型价格列表 5.运行项目…
阅读更多...
深度学习技巧应用35-L1正则化和L2正则在神经网络模型训练中的应用

深度学习技巧应用35-L1正则化和L2正则在神经网络模型训练中的应用

大家好，我是微学AI，今天给大家介绍一下深度学习技巧应用35-L1 正则化和L2正则在神经网络模型训练中的应用。L1正则化和L2正则化是机器学习中常用的两种正则化方法，用于防止模型过拟合并提高模型的泛化能力。这两种正则化方法通过在损失函数中添加惩罚项来控制模型的复杂性。…
阅读更多...
最新文章

Copyright @ 2022~2023