CSDN竞赛第四期季军 解题思路及参赛经历分享

CSDN竞赛第四期季军 解题思路及参赛经历分享

参赛经历

前面先说说参赛经历，这一期的题解在下面，想直接看题解的同学可以往下翻。

这已经是我第三次参赛了，前两次都没有获奖，这次进了前三，给大伙分享一下我的参加经历和解题思路🥰🥰。

第一次参赛

排名101，第一次参加CSDN的编程比赛，没认真打哈哈哈哈，后面发现这个比赛好像挺容易获奖的，前30名就有实物奖励了，就开始认真打了。

第二次参赛

排名45，这一期开始有老六了，就是一些人开小号去刷分刷时间，去掉一些老六的话我应该排在40名以内。
有点可惜错了一道选择题，害，就差这10分了。（下图排名2、3的都是老六选手，后面被ban掉了）

第三次参赛

排名第三，这一次是四道编程题了，容错率更大一些，所以拿了个第三哈哈哈。

本期解题思路分享

前两题比较简单，很快啊，啪的一声，题就过了，主要是后面两题，卡了很久。

第一题：小玉家的电费

题目描述

夏天到了，各家各户的用电量都增加了许多，相应的电费也交的更多了。小玉家今天收到了一份电费通知单。小玉看到上 面写：据闽价电[2006]27号规定，月用电量在150千瓦时及以下部分按每千瓦时0.4463元执行，月用电量在151~400 千瓦时的部分按每千瓦时0.4663元执行，月用电量在401千瓦时及以上部分按每千瓦时0.5663元执行;小玉想自己验证一 下，电费通知单上应交电费的数目到底是否正确呢。请编写一个程序，已知用电总计，根据电价规定，计算出应交的电费 应该是多少。

输出时保留一位小数。

解题思路

这题主要是把用户用电的不同区间分开来计算，最后再输出的时候保留一位小数就好了。

package cn.sticki.offer.exam.csdn;import java.util.Scanner;/*** @author 阿杆* @version 1.0* @date 2022/8/22 10:38*/
public class Test1 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);String str_0 = scan.nextLine().trim();int amount = Integer.parseInt(str_0);scan.close();float result = solution(amount);System.out.printf("%.0f\n", result); // 保留一位小数，直接改模板}public static float solution(int amount) {float result = (float) 0.0;// TODO: 请在此编写代码if (amount <= 150) {result += 0.4463 * amount;} else if (amount <= 400) {result += 0.4463 * 150;result += 0.4663 * (amount - 150);} else {result += 0.4463 * 150;result += 0.4663 * (400 - 150);result += 0.5663 * (amount - 400);}return result;}}

第二题：反转字符串

题目描述

对于一个字符串，请设计一个算法，只在字符串的单词间做逆序调整，也就是说，字符串由一些由空格分隔的部分组成，你需要将这些部分逆序。 给定一个原字符串A，请返回逆序后的字符串。例，输入"I am a boy!“输出"boy! a am I”

解题思路

这题其实就是反转列表，把每个单词放到先存到List中，然后反转这个List即可。

正常的解题方法：

package cn.sticki.offer.exam.csdn;import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;/*** @author 阿杆* @version 1.0* @date 2022/8/22 10:47*/
public class Test2 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);String str = scan.nextLine().trim();scan.close();ArrayList<String> result = solution(str);for (int i = 0; i < result.size(); i++) {System.out.print(result.get(i) + " ");}}public static ArrayList<String> solution(String str) {ArrayList<String> result = new ArrayList<>();// TODO: 请在此编写代码// 以空格为分隔符将字符串截断String[] strings = str.split(" ");for (int i = 0; i < strings.length; i++) {result.add(strings[i]);}Collections.reverse(result);return result;}}

通过修改模板，读取的时候就直接把单词存放到List里，这样处理起来更快也更方便：

package cn.sticki.offer.exam.csdn;import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;/*** @author 阿杆* @version 1.0* @date 2022/8/22 10:47*/
public class Test2 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 注意这里我把输入改掉了，我用hasNext判断是否结束，是只能在oj上跑的，本地跑不了ArrayList<String> list = new ArrayList<>();while (scan.hasNext()) {String next = scan.next();list.add(next);}scan.close();ArrayList<String> result = solution(list);for (int i = 0; i < result.size(); i++) {System.out.print(result.get(i) + " ");}}public static ArrayList<String> solution(ArrayList<String> list) {Collections.reverse(list);return list;}}

第三题：小Q整数分割

题目描述

小Q决定把一个整数n，分割为k个整数。 每个整数必须大于等于1。 小Q有多少方案。

输出一个整数，即有多少种不同的分法。答案对1e9+7取模。

解题思路

这题dp，可以把题目看成，一共有n个球，k个桶，每个桶里至少放一个球，问能有多少种放法（每个球都是一样的）

状态量map[i][j]表示将 i 个球分到 j 个桶里，每个桶最少一个球，那么我们要算的其实就是 map[n][k] 。

状态推导
当前状态一定由以下两种情况组成

• 至少有一个桶是只放一个球的。因为有一个桶和一个球已经被使用了，那么当前还剩 i - 1个球和 j - 1个桶，即 map[i - 1][j - 1]。
• 没有一个桶是只放一个球的。我们可以转换为下面几步：
  1. 先给所有的桶里放一个球，那么还剩 i - j 个球
  2. 把剩下的球再分到所有的桶里，每个桶至少分一个球，也就是把剩下的球分到 j 个桶里
  3. 这又回归到我们状态量了，等于是 map[i - j][j]

有了上面两种状态，那么有 map[i][j] = map[i - 1][j - 1] + map[i - j][j]; 那么这题就差不多做出来了。

还有几个前置条件需要列一下：

• 当 i = j 时，只能分一种情况，就是给每个桶分一个球
• 当 j = 1 时，也只有一种情况，就是把所有的球放到一个桶里
• 当 i < j 时，嗝屁，桶比球多，这咋分，分不了，只能算 0 种

下面看代码，注意要取模：

package cn.sticki.offer.exam.csdn;import java.util.ArrayList;
import java.util.Scanner;/*** @author 阿杆* @version 1.0* @date 2022/8/22 11:25*/
public class Test3 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);String str_0 = scan.nextLine();String[] line_list_0 = str_0.trim().split(" ");ArrayList<Integer> arr = new ArrayList<>();for (int i = 0; i < line_list_0.length; i++) {arr.add(Integer.parseInt(line_list_0[i]));}scan.close();int result = solution(arr);System.out.println(result);}public static int solution(ArrayList<Integer> arr) {int n = arr.get(0);int k = arr.get(1);int mod = 1000000007;// 如果n<k，是分割不了的，直接返回0if (n < k) {return 0;}int[][] map = new int[300][300];for (int i = 1; i <= n; i++) {map[i][1] = 1;}for (int i = 2; i <= n; i++) {for (int j = 2; j <= i && j <= k; j++) {if (i > j) {map[i][j] = ((map[i - 1][j - 1] % mod) + (map[i - j][j] % mod)) % mod;} else {map[i][j] = 1; // 这里else只有一种情况，就是 j == i，故直接赋值0}}}return map[n][k];}
}

第四题：新型美丽数列

题目描述

定义美丽数列A：

1. 数列中相邻的数越是靠内相对大小加一,a[2]=a[1]+1,a[n-2]=a[n-1]+1…
2. 距离边缘距离相等的数的大小相等:a[0] = a[n-1],a[1] = a[n-2]…

通过修改最小的数字使得给定数列变成美丽数列。 修改后的值必须仍是正整数。返回修改数。

解题思路

说实话这题我没太理解到底要返回什么结果，但是这个数列的操作我还是看懂了，就是说最终数列必须是这样的：

• 1 2 3 2 1
• 5 6 6 5
• 7 8 9 10 11 10 9 8 7

然后这题的话数据量好像不是很大，直接暴力模拟一下就好了，我的思路：

1. 以第 i 个数为基准，然后按照题目的条件，模拟出一个美丽数列，就是新建一个临时数组，数组中所有的数都是按照美丽数列的要求，并且参照第 i 个数生成的，那么它一定是美丽数列。
2. 对比原始数列和这个美丽数列中的每一个数，判断有几个数是不相同的，记录为 min
3. 循环第一步和第二步，找到最小的 min ，就是答案了
4. 需要注意在第一步的时候，如果某个位置生成了小于1的数那么这个数组是不能用的，应该直接丢掉

感觉思路没错，但是这题只过了20%（就离谱），所以代码就不贴了哈哈哈。

上面的代码都是我赛后重新在本地IDEA写的，跟比赛时写的代码可能有出入，也可能有些小问题。
分享的思路和代码如果有错误的地方，欢迎各位同学批评指正😋😋

给官方提的一些建议

参赛的bug基本都有同学在社区反应了，这边我写一些的是一些个人的建议

1. 题目里给的数据范围可以更准确一些。第四期第三题因为有特殊样例超数据范围，导致很多人卡了很久（包括我）。
2. 题意可以描述的更清楚一些，样例也可以多给几个。这条我指的是第四题嘿嘿嘿🤣。
3. 初始模块可以再靠谱一点的。我确实发现有好几题都需要修改模块才能通过，比如 int 改为 long之类的，还有一些地方可以通过修改模板找到更快更方便的解题方法（我上面题解里就有）。
   我确实能够通过修改模板过题，但是对于其他大多数同学来说，未必能够发现其中的问题，因为这是官方模块，所以他们不会怀疑。
   或者说，直接不给模板，让大家自己写输入输出？

昂，大概就想到了这些，我是出于一个写题人的感受进行考虑的，如有不妥之处，还请多多包涵。