10.21上海赛区预选赛小结

由于事先被通知说本校的队伍不能参加本校的比赛,于是这场比赛我就成了看客。

一共8道题:

balls,我没想到可以用二分匹配解,更不知道最小路径覆盖为何物=.=,后来google一下,才知道解法,惭愧惭愧。

communication,有点复杂的立体几何题,实在不高兴自己推了,跳过=.=

even or odd,一看数据规模,就知道要用至多O(n)的解法,然后根据八数码问题的解法,猜想可能和置换群有关,然后就做出来了。不过这题被卡了MLE,我用C和C++多个版本的代码提交,不是WA就是MLE,很郁闷。

firing,线段树,不过题目里li、ri和m的关系很奇妙,看了半天没看懂具体内容,跳过=.=

lazy,简单题,POJ上有类似的题目,从大的开始乘,小的开始除,保证不会除不尽。

msn,先要用线段树计算在线时间,然后贪心求最优解,不过貌似要用最优匹配,但是我用贪心做出来的解和数据一样^_^

travel,完全不知道解法……

walk,镜面反射问题,貌似POJ上也有类似的题,反正我也做不出=.=

总体而言,正常比赛的情况下,做出4题是正常的,比赛结果也是如此,除去相同的学校,做出4题的学校应该能晋级。

不过服务器的问题一直困扰着所有的人……

其实OpenJudge(因为设想要开源,所以把Online改成了Open)的设计理念是很好的,它把数据库、用户界面、判题程序分开,只要数据库不崩溃,其它两部分的问题就可以用机器换性能的方法解决。但是这次时间仓促,比赛用的域名是一周前才刚刚申请到的,而路由的部分是其它部门管理的,所以用多台服务器做用户界面有点困难,而这也就成了所有问题的起因=.=

在网络赛中最重要的是减少每个用户的流量,一个用户少用了流量,就可以把这部分流量分配给其它用户。于是便想到了Ajax,只需要下载一些关键数据就可以完成客户端的刷新。不过貌似gwt编译出来的文件,有比较大的性能问题。比赛刚开始的时候,服务器完全失去响应,当然这也是Ajax的弊端,用户需要先下载至少50K的数据,才能打开初始页面。而服务器端的Java程序,不知道是什么问题,不能应付大量的数据库查询,而当时数据库里几乎还没有数据,令人费解。而且那个Ajax程序的统计也有问题,在Statistics页面里,C/C++/Java的提交数量之和>Total的数量,很神奇的现象=.=

比赛就在一片骂声之中过了2个多小时,这时候Larva小组奇迹般地用php重写了用户界面,一下子扭转了局面。最初是Status,后来又补上了Ranklist和Submit,php的性能比Java高出不少,从此Ajax就被冷落了。我也就是在这时候开始交C,反反复复的MLE和WA,无语=.=然后几个牛校就开始争相爬头,最后有5个学校完成所有题目,令人仰慕……

虽然一开始出了一些问题,但是Larva的反应速度还是可圈可点的,逃脱了和THU相提并论的下场=.=……

接下去就要看西安那边的状况了,大家拭目以待吧……


发表评论

电子邮件地址不会被公开。 必填项已用*标注