网站建设试题以及答案,泉州响应式网站建设,有免费推广平台,郑州网站搭建竞赛总览
CSDN 编程竞赛四十期#xff1a;比赛详情 (csdn.net)
竞赛题解
题目1、小鱼的航程
有一只小鱼#xff0c;它上午游泳150公里#xff0c;下午游泳100公里#xff0c;晚上和周末都休息#xff08;实行双休日)。假设从周x#xff08;1x7#xff09;开…竞赛总览
CSDN 编程竞赛四十期比赛详情 (csdn.net)
竞赛题解
题目1、小鱼的航程
有一只小鱼它上午游泳150公里下午游泳100公里晚上和周末都休息实行双休日)。假设从周x1x7开始算起请问这样过了n天以后小鱼一共累计游泳了多少公里呢
#include cstdioint 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个字母{ab…z}这些特殊的单词长度不超过6且字母按升序排列。把所有这样的长度相同的单词放在 一起按字典顺序排列一个单词的编码就对应着它在整个序列中的位置。你的任务就是对于所给的单词求出它的编码。
第十四期竞赛时遇到过这道题洛谷原题。
题目3、一维数组的最大子数组和
给定一个整数数组nums找到一个具有最大和的连续子数组输出该子数组在原数组中的开始下标和结束下标。原数组下标从0开始。
第二十一期竞赛出现过一次问题是子数组最大和的数值这一次变成起始下标和结束下标了。但核心思想和之前是一样的下面博主来详细地讲解一下。
使用前缀和算法计算出每一项数据的前缀和。可以利用哨兵巧妙地处理这个问题。
第一项数据置为零从后面开始读入数据。计算前缀和时第二项的前缀和为前两项的和第三项的前缀和为前三项的和以此类推第二项的前缀和实际值是0第一项数据。这样做不但可以简化初始化时的方式还可以优化起点下标的计算方法。
使用时假设需要求第一项到第五项数据的累加和只需用前缀和[6]减去前缀和[1]。这时由于引入了哨兵位置所以起点下标与计算时使用的前缀和下标对应直接使用1即可。终点下标的目标值是5但是实际使用的第六项的前缀和进行计算因此终点下标需要减一下。如果不引入哨兵的话那么可以直接使用终点下标但起点下标需要额外进行判断例如求第一项到第五项数据的累加和但是如果用前缀和[5]减去前缀和[1]只能得到第二项到第五项数据的累加和还要额外补充一下第一项的数据。由此可见引入哨兵位置可以极大地提升操作的便利性性价比是很高的。
求累加和最大区间时可以结合贪心算法。例如第一项到第五项之间的数据累加和小于零那么可以直接使用第六项数据的位置作为新的区间起点而无需用第一项到第五项之间的数据累加和加上第六项这样只会使求和结果越来越小。反之如果区间的累加和大于零那么遇到下一项时直接用前面的累加和加上下一项的值即可这里体现出了贪心的思想。
题目4、喜水青蛙
总是喜欢在水里嬉戏的青蛙某天要过河拜访一位朋友。已知河道中长满了带刺的不知名生物能通过的路只有一条直线长度为L。直线上随机分布着m块石头。青蛙的最小跳跃距离是s最大跳跃距离是t。青蛙想要尽可能的少踩石头那么它通过河道最少会踩到多少石头
NOIP原题。在NOIP竞赛规定的测试数据范围中这道题目的长度L参数范围特别大。因此需要进行状态压缩只保留下一些必要的状态否则会超时只能通过部分测试点。去搜索一套NOIP题解集的网盘资源即可学到NOIP系列题目的解法。
