2008 年 5 月 17 日,在浙江大学成功举行了浙江省第五届大学生程序设计竞赛。本人的解
题报告如下:
A 简单题
因为 p 的范围很小才 99 所以从 700-799 就可以满足全部要求了。可以打表出来,找出每
个连续的一段满足要求的数,保存起来(并且要求新存的段长度比原先的要长),打出一
张表,对每个要求的数,2 分答案。(把 1-99 的结果都保存好,直接输出)。反正“转折
点”很少,怎么搞都可以。
B 简单题
直接 bfs 无向图 mst。
C 中等偏难。
给定直线,对每条直线,传说解不等式组可以过,直接看是否存在一个点在直线之上。
(左端点取 max,右端点取 min,如果左>=右,直接 break 掉)。有点 ft...O(n^2)
n=5000 rp 好的可以过....
我用的方法类似于凸包,先把所有直线按照斜率 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 先给 B i 个元素,然后再和 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)因为 a b 都是
排序好的,所以 ca[j]这个值可以 2 分出来,(同理可以算出 cb[j],表示 a[cb[j]]>b[j-
cb[j]] 的第一个位置)。 前面排序再预处理求 ca cb 的时间复杂度为 O(nlogn)。然后,我
枚举 i 后,至少需要的代价是 i*(i-1),由给定的 cost 可以确定至多交换的次数是(cost-
i*(i-1))/2,然后由“划算”的程度,决定交换的次数至多是 ca[i],于是这两个值取 min,就是
交换的次数。这样交换的次数可以由 i 求出来,并且此时 A 中最小值应该是 min(换进来的
评论0