Codeforces Round 938 (Div. 3) A - F 题解

A. Yogurt Sale

题意：要购买n个酸奶，有两种买法，一种是一次买一个，价格a。一种是一次买两个，价格b，问买n个酸奶的最小价格。
题解：很容易想到用2a和b比较，判断输出即可。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 4e5 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , k , c , a[maxn] ;
ll head[maxn] , nxt[maxn] , ver[maxn] , cnt , ans ;

void solve(){
	n = read() ;
	k = read() ;
	c = read() ;
	if(k * 2 <= c){
		cout << n * k << endl ;
		return ;
	}
	else{
		cout << (n / 2) * c + (n - (n / 2) * 2) * k << endl ;
	}
}

int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

B. Progressive Square

题意：给你n，c，d，你要生成n*n的矩阵，按照规则a_{i+ 1,j} = a_{i,j} + c , a_{i,j + 1} = a_{i,j} + d。给你n*n个数字，看看能否生成这样的矩阵并且包含所有数字。
题解：用最小数字开始枚举即可，n范围在500，轻松通过。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , k , c , a[maxn] ;
ll head[maxn] , nxt[maxn] , ver[maxn] , cnt , ans ;
ll b[550][550] ;
vector < ll > q ;
void solve(){
	q.clear() ;
	n = read() ;
	k = read() ;
	c = read() ;
	for(int i = 1 ; i <= n * n ; i ++){
		a[i] = read() ;
	}
	sort(a + 1 , a + n * n + 1) ;
	ll rt = a[1] ;
	b[1][1] = rt ;
	for(int i = 2 ; i <= n ; i ++){
		b[1][i] = b[1][i - 1] + c ;
  	}
	for(int i = 2 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			b[i][j] = b[i - 1][j] + k ;
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			q.push_back(b[i][j]) ;
		}
	}
	sort(q.begin() , q.end()) ;
	ll Rt = 0 ;
	for(int i = 1 ; i <= n * n ; i ++){
		if(q[Rt] != a[i]){
			cout << "NO\n" ;
			return ;
		}
		Rt ++ ;
	}
	cout << "YES" << endl ;
}

int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

C. Inhabitant of the Deep Sea

题意： 给你n个数字和k，每次怪兽都会按照攻击前面一次再攻击后面一次的顺序攻击，每次造成1滴血量伤害，问最多能击败多少个船。
题解：可以将k分解成两部分，然后枚举统计答案即可。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , k , c , a[maxn] ;
ll head[maxn] , nxt[maxn] , ver[maxn] , cnt , ans ;
vector < ll > q ;
void solve(){
	n = read() ;
	k = read() ;
	for(int i = 1 ; i <= n ; i ++){
		a[i] = read() ;
	}
	ll l = (k + 2 - 1) / 2 ;
	ll r = k / 2 ;
	ll rt = 1 ;
	ll ans = 0 ;
	while(l != 0){
		if(rt > n){
			break ;
		}
		if(l - a[rt] >= 0){
			l -= a[rt] ;
			ans ++ ;
			a[rt] = 0 ;
			rt ++ ;
		}
		else{
			a[rt] -= l ;
			l = 0 ;
			break ;
		}
	}
	rt = n ;
	while(r != 0){
		if(rt < 1){
			break ;
		}
		if(a[rt] == 0){
			break ;
		}
		if(r - a[rt] >= 0){
			r -= a[rt] ;
			ans ++ ;
			a[rt] = 0 ;
			rt -- ;
		}
		else{
			a[rt] -= r ;
			r = 0 ;
			break ;
		}
	}
	cout << ans << endl ;
}

int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

D. Inaccurate Subsequence Search

题意：给你一个数组a和数组b，长度分别为n和m，看看有多少组可以满足1<=l<=n - m + 1满足至少有k个相同的数字？
题解：可以用STL里的map来统计数组b，然后先用map统计1-m的数字有多少相同的，定义l = 1, r = m，然后每次让l++，r++，统计有多少个相同数字，直接统计答案即可。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , k , c , a[maxn] , b[maxn] ;
ll head[maxn] , nxt[maxn] , ver[maxn] , cnt , ans ;
vector < ll > q ;
void solve(){
	map < ll , ll > mp , p ;
	n = read() ;
	k = read() ;
	c = read() ;
	for(int i = 1 ; i <= n ; i ++){
		a[i] = read() ;
	}
	for(int i = 1 ; i <= k ; i ++){
		b[i] = read() ;
		mp[b[i]] ++ ;
	}
	ll sum = 0 , ans = 0 ;
	for(int i = 1 ; i <= k ; i ++){
		p[a[i]] ++ ;
		if(p[a[i]] <= mp[a[i]]){
			sum ++ ;
		}
	}
	if(sum >= c){
		ans ++ ;
	}
	ll l = 1 , r = k ;
	while(1){
		if(r >= n){
			break ;
		}
		if(p[a[l]] - 1 < mp[a[l]]){
			sum -- ;
			p[a[l]] -- ;
		}
		else{
			p[a[l]] -- ;
		}
		if(p[a[r + 1]] + 1 <= mp[a[r + 1]]){
			sum ++ ;
			p[a[r + 1]] ++ ;
		}
		else{
			p[a[r + 1]] ++ ;
		}
		if(sum >= c){
			ans ++ ;
		}
		l ++ ;
		r ++ ;
	}
	cout << ans << endl ;
}

int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

E. Long Inversions

题意：给你一个字符串s，可以选择一个k，每次修改i<=l<=i + k - 1，翻转里面所有的数字，将0变成1，将1变成0，目标是想要将序列全部变成1,。问能满足最大的k是多少。
题解：看到最大的k，先想到了二分，能否从小推大，但是发现不行，那么看到数据n<=5000，那么可以想到枚举即可，n^2logn可以通过，首先思考怎么看能否能将所有的数字变成1，很明显从前面到后面依次遍历，如果碰到了0，那么就翻转当前位置i到i + k - 1。那么现在的复杂度是n^3，很明显通过不了。那么就想到了数据结构，那么就想到用树状数组来维护。如果说当前为0，那么就让i<=j<=i + k - 1加1，如果说(a[i] + query(a[i]) mod 2) mod 2等于0，那么就区间增加1，如果说等于1那么就不修改，最后遍历一遍看看是否全为1即可。复杂度O(n^2logn)。

代码：

#include<bits/stdc++.h>
#define ll long long
const int maxn = 5000 + 7 ;
using namespace std;
ll t , n , m , p , l , r , a[maxn] , tree[maxn] ;
char s[maxn];
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll lowbit(ll x){
	return x & (-x) ;
}
void update(ll x , ll y){
	for( ;x <= n ; x += lowbit(x)){
		tree[x] += y ;
	}
}
ll Query(ll x){
	ll ans = 0 ;
	while(x != 0){
		ans += tree[x] ;
		x -= lowbit(x) ;
	}
	return ans ;
}
void solve(){
	n = read() ;
	scanf("%s" , s + 1) ;
	for(int i = 1 ; i <= n ; i ++) 
		a[i] = s[i] - '0' ;
	for(int i = n ; i >= 1 ; i --){
		for(int j = 0 ; j <= n ; j ++){
			tree[j] = 0 ;
		}
		bool f = 0 ;
		for(int j = 1 ; j + i - 1 <= n ; j ++){
			ll res = (a[j] + (Query(j) % 2)) % 2 ;
			if(res == 0){
				update(j , 1) ;
				update(j + i , -1) ;
			}
		}
		for(int j = 1 ; j <= n ; j ++){
			ll res = (a[j] + (Query(j) % 2)) % 2 ;
			if(res == 0){
				f = 1 ;
			}
		}
		if(f == 0){
			cout << i << endl ;
			return ;
		}
	}
	cout << 1 << endl ;
}
int main()
{
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0;
}
注：也不知道为什么，我一开始用线段树写T了5发，也不知道是我常熟大吗！

F. Unfair Game

题意：给你四个数字，分别代表1,2,3,4的数量，Alice和Bob在进行游戏，如果说所有的数字异或和不为0那么Alice赢，如果说是0那么Bob赢，Eve每次会去掉一个数字，每次都用最优的方式去掉数字，问最多Bob能获胜多少次。
题解：这个题其实很好想，首先可以想到4只要有那么就一定和1，2,3没有任何关系，因为无法组成0，那么就将4的数量单独拿出来看，再看1，2,3的数量，可以想到1和2可以和3抵消掉，然后就可以想出一种方法，就是将1,2,3的数量取min，然后加上4的数量除以2，是一种情况，再看如果说每个的数字是偶数的话，那么很明显比1,2,3抵消要更优，因为每个数字是偶数，如果说是第一种情况最多是2，但是第二种情况每次减2的话答案可以增加3。最后就是特殊的情况，比如1,2，3的数量一样，并且全是奇数，那么答案要加1。如果说三个数字都是奇数，那么答案也要加1。这个题就迎刃而解了。复杂度非常低！
代码：
#include<bits/stdc++.h>
#define ll long long
const int maxn = 5000 + 7 ;
using namespace std;
ll t , n , m , p , l , r , tree[maxn] ;
char s[maxn];
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll a , b , c , d ;
void solve(){
	a = read() ;
	b = read() ;
	c = read() ;
	d = read() ;
	bool f = 0 ;
	if((a == b && b == c && a % 2 == 1) || ((a % 2 == 1) && (b % 2 == 1) && (c % 2 == 1))){
		f = 1 ;
	}
	ll res = (min(min(a , b) , c) + d / 2) ;
	ll Res = (a / 2) + (b / 2) + (c / 2) + (d / 2) + ((f == 1) ? 1 : 0) ;
	cout << max(res , Res) << endl ;
}                                                                                                                                                                                              
int main()
{
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0;
}

喜欢作者的记得点赞收藏加关注哦~

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

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

相关文章

小程序开发SSL证书下载和安装

小程序开发SSL证书下载和安装

在开发小程序时&#xff0c;确保数据的安全传输至关重要&#xff0c;而实现这一目标的关键在于正确获取与安装SSL证书。以下详细介绍了从获取到安装SSL证书的完整流程&#xff0c;以助您为小程序构建可靠的加密通信环境。 一、小程序SSL证书类型选择&#xff1a; 域名验证型D…
阅读更多...
【PyTorch][chapter 25][李宏毅深度学习][Transfer Learning-1]

【PyTorch][chapter 25][李宏毅深度学习][Transfer Learning-1]

前言&#xff1a; 迁移学习是一种机器学习的方法,指的是一个预训练的模型被重新用在另一个任务中。 比如已经有个模型A 实现了猫狗分类 模型B 要实现大象和老虎分类,可以利用训练好的模型A 的一些参数特征,简化当前的训练 过程. 目录&#xff1a; 简介 Model Fine-Tuning (…
阅读更多...
【C++】类和对象①（什么是面向对象 | 类的定义 | 类的访问限定符及封装 | 类的作用域和实例化 | 类对象的存储方式 | this指针）

【C++】类和对象①（什么是面向对象 | 类的定义 | 类的访问限定符及封装 | 类的作用域和实例化 | 类对象的存储方式 | this指针）

目录 前言 什么是面向对象&#xff1f; 类的定义 类的访问限定符及封装 访问限定符 封装 类的作用域 类的实例化 类对象的存储方式 this指针 结语 前言 最早的C版本&#xff08;C with classes&#xff09;中&#xff0c;最先加上的就是类的机制&#xff0c;它构成…
阅读更多...
Day3-HBase重要概念

Day3-HBase重要概念

HBase 结构 HRegion 概述 在HBase中&#xff0c;会从行键方向上对表来进行切分&#xff0c;切分出来的每一个结构称之为是一个HRegion 切分之后&#xff0c;每一个HRegion会交给某一个HRegionServer来进行管理。HRegionServer是HBase的从节点&#xff0c;每一个HRegionServ…
阅读更多...
如何使用Java和RabbitMQ实现延迟队列（方式二）？

如何使用Java和RabbitMQ实现延迟队列（方式二）？

前言 昨天写了一篇关于Java和RabbitMQ使用插件实现延迟队列功能的文章&#xff0c;今天来讲下另外一种方式&#xff0c;不需要RabbitMQ的插件。 前期准备&#xff0c;需要安装好docker、docker-compose的运行环境。 需要安装RabbitMQ的可以看下面这篇文章。 如何使用PHP和R…
阅读更多...
Spring Cloud微服务入门（四）

Spring Cloud微服务入门（四）

应用容错的概念 应用错误-雪崩效应 定义&#xff1a; 服务雪崩效应是一种因“服务提供者的不可用”&#xff08;原因&#xff09;导致“服务调用者不可用”&#xff08;结果&#xff09;&#xff0c;并将不可用逐渐放大的现象。 服务雪崩的过程可以分为三个阶段&#xff1a; 服…
阅读更多...
Excel全套213集教程

Excel全套213集教程

Excel全套213集教程 包含技术入门93集 图表17集 数据透视35集 公式函数68 基础入门 93节 https://www.alipan.com/s/cMxuPstkS1x 提取码: 77dd 点击链接保存&#xff0c;或者复制本段内容&#xff0c;打开「阿里云盘」APP &#xff0c;无需下载极速在线查看&#xff0c;视…
阅读更多...
电商社交新零售：创新引领新趋势，变革新零售思维格局-亿发

电商社交新零售：创新引领新趋势，变革新零售思维格局-亿发

新零售O2O模式是如何颠覆传统零售商业模式&#xff1f; 传统电商出现瓶颈&#xff1a; 传统电商在发展过程中逐渐出现了瓶颈&#xff0c;主要表现在市场竞争激烈、用户获取成本上升、用户黏性下降等问题。传统电商往往只能通过价格竞争或促销活动来吸引用户&#xff0c;而这种…
阅读更多...
SSL、TLS和HTTPS：网络安全的重要基石

SSL、TLS和HTTPS：网络安全的重要基石

随着互联网的快速发展&#xff0c;网络安全问题日益凸显。为了保护数据在传输过程中的安全&#xff0c;各种加密协议和技术应运而生。SSL&#xff08;安全套接层&#xff09;、TLS&#xff08;传输层安全&#xff09;和HTTPS&#xff08;超文本传输安全协议&#xff09;是三个最…
阅读更多...
超级agent的端语言模型Octopus v2: On-device language model for super agent

超级agent的端语言模型Octopus v2: On-device language model for super agent

大型语言模型&#xff08;LLMs&#xff09;在函数调用方面展现出卓越的应用潜力&#xff0c;特别是针对Android API的定制应用。与那些需要详尽描述潜在函数参数、有时甚至涉及数万个输入标记的检索增强生成&#xff08;RAG&#xff09;方法相比&#xff0c;Octopus-V2-2B在训练…
阅读更多...
uniapp引入微信小程序版本VantUI，使用VantUI的自定义tabbar，并解决自定义tabbar出现闪烁的情况

uniapp引入微信小程序版本VantUI，使用VantUI的自定义tabbar，并解决自定义tabbar出现闪烁的情况

1.uniapp引入微信小程序版本VantUI 去vant官网下载源码&#xff0c;源码放在github&#xff0c;自行去下载下来 https://vant-contrib.gitee.io/vant-weapp/#/home 在pages.json的globalStyle里面注册组件 "globalStyle": {"navigationBarTextStyle": &qu…
阅读更多...
gitlab使用

gitlab使用

个人笔记&#xff08;整理不易&#xff0c;有帮助点个赞&#xff09; 笔记目录&#xff1a;学习笔记目录_pytest和unittest、airtest_weixin_42717928的博客-CSDN博客 个人随笔&#xff1a;工作总结随笔_8、以前工作中都接触过哪些类型的测试文档-CSDN博客 目录 一&#xff1a…
阅读更多...
【xcode15.3 打包报错 Command SwiftCompile failed with a nonzero exit code】

【xcode15.3 打包报错 Command SwiftCompile failed with a nonzero exit code】

升级Xcode15后 打包报错 xxx Command SwiftCompile failed with a nonzero exit code 解决办法&#xff1a; 选中pod 报错的库 Code Generation->Compilation Mode改成和debug一样的 Incremental。
阅读更多...
智慧水库解决方案（打造水库智慧监测体系）

智慧水库解决方案（打造水库智慧监测体系）

​作为一名水利自动化系统集成商,最近我司接手了一个智慧水库建设项目。这个项目位于一座山区的大型水库,目的是对其进行现代化、智能化改造,提升供水、防洪等管理水平。&#xff08;key-iot.com.cn&#xff09; 在方案设计之初,我们组织了现场勘测,全面了解水库的实际情况。这…
阅读更多...
完全可定制的富文本编辑器：逻辑清晰，插件赋能 | 开源日报 No.218

完全可定制的富文本编辑器：逻辑清晰，插件赋能 | 开源日报 No.218

ianstormtaylor/slate Stars: 28.8k License: MIT slate 是一个完全可定制的框架&#xff0c;用于构建富文本编辑器。 可以构建类似 Medium、Dropbox Paper 或 Google Docs 的富文本编辑器通过一系列插件实现所有逻辑&#xff0c;避免代码复杂度受到 Draft.js、Prosemirror 和…
阅读更多...
最少按键次数

最少按键次数

题目描述 给你一个字符串 s&#xff0c;由小写英文字母组成。 电话键盘上的按键与 不同 小写英文字母集合相映射&#xff0c;可以通过按压按键来组成单词。例如&#xff0c;按键 2 对应 ["a","b","c"]&#xff0c;我们需要按一次键来输入 &quo…
阅读更多...
web前端框架设计第四课-条件判断与列表渲染

web前端框架设计第四课-条件判断与列表渲染

web前端框架设计第四课-条件判断与列表渲染 一.预习笔记 1.条件判断 1-1&#xff1a;v-if指令&#xff1a;根据表达式的值来判断是否输出DOM元素 1-2&#xff1a;template中使用v-if 1-3&#xff1a;v-else 1-4&#xff1a;v-else-if 1-5&#xff1a;v-show&#xff08;不支…
阅读更多...
默克尔（Merkle）树 - 原理及用途

默克尔（Merkle）树 - 原理及用途

默克尔&#xff08;Merkle&#xff09;树的原理以及用途 引言 在当今数字化时代&#xff0c;确保数据的完整性是至关重要的。默克尔树作为一种高效的数据结构&#xff0c;被广泛应用于网络安全、分布式系统以及加密货币等领域&#xff0c;用于验证大量数据的完整性和一致性 数…
阅读更多...
20240408在全志H3平台的Nano Pi NEO CORE开发板的eMMC刷Ubuntu Core 16.04

20240408在全志H3平台的Nano Pi NEO CORE开发板的eMMC刷Ubuntu Core 16.04

20240408在全志H3平台的Nano Pi NEO CORE开发板的eMMC刷Ubuntu Core 16.04 2024/4/8 20:46 参考资料&#xff1a; https://wiki.friendlyelec.com/wiki/index.php/NanoPi_NEO_Core/zh#.E5.AE.89.E8.A3.85.E7.B3.BB.E7.BB.9F [ OK ] Created slice Slice /system/getty. [ …
阅读更多...
linux centos 系统 docker及podman拉取kylin麒麟镜像内部及部署安装Gaussdb数据库

linux centos 系统 docker及podman拉取kylin麒麟镜像内部及部署安装Gaussdb数据库

研究总结来之不易 1.首先下载安装包&#xff0c;网址&#xff1a; 软件包 | openGauss 2.参考安装连接&#xff1a; 单节点安装 openGauss学习笔记-03 openGauss极简版单节点安装_opengauss 笔记-CSDN博客 当然他们说的有些也是不完全一样的&#xff0c;根据自己的环境摸索…
阅读更多...
最新文章

Copyright @ 2022~2023