荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: *成都回忆*(zz from ZSU)
发信站: 荔园晨风BBS站 (2005年11月10日23:23:44 星期四), 站内信件
发信人: infant (水中的鱼), 信区: ACMICPC
标 题: *成都回忆*
发信站: 逸仙时空 Yat-sen Channel (Thu Nov 10 19:48:54 2005), 站内信件
很多东西忘了，记起来的就写写吧。。
A题：比较麻烦的模拟题(欧尘做的)
B题：有难度，比赛完了才知道用后缀数组。
C题: 我敲的，简单说说方法
设：前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);
D题：状态不多，可以直接搜。但是因为有8个状态参量，中间处理比较复杂。(我
打的，最后没时间敲完)
E题：不知道怎么做
F题：更麻烦的模拟题，题目好长。(欧尘打了几行，放弃)
G题：比较有趣的图论题，题目意思就是加入最少的边，使得所有点在圈中。方法
是枚举根节点，根据叶结点计算。(健明做的，叫他写详细点)
H题：谁做了告诉我
I题：比较简单。11，13，17，19与其它互质，一定可以取到最大值。其它最小公
倍数在可接受的规模之内。
游记：
怀着莫名其妙的心情，我来到了成都。也许是因为40多个小时的旅途劳顿，成都给
我的第一印象是有点晃。天雾蒙蒙的，比较凉快。
从一下火车，川大的同学热心，从始至终感染我，直到离开成都。从那个帮提行李
的同学口里我了解到，原来川大有这么多校区。
更重要的是，我们比赛和住宿的龙泉校区正是靓颖读书的地方。哈哈。得来全不费
工夫，赚到了。小实和沛沛，羡慕我吧。
到了龙泉校区，天和心情一同豁然开朗。这里确是很美的地方。于是我们开始狂拍
照片。虽然欧尘的鼾声惊天地泣鬼神，但总得来说我休息得不错。
第二天试机，之前文志说了很多注意的地方。事实证明比赛环境是很不错的，我们
习惯的编辑器都有，用起来比较顺手。那些奇怪的返回也没有出现。好像赛场电源出过
一点故障。我不经意听到那些组织者的谈话，似乎准备了几套方案，也就放心了。
晚上，我们三条友开了个小会。大概(1)警惕训练时常出现的小问题，例如屏蔽和I/O格式
。(2)布置第二天的战略。(3)鼓励他们发挥潜能，健明常有好思路，尤其是图论题，
偶尘思维缜密，做题稳重。(4)克服训练时的坏习惯，例如健明打程序前没有规划，
结果越打越糊涂。
第三天早上，我醒得很早，喝了杯健明的麦斯威尔，怀揣郭老师买的朱古力。进到
考场。
说真的开始前确实有点紧张，但是我是队长，得装作不紧张。后来看到对面的浙大
同学，似乎比我们还紧张，我们就不紧张了。哈哈。
随着黄金雄一声令下，比赛开始。我看DEF,欧尘看ABC,健明看GHI。看完题以后，
我愣住了，问他们有没有题可以打。他们也愣住了。就这样愣了半个钟，这才发现全场
都愣住了。我大概估计到了今天的题目不是那么好做的，对习惯做快题的队无疑是一个
打击。“OK，大家把自己看的题目说说，交流一下。” 于是我们3人将各自的题目和想
法说了一下，并开始对有些题目着重讨论。欧尘C题想推出一个组合公式但是没有成功，
并且我觉得规模也不允许用组合公式，除非可以约掉大部分。于是我开始思考递推公式。
B题的复杂度让人愕然，我和欧尘讨论了很久没有结果(当时不知道用后缀数组)。G题是最
有希望的，健明对这样的题一向有很好的想法。每次我们讨论设想的过程就是逐渐完善的
过程。最后考虑到了各种情况，方法就出来了。在没有人过题的一个多钟头里，确实比较
难把握方向。我们三人常常看看这题，瞧瞧那题。这样绝对不行，因为每题都想一下，精
力分散，过了这么久都没思路，那么很容易养成思维的惰性。于是我叫他们各自专心攻较
有感觉的一两题。大约1个小时10多分钟黄色气球在东方升起，终于开张了。随后各种颜色
的气球逐渐升起，有F题,I题,G题。有了方向就好办了。也许是第一次参赛，我们还是
范了些错误，一开始就水了一下C题，其实我一向不赞成水题的，且根据这套题的
风格，不太可能有水题，但是还是忍不住侥幸心理，同意了他们水一下。另外I题,健明
交第一次I的时候，把"lld"写成了"d"。这是我的责任，没有再次检查常见的小问题。
仅有的两次罚时都有点不应该。I题过掉以后。其他题还没有成熟的想法。于是我决定让
欧尘做一题模拟题，让他独立code，我和健明继续讨论其他题目。事实证明，这次比赛
的关键就是那两题模拟题。F题早早有人做出，虽然题目很长但是我觉得有机会，
就叫欧尘赶快打。A题也很早有人过掉，红色气球很刺眼，似乎是深大最先过的。欧尘对
F题没有信心，但是仔细看完A题后。他神采奕奕的，我就知道有希望了，不过那时还不知
道这可是出线的希望。从那时开始，欧尘只要有空闲时间就敲A题。我和健明继续讨论C题
和G题。当我正在苦苦思寻递推方法的时候，健明找到了一个很简单的概率公式。我们比
较了一下相邻项的大小。结论是很明显的。这题很快过掉。这时候已经有不少人过掉2题
了。好像是交大已经有3题了。这个时候G题的方法已经很成熟了。D题的方法也很明显，
于是我决定打D题。叫健明规划好G题后再打。我和欧尘轮流code。这样没过多久，健明已
经在纸上写好了程序，上来敲了5分钟，瞬间过掉，爽呆了。这个时候大概还有1个多钟头
，我和欧尘轮流code。健明思考BE。欧尘常敲到一半，停下来打印一份，看看再敲。我只
要机器有空闲就上去敲，没有空闲就和健明讨论另外两题。这样过了大概半个钟头，这时
我觉得应该在两题之间选择一题，就叫欧尘全力写A题，调试也用机器，无论如何把这题
做出来。最后的半个钟头，3题有不少队，4题有一只队。我知道欧尘能做出A题，现在我
仍然相信。在最后的时间里，我们提交了几次，发现了几个bug，每一次都有机会。我知
道这题已经做对98%了。那时有句话一直在我心里，没敢说，怕给欧尘太大压力。“哈哈.
只要yes。我们就出线了。” 最后时刻确实比较刺激。比赛结束了。欧尘老是呆呆的。
哈哈，其实那题做出来，没做出来，又有什么关系？我们的成绩已经很出乎别人预料了。
更重要的是我们享受了比赛的过程。我觉得这次我们三条友表现是完美的，尤其是健明。
晚宴上，节目好看得不得了，东西好吃得不得了。那个跳独舞的女生太靓了。从她
一出场，文志就活起来了。蹲在台前一阵狂拍。立方紧随其后。两台相机“咔嚓。。咔嚓
。。卡咔嚓。。”呵呵，回来问他们要相片吧。晚宴的高潮来自川剧变脸，所有人站起来
围住舞台，掌声欢呼声震耳欲聋。我估计那个帅哥，表演这么多年还没见过这么热烈的场
面，早早就喘大气。真担心他手抖露出马脚。
第二天，我们去了音乐房子。可惜早上没开门。相片是有的。沛沛，小实以后有机
会到成都晚上再去吧。
我的第一次也是最后一次ACM之旅结束了，总算完成了一个心愿，没有遗憾了。成
都确实是个好地方，美女多，民风好；川大的同学很热情，对中大的人非常友好。在这里
要对川大的老师和同学，以及为这次竞赛付出辛勤劳动的人，表示由衷的感谢。
你们辛苦了! 让所有参加这次竞赛的人留下了美好回忆，你们做到了。
这次后羿拿了铜牌。也许并不能说明什么。小熊，立方，黄硕，继续努力，你们的
机会还多。好好总结，快些成熟起来，中大ACM的未来属于你们!
就快离开这里了，虽然有点不舍。感谢郭老师，感谢carp，inkfish，magicpig，kk。。
感谢所以给我帮助和鼓励的师兄。你们教会我的远远不止打程序。还要感谢小实，呵呵。
。另外感谢我的两位队友。。轩辕剑有你们才会锋利。。杭州不能陪你们去了。。好好把
握。。该出手时要出手。小实也要加油。。你不缺实力。。可能每次总是运气差一点。
。做掉那个谁。。你的收官之战应该比我精彩。。
好了。。胡乱写一通。。我不想淹没在回忆中。。就这样吧。。有错也不改了。。
--
※ 来源:．逸仙时空 Yat-sen Channel bbs.zsu.edu.cn．[FROM: 192.168.44.195]
--
我只想要往前飞
能飞多远也无所谓
我害怕了后悔
那种遗憾的滋味
往前飞......
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店