算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
额,前天比了一年一度的东北四省赛。地点是鞍山的辽宁科技大学。 

星期六早到了辽宁科技大学,在安排的寝室里睡了一个上午,中午吃饭之后就去参加开幕式了,表示各种催眠,不过通化师范学院的老师还是很喜感的哈哈。。。
下午参加热身赛,比较新奇的就是XP系统加一个不好用的Netbeans。。。 于是熟悉了一下code::blocks,做了做题目,乱测了一堆东西,就去和志愿者聊天了 - -
期间还被采访了一次,压力山大。。。。
晚上在校园里散步了一个多点,然后回寝室三国杀。。。
第二天正式赛,比赛过程极其纠结。。。
上来小毛从后往前读题,磊哥从前往后读题。小毛瞬间确定了I题是水题,题目描述是求四边形面积,于是小毛上去拍了个模板WA掉。。。
我在登陆完账号以后也加入了读题行列,小毛好像看到了某题是磊哥可以做的,于是让磊哥去读K题去了。
于是我开始了从前往后的读题历程: 
A题,求1000个长度为1000的串的最大字典序的公共子串,后缀数组求LCP?,貌似不会。。。
B题,给两个数m,n,求所有满足m mod k + n mod k >= k的k的欧拉函数之和,想了想,没思路,跳过。。。
C题,题目描述又逆天了。。。又是***翻译的? Orz。。。读不懂
然后小毛继续提交I,继续WA,我不淡定了 - - 
迅速翻题册, 终于找到了一道水题H,这时候我们的提交突然反常了,返回结果是"Interval Server Error"? 我叫志愿者把裁判找来,那个SB盯了那个返回结果足足半分钟自言自语了一句“服务器错误”然后才去找裁判。。。 真尼玛服了
裁判来了之后问题解决。 毛哥果不其然继续WA。。。 于是打印出来,换我敲完H题,1Y。
毛哥发现木有给四边形的端点极角排序就拍模板了,改过之后4Y。
磊哥发现K题的样例有问题,我上去提问无果,于是我去大号了。。。当时厕所只能进1人,我还在外面等了好久。
回来看D题,发现其水题本质,其实就是用高精模拟一个四舍五入,于是上去敲完,提交发现restricted function,原来没有删freopen。。。 再交2Y
这是已经一个小时了 - -,我们队三题排在第18,预感要悲剧 - - 。。 发现F题过的较多,于是去看F,磊哥上来写J题。
发现F题是水模拟,于是换下磊哥敲F,1Y。
在磊哥换下我之前,磊哥给我讲了G题的做法。G题的模型其实就是在一个已部分染色的矩阵上选择最大未染色的子矩阵。
于是磊哥继续写J,我在思考G的一些细节。磊哥交J,WA。于是换我上G,敲好之后提交WA,发现一处NC错误,再交还是WA。我不淡定了。
这时发现J和K的题面都改了,于是让磊哥上去敲K。
K题就是问从某点出发走K步后,最终可以到达哪些点。其实就是矩阵乘法就可以做,于是小毛去找J的bug,我去看G的代码。
这时候比赛大概进行了一半了,第一大概有6,7道了,我也没关心自己队伍的排名,不想自乱阵脚。
磊哥敲完之后提交,TLE。我指出磊哥几处可以优化的地方,再交WA。
于是我和磊哥互相找错,毛哥上去暴力J题。
磊哥一下子就指出我代码的Bug了,我上去改了几行之后,G题3Y。
这时大概3h左右吧,我们终于有5题了,但是一刷榜立刻傻了,大部分队伍都6题了,包括我们的大一队。。。 发现B题和C题过的人最多
于是我和小毛去看B和C,磊哥再反复改K,终于在发食物的时候6Y了。。。
小毛看题无果,继续敲J,提交发现暴力也WA - -
这时我和磊哥决定去找B题的规律,于是我果断换下小毛,去打表,发现虽然k是没有规律的,但是k的欧拉函数和的结果居然是m*n。。。
于是B题1Y,刷榜发现已经到第五了,但是是7题里面最后一名 - -  不久之后封榜了。。。
我发现我们几乎是6题和6题往上唯一一个没有做C题的 - - 但是我实在是读不懂题啊 。。。 但是磊哥居然一下子就读懂了,大家决定一起攻C
C题的意思就是给一个图,每个节点有一个权值,这些权值要保证总数不变的情况下,可以自由的通过边来转移。请问在最优的转移方案下,权值最大的节点是多少。
很多条件都是我们YY的额 - -
做法就是先缩点(不缩点时间复杂度会达到O(V^3)...,缩点之后的复杂度我木有证明,如果边很多的话拓扑序高的点就会很少。。。),建反图,然后枚举拓扑序最高的点,对这些点搜索。
我一看卧槽这不是我最擅长的图论么 - - 于是20分钟调试完提交 WA。。。 发现了一个return的小错误
(如果用vim的话,我可以同时看更多代码,这个错误肯定可以避免的额。。。)
改过之后,过了队友给设计的所有数据,提交之后2Y。还剩25分钟,全部给磊哥改J题了 - - 。。。 无果, 比赛结束
最后还是掉到第七了,工大的两支队伍也后程发力,凭借罚时的优势超过了我们,和我预期的结果大抵相同。。。 没办法 这就是实力的差距吧 - - 

后记

对于比赛结果没什么可说的,我们队唯一的亮点就是最后两小时A四道吧。。。 今晚怎么也睡不着,于是爬起来把这篇总结写了。
首先赞大一的小孩,首次出征就是2等,尤其赞lenohoo。。。 这学期天天熬夜刷题 。。。
其实HEU除了10年regional拿了一金两银光荣进final亮了一把以外,其他的年份里真的和“强校”不沾什么边,尤其是现在。
也恰恰是yizer的队伍鼓励了我们,给了我们新的目标,也让我压力山大 - - 。。。。
去年的夏天,HEU集训队就像一盘散沙。。。 也直接导致了Dream_Of_Miracle以一铜一铁收尾。
当时的心情差到了极点,不仅仅是成绩不好,也是深深的为自己曾经的不努力和不作为而懊恼。
去年5月开始刷tc和cf,尤其是上学期,整整一个学期,只因为去现场赛缺了一场tc和一场cf。
那时候每次包宿都是自己一个人,真是突出一个爽(现在tc和cf都只差一点就黄了)。。。 不过这学期大一大二的新队员们也加入了包宿大军,让我挺高欣的。
让我最自豪的一点就是: 这次东北赛除了Dream_Of_Miracle和Lupus,其他所有队员(除了某酱油)都只有短短半年的集训时间!狂赞!!!
而且只有一个队悲催了没拿奖 - - 
不过因为Lupus的低迷,看来今年我还是不能安心退役的,好想爽爽快快再来一年!
posted on 2012-06-12 02:16 西月弦 阅读(681) 评论(4)  编辑 收藏 引用 所属分类: 比赛感言

FeedBack:
# re: 2012 东北四省赛小结
2012-06-12 20:28 | 李聪
豪哥是用来膜拜的……昨晚又去刷夜了,东北赛做出来的也是我们六个题中最难的C题,膜拜至寒假之前,必须的,真真的  回复  更多评论
  
# re: 2012 东北四省赛小结
2012-06-13 09:49 | 西月弦
@李聪
Orz lenohoo!!!!  回复  更多评论
  
# re: 2012 东北四省赛小结
2012-09-11 03:58 | zzx
#include<stdio.h>
int main(){
long long m,n;
while(~scanf("%lld%lld",&n,&m))
printf("%lld\n",m*n);
}
WA了 被鄙视
老钟神过C题后 直接cin cout 过了  回复  更多评论
  
# re: 2012 东北四省赛小结
2012-09-11 10:48 | 西月弦
@zzx
%lld 神级脑惨行为不解释,自己去看《CS:APP》去  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理