笔试强训 Day 14：乒乓球筐、组队竞赛、删除相邻数字的最大分数

Day14乒乓球筐思路使用哈希表计算 A 中每种乒乓球的个数再枚举 B 对应的乒乓球种类对应的 hash–当有 hash 小于 0不符合条件注意本题的输入方式非常特殊输入 ABCDFYE CDEbr/ABCDGEAS CDECDE代码实现importjava.util.*;importjava.io.*;publicclassMain{privatestaticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{StringstrA;while((strAin.next())!null){StringstrBin.next();int[]hashnewint[26];for(charch:strA.toCharArray()){hash[ch-A];}booleanflagtrue;for(inti0;istrB.length();i){charchstrB.charAt(i);hash[ch-A]--;if(hash[ch-A]0){out.println(No);flagfalse;break;}}if(flag)out.println(Yes);}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());}StringnextLine()throwsIOException{returnbf.readLine();}}组队竞赛贪心三个为一组把所有人中最小的那几个去掉剩下的按两个一组选的水平值的队员要刚刚好有一个比他大一点点的思路有 cnt 支队伍先对队员排序剔除最小的 cnt 个剩下的队员选择相邻两个为一组一组中较小的作为队伍的水平值注意返回结果使用 int 会溢出代码实现importjava.util.*;// 1 2 5 5 5 8// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intcntin.nextInt();intncnt*3;int[]numsnewint[n];for(inti0;in;i)nums[i]in.nextInt();longret0;Arrays.sort(nums);for(inticnt;in;i2){retnums[i];}System.out.println(ret);}}删除相邻数字的最大分数1. 解法一 (动态规划)状态表示f[i] 选择 nums[i] 时的最优解g[i] 不选择 nums[i] 时的最优解dp[i] 两种最优解的最优解状态转移方程对数组排序根据 nums[i] 和 nums[i-1] 之间的三种关系分别填 f[i]g[i]importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();int[]numsnewint[n1];int[]hashnewint[10001];longret0;for(inti1;in;i){nums[i]in.nextInt();hash[nums[i]];}Arrays.sort(nums);// 选 i 和不选 i 时的最优解long[]fnewlong[n1];long[]gnewlong[n1];// 两种最优解的最优解long[]dpnewlong[n1];for(inti1;in;i){intcnthash[nums[i]];if(nums[i]nums[i-1]){f[i]f[i-1];g[i]g[i-1];}elseif(nums[i]-nums[i-1]1){f[i]g[i-1]nums[i]*cnt;g[i]Math.max(f[i-1],g[i-1]);}else{f[i]Math.max(f[i-1],g[i-1])nums[i]*cnt;g[i]Math.max(f[i-1],g[i-1]);}dp[i]Math.max(f[i],g[i]);}System.out.println(dp[n]);}}2. 解法二Delete and Earn / 打家劫舍本质是经典的Delete and Earn / 打家劫舍但这份代码不是最优写法主要有几个问题nums[i] * cnt这里是int * int会先按int计算虽然本题最大1e4 * 1e5 1e9没溢出但更稳妥应该转long。排序O(n log n)不是必须的因为值域只有10000可以直接按值域 DP做到O(n maxA)。f/g/dp三个数组也不需要两个变量就够。更优写法如下importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();intmaxV0;int[]numSumsnewint[10001];for(inti0;in;i){intnumin.nextInt();numSums[num]num;maxVMath.max(maxV,num);}longpreOne0,preTwo0;for(inti0;imaxV;i){longcurMath.max(numSums[i]preTwo,preOne);preTwopreOne;preOnecur;}System.out.println(preOne);}}代码讲解importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);// 数组长度intnin.nextInt();/* * points[x] 表示 * 如果我们最终决定选择数字 x那么所有 x 都可以被依次选走 * 能获得的总分就是 x * x 出现的次数。 * * 例如数组为 * 1 2 1 3 2 2 2 2 3 * * points[1] 1 1 2 * points[2] 2 2 2 2 2 10 * points[3] 3 3 6 * * 原问题就转换成 * 在 points 数组中选择若干个位置不能选择相邻位置 * 让选择到的 points 值之和最大。 */long[]pointsnewlong[10001];// 记录输入中出现过的最大数字后面 DP 只需要遍历到 maxValueintmaxValue0;for(inti0;in;i){intnumin.nextInt();// num 每出现一次如果选择 num就可以多获得 num 分points[num]num;maxValueMath.max(maxValue,num);}/* * 这是“打家劫舍”模型。 * * 对每个数字 i 来说有两种选择 * * 1. 不选择 i * 那么最大分数就是处理到 i - 1 时的最大分数prevOne * * 2. 选择 i * 因为选择 i 会删除 i - 1所以不能加处理到 i - 1 的结果 * 只能加处理到 i - 2 时的最大分数prevTwo points[i] * * 所以状态转移为 * dp[i] max(dp[i - 1], dp[i - 2] points[i]) * * 这里没有真的开 dp 数组而是只用两个变量滚动保存 * * prevTwo 表示 dp[i - 2] * prevOne 表示 dp[i - 1] */longprevTwo0;longprevOne0;for(inti1;imaxValue;i){// current 表示 dp[i]也就是处理完数字 1 到 i 后的最大得分longcurrentMath.max(prevOne,prevTwopoints[i]);// 向后推进一位// 下一轮的 dp[i - 2] 就是当前的 dp[i - 1]prevTwoprevOne;// 下一轮的 dp[i - 1] 就是当前的 dp[i]prevOnecurrent;}// 循环结束后prevOne 就是处理完 1 到 maxValue 后的最大得分System.out.println(prevOne);}}选择数字x一次只能得x分但选择了一个x后只会删除所有x-1和x1不会删除其他x。所以如果决定选x最优一定是把所有x都选完收益是x * count[x]于是问题变成在数字 1..10000 中选若干个数不能选相邻数字使收益总和最大这就是打家劫舍dp[i] max(dp[i - 1], dp[i - 2] points[i])所以这个版本更优时间复杂度O(n maxA)maxA 10000 空间复杂度O(maxA)也可以认为是常数级排序版是时间复杂度O(n log n) 空间复杂度O(n)能过但不是最优写法。