Day 32素数回文解题思路字符串操作注意第二个循环方向拼接回文的写法以及跳过最后一个数字的复制方式注意字符数组转字符串的操作注意判断素数的模版方法代码实现importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);char[]tmpInteger.toString(in.nextInt()).toCharArray();inttmpltmp.length;intntmpl*2-1;char[]snewchar[n];for(inti0;itmpl;i)s[i]tmp[i];// 跳过倒数第一个的复制for(intitmpl,jtmpl-2;j0;i,j--)s[i]tmp[j];longnumLong.parseLong(String.valueOf(s));booleanflagisPrime(num);System.out.println(flag?prime:noprime);}privatestaticbooleanisPrime(longnum){if(num2)returnfalse;if(num%20)returnnum2;for(longi3;inum/i;i2){if(num%i0)returnfalse;}returntrue;}}活动安排解题思路对活动开始时间排序如果下一个活动的开始时间 上一个活动的结束时间则 cnt针对冲突与不冲突两种情况更新上一个活动的结束时间代码实现importjava.util.*;importjava.io.*;publicclassMain{privatestaticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt();int[][]numsnewint[n][2];for(inti0;in;i){nums[i][0]in.nextInt();nums[i][1]in.nextInt();}Arrays.sort(nums,(v1,v2)-{returnInteger.compare(v1[0],v2[0]);});intcnt1;intpreStartnums[0][0],preEndnums[0][1];for(inti1;in;i){if(nums[i][0]preEnd){preEndnums[i][1];cnt;}else{preEndMath.min(preEnd,nums[i][1]);}}out.println(cnt);out.close();}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringlinebf.readLine();if(linenull)returnnull;stnewStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}合唱团解题思路动态规划。f[i][j]表示一共选择j个学生并且第j个选择的是位置i的学生此时能得到的最大乘积。g[i][j]表示相同条件下的最小乘积。之所以要同时记录最大值和最小值是因为能力值可能为负数较小的负数 × 负数 较大的正数例如-10 × -5 50 2 × -5 -10当前学生能力值为负数时之前的最小乘积反而可能变成当前的最大乘积。初始化时只选择位置i的一个学生f[i][1] g[i][1] arr[i];状态转移时假设当前选择位置i上一个选择的位置是prev。题目要求两个被选学生的位置差不超过d因此i - prev d也就是prev i - d同时prev必须在i前面所以它的范围为Math.max(i - d, j - 1) prev i - 1然后分别计算之前的最大乘积 × arr[i] 之前的最小乘积 × arr[i]从中更新当前最大值和最小值。以示例为例能力值7 4 7 k 2 d 50选择位置 1 和位置 3位置差3 - 1 2 50 乘积7 × 7 49因此最终答案是49。该算法的时间复杂度是O(n × k × d)在n 50、k 10、d 50的数据范围内完全足够。代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();int[]numsnewint[n1];for(inti1;in;i)nums[i]in.nextInt();intkin.nextInt(),din.nextInt();// 一共选择 j 个学生并且第 j 个选择的是位置 i 的学生此时能得到的最大乘积。long[][]fnewlong[k1][n1];long[][]gnewlong[k1][n1];// 单独初始化选一个人的情况for(inti1;in;i){f[1][i]nums[i];g[1][i]nums[i];}// 从第二个人开始选for(intj2;jk;j){// 优化: f[j][i] 已经选择了 j 个人, 第 j 个人编号是 i, 那么编号 i 一定大于等于 jfor(intij;in;i){f[j][i]Long.MIN_VALUE;g[j][i]Long.MAX_VALUE;// 枚举上一个学生的起始编号// f[j-1][pre] 表示选择上一个学生, 这个学生 pre 能距离 i 的最远位置// pre 编号一定大于等于 j-1 - pre j-1// pre 编号一定和当前编号距离小于等于 d - i - pre dintpreMath.max(j-1,i-d);for(intprevpre;previ;prev){longproduct1f[j-1][prev]*nums[i];longproduct2g[j-1][prev]*nums[i];f[j][i]Math.max(f[j][i],Math.max(product1,product2));g[j][i]Math.min(g[j][i],Math.min(product1,product2));}}}// 最终答案可能为负数, 不能初始化为 0longretInteger.MIN_VALUE;// 枚举选够 k 个人的最大值for(intik;in;i)retMath.max(ret,f[k][i]);System.out.println(ret);}}