2008年浙江省赛ACM解题报告

2008年5月17日，在浙江大学成功举行了浙江省第五届大学生程序设计竞赛。本人的解题报告如下：

A简单题

因为p的范围很小才99所以从700-799就可以满足全部要求了。可以打表出来，找出每个连续的一段满足要求的数，保存起来（并且要求新存的段长度比原先的要长），打出一张表，对每个要求的数，2分答案。（把1-99的结果都保存好，直接输出）。反正“转折点”很少，怎么搞都可以。

B简单题

直接bfs无向图mst。

C中等偏难。

给定直线，对每条直线，传说解不等式组可以过，直接看是否存在一个点在直线之上。（左端点取max,右端点取min，如果左>=右，直接break掉）。有点ft...O(n^2)n=5000rp好的可以过....

我用的方法类似于凸包，先把所有直线按照斜率a由小到大排序，斜率相同取b较大的，扔掉b小的。于是所有直线斜率不同。准备一个栈，栈里面存放上一次能看到的“最上面”的直线以及这条直线能看到的范围x(x值右边的部分可以被看到）。初始时，把斜率最小的直线入栈，并记录x值为-inf。然后对第i条直线，所做的是用第i条直线和栈顶直线求交点x,如果这个x值不大于栈顶的x值，则把栈顶元素弹出，继续求交，否则退出。这种判断操作直到栈为空，或者当前栈顶的x值大于栈顶的x值。然后把第i条直线入栈，继续，看后面的直线。最后栈中的直线数就是能看到的。这种做法类似于凸包的方法，除去排序外，每条直线至多出入栈一次，复杂度O(n)。总复杂度是O(nlogn)。

D难题。

这题是比较有意思和有搞头的题。应该可以算压轴题吧。题目意思不难，但是很难做。我想了好久，想出个方法，但是比vb的方法难一些。其实可以贪心。首先集合大小为1时，没法搞，直接判断掉。我们把A集合和B集合里的数都由小到大排序。要移动元素并且保证代价，那么可以选择的操作方法是A和B交换一些元素，然后A再给B(或者B再给A)若干个元素。我们只讨论最后A再给B若干个数的情形，B给A的可以类似讨论。那么设A和B交换的个数为x,（注意交换完后，A和B仍然还各有n个元素），最后A再给B的元素个数为i,因为不能清空A,所以0<=i<n。如果枚举i，再枚举x，则复杂度要到O(n^2)，n=20000,不可忍受。考虑整个过程：A先把最小的x个和B中最大的x个交换，然后A再继续把原来其中的最小的i个给B。（移动进来的元素不准再移动出去，因为会浪费代价）。那么从效果上考虑，A把最小的（x+i）个元素给了B,B把最大的x个元素给了A。那么我们完全可以把这个过程变为A先给Bi个元素，然后再和B交换x个元素，这样可以达到相同的效果。但是这样的好处是，A和B开始交换时是从A的第i个元素和B的第(n-1)个元素开始的。（下标都是从0开始）。那么这样交换多少个才“划算”呢？即如何确定x呢？显然，交换的次数并非越多越好。我们只要交换到A中最小元素比B中最大元素大就可以停止交换了。于是可以预先搞一个数组ca[j]表示从A的第j个元素开始和B的第(n-1)个元素开始交换，最多交换多少次是“划算”的。即找到第一个满足a[j+ca[j]]>b[n-1-ca[j]]的位置（如果不存在这样的位置显然ca[j]=n-j）因为ab都是排序好的，所以ca[j]这个值可以2分出来，（同理可以算出cb[j],表示a[cb[j]]>b[j-cb[j]]的第一个位置)。前面排序再预处理求cacb的时间复杂度为O(nlogn)。然后，我枚举i后，至少需要的代价是i*(i-1)，由给定的cost可以确定至多交换的次数是(cost-i*(i-1))/2,然后由“划算”的程度，决定交换的次数至多是ca[i]，于是这两个值取min,就是交换的次数。这样交换的次数可以由i求出来，并且此时A中最小值应该是min(换进来的最小值,第一个没被换出去的值），B中的最大值应该是max(换进来的最大值,尾端第一个没被换出的值)，这些都很容易求，于是可以求出题目中的N和M,枚举i值，取N-M最大的即可。（再类似考虑B给Ai个，再循环一次，取最大值就好了）。后面枚举的复杂度是O(n)。（预处理ca,cb后，循环里所有操作是O(1)的）因此，总时间复杂度O(nlogn)。

E我出的题，简单题。

没有太多好说的，直接硬搞就行。原题的输出要求比这个麻烦得多，是要输出(f(x))'=g(x)的，这就有对系数为1和0的输出处理，以及指数为0和1的处理。题目简化了，没什么注意的地方了。

F简单题

找最大最小值，没什么好说的。

G我出的题，可以认为是简单模拟。

直接打表10^9是显然不可行的。其实我认为最简单的做法，是预map所有不超过1000的数的读法和阿拉伯数，这样读数可以分3节处理。注意一下and,zero等就好了。输出直接输出数字没有逗号。-.-

H简单dp。

背包....注意体力可以为0，满了不能再超。

I比较复杂的模拟

稍微有点复杂，但不是难到做不了，我写的代码210+行。大部分在解析xml。当然采取了偷懒的方法，如tag只看“<”里第一个非空白的字母（或前2个字母），频繁使用isdigit,isspace等库函数。然后当解析到rule或者default时，用strstr看里面是否有interval=和wait=的字样，如果有再用*10法处理数字。我并没假设“=”后面一定有引号，所以处理数字前是从“=”后面第一个是数字的处理到连续数字后面第一个非数字的。还有不管什么东西，我把XML里的所有字母都tolower了一次。（转换成小写字母了）。还有一点注意的是tag间的空白不能随便忽视。比如之间的字符全都有用（包括空格），也就是说从一个tag的“>”开始读到下一个tag的“<”结束。这样就处理好了XML。

然后对处理看到的帖子，对每个时间，（不是第一个帖子的话）分析看到这个帖子的时间加上wait值和上次发贴时间加上上次保存的interval值是否不小于当前的时间。如果是，则可以发贴，保存发帖时间，更新interval。看起来就这么简单。但是我认为还是有2点要注意的：（1）关于时间，题目上说看到的帖子是按时间先后排序的，2个帖子时间间隔小于24小时，也就是说，单看hh:mm:ss，可能后面的时间小于前面的时间时，这就是下一天的时间了。（按题目描述应该没有恰好24小时的情况，不过如果有的话，我简单地把第个时间忽略掉），我采取处理时间的方法是绝对时间，就是把时间通过hh*3600+mm*60+ss，转换成秒，然后看这个值%(一天的秒数）是增大还是减小了，然后决定加上多少来保证时间的单调递增，输出时还要转换成hh:mm:ss的形式(2)输入关于格式，题目后半部分的输入格式，hh:mm:ss后面一定有一个空格不算做发帖内容,这在匹配发帖内容时至关重要。（也许要匹配规则中可能包含首空格）在效率上，我使用的是getchar()，估计被gets要高一些吧。:)

J中等题

比较显然的矩阵乘方。用O(nlogn)的求幂方法即可。有一点注意题目中的K=0时（没有从该容器倒水的规则），并不是把其中的水都到出去，而是它其中的水始终保持不变。（若第p个容器K=0，则与输入的是1,下一行是p，等价）

K中等题

O(n^3)的dp。枚举两行i,j再枚举一列k。起初，用一个ans=0表示结果，设a[c]表示设定i,j后截止到当前列，i,j行的位置都是第c种福娃的列数。(c=0,1,2,3,4)。每当循环k前，先把a数组都清0。mat为输入矩阵，然后循环k,如果mat[i][k]==mat[j][k]，设mat[i][k]为第c种福娃，则总数ans显然应该加上a[c]（前面那些列都可以和当前列构成满足要求的矩阵的），并且a[c]数加1。最后ans为所求。

L简单题

可能图看不大清楚。其实点光源到（x,y,z)到它在z=0平面的投影点的光强度最强，然后随着它在z=0平面投影点为圆心的同心圆由里到外强度逐渐减弱，点光源(x,y,z)