Educational Codeforces Round 167 (Rated for Div. 2)(A~C)题解

A. Catch the Coin

 

 解题思路:

最终𝑥一定会相等,我们考虑直接到下面接住他。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], h[N];
ll dis[1005][1005];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
struct node {
	ll a, b, c;
}f[N];
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> a >> b;
		if (b>=-1) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

B. Substring and Subsequence

 

解题思路:

由于 a 是肯定全部要出现的,因此只要找出在 a 中最多能匹配上 b 中的多少个字符

不难发现 b 中匹配的一定是连续的一段,因此可以暴力枚举区间然后暴力检验

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], h[N];
ll dis[1005][1005];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
struct node {
	ll a, b, c;
}f[N];
string s1, s2;
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> s1 >> s2;
	    ans = 0;
		for (int i = 0; i < s2.size(); i++) {
			ll num1 = i, num2 = 0;
			for (int j = 0; j < s1.size(); j++) {
				if (s1[j] == s2[num1]) {
					num1++;
					num2++;
				}
			}
			ans = max(ans, num2);
		}
		
		cout << s1.size() + s2.size() - ans << endl;
	}
	return 0;
}

C. Two Movies

 

解题思路:

首先如果 ai,bi不同,则直接把评分加到较大的那个数上去一定是最优的,这个分析一下会发现对于所有情形成立

在此基础上可以先得到两部电影的评分,分别记为 x, y,然后考虑将剩下的1 1数量记为 X,-1 -1数量记为 Y

分类讨论一下加入 X 个 1 和 Y 个 −1 的影响即可,每次先把两个数做到平均一定是最优的

代码:


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], h[N];
ll dis[1005][1005];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
struct node {
	ll a, b, c;
}f[N];
string s1, s2;
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n;
		int x=0, y=0, X=0, Y=0;
		for (int i = 1; i <= n; i++)
			cin >> w[i];
		for (int j = 1; j <= n; j++)
			cin >> v[j];
		for (int i = 1; i <= n; i++) {
			if (w[i] != v[i]) {
				if (w[i] > v[i]) x+=w[i];
				else y+=v[i];
			}
			else {
				if (w[i] == 1) {
					X++;
				}
				else if (w[i]==-1) {
					Y++;
				}
			}
		}
		if (X <= abs(x - y)) {
			if (x <= y) x += X;
			else y += X;
		}
		else {
			int k = X - abs(x - y);
			maxx = max(x, y);
			x = y = maxx;
			x += k / 2, y += (k + 1) / 2;
		}
		if (Y <= abs(x - y)) {
			if (x <= y) y -= Y;
			else x -= Y;
		}
		else {
			int k = Y - abs(x - y);
			minn = min(x, y);
			x = y = minn;
			x -= k / 2, y -= (k + 1) / 2;
		}
		cout << min(x, y) << endl;
	}
	return 0;
}

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

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

相关文章

【数据结构与算法】希尔排序

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法》 期待您的关注 ​

CH552G使用的pwm出现的问题,及设置

输出pwm的频率周期很不准确 可能是因为没有外部晶振的稳定晶振周期有关。 使用的示波器出现操作失误 在使用小型示波器的过程中发现集成了信号发生器和示波器的连接端口是不同的。刚开始把示波器测试口错插入了信号发生器的接口&#xff0c;困扰好一会儿&#xff0c;幸好用一…

人工智能、机器学习、神经网络、深度学习和卷积神经网络的概念和关系

人工智能&#xff08;Artificial Intelligence&#xff0c;缩写为AI&#xff09;--又称为机器智能&#xff0c;是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 人工智能是智能学科重要的组成部分&#xff0c;它企图了解智能的实质…

浅谈进程隐藏技术

前言 在之前几篇文章已经学习了解了几种钩取的方法 浅谈调试模式钩取浅谈热补丁浅谈内联钩取原理与实现导入地址表钩取技术 这篇文章就利用钩取方式完成进程隐藏的效果。 进程遍历方法 在实现进程隐藏时&#xff0c;首先需要明确遍历进程的方法。 CreateToolhelp32Snapsh…

区块链技术如何改变供应链管理?

引言 供应链管理在现代商业中扮演着至关重要的角色&#xff0c;确保产品和服务从原材料到最终消费者的顺利流转。然而&#xff0c;当前的供应链管理面临诸多挑战&#xff0c;如信息不透明、数据篡改和效率低下等问题&#xff0c;这些问题严重制约了供应链的整体效能和可信度&am…

Go:hello world

开启转职->Go开发工程师 下面是我的第一个go的程序 在上面的程序介绍&#xff1a; 1、package main 第一行代码package main定义了包名。必须在源文件中非注释的第一行指明这个文件属于哪个包&#xff0c;如&#xff1a;package main。package main表示一个可独立执行的程…

acwing 291.蒙德里安的梦想

解法&#xff1a; 核心&#xff1a;先放横着的&#xff0c;再放竖着的。 总方案数&#xff0c;等于只放横着的小方块的合法方案数。 如何判断当前方案是否合法&#xff1f;所有剩余位置&#xff0c;能否填充满竖着的小方块。 即按列来看&#xff0c;每一列内部所有连续的空着的…

DoIP-1 简介

1. 概述 DoIP-Diagnostic Over Internet Protocol &#xff0c;基于TCPIP协议族的诊断传输协议 DoIP国际标准定义为ISO 13400&#xff0c;总共由五部分组成&#xff1a;  ISO13400-1DoIP的综述  ISO13400-2DoIP的传输层和网络层服务&#xff08;主体部分&#xff09;  I…

JavaSe系列二十七: Java正则表达式

正则表达式 为什么要学习正则表达式再提几个问题解决之道-正则表达式正则表达式基本介绍介绍 正则表达式底层实现实例分析 正则表达式语法基本介绍元字符-转义号 \\\\元字符-字符匹配符元字符-选择匹配符元字符-限定符元字符-定位符分组非贪婪匹配 应用实例对字符串进行如下验证…

【c++刷题笔记-数组】day29:452. 用最少数量的箭引爆气球、 435. 无重叠区间 、 763.划分字母区间

452. 用最少数量的箭引爆气球 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a;先按照左边界排序&#xff0c;当前的左边界大于前一个的右边界的时候&#xff0c;表示没有覆盖所以需要一根箭&#xff0c;反之则要更新为最小的右边界 重点&#xff1a;是区间覆盖问题…

webrtc gcc详解

webrtc的gcc算法(Google Congestion Control)&#xff0c;貌似国内很多文章都没有细讲&#xff0c;原理是怎么样的&#xff0c;具体怎么进行计算的。这里详解一下gcc。 gcc算法&#xff0c;主要涉及到&#xff1a; 拥塞控制的关键信息和公式 卡曼滤波算法 gcc如何使用卡曼滤…

JavaScript 原型链那些事

在讲原型之前我们先来了解一下函数。 在JS中&#xff0c;函数的本质就是对象&#xff0c;它与其他对象不同的是&#xff0c;创建它的构造函数与创建其他对象的构造函数不一样。那产生函数对象的构造函数是什么呢&#xff1f;是一个叫做Function的特殊函数&#xff0c;通过newFu…

Python从入门到放弃——深入研究Print函数

深入浅出Print函数 第一个代码“Hello World” 在正常配置了PyCharm或者Thonny等编辑器之后&#xff0c;我们开始写第一个代码。正常的情况下学习一门编程语言&#xff0c;一般第一个代码都是输出Hello World。那么如何打印Hello World呢&#xff1f; print("Hello Wor…

第六十八回 东平府误陷九纹龙 宋公明义释双枪将-文心大模型ernie-speed免费使用方法

宋江和卢俊义抓阄儿&#xff0c;宋江打东平府&#xff0c;卢俊义打东昌府&#xff0c;谁先打下谁做梁山泊主。宋江带领林冲、花荣、刘唐等二十八人&#xff0c;卢俊义带领吴用、公孙胜、关胜等二十八人。 宋江等人到了东平府外安山镇&#xff0c;郁保四和王定六自告奋勇去下战…

io流 多线程

目录 一、io流 1.什么是io流 2.流的方向 i.输入流 ii.输出流 3.操作文件的类型 i.字节流 1.拷贝 ii.字符流 ​3.字符流输出流出数据 4.字节流和字符流的使用场景 5.练习 6.缓冲流 1.字节缓冲流拷贝文件 2.字符缓冲流特有的方法 1.方法 2.总结 7.转换流基本用法…

掌握MySQL基础命令:数据更新操作详细操作(数据的增删改)

MySQL数据修改是指使用SQL语句&#xff08;如UPDATE、INSERT、DELETE&#xff09;对数据库表中的数据进行更改、添加或删除的操作&#xff0c;常见的操作包括更新表中的记录、插入新记录以及删除现有记录 。 一、数据插入 1插入完整的数据记录 2插入非完整的数据记录 3插入多…

Vulkan 学习(1)---- Vulkan 基本概念和发展历史

目录 Vulkan及其演化史Vulkan 基本概念基本术语 Vulkan 的原理Vulkan应用程序Vulkan的编程模型硬件初始化窗口展示表面资源设置流水线设置描述符和描述符缓冲池基于SPIR-V的着色器流水线管理指令的记录队列的提交 Vulkan及其演化史 目前主流的图形渲染API有OpenGL、OpenGL ES、…

应急响应--网站(web)入侵篡改指南

免责声明:本文... 目录 被入侵常见现象: 首要任务&#xff1a; 分析思路&#xff1a; 演示案例: IIS&.NET-注入-基于时间配合日志分析 Apache&PHP-漏洞-基于漏洞配合日志分析 Tomcat&JSP-弱口令-基于后门配合日志分析 (推荐) Webshell 查杀-常规后门&…

ThinkPHP定时任务是怎样实现的?

接到一个需求&#xff1a;定时检查设备信息&#xff0c;2分钟没有心跳的机器&#xff0c;推送消息给相关人员&#xff0c;用thinkphp5框架&#xff0c;利用框架自带的任务功能与crontab配合来完成定时任务。 第一步&#xff1a;分析需求 先写获取设备信息&#xff0c;2分钟之…

Winform中使用HttpClient实现调用http的post接口并设置传参content-type为application/json示例

场景 Winform中怎样使用HttpClient调用http的get和post接口并将接口返回json数据解析为实体类&#xff1a; Winform中怎样使用HttpClient调用http的get和post接口并将接口返回json数据解析为实体类_winform解析json-CSDN博客 上面使用HttpClient调用post接口时使用的HttpCon…