第一题:连线问题【P382】 50%R 50%W (T:O(n2);V:O(n))
*错因:没有单独处理横坐标相同的情况(即分母为零的情况)
1.核心思想:分别求各个点之间连线的斜率,找出最多的不同斜率。
2.易错点:忘记考虑分母为零。
3.技巧:set 集合容器可避免重复。
第二题:麻烦的聚餐【P383】 R (T:O(g2);V:O(n2))
1.核心思想:最长不下降(不上升)序列
2.易错点:数据最大为30000,裸的最长不下降会超时。
3.技巧:累计处理连续的点可减小复杂度。
第三题:流星雨【P384】 90%R 10%W (T:O(?);V:O(n2))
*错因:计算陨石应该从第一秒开始,代码打错了边界,为第二秒开始。
1.核心思想:预处理最终陨石落点,和陨石降落顺序。并对扩展节点是否反复入队进行判断,以此优化。
2.易错点:判断陨石降落要在扩展该秒节点之前。
3.技巧:可以用queue队列。
第四题:旅馆【P385】 W(T:O(n);V:O(n))
*错因:误以为用二分答案,实际上本题的空房间所在位置并不是按大小顺序排好的。可能50是有人的,而24是无人的。二分答案会错开这种情况。
1.核心思想:第一个房间j,到最后一个房间jj=j+b-1;倒着枚举,一旦发现有人的房间,就让j移动到那里,做标记,continue,减少循环次数。详细见代码。
2.易错点:用cin cout会超时。改为scanf和printf就刚好可以过。
3.技巧:判断连续问题用递推式代替循环。