荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: 成都, 这里没有遗忘 - 成都赛总结(zz from ZSU)
发信站: 荔园晨风BBS站 (2005年11月10日17:38:52 星期四), 站内信件
发信人: whimsy (奇思), 信区: ACMICPC
标 题: 成都, 这里没有遗忘 - 成都赛总结
发信站: 逸仙时空 Yat-sen Channel (Thu Nov 10 14:37:21 2005), 站内信件
∞ 1 ∞
剩下不到1分钟, 在队友的催促下心有不甘地做了最后一次提交. Wrong Answer.
比赛就在这个时候结束了, 迷迷糊糊地跟着去照相留念, 一切还彷若在梦中…
∞ 2 ∞
五个小时前.
趁比赛还没开始, 先去看了看气球的颜色: A题红色, C题黄色, G题蓝色… I题比较特
别, 是花色. 当时看到带花色的有各种不同的颜色组合, 就开玩笑的说先把I题过了看看拿
到的是什么颜色, 没想到言中了.
一开始把题目分开来看, 我看A~C, 张翼看D~F, 容健明看G~I.
A题题目比较长, 没怎么看就跳过了. B题是求若干串的最大公共子串, 开始觉得好像
在zoj做过类似的题, 就跟张翼说了, 不过后来觉得数据规模实在太大了. C题是一道组合
数学的题目, 看完题目后跟张翼说了题意, 不过没什么头绪. 后来又回过头看A题, 大概看
了看题意, 觉得是非常复杂的模拟题.
张翼看完了他那部分, 就跟我们交流题目. D题是一道和迷宫有关的题目, 我们都觉得
应该可以用搜索. E题是求满足指定要求的集合个数的, 当时没有什么想法(后来一起坐车
的一个浙大的说这题好像可以用DP, 不过没细想). F题是有七页纸的超长题目, 当时张翼
没看完题目, 不过感觉应该是模拟题.
健明看的G题是问一棵树最少加上多少条边就可以去掉任意一个顶点都仍然连通. 他觉
得可以根据顶点的度数来判断, 不过当时的想法可以找出反例来. I题是求一些周期在20以
内的周期序列在什么时候它们的值之和最大, 健明算了1到20的最小公倍数, 发现实在太大
了. 而我除了相同周期的序列可以先合并之外也想不出什么.
这时比赛已经进行了相当长的时间, 而我们仍没有一道题是觉得可以做的. 此时比较
多的人过了C题, 健明就健议先水一下. 水的方法是: 直接把input加1除3. 健明很快打完
程序, 提交. Wrong Answer.
当时有一些队过了F, 张翼就叫我先看看F. 先看看样例, 觉得有点像拓扑排序, 后来
发现想错了. 这时健明发现互质周期的序列的最大和可以由它们各自最大值的和简单算出,
从而大大减少I题的运算复杂度. 于是健明就开始敲那题.
健明的I题过了样例, 测试了几个数据后提交. Wrong Answer. 这时我想到那题的数据
比较大, 就问他会不会爆long, 他才发现最后的输出%lld写错成%d. 再次提交, 终于得到
我们队的第一个Yes. 一个黄色的气球插在我们的花盆上, 但心里并不轻松, 因为比较多的
队已经过了两题.
张翼催我做F题. 重新审视一下题意, 发现是模拟题, 题目把所有步骤写得很清楚了,
做了一些简单的规划后就开始敲题. 敲着敲着发现有个地方很难处理, 没办法做下去. 这
时想用brutal的方法算出C题的后几个数据, 看看有没有规律, 不过张翼说这道题有规律的
可能性不大, 更有可能是递推.
这时有两队过A题, 张翼觉得应该是模拟题, 就叫我看下. 看明了题目, 发现算法不太
复杂, 略规划下就开始敲了.
健明推出了C题的公式, 张翼说程序很短. 我就先让他敲了, 自己的程序则打印出来,
在上面手写程序. 健明也想出了G题的做法, 用一张纸手写程序.
张翼的题打完, 测几个数据后提交, 我们队得到了第二个气球. 这时我的程序也写好
了, 就上去打. 打完之后, 编译一大堆错, 把程序和编译错误信息全都打印出来, 由健明
去打G题. 张翼开始想D题, 算了一下状态总数后, 觉得搜索应该可以过.
健明打完G题, 测过数据后submit. Yes! 第三个气球送了过来.
又改了下我的程序, 没有编译错了, 不过运行时出错. 继续打印, 张翼开始敲D题.
把运行时出错的bug改了, 这时比赛还剩下半小时, 张翼决定放弃D题, 全部时间用来
做A.
这时A题的运行结果已经比较接近样例, 又改了几个bug后, 样例过了. 提交. Wrong
Answer.
又测多几个数据, 发现程序的一些bug, 提交. Wrong Answer.
只剩5分钟多了, 又发现一个比较致命的bug. 终于改好之后, 满怀希望的提交. 还是
Wrong Answer.
一直到比赛结束, 奇迹还是没有出现.
∞ 3 ∞
回顾一下做过和没做过的题:
C题:
一个N个元素的序列, 取出前M个时认为它们不是最大的, 之后取出比前面的数大的数
就认为它是最大, 问M取多少时猜对最大数的概率最大.
设: 前j个说No猜对最大数的概率为f(j) 求: 假设最大的数在位置i, 则只要前i-1个
数中的最大数在前j个就可以猜对, 这个概率为 j/(i-1)N. 那么可知f(j)=(j/N)(1/j+1/(j
+1)...1/(n-1))。现在只要求出M使得f(M)最大. 要使f(j+1)-f(j)>0, 只要1/(j+1)+...1/
(n-1)>1这是单调减的. 那么很容易O(n)时间内找最大的f(j).
程序就几行:
for (su=0,j=n-1;j>0;j--)
{
su+=1/j;
if ( su>1 ) break;
}
printf("%d\n",j);
G题:
在一棵树上加最小的边, 使得去掉任意一个顶点, 图还是连通的.
这题的大概做法是枚举根节点, 然后用叶结点配对连边.
I题:
题目意思是有若干不同周期的序列, 求: 在哪一个时刻,所有序列在该时刻的值的和最
大. 周期的范围在1到20之间.
状态总数是1和20的最小公倍数, 这个数显得有些过大. 但是注意到对于两个具有互质
周期的序列, 它们在同一时刻的最大和是两个序列的最大数值的和, 所以可以把11,13,17,
19这些和1-20之间任何一个数互质的质数抽出来, 剩下的数的最小公倍数在可接受的时间
规模之内.
所以, 最后的做法是, 求出除了11,13,17,19这些周期之外的序列在哪个时刻它们的和
最大, 然后把这个最大值跟11,13,17,19周期的序列的最大值相加.
A题:
有一些模块, 可以从输入里取出原料, 根据一定的规则生产出相应的产品(其实是一些
字符串替换). 给出所有原料, 模块以及连接方法, 求出指定模块的产品.
题目不难, 但是处理起来很麻烦, 而且估计有不少陷阱. 最后还是没能过, 哭.
B题
求若干字符串的最大公共子串.
本来想两个两个来找公共子串, 复杂度太大, 没想下去.
D题
一道关于迷宫的题, 可以用搜索, 但处理很麻烦.
E题
有一些关于集合的关系式, 求出满足这些关系式的集合个数.
据说可以dp?
F题
一道关于并行运算的模拟题. 有若干表达式, 它们有一些依赖关系, 可以根据这些依
赖关系做成一个DAG. 但是这个DAG没有办法用xml记录, 所以要根据题目的步骤, 把DAG转
化成一棵XX树, 然后用xml格式输出.
这题比较烦, 比较烦, 比较烦...
H题
没看.
∞ 4 ∞
开始没认真看A题, 导致最开始时错过了一道可以做的题. 结果开始一个多小时机器是
空闲的, 到后来做A题时时间已经比较吃紧了, 而且做的时候考虑不全面, 最后以郁闷的
Wrong Answer结束.
没有完全看清题目就开始做F题, 结果在上面浪费了不少时间, 最后还是半途而废.
我们队的罚时在做3题的队伍里是最高的, 除了因为提交比较迟外, 错了两次也增加了
40分的罚时. 第一次错是因为想水C题, 正如张翼所说, 以后不能随便水题了. 第二次是因
为输出. 两次错得都很不值得.
不止一次的想, 如果我们队过了第4题, 结果会是怎样呢. 但是, 比赛没有如果.
∞ 5 ∞
在机场收到张翼的短信: 第六名. 我们队总算有惊无险地拿到金牌. 但却怎么都高兴不
起来, 只想对队友说: 你们做得很棒, 我没完成任务, Sorry.
--
Alice, Bob, Carol and Dave
※ 来源:．逸仙时空 Yat-sen Channel bbs.zsu.edu.cn．[FROM: 192.168.36.249]
--
抓緊時間把感情的帳單
好好去認認真真一一的清還
為身邊每個人
不要怠慢
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店