荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: 成都之行(zz from ZSU)
发信站: 荔园晨风BBS站 (2005年11月10日23:24:39 星期四), 站内信件
发信人: Goffe (神话般的傻瓜), 信区: ACMICPC
标 题: 成都之行
发信站: 逸仙时空 Yat-sen Channel (Thu Nov 10 18:06:53 2005)
从成都回来了，趁对题目没有印象之前先写一写总结吧。
出发前，郭老师说，如果进了前六，就带我们去吃一顿正宗的川菜，唉，这句话
非常打击我的积 极性，因为我是很怕辣的；不过后来郭老师又说，中大出去比赛，没有一
次拿不到前六的，这句话又令我 很紧张，要是我们拿不到就丢脸了。那么只好硬着头皮去
拼一回了。还好，最后还是刚好拿到了前六，至 于“正宗的川菜”嘛，不予评价……
4号到了成都，晚上就到组委会提供的免费上网地方上网，Hooyee队都在做题，搞
得我都想做， 看到BBS上在讨论一道题目，于是做了做，不是WA就是TLE，非常郁闷，而且
Cubic看到我在做，也开始做 ，他做出来了我还不行，搞得我很紧张，怕比赛时的状态也
是这样就惨了。
5号热身赛，题目两道，第一道A+B，瞬间搞定，第二道一开始觉得是DP，得到了
无数TLE，挺影 响心情的，真的怕比赛时状态就这个样子，后来才知道是穷举加贪心，赶
在所有人走光之前做了出来，总 算找回了一点信心。
6号，正式比赛了，前两天的事情都不去想，专心比赛。结果嘛，也可以接受。
赛前决定，分开看题，欧尘看ABC，张翼看DEF，我看GHI。
G题，是在一个无环连通图上，加一些边，使得任意一个点被去掉以后，其他点都
仍然连通。开 始的时候想贪心，把这个图看成一科树，然后把叶子节点连起来就可以了，
那么加的边的总数就是叶子总 数加一再除二，发现错了，继续看题。
H题，好像是给出空间中的一些点，在给出在一维上的分散度(scatter degree)的
公式，求三维 最大分散度，好像是这样，没看懂，不敢碰。
I题，有长度为1～20的周期，求哪个时刻各周期的值的和最大。算了一下最小公
倍数，三千万， 不可能穷举，先放一下。
另外一边欧尘和张翼已经在讨论了，我也听了一下，欧尘说试一下水C，我记得当
时欧尘说的水 法是直接除2输出的，不过这次比赛半个多小时都没有人AC，不可能就这样
水掉的，所以不出意料的得到 了一个WA。然后跟张翼讲了I的一下题意，受到欧两次的启
发：第一，可以将相同长度的周期先合并，第 二，这一题跟素数有关。然后就突然想到两
个周期选最大的加一起就行了，然后发现要周期长度互质，于 是把11，13，17，19提取出
来，因为他们是素数，跟任何数都互质，且在1～20里没有他们的倍数。然后 把其他的数
求一下最小公倍数，5040，肯定行了！于是这一题很快就过了。其实在写程序之前就已经
注意 到可能会爆long，所以写的时候都已经小心的用long long了，不过在写的过程中才
想到以上的算法，于 是改了程序，输入也用%lld，但是输出却忘了%lld，没了一次罚时。
郁闷啊！
听欧尘说了C，觉得应该不难，于是跟张翼一起在算。经过一番计算以后终于想到
了：假设最大数在第i位，概率是1/N,然后，第i位之前最大的数在第j位或者之前的概率是
j/(i-1),然后对于全部的i，第j位可以赢的概率就是f(j)=j/N(1/j+1/(j+1)+.......+1/(
N-1))，然后f(j)取最大值的j就是答案M，经过计算简化以后，程序非常简单。
int i;
double f;
while(scanf("%d",&i)!=EOF)
{
f=0;
for(i--;su<=1;i--)su=su+1/((long double)i);
printf("%d\n",i);
}
最后在想G题，张翼说我通常在图论题上有奇怪的想法，而且虽然不能证明，但经
常是对的，想不到这次被他说中了。G题的意思就是将图看成一棵树，然后所有叶子节点都
必须连一条线，使得它在经过根节点的圈上。另外，当一个点有i各子树的话，至少要i-1
条边才能使全部子树连通。实现方法比较特别，首先统计只有1度的点，记为L，然后枚举
所有度不为1的点 i 作为根，该点叶子最多的子树的叶子树为 Ki，子树数目（也就是该点
的度数）为 Si，然后以在（L+1）/2，Ki，Si-1这几个数中选最大的一个作为Ai，最后在
A中最小一个输出就是答案了。
做完三题的时候，欧尘在做A，B没有队AC，估计不行了，张翼做D，我就看E，但
是根本想不到怎么做，F估计没时间看了，看了也没时间做了，H看不懂，于是就以这个状
态一直到比赛结束。得了第六，觉得还可以，只是最后一题出不来依然有点遗憾。
这次比赛有一点很仲要的收获，就是做题之前要规划好，最好在纸上写一下，因
为我的G题就是这样，code好了以后什么都没改过就提交AC了。
下星期还有杭州赛区，一定要吸取经验，争取下次也取得好成绩。
--
※ 来源:．逸仙时空 Yat-sen Channel http://bbs.zsu.edu.cn [FROM: 192.168.48.152]
--
抓緊時間把感情的帳單
好好去認認真真一一的清還
為身邊每個人
不要怠慢
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店