当前位置: 首页 > news >正文

2023环翠区编程挑战赛中学组题解

T1. 出栈序列

题目描述

栈是一种“先进后出”的数据结构,对于一个序列1,2,...,n1,2, ...,n1,2,...,n,其入栈顺序是1,2,...n1,2, ...n1,2,...n,但每个元素出栈的时机可以自由选择。

例如111入栈、111出栈,222入栈、333入栈、333出栈、222出栈,于是出栈序列为 1321\ 3\ 21 3 2

对于入栈顺序12...n1\ 2\ ...\ n1 2 ... n,出栈序列有很多个,但出栈序列的总数不是12...n1\ 2\ ...\ n1 2 ... n的全排列数,因为有些排列不满足出入栈规则。

例如3123\ 1\ 23 1 2就不是一个合法的出栈序列,因为333先出栈意味着此时111222在栈里面,入栈顺序是121\ 21 2,于是出栈必须是212\ 12 1

小明仔细研究了出入栈的规则,它发现凡是不合法的出栈序列都有一个规律,至少有一个数,后面比它小的数,存在递增的情况。

现在请你帮助小明编写程序,对于给定的出栈序列,判断是否合法。

输入格式:

第一行ttt,表示ttt组数据
对每组数据
第一行nnn,表示序列长度
第二行1..n1..n1..n的一个排列,表示要判断的出栈序列

输出格式:

ttt行,每行YesNo,表示出栈序列是否合法

输入样例1:

2
3
1 2 3
3
3 1 2

输出样例1:

Yes
No

数据范围

所有数据:t<=5t<=5t<=5
样例1-3:n<=100n<=100n<=100
样例4-5:n<=2000n<=2000n<=2000
样例6-10:n<=105n<=10^5n<=105

代码实现

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], stk[N], top;
int main()
{int t;scanf("%d", &t);while(t --){int n, x;scanf("%d", &n);int in = 1, out; //进栈in,出站outfor(int i = 1; i <= n; i ++) {scanf("%d", &out);while(in <= out) stk[top ++] = in ++; //将小于等当前入栈元素的所有数据入栈if(stk[top - 1] == out) { top --; } //检查栈顶元素是否为要出栈的数据else break;}if(top == 0) puts("Yes");else puts("No");}
}

领头牛

题目描述

在我国有一处牧场,里面养育着两种牛分别是HHH牛和GGG牛。为了方便实时管理我们需要在牛群中选出领头牛,这样我们只需要牵着领头牛其他牛自然就会跟着走。

现在我们要分别选出HHH领头牛和GGG领头牛凑成一对。

现在我们让牛群站成一排,例如: GHHGGHHGGHHG ,每头牛都有一个属性“领导能力”。假设第 111 头牛的领导能力为 222 ,那么他可以领导包含自身之后的两头牛也就是 “GHGHGH” 。

但是光有领导能力是不够做领头牛的,领头牛的要求满足两种要求之一:

  • 能够领导自身品种全部的牛;
  • 能够领导对方的领头牛。

我们会给出队伍顺序和每头牛的领导能力,请问有多少对领头牛?

输入格式

第一行输入 nnn 表示牛的数量;
第二行输入nnn个字符,有GGGHHH组成,表示牛的排列顺序;
第三行输入nnn个数,表示牛的领导能力。

输出格式:

输出一个整数nnn表示可以凑成几对领导牛。

输入样例1:

4
GHHG
2 2 1 1

输出样例1:

1

样例1说明:

第一头牛GGG,可以领导222头牛“GHGHGH”,没有包含全部的GGG牛,但是第二头牛HHH可以领导222头牛“HHHHHH”,包含了所有的HHH牛,所以第二头HHH牛是领头牛,那么第一头GGG牛包含了对方的领头牛,所以第一头GGG牛也是领头牛。
现在就是GGG有一头领头牛,HHH有一头领头牛,那么只能凑一对(1,2)(1,2)(12)

输入样例2:

3
GGH
2 2 1

输出样例2:

2

样例2说明:

第一头牛GGG,领导222头牛“GGGGGG”包含全部的GGG牛,所以是领头牛;
第二头牛GGG,领导222头牛“GHGHGH”包含对方领头牛,所以是领头牛;
第三头牛HHH,领导111头牛“HHH”包含全部H牛,所以是领头牛;
配对(1,3)(1,3)13(2,3)(2,3)23所以有222

数据范围:

对于20%的数据:1≤n≤201 ≤ n ≤ 201n20
对于40%的数据:1≤n≤1001 ≤ n ≤ 1001n100
对于60%的数据:1≤n≤50001 ≤ n ≤ 50001n5000
对于80%的数据:1≤n≤200001 ≤ n ≤ 200001n20000
对于100%的数据:1≤n≤1000001 ≤ n ≤ 1000001n100000。​​

代码实现(80分)

模拟,时间复杂度为O(n2)O(n^2)O(n2)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int a[N], g[N], h[N];
int main()
{int n, x;cin >> n;cin >> s + 1;int s1 = 0, s2 = 0;for(int i = 1; i <= n; i ++){if(s[i] == 'G') s1 ++;else s2 ++;}for(int i = 1; i <= n; i ++) {cin >> x;a[i] = i + x - 1; //a[i]保存领导能力到达的位置}//处理第一种领导者:其记录的名单上包含它的品种的所有奶牛for(int i = 1; i <= n; i ++){int gg = 0, hh = 0;for(int j = i; j <= a[i]; j ++){if(s[j] == 'G') gg ++;else hh ++;}if(s[i] == 'G' && gg == s1) g[i] = 1; //标记为领导者else if(s[i] == 'H' && hh == s2) h[i] = 1; //标记为领导者}//处理第二种领导者:其记录的名单上记录了另一品种奶牛的“领导者”。for(int i = 1; i <= n; i ++){for(int j = i; j <= a[i]; j ++){if(s[i] == 'G' && h[j] == 1){g[i] = 1;break;}else if(s[i] == 'H' && g[j] == 1){h[i] = 1;break;}}}int c1 = 0, c2 = 0;for(int i = 1; i <= n; i ++)if(g[i]) c1 ++;for(int i = 1; i <= n; i ++)if(h[i]) c2 ++;cout << c1 * c2 << endl;
}

代码实现(100分)

朴素做法的问题在于使用了两层循环,其实第二层循环可以使用前缀和进行优化,用空间换时间。

  • s1[]前缀和数组,s1[i]表示前i个字符中字符G的个数
  • s2[]前缀和数组,s2[i]表示前i个字符中字符H的个数
  • gs[]前缀和数组,gs[i]表示前i头牛中第一类G品种领导者的数量
  • hs[]前缀和数组,hs[i]表示前i头牛中第一类H品种领导者的数量
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int a[N], s1[N], s2[N], g[N], h[N], gs[N], hs[N];
int main()
{int n;cin >> n;cin >> s + 1;for(int i = 1; i <= n; i ++) {cin >> x;a[i] = i + x - 1; //a[i]保存领导能力到达的位置}//s1[i]前缀和, 表示前i个字符中字符G的个数//s2[i]前缀和, 表示前i个字符中字符H的个数for(int i = 1; i <= n; i ++){s1[i] = s1[i - 1], s2[i] = s2[i - 1];if(s[i] == 'G') s1[i] ++;else s2[i] ++;}//处理第一种领导者:其记录的名单上包含本身的品种的所有奶牛for(int i = 1; i <= n; i ++){//gg表示从i到a[i]位置所有G的个数//hh表示从i到a[i]位置所有H的个数int gg = s1[a[i]] - s1[i - 1], hh = s2[a[i]] - s2[i - 1];//其记录的名单上包含本身的品种的所有奶牛if(s[i] == 'G' && gg == s1[n]) g[i] = 1; //将i位置标记为'G'的领导者else if(s[i] == 'H' && hh == s2[n]) h[i] = 1;//将i位置标记为'H'的领导者}//gs[i]前缀和,表示前i个奶牛中G的第一种领导者个数//hs[i]前缀和,表示前i个奶牛中H的第一种领导者个数for(int i = 1; i <= n; i ++){gs[i] = gs[i - 1], hs[i] = hs[i - 1];if(g[i]) gs[i] ++;if(h[i]) hs[i] ++;}//ga表示G的第一种领导者个数,ha表示H的第一种领导者个数int ga = gs[n], ha = hs[n];//处理第二种领导者:其记录的名单上记录了另一品种奶牛的“领导者”。for(int i = 1; i <= n; i ++){  //其记录的名单上记录了另一品种奶牛的领导者if(s[i] == 'G' && (hs[a[i]] - hs[i - 1]) != 0) ga ++;else if(s[i] == 'H' && (gs[a[i]] - gs[i - 1]) != 0) ha ++;}cout << ga * ha << endl;
}

两端对齐

题目描述

小明最近在用软件写文档时发现,在英文内容的键入时,软件会自动添加一些额外的空格到内容中,使得整段英文在文本区域的两端对齐,并且不会出现单个单词被拆分到两行的情况,看上去整齐又美观。

现在给定一篇文章中的nnn个单词,请试着将其按顺序以“两端对齐”的方式输出,要求:

  • 单词间至少由一个空格隔开,行末单词后无空格
  • 各行字符数均为mmm个,必要时可以在单词间补充额外的空格
  • 一行内单词间的空格数要尽量相同,若始终不能均匀分配,那么左侧的空格数可以多一些
  • 输出行数要尽可能少一些,也即每行放置的单词要尽可能多一些
    最后一行要左对齐,单词间不再插入额外的空格,末尾补空格至mmm个字符

输入格式:

第一行输入两个数nnnmmm
接下来nnn行,每行111个单词s​is_​isi​​ ,均由小写字母构成

输出格式:
输出排版后的文章(数据保证有解)

输入样例:

10 14
to
be
or
not
to
be
that
is
a
question

输出样例:

to  be  or not
to  be that is
a question

样例说明:

第1行在前两个单词后分别额外添加了一个空格;
第2行在第一个单词后额外添加了一个空格;
最后一行在末尾额外添加了4个空格。
各行均为141414个字符,输出的换行符不算入mmm

数据范围:

对于30%的数据:1≤n≤1001\le n \le1001n100
对于60%的数据:1≤n≤10001\le n \le10001n1000
对于100%的数据:1≤n≤1041\le n \le10^41n1041≤m≤1061\le m \le10^61m1061≤∣si∣≤1001\le|s_i|\le1001si100

代码实现(模拟?)

时间复杂度O(n2)O(n^2)O(n2)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
string a[N];
int main()
{int n, m;cin >> n >> m;for(int i = 0; i < n; i ++) cin >> a[i];string s = a[0]; //保存每行由单词和一个空格组成的字符串int cnt = 1; //每行单词的数量for(int i = 1; i < n; i ++){int len = s.size() + 1 + a[i].size(); //每行单词的长度if(len <= m) { s = s + ' ' + a[i]; cnt ++; }//每行字符串的长度不超过melse { //加入新单词后长度超过m            int b = m - s.size(); //需要填补空格int c = b / cnt; //平均每个单词需要额外添加的空格数量int r = b % cnt; //剩余需要在左侧补充的空格数量for(int j = i - cnt; j < i; j ++) // 输出单词{if(j != i - 1) cout << a[j] << " "; //不是本行最后一个单词,添加一个空格else cout << a[j]; //本行最后一个单词不添加空格for(int k = 0; k < c; k ++) cout << " "; //输出平均的空格if(r != 0) { //输出需要在做出补充的剩余空格,每个单词只补一个cout << " ";r --;}}cout << endl;s = a[i];cnt = 1;}}cout << s << endl; //输出最后一行的单词
}

T4. 免费超市

题解在我的另一篇博客,环翠区中小学生编程挑战赛题解中学组T4:免费超市

相关文章:

2023环翠区编程挑战赛中学组题解

T1. 出栈序列 题目描述 栈是一种“先进后出”的数据结构&#xff0c;对于一个序列1,2,...,n1,2, ...,n1,2,...,n&#xff0c;其入栈顺序是1,2,...n1,2, ...n1,2,...n&#xff0c;但每个元素出栈的时机可以自由选择。 例如111入栈、111出栈&#xff0c;222入栈、333入栈、333…...

手撸一个Switch开关组件

一、前言 手撸系列又来了&#xff0c;这次咱们来撸一个Switch开关组件&#xff0c;废话不多说&#xff0c;咱们立刻发车。 二、使用效果 三、实现分析 首先我们先不想它的这个交互效果&#xff0c;我们就实现“不合格”时的一个静态页面&#xff0c;静态页面大致如下&#x…...

2023年1月冰箱品牌销量排行:销量环比增长26%,销售额36亿+

鲸参谋电商大数据2023年1月京东平台“冰箱”销售数据出炉&#xff01; 根据鲸参谋平台电商数据显示&#xff0c;2023年1月份&#xff0c;在京东平台上&#xff0c;冰箱的销量将近130万件&#xff0c;环比增长26%&#xff0c;同比下滑8%&#xff1b;销售额达36亿&#xff0c;环比…...

DSP CCS 开发问题总结及解决办法

文章目录 问题汇总 1. CCS编译器的Project菜单栏工程导入选项丢失&#xff0c;怎么解决&#xff01; 1.1启动CCS后发现导入工程菜单栏丢失&#xff0c;无法导入工程文件。 1.2方法一 工程选项的导入工程文件丢失&#xff0c;如果要重新获得相应的选项&#xff0c;就需要删除当前…...

Vue3.x+Element Plus仿制Acro Design简洁模式分页器组件

Vue3.xElement Plus仿制Acro Design简洁模式分页器组件 开发中难免会遇到宽度很窄的列表需要使用分页器的情况&#xff0c;这时若使用Element Plus组件的分页器会导致分页器内容超出展示的区域&#xff0c;而Element Plus组件中目前没有Acro Design那样小巧的分页器&#xff08…...

经典文献阅读之--VoxelMap(体素激光里程计)

0. 简介 作为激光里程计&#xff0c;常用的方法一般是特征点法或者体素法&#xff0c;最近Mars实验室发表了一篇文章《Efficient and Probabilistic Adaptive Voxel Mapping for Accurate Online LiDAR Odometry》&#xff0c;同时还开源了代码在Github上。文中为雷达里程计提…...

.NET6中使用GRPC详细描述

Supported languages | gRPC&#xff0c;官网。至于原理就不说了&#xff0c;可以百度原理之后&#xff0c;然后再结合代码&#xff0c;事半功倍&#xff0c;就能很好理解GRPC了。 目录 一、简单使用 二、实际应用 一、简单使用 1.使用vs2022创建一个grpc程序&#xff0c;…...

ML@矩阵微积分基础

文章目录矩阵微积分Matrix calculus记法简单Jacobi Matrix分子记法分母记法一般形式的Jacobi MatrixTypes of matrix derivative向量求导向量对标量求导标量对向量求导向量对向量求导矩阵求导矩阵对标量求导(切矩阵)标量对矩阵求导记法向量求导 向量对标量求导标量对向量求导向…...

华为OD机试真题Python实现【优秀学员统计】真题+解题思路+代码(20222023)

优秀学员统计 题目 公司某部门软件教导团正在组织新员工每日打卡学习活动,他们开展这项学习活动已经一个月了,所以想统计下这个月优秀的打卡员工。每个员工会对应一个 id,每天的打卡记录记录当天打卡员工的 id 集合,一共 30 天。 请你实现代码帮助统计出打卡次数 top5 的…...

docsify在线文档支持pdf查看

目录 步骤一&#xff1a;添加插件 步骤二&#xff1a;添加pdf地址 步骤三&#xff1a;成果展示 docsify是一个在github上很好用的文档转换网页的工具&#xff0c;但是大部分情况我们都是使用的markdown文件。最近想把pdf文档也能支持在这上面展示&#xff0c;研究后总结一下…...

ES6中Set类型的基本使用

在ES6之前&#xff0c;存储数据的结构主要有两种&#xff1a;数组、对象。 在ES6中新增了另外两种数据结构&#xff08;存放数据的方式&#xff09;&#xff1a;Set、Map&#xff0c;以及他们的另外形式WeakSet、WeakMap。 Set的基本使用 Set是一个新增的数据结构&#xff0c…...

【VUE3.0_CSS功能】

CSS功能组件css作用域深度选择器&#xff08;标签名空格:deep(标签名)&#xff09;插槽选择器&#xff08;:soltted(标签名)&#xff09;全局选择器&#xff08;:global(类名)&#xff09;动态CSS&#xff08;v-bind&#xff09;useCSSModule拓展知识&#xff1a;deep的写法组件…...

微机原理复习总结6:汇编语言程序设计

本篇博客主要分享几道汇编语言例题编写一完整的程序&#xff0c;从键盘输入一组字符&#xff0c;直到输入“0”为止&#xff0c;当输入是小写字母时&#xff0c;则修改为大写字母&#xff0c;输入的字符存放在string为首址的存储单元中。data segment ;数据段定义 st…...

计算机网络 部分原理和过程

下面是一台计算机 Ping 和不在同一 IP 网络上的另一台计算机的全过程&#xff1a; 该计算机首先确定要 Ping 的目标 IP 地址&#xff0c;并检查该 IP 地址是否与本地 IP 地址在同一 IP 网络上。如果目标 IP 地址与本地 IP 地址不在同一 IP 网络上&#xff0c;则需要通过路由器…...

C++实现链表

C实现链表 众所周知&#xff0c;C/C语言实现的链表是由一个一个的结点构成&#xff0c;每个结点分为数据域和指针域&#xff0c;指针域中存储了其后继结点的地址&#xff0c;通过地址来访问下一个结点。 链表是一系列节点串联形成的数据结构&#xff0c;链表存储有序的元素集合…...

MySQL索引篇

文章目录说明&#xff1a;索引篇一、索引常见面试题按数据结构按物理存储分类按字段特性分类按字段个数分类索引缺点&#xff1a;什么时候适用索引&#xff1f;什么时候不需要创建索引&#xff1f;常见优化索引的方法&#xff1a;发生索引失效的情况&#xff1a;二、从数据页角…...

Ardiuno-交通灯

LED交通灯实验实验器件&#xff1a;■ 红色LED灯&#xff1a;1 个■ 黄色LED灯&#xff1a;1 个■ 绿色LED灯&#xff1a;1 个■ 220欧电阻&#xff1a;3 个■ 面包板&#xff1a;1 个■ 多彩杜邦线&#xff1a;若干实验连线1.将3个发光二极管插入面包板&#xff0c;2.用杜邦线…...

Leetcode.1234 替换子串得到平衡字符串

题目链接 Leetcode.1234 替换子串得到平衡字符串 Rating &#xff1a; 1878 题目描述 有一个只含有 Q, W, E, R四种字符&#xff0c;且长度为 n 的字符串。 假如在该字符串中&#xff0c;这四个字符都恰好出现 n/4次&#xff0c;那么它就是一个「平衡字符串」。 给你一个这样…...

聚类算法之K-means算法详解

文章目录 什么是聚类k-means算法简介牧师-村民模型算法步骤伪代码流程描述手动实现优缺点优点缺点算法调优与改进数据预处理合理选择 K 值手肘法Gap Statistic(间隔统计量)轮廓系数法(Silhouette Coefficient)Canopy算法拍脑袋法采用核函数K-means++ISODATA参考文献<...

电话呼入/呼出CSFB流程介绍

MO CSFB 注册的LAI跟SYS_INFO不同会触发LU流程;LU流程结束后,判断LOCATION UPDATING ACCEPT消息中的"Follow-on proceed"参数状态。(1)如果IE消息中有"Follow-on proceed",终端直接发送CM Service Request; (2)如果IE消息中没有"Follow-on procee…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...