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系列题目的解法。