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…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...