171.17集训队试题全国青少年信息学奥林匹克

1、青少年信息学中国国家队训练 2010-2011提交源程序须加后缀注意：最终测试时，所有编译命令均不打开任何优化开关。对于Pascal 语言对于C语言对于C+语言题目名称ConstructDigitBrt目录可执行文件名Construct.cpp/pasDigit.cpp/pasBrt.cpp/pas输入文件名标准输入标准输入标准输入输出文件名标准输出标准输出标准输出每个测试点时限1S1S1S测试点数目202020每个测试点分值555是否有部分分无无无题目类型传统型传统型传统型Construct【问题描述】随着开放的深入推进小T 家要拆迁了当对未来生活充满美好憧憬的小T 看到拆迁青年变成了绝望的

2、钉子户。的时候，小 T 从一位大好的由于小T 的家位于市中心，拆迁工作又难以进行，有关部门决定先把小 T 家用围栏围起来，以免影响市容。考虑到要建设资源节约型社会，他们希望所用的围栏长度越短越好，由于市中心寸土寸金，在围栏长度最短的情况下，围出的多边形面积越小越好。为了简化问题，约定，小T 的家是一个多边形，并且每条边与坐标轴平行，围栏的也是多边形，每条边与坐标轴平行。【输入格式】在第一行列出整数n多边形的顶点的数量。在以下 n 行中的每一行都有两个整数沿逆时针方向走过这个多边形顺次所经过的顶点的坐标。边界的任意三个连续顶点不在一条直线上。多边形的边界不含自交和自切。【输出格式】输出两行，第一

3、行为围栏最短的长度，第二行为长度最短的前提下，最小的面积。【样例输入】80 09 09 96 96 33 33 60 6【样例输出】3663【数据范围】对于 10%的数据 n20对于 70%的数据 n5000对于 100%的数据 4n100000，坐标的绝对值不超过 109 。【解题】题目的大意是求一个在周长最小的情况下面积最小的多边形，使得这个多边形能够覆盖输入中给出的多边形。所有多边形的边都是与坐标轴平行的。求多边形的周长和面积。首先，假设没有最后一个条件：多边形的边与坐标轴平行，只需要求出原多边形所有点的凸包就可以了。不难证明，凸包的周长一定是最短的，并且是唯一确定的。那么，如果加入这个

4、条件呢？问题的性质会不会发生改变呢？告诉，问题不会有质的变化，因为这样的条件就类似于把续的函数改成一个离散的函数。事实上，发现只需要把求出的凸包中所有的斜线变成拐角，最后的多边形就满足各边平行与坐标轴，也不难证明这样的多边形的周长也是最短的。不过，这么说太过于抽象了，也不方便编写程序来实现。析来找出题中所求的多边形的性质。可以通过的分不难发现，这个多边形仍然必须是凸的。因为如果这是一个凹多边形，那么它的周长一定不是最短的，可以把通过把凹的那一部分“拉直”来出一个周长更短的多边形。还有一个显而易见的性质就是在本题里坐标是可以离散化的。同时，还发现，如果保证了周长最小，那么多边形的面积实际上也已经

5、确定。这样，问题就转化成了求一个周长最小的凸多边形包含原多边形。这里，仍然可以套用求凸包的算法，只需要稍加修改。凸多边形是由上凸壳和下凸壳组成的，因此，壳。可以把问题分成相同的两部分，分别求上下凸来考虑求上凸壳的过程。自上向下，凸壳宽度会逐渐增加。并且，对于每一个高度，组成最后多边形的一定是最左和最右的点，因为如果中间有点，就不满足这是一个凸多边形了。可以首先离散出原多边形所有的高度，而新的多边形，根据上面所。可以从最高的点开始在向下扫描。用 L 和R分析的，也只会有这些点来左右边界，在向下的过程中不断更新L 和 R 的值。对于每一个高度，根据此时的 L 和 R形。之后可以用同样的方法求出下凸

6、壳，然后将两部分拼接起来。最后再用差积求面积即可。用差积计算的时候要注意保持所有的点按照顺时针或者逆时针顺序排列。另外，由于本题所有的边都与坐标轴平行，因此在具体实现的时候，不建左右边界上的点，每一层的边界点就组成了最后的多边议使用任何实数，以免发度问题。回顾本题，这是一道比较简单的题目，一开始，很容易把它和求凸包的问题联系起来，以此确定考虑问题的方向，然后只要稍加分析，就能够找出要求的多边形的一些性质。之后，通过这些性质，只需要通过简单的扫描就可以解决问题。Digit【问题描述】在数学课上，小 T 又被老师发现上课睡觉了。为了向全班同学证明小 T 刚才没有好好听课，数学老师决定出一道题目刁难

7、一下小 T，如果小 T 答不出，那么情节就按照俗套的路线发展下去了，小 T 显然无法解决这么复杂怜的小T 只能向你求助：题目是这样的：求一个满足条件的n 位数 A(不能有前导 0)，满足它的数字和为 s1,并且，A*d的数字和为s2.，可【输入格式】一行四个整数：n, s1, s2, d【输出格式】若存在最小的满足条件的数，则输出这个数，否则输出-1。【样例输入】2 9 9 5【样例输出】18【样例说明】1+8=918*5=909+0=9【数据范围】对于 20%的数据满足n5。对于 50%的数据满足n40对于 100%的数据满足 1n100，0s1n*9，0s2(n+1)*9,0d9【解题】这

8、是一道数位统计题，题目大意是要求一个满足条件的 n 位数 A(不能有前导 0)，满足它的数字和为s1,并且，A*d 的数字和为 s2。对于所有的数位统计题，算法都是适用的，本题也可以通过枚举每个数再判断来通过部分数据，这里就不在赘述了。来考虑动态规划的方法来解决这个问题。那么，就有两种方式来状态，一种是基于 A 来状态，另一种是基于 A*d 来状态。事实上两种方式都是可以行的，这里重点第二种。由于题目中要求最小的A，因此向地位递推。对于 A*d 的某考虑从一位，它有两部分组成，第一部分是 A 的这一位乘以 d 之后的个位，另一部分是A 的低一位的数乘以d 之后的十位。的状态来，optLenSu

9、m1Sum2Remain，Len 表可以用一个示当前长度，Sum1 和Sum2 分别表示当前的A 和A*d 的数位和，Remain 表示A的低一位的乘积的十位。这样就非常有效地了状态，对于转移，只需要枚举A 的下一位的数就可以了。来计算一下复杂度， 状态复杂度是 O(93*n3) ，转移复杂度是 O(94*n3)。显然，这个复杂度是难以承受的。要进一步优化，就要找出最小的数的一些性质。由于 opt 是一个 0/1 状态，这样太过浪费，尝试通过把 Len在 opt应该里来减少一维。那么，对于相同的状态可能有很多个满足条件的 Len，哪一个呢？发现，在 A 的某些位置中间添上一些 0，既不会影响

10、A 的数字和，也不会影响 A*d 的数字和。因此，的数变成长度为n。可以通过添加一些 0 来使得本来长度不够 n这样，回到之前，对于很多相同状态的 Len，就应该最小的就可以那一个，在 Len 相同的时候，则应该较小的那个数。这样，在中间添加一些 0 补满 n 位。考虑 0 添加的位置，应该是越靠前越好，这样能够使得这个数最小，但又不能够是前导 0。所以，最优的方案应该是 0 之前有一个非 0 数位。综上，就可以枚举 A 的最，在之后补足 0，然后再在最后添是枚举的，并且之后跟了尽可能多的 0(因为之前的上状态里的数。由于最Len 是取的最小的)，因此，这样构造出来的一定是最小的。在编写程序的

11、时候还需要注意，A*d 可能是n+1 位，需要分类一下。由于所有的状态都可以预处理出来，因此计算状态的复杂度和枚举的复杂度是不叠加的，总的复杂度就优化成 O(94*n2)，能够通过全部的测试数据。当然，这样还是不够的，还需要对这个题目进行一些常数优化，特别是在预处理状态的时候，尽量不使用递归，要统计这些状态，需要一定的复杂度，因此，还需要加上一些二进制的优化，比如树状数组。回顾本题，先发现了常规的数位统计的做法，经过复杂度分析，发现还需要优化。然后通过寻找这些数的性质，发现了一种构造的方案，再经过层层分析和不断完善，最后找到的解决问题的方法。这道题非常具有思考性，特别是对于最小的分析，非常巧妙

12、。Brt【问题描述】小T 的城市刚刚开始推行BRT（Bus RaTransit），其实，就是一种车。BRT 有 N 个站台，分别为 1 到 N，按照列车通过的顺序递增排列。在列车到站时，会有一些乘客上车，也会有一些乘客下车。由于 BRT 内空间狭小，乘客完全无法走动，在车上只有靠近车门的乘客才能够下车。和大部分车一样，BRT 有 2 个车门前门和后门。每一个上车的乘客可以选择从前门或者后门上车。现在有 M 个乘客，为 1 到 M，每个人都有各自的起点和终点，现在，需要聪明的你来安排一种上下车的方案，使得每个乘客都能够在各自的终点下车。【输入格式】第一行是两个整数 N,M。下面依次有 M 行，每

13、行有两个整数，表示一个乘客的起点和终点。【输出格式】输出你的方案：输出包括 2M 行，每行一种操作【样例输入】5 753 5【样例输出】1 11 23 22 41 X为X 的乘客从前门上车2 X为X 的乘客从后门上车3 X为X 的乘客下车41 53 73 63 5【解题】这道题的大致意思是说，有一个双端队列，可以从队首或者队尾和删除一些元素，要求元素按照一定的顺序操作序列。队列之后，再被删除。要求一个合法的这题容易让人联想到图论的一些问题，因为它看起来和拓扑等等算法密切相关。但是，如果用图论的算法来套本题，会让人无从下手。事实上，如果这是两个栈，而不是一个双端队列，这就可以通过贪心+染色算法来

14、解决，NOIP2010 的提高组最后一题就是这样的。由于队列的特殊性，即一个从队尾进入的人可能从队首出去，这点是不符合拓扑的性质的，是本题的最点。既然没有合适的算法，就让重新来分析一下这道题目的性质：用Li表示第i 号车厢的起点，Ri表示i 号车厢的目的地。首先需要确定一个将乘客上车的顺序。对于两位乘客，如果起点不同，则由题目知起点小的乘客先上车，若起点相同，则终点大的乘客先上车因为终点小的将先下车，所以将终点小的放在终点大的人的外面，不会对终点大的人产生影响。记第 i 个人的上车次序为 pi。每到一站，下，方便考虑。假设第i 个人上车后，导致第 v 个人再也不可能在目的则必然有RiRv（否则

15、i 不会对 v 产生影响）。用ci表示第i 个人上车的操作方案。优先将需要下车的人先车。由于BRT 是前后对称的，这里只i 个人从前面上车的情况。由于 RiRv，因此第 v 个人必然无法从前门下，而由于第 v 个人再也不可能在目的RuRv。车，因此第 v 个人的右边必然存在另一个上车的人 u，满足这里已经有了四个式子：pipu，pipv，RiRv，RuRv。情况 1：pupv由于u 比 v 晚上车，所以如果 cu=cv且ci!=cu，则同上，v 号人将被夹在中间，导致不能下车。稍作整理，可以得到如下两组充要的式子：对于人i,u,v，满足pvpuRuRv或者(2) RiRvRu且 cu=cv且 cu!=ci且 cu=cv且 cu=ci则必然使得整个问题无