noip2002提高组题解

再次280滚粗。今天早上有点事情,所以做题的时候一直心不在焉,应该是三天以来状态最差的一次,所以这个分数也还算满意了。状态真的太重要了。

第一题:均分纸牌

贪心。(昨天看BYVoid的noip2001题解的时候一不小心看到了2002的题解里的两个字,就是贪心,然后就很放心地写了,这算不算作弊啊。。。)

貌似我的方法挺奇怪的:遍历,计算出[卡牌数与平均数之差],在里面找到差最大的那堆卡牌,然后分别统计最大堆左边和右边的[卡牌数与平均数之差]的和,然后决定从最大堆中往哪边分牌以及分多少牌。如果堆两边[卡牌数与平均数之差]的和都为负,就向更小的那个方向分牌,分的牌数恰好等于该方向[卡牌数与平均数之差]的和的绝对值(绕来绕去好别扭);如果两边和一正一负,往负的方向分,分的牌数为正的方向之和加上最大堆自身的与平均数的差。

果然是很奇怪的策略。居然能一次AC我表示十分感动。

貌似网上的题解是依次而且是一次将各个牌堆变为目标状态。果然通俗易懂。

第二题:字串变换

又是字符串。。。NOIP两大坑:字符串和浮点。

看到最多10步果断想到ID-DFS,写起来各种方便,时间也还能忍受。不用多讲,每次查找替换然后往下搜索。ID-DFS所有点加起来居然只跑了0.7s,我是应该说数据太弱还是说学校测评机太好。。

1次AC。

第三题:自由落体

水题。但是我爆零了。而且还是不知道什么地方错了。反正是水题。错就错了。本题不需要题解。

目前仍爆零。不愿再做。

第四题:矩形覆盖

嗯,这道题目一开始看的时候确实会觉得很难。但是仔细分析之后发现搜索或者枚举就好。我用的是深搜,每次新扫描到一个点就修改当前矩形的上下左右边界,或者干脆另起一个矩形。注意点是要排序的,而且第一次按横坐标排序,搜索,第二次按纵坐标排序,再搜索。注意如果横坐标相同就纵坐标小的优先。在这个细节被卡掉一个点,所以只拿了80分。

经验教训:

1. 不要畏难;

2. 排序的时候注意当第一关键字相同时应该采取什么策略(第二关键字优先或者随意);

3. 不要高估了NOIP的题目。

原文地址:https://www.cnblogs.com/lsdsjy/p/3859273.html