Codeforces Round #894 (Div.3)
文章目录
- 前言
- A. Gift Carpet
- 题目:
- 输入:
- 输出:
- 思路:
- 代码:
- B. Sequence Game
- 题目:
- 输入:
- 输出:
- 思路:
- 代码:
- C. Flower City Fence
- 题目:
- 输入:
- 输出:
- 思路:
- 代码:
- D. Ice Cream Balls
- 题目:
- 输入:
- 输出:
- 思路:
- 代码:
- E. Kolya and Movie Theatre
- 题目:
- 输入:
- 输出:
- 思路:
- 代码:
- 总结
前言
昨天晚上打了一场Codeforces Div3 唉 打的很不好,只AC了两道思维题目。
A. Gift Carpet
题目:
链接:A. Gift Carpet
最近,Tema和Vika庆祝了家庭日。他们的朋友阿里娜给了他们一块地毯,可以表示为n⋅m
小写拉丁字母表。
维卡还没有看到礼物,但特玛知道她喜欢什么样的地毯。维卡会喜欢地毯,如果她能读上她的名字。她从左到右逐列阅读,并从当前列中选择一个或多个或零个字母。
从形式上讲,如果可以按从左到右的顺序选择四列不同的列,例如第一列包含“v”,第二列包含“i”,第三列包含“k”,第四列包含“a”,女孩会喜欢地毯。
帮助特玛提前了解维卡是否会喜欢艾琳娜的礼物。
输入:
每个测试由多个测试用例组成。输入的第一行包含单个整数t
(1≤t≤100) — 测试用例的数量。然后是测试用例的说明。
每个测试用例的第一行包含两个整数n,m
(1≤n,m≤20) — 地毯的尺寸。
下一个n行包含m每个小写拉丁字母,描述给定的地毯。
输出:
对于每组输入数据,如果 Vika 喜欢地毯,则输出“YES”,否则输出“NO”。
您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。
思路:
控制行和列的for循环互换,然后一列一列的去找,找到就k++然后跳出去下一列
最后如果k==4
就是输出yes
否则就是输出no
即可。
tip:唉 继续加油!!!
代码:
#include<iostream>
using namespace std;
int main()
{int t;cin>>t;while(t--){int n,m;cin>>n>>m;char s[22][22];for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>s[i][j]; }}int k=0;for(int i=k;i<m;i++){for(int j=0;j<n;j++){if(s[j][i]=='v'){if(k==0) {k++;break;}}if(s[j][i]=='i'){if(k==1){k++;break;}}if(s[j][i]=='k'){if(k==2){k++;break;}}if(s[j][i]=='a'){if(k==3){k++;break;}}}}if(k==4) cout<<"yes"<<endl;else cout<<"no"<<endl;}return 0;
}
B. Sequence Game
题目:
链接:B. Sequence Game
Tema and Vika are playing the following game.
First, Vika comes up with a sequence of positive integers a
of length m
and writes it down on a piece of paper. Then she takes a new piece of paper and writes down the sequence b
according to the following rule:
First, she writes down a1
Then, she writes down only those ai (2≤i≤m) such that ai−1≤ai
Let the length of this sequence be denoted as n
For example, from the sequence a=[4,3,2,6,3,3]
Vika will obtain the sequence b=[4,6,3]
She then gives the piece of paper with the sequence b
to Tema. He, in turn, tries to guess the sequence a
Tema considers winning in such a game highly unlikely, but still wants to find at least one sequence a
that could have been originally chosen by Vika. Help him and output any such sequence.
Note that the length of the sequence you output should not exceed the input sequence length by more than two times.
大概意思:
就是输入一个数组b,大小为n然后推测数组a里面的数字
推测的依据是:
- 先写出来一个a[1];
- 然后如果a[i-1]<a[i]的话就存放到b数组里面
题目也是让你从b—>a,用b推出a数组酱紫
输入:
Each test consists of multiple test cases. The first line of input data contains a single integer t (1≤t≤104) — the number of test cases. This is followed by a description of the test cases.
The first line of each test case contains a single integer n (1≤n≤2⋅105) — the length of the sequence b
The second line of each test case contains n
integers b1,b2,b3,…,bn (1≤bi≤10^9) — the elements of the sequence.
The sum of the values of n over all test cases does not exceed 2⋅10^5
输出:
For each test case, output two lines. In the first line, output a single integer m
— the length of the sequence (n≤m≤2⋅n). In the second line, output m integers a1,a2,a3,…,am (1≤ai≤109) — the assumed sequence that Vika could have written on the first piece of paper.
If there are multiple suitable sequences, you can output any of them.
思路:
emm勉强可以说是双指针算法吧,就是开一个result数组存放需要添加的内容,然后设置一个m=0指针去添加数据就行了
核心地方就是当遇到降序的时候:直接添加一个数字1解决所有问题,就这样…
代码:
#include<iostream>
using namespace std;int n,a[200005],m,b[400005];int main()
{int t;scanf("%d\n",&t);while(t--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];m=0;b[++m]=a[1];for(int i=2;i<=n;i++){if(a[i]<a[i-1]) b[++m]=1;b[++m]=a[i];}printf("%d\n",m);for(int i=1;i<=m;i++) printf("%d ",b[i]);puts("");}return 0;
}
C. Flower City Fence
链接:C. Flower City Fence
题目:
Anya lives in the Flower City. By order of the city mayor, she has to build a fence for herself.
The fence consists of nplanks, each with a height of aimeters. According to the order, the heights of the planks must not increase. In other words, it is true that ai≥aj for all i<j.
Anya became curious whether her fence is symmetrical with respect to the diagonal. In other words, will she get the same fence if she lays all the planks horizontally in the same order.
For example, for n=5, a=[5,4,3,2,1], the fence is symmetrical. Because if all the planks are laid horizontally, the fence will be [5,4,3,2,1], as shown in the diagram.
But for n=3, a=[4,2,1], the fence is not symmetrical. Because if all the planks are laid horizontally, the fence will be [3,2,1,1], as shown in the diagram.
Help Anya and determine whether her fence is symmetrical.
输入:
The first line of the input contains an integer t (1≤t≤104) — the number of test cases.
The description of the test cases follows.
The first line of a test case contains a single integer n (1≤n≤2⋅105) — the length of the fence.
The second line of a test case contains n integers a1≥a2≥a3≥⋯≥an (1≤ai≤109) — the heights of the planks.
The sum of the values of n for all test cases does not exceed 2⋅105.
输出:
For each test case, output “YES” if the fence is symmetrical, otherwise output “NO”.
You can output each letter in any case (lowercase or uppercase). For example, the strings “yEs”, “yes”, “Yes” and “YES” will be accepted as a positive answer.
思路:
题目大意就是给你一个数组让你把这个数组抽象成长方体然后组合在一起,然后从对角线切分看是否关于切割线对称,如果对称就输出YES 否则 输出NO
算法标签:思维题
其实解决思路就是 a[a[i]]
这个方法,其实a[a[i]]
完美的解决了对称的问题,真的很不错,仔细想想是不是呢???
确实是这样的。
代码:
#include<stdio.h>int a[200005];void solve()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;++i){if(a[i]>n || a[a[i]]<i) {puts("No");return;}}puts("Yes");return;
}
int main()
{int t;scanf("%d",&t);while(t--) solve();return 0;
}
D. Ice Cream Balls
题目:
链接:D. Ice Cream Balls
Tema decided to improve his ice cream making skills. He has already learned how to make ice cream in a cone using exactly two balls.
Before his ice cream obsession, Tema was interested in mathematics. Therefore, he is curious about the minimum number of balls he needs to have in order to make exactly ndifferent types of ice cream.
There are plenty possible ice cream flavours: 1,2,3,…. Tema can make two-balls ice cream with any flavours (probably the same).
Two ice creams are considered different if their sets of ball flavours are different. For example, {1,2}={2,1}, but {1,1}≠{1,2}.
For example, having the following ice cream balls: {1,1,2}, Tema can make only two types of ice cream: {1,1} and {1,2}
Note, that Tema do not need to make all the ice cream cones at the same time. This means that he making ice cream cones independently. Also in order to make a following cone {x,x} for some x, Tema needs at least 2 balls of type x
Help Tema answer this question. It can be shown that answer always exist.
输入:
Each test consists of multiple test cases. The first line of input contains a single integer t (1≤t≤104) — the number of test cases. Then follows the description of the test cases.
The first line of each test case contains a single integer n (1≤n≤1018) — the number of ice cream types that Tema wants to make.
输出:
For each test case, output a single integer — the minimum number of balls Tema needs to buy.
思路:
可以抽象成为一个二叉树,就是一种雪糕必须有两种数字组合,然后我就蒙了哈哈哈,看大佬的代码大佬应该是总结出来了规律然后利用数学知识写出来了,反正我太菜了…对不起佬们
代码:
#include<iostream>
#include<cmath>using namespace std;int a[200005];void solve()
{long long n;cin>>n;long long p=(1+sqrt(n*8+1))/2;cout<<p+n-p*(p-1)/2<<endl;return;
}int main()
{long long t;cin>>t;while(t--) solve(); return 0;
}
E. Kolya and Movie Theatre
链接:E. Kolya and Movie Theatre
题目:
Recently, Kolya found out that a new movie theatre is going to be opened in his city soon, which will show a new movie every day for n days. So, on the day with the number 1≤i≤n, the movie theatre will show the premiere of the i-th movie. Also, Kolya found out the schedule of the movies and assigned the entertainment value to each movie, denoted by ai
However, the longer Kolya stays without visiting a movie theatre, the larger the decrease in entertainment value of the next movie. That decrease is equivalent to d⋅cnt, where d is a predetermined value and cnt is the number of days since the last visit to the movie theatre. It is also known that Kolya managed to visit another movietheatre a day before the new one opened — the day with the number 0. So if we visit the movie theatre the first time on the day with the number i, then cnt — the number of days since the last visit to the movie theatre will be equal to i
For example, if d=2 and a=[3,2,5,4,6], then by visiting movies with indices 1 and 3, cnt value for the day 1 will be equal to 1−0=1 and cnt value for the day 3 will be 3−1=2, so the total entertainment value of the movies will be a1−d⋅1+a3−d⋅2=3−2⋅1+5−2⋅2=2.
Unfortunately, Kolya only has time to visit at most m movies. Help him create a plan to visit the cinema in such a way that the total entertainment value of all the movies he visits is maximized.
输入:
Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains three integers n, m, and d (1≤n≤2⋅105, 1≤m≤n, 1≤d≤109).
The second line of each set of input data contains n integers a1,a2,…,an (−109≤ai≤109) — the entertainment values of the movies.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
输出:
For each test case, output a single integer — the maximum total entertainment value that Kolya can get.
思路:
算法标签:贪心算法
利用优先队列(priority_queue)的用法进行编写代码,优先队列的知识点:C++中优先队列的priority_queue<int,vector<int>,greater<int>>与priority<int>的用法
主要用优先队列存放大于0的元素,然后除了第一个数据后的每m个数据就可以存放到记录数组里面,最后遍历找价值最大的即可
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;int n,m,d,a[200005],b[200005];void solve()
{priority_queue<int,vector<int>,greater<int> >q;cin>>n>>m>>d;for(int i=1;i<=n;i++) cin>>a[i];int s=0,ans=0;for(int i=1;i<=n;i++){if(a[i]>0){s+=a[i];q.push(a[i]);while(q.size()>m) s-=q.top(),q.pop();}b[i]=s;}for(int i=1;i<=n;i++) ans=max(ans,b[i]-d*i);cout<<ans<<endl;
}signed main()
{int t;scanf("%lld\n",&t);while(t--) solve();return 0;
}
总结
第二次打CF Div3 比起大一寒假那次多写出来一道思维题,也算是有点点进步吧,今天早上起来锻炼完身体后就开始补题,把我蹦一蹦能够到的"桃子"给摘下来进行学习,虽然打的时候很坐牢,但是成长后的感觉真的很不错,慢慢进步慢慢比赛总会有一天你会变强的,加油夏目浅石.
相关文章:

Codeforces Round #894 (Div.3)
文章目录 前言A. Gift Carpet题目:输入:输出:思路:代码: B. Sequence Game题目:输入:输出:思路:代码: C. Flower City Fence题目:输入:…...

MyBatid动态语句且模糊查询
目录 什么是MyBtais动态语句??? MyBatis常用的动态标签和表达式 if标签 Choose标签 where标签 MyBatis模糊查询 #与$的区别 编辑 MyBatis映射 resultType resultMap 什么是MyBtais动态语句???…...

JVM——垃圾回收器G1+垃圾回收调优
4.4 G1(一个垃圾回收器) 定义: 取代了CMS垃圾回收器。和CMS一样时并发的。 适用场景: 物理上分区,逻辑上分代。 相关JVM参数: -XX:UseG1GC-XX:G1HeapRegionSizesize-XX:MaxGCPauseMillistime 1) G1 垃圾回收阶段 三个回收阶段࿰…...
【SA8295P 源码分析】23 - QNX Ethernet MAC 驱动 之 emac1_config.conf 配置文件解析
【SA8295P 源码分析】23 - QNX Ethernet MAC 驱动 之 emac1_config.conf 配置文件解析 系列文章汇总见:《【SA8295P 源码分析】00 - 系列文章链接汇总》 本文链接:《【SA8295P 源码分析】23 - QNX Ethernet MAC 驱动 之 emac1_config.conf 配置文件解析》 主要参数如下: hw_…...

iptables的使用规则
环境中为了安全要限制swagger的访问,最简单的方式是通过iptables防火墙设置规则限制。 在测试服务器中设置访问swagger-ui.html显示如下,区分大小写: iptables设置限制访问9783端口的swagger字段的请求: iptables -A INPUT -p t…...
JS 动画 vs CSS 动画:究竟有何不同?
在 Web 前端开发中,动画是提高用户体验的关键因素之一。我们通常可以使用 JavaScript(JS)和 CSS 来创建动画效果。但是,这两者之间有哪些区别呢?在本文中,我们将深入研究 JS 动画和 CSS 动画,探…...

供应链 | 大数据报童模型:基于机器学习的实践见解
论文解读:李欣 马玺渊 作者:Gah-Yi Ban, Cynthia Rudin 引用:Ban, Gah-Yi and Cynthia Rudin. The big data newsvendor: Practical insights from machine learning. Operations Research 67.1 (2019): 90-108. 文章链接:https…...
Java开发工作问题整理与记录
1、为什么Autowired不能注入static成员属性 扫描Class类需要注入的元数据的时候,直接选择忽略掉了static成员(包括属性和方法) Spring 依赖注入是依赖set方法, set方法是普通的对象方法,static变量是类的属性 AutowiredAnnotationBeanPostP…...

静态代码扫描持续构建(Jenkins)
前提条件 已正确安装、配置Jenkins环境,并装有 Gradle 插件、HTML 插件、SVN 插件等。如下图所示: 已正确安装、配置android sdk,在cmd窗口输入命令“android -h”,回车 配置步骤 打开Jenkins,新建一个job,输入项目…...
Git gui教程---汇总篇
想说的 汇总篇就是你应该已经学会基本操作了。剩下的代码上传云端之类的我懒得教了,反正你看命令版也差不多了,具体怎么操作就自己想吧。接下来的汇总篇,主要将每一个篇章对应的git命令写出来,一一对应,毕竟现在的编辑…...

flink sql checkpoint 调优配置
- execution.checkpointing.interval: 检查点之间的时间间隔(以毫秒为单位)。在此间隔内,系统将生成新的检查点 SET execution.checkpointing.interval 6000; - execution.checkpointing.tolerable-failed-checkpoints: 允许的连续失败检查…...
Linux 网络文件共享介绍
Linux 网络文件共享介绍 一.常见的存储类型 目前常见的存储类型有 DAS,NAS,SAN 等,最主要的区别是硬盘存储媒介是如何 于处理器连接的,以及处理器使用何种方式来访问磁盘,以及访问磁盘使用 的协议(网络协议、I/O 协议)。 三种存储类型如下 直…...
Qt中如何在qml文件中使用其他的qml文件并创建对象
如果想使用其他的qml文件直接创建对象,必须先这样导入其qml文件并as成别名,才可以创建对象并使用它。 一、导入qml文件,例如: import "CameraConfig.qml" as CameraConfig import "CameraDevelopView.qml" a…...

学习心得04:CUDA
2018年的时候,看过同事使用CUDA。因为工作忙,所以也没请教。 近来买了本入门的CUDA书,学习了一番。有两个心得: 工作拆分。 CUDA是并行计算,也就是大量重复的可拆分的计算。数组最符合这个要求。简单点就是把数组外面…...
OpenCV实现摄像头图像分类(Python版)
先安装MMEdu库! MMEdu安装:https://blog.csdn.net/zyl_coder/article/details/132483865 下面的代码请在Jupyter上运行,并自己准备数据集。若模型还未训练,请先在本地训练完模型后再进行模型推理。 import cv2 capture cv2.Vi…...

计算机竞赛 地铁大数据客流分析系统 设计与实现
文章目录 1 前言1.1 实现目的 2 数据集2.2 数据集概况2.3 数据字段 3 实现效果3.1 地铁数据整体概况3.2 平均指标3.3 地铁2018年9月开通运营的线路3.4 客流量相关统计3.4.1 线路客流量排行3.4.2 站点客流量排行3.4.3 入站客流排行3.4.4 整体客流随时间变化趋势3.4.5 不同线路客…...
sonarqube报错http status 500-internal server error,什么原因,怎么解决
sonarqube报错http status 500-internal server error,什么原因,怎么解决 答案: SonarQube报错HTTP状态500-内部服务器错误通常是由于服务器端出现了一些问题导致的。这可能是由于配置错误、资源不足、数据库连接问题或其他一些未知的问题引起的。 以下…...
工业设计的四个主要阶段,你都知道吗?优漫动游
一般来说,工业设计有几个基本程序:概念过程——设计创造的意识,即为什么创造。如何使你的想法成为现实,最终形成一个实体;实现过程——在工作消费中创造;行为过程实现其所有价值。在整个设计过程中,设计师需要始终站在…...

【DevOps视频笔记】4.Build 阶段 - Maven安装配置
一、Build 阶段工具 二、Operate阶段工具 三、服务器中安装 四、修改网卡信息 五、安装 jdk 和 maven Stage1 : 安装 JDK Stage 2 : 安装 Maven 2-1 : 更换文件夹名称 2-2 : 替换配置文件 settings.xml- 2-3 : 修改settings.xml详情 A. 修改maven仓库地址 - 阿里云 B…...
linux非GUI模式执行带有jpgc线程组jmeter脚本报错
linux非GUI模式执行jmeter脚本报错 Error in NonGUIDriver java.lang.IllegalArgumentException: Problem loading XML from:/root/fer/xxx.jmx. Cause: CannotResolveClassException: kg.apc.jmeter.vizualizers.CorrectedResultCollectorDetail:com.thoughtworks.xstream.c…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...

Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...

使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...