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

CSDN 编程竞赛四十期题解

竞赛总览

CSDN 编程竞赛四十期:比赛详情 (csdn.net)

竞赛题解

题目1、小鱼的航程

有一只小鱼,它上午游泳150公里,下午游泳100公里,晚上和周末都休息(实行双休日)。假设从周x(1<=x<=7)开始算起,请问这样过了n天以后,小鱼一共累计游泳了多少公里呢?

#include <cstdio>int main () {long long int result = 0;long long int x, n;scanf ("%lld %lld", &x, &n);while (n --> 0) {if (x >= 7) {x = 1;} else if (x >= 6) {x += 1;} else {x += 1;result += 250;}}return 0;
}

直接模拟即可解决此题。注意,由于数据范围较大,暴力模拟会超时,需要在循环前面进行优化。

小鱼每周工作五天,一周可以游泳1250公里。将剩余天数变为7的余数,循环时只计算零头即可。

题目2、编码

编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码:把一些有规律的单词编成数字。字母表中共有26个字母{a,b,…,z},这些特殊的单词长度不超过6且字母按升序排列。把所有这样的长度相同的单词放在 一起,按字典顺序排列,一个单词的编码就对应着它在整个序列中的位置。你的任务就是对于所给的单词,求出它的编码。

第十四期竞赛时遇到过这道题,洛谷原题。

题目3、一维数组的最大子数组和

给定一个整数数组nums,找到一个具有最大和的连续子数组,输出该子数组在原数组中的开始下标和结束下标。原数组下标从0开始。

第二十一期竞赛出现过一次,问题是子数组最大和的数值,这一次变成起始下标和结束下标了。但核心思想和之前是一样的,下面博主来详细地讲解一下。

使用前缀和算法,计算出每一项数据的前缀和。可以利用哨兵,巧妙地处理这个问题。

第一项数据置为零,从后面开始读入数据。计算前缀和时,第二项的前缀和为前两项的和,第三项的前缀和为前三项的和,以此类推(第二项的前缀和实际值是0+第一项数据)。这样做,不但可以简化初始化时的方式,还可以优化起点下标的计算方法。

使用时,假设需要求第一项到第五项数据的累加和,只需用前缀和[6]减去前缀和[1]。这时,由于引入了哨兵位置,所以起点下标与计算时使用的前缀和下标对应,直接使用1即可。终点下标的目标值是5,但是实际使用的第六项的前缀和进行计算,因此终点下标需要减一下。如果不引入哨兵的话,那么可以直接使用终点下标,但起点下标需要额外进行判断(例如,求第一项到第五项数据的累加和,但是如果用前缀和[5]减去前缀和[1],只能得到第二项到第五项数据的累加和,还要额外补充一下第一项的数据)。由此可见,引入哨兵位置可以极大地提升操作的便利性,性价比是很高的。

求累加和最大区间时,可以结合贪心算法。例如,第一项到第五项之间的数据累加和小于零,那么可以直接使用第六项数据的位置作为新的区间起点,而无需用第一项到第五项之间的数据累加和加上第六项,这样只会使求和结果越来越小。反之,如果区间的累加和大于零,那么遇到下一项时,直接用前面的累加和加上下一项的值即可,这里体现出了贪心的思想。

题目4、喜水青蛙

总是喜欢在水里嬉戏的青蛙,某天要过河拜访一位朋友。已知河道中长满了带刺的不知名生物,能通过的路只有一条直线,长度为L。直线上随机分布着m块石头。青蛙的最小跳跃距离是s,最大跳跃距离是t。青蛙想要尽可能的少踩石头,那么它通过河道最少会踩到多少石头?

NOIP原题。在NOIP竞赛规定的测试数据范围中,这道题目的长度L参数范围特别大。因此,需要进行状态压缩,只保留下一些必要的状态,否则会超时,只能通过部分测试点。去搜索一套NOIP题解集的网盘资源,即可学到NOIP系列题目的解法。

http://www.lryc.cn/news/43465.html

相关文章:

  • 【TypeScript学习之路】泛型
  • 数据分析学习项目:东京奥运会跳水评论分析
  • Winform/Csharp中使用Linq的Where条件筛选、Select字段映射(左外连接并设置无匹配时默认值)、OrderBy(排序并自定义排序规则)
  • Linux-常用的Shell命令
  • Go语言基础:数组定义及循环遍历
  • 【树与二叉树】二叉树顺序结构实现以及堆的概念及结构--详解介绍
  • 天狗实战(二)SpringBoot API开发详解 --SpringMVC注解+封装结果+支持跨域+打包(下)
  • 实验一 Windows系统安全实验【网络安全】
  • 蓝桥杯正确的解题姿势
  • 【mysql】性能优化
  • Jupyter安装与远程使用过程记录
  • Swift入门
  • 【HashMap】jdk1.8中HashMap的插入扩容源码学习分析
  • Linux编译器-gcc/g++ 使用
  • 网络安全专家最爱用的9大工具
  • Linux内核设计与实现第四章学习笔记
  • i.MX9352——介绍一款多核异构开发板
  • 【Python】一文学会面向对象?当然可以的
  • ElasticSearch - SpringBoot整合ES:精确值查询 term
  • 【GPT4】微软对 GPT-4 的全面测试报告(2)
  • Docker打包exe运行环境
  • springboot+vue田径运动会成绩管理系统java
  • 我能“C”——详解操作符(上)
  • 第一章Vue基础
  • 【虚幻引擎UE】UE5核心效率插件推荐
  • 记录丨阿里云校招生的成长经历
  • 蓝桥杯第14天(Python版)
  • 双指针常用方法
  • 人工智能大模型之ChatGPT原理解析
  • 傅里叶谱方法-傅里叶谱方法的原理、快速傅里叶变换及其Matlab程序实现