第一题:智商评估【P377】 W (T:O(k*n*log2n);R:O(n))k为数据组数;
*错因:计算各个星球的居民时,没有考虑到到最后一个星球时(即数组尾)要移出数组。加少了一个。
1.核心思想:快速排序,分别计算星球人数,判断奇偶性,按要求输出数字。
2.易错点:两个int数据相加有可能超过int范围,故必须定义为long long。
3.技巧:用一层for循环枚举所有数据,由q标记起点计算人数比用两层while效率高。
第二题:猴子【P378】 W(T:O(n2);R:O(n2))
*错因:分析时第一次将动态规划的顺序弄反了。应该以跳跃次数为第一层,树的顺序为第二层。写反之后会导致部分数据重合加在一起。第二次误分析为最短路。用floyd会使数据反复被覆盖,而导致原数据不能参与之后的判断。
1.核心思想:动态规划。从第一棵树开始向外扩展,由dic[i][k]=max(dic[i-1][j]+bl[k],dic[i-1][j]);推出每棵树的最优解。
2.易错点:猴子的跳跃次数是不定的,不能使后面的数据先于其前面被覆盖。
第三题:读数【P379】 60%R 40%W (T:O(n);R:O(n))
*错因:读题时把“不论是否出现‘+’都不输出”看成了“不会出现‘+’”;另外关于每四位数第一个零出现的标记不仅要满四清零,还要在出现非零整数时清零。
1.核心思想:分类讨论,将不同情况分别处理。每四位处理一次。
2.易错点:列举情况:000000000;241545.等。要将各种情况考虑完整。
3.技巧:不能光勾下整句话,要圈出关键词,避免误解题意。
第四题:转弯机器人【P380】 五个点出现死循环(T:O(R*C);R:O(4k*R*C))
*错因:暂时没有发现为什么会出现死循环。可以肯定有点重复入队,查出来之后补在回复里。
1.核心思想:用结构体记录不同方向来的最优解,用广搜来找出所有可能。
2.易错点:不同方向来的解与左转右转的关系要弄清楚。
3.技巧:处理转弯问题可以通过表示其方向来代替比较横纵坐标。
另详见代码。