查看文章 |
09ACM/ICPC上海邀请赛总结
2009-05-31 21:37
到上海参加比赛真是很happy的一次经历。承办方DHU的环境不错，建筑也很cool。住的维也纳国际酒店服务也很赞，比去年成都赛区的那个同是四星的不知好多少。 29日到达早上到达上海，摸索着到达学校和宾馆已经快10点了。旅途很累，由于在郊区，附近也没有什么很值得逛的，中午吃饭后我们就睡觉顺便看了一下资料。晚上走到松江大学城的小吃街吃了一顿，还不错:)也算是逛了一下。 30日早上10点热身赛，11点热身赛结束，12点到17点正式比赛，时间比较紧凑。赛完我们就闪离学校了。晚上又zs的几个交大和财大的同学带领体验了一下上海菜，又夜游了一下交大，最后还送我们到火车站，实在是感谢不尽啊。 今天就回到学校啦~~~ 接下来说说比赛吧:D 上海邀请赛来的队伍主要是上海，福建和浙江的队伍，其他地方来的就不是很多了。总共104支队伍，其中上海交大来了5支，复旦5支，同济大学6支。我们Hust来了两支队伍，CFOP和RushTime。命题组长是复旦的杨溢。结果排名在（http://acm.dhu.edu.cn/dhuoj/rank/contest12.html） 上午的热身赛时间不多，就测了一下机器，java，还试了一下clock()，不过交的时候出现一些诡异的问题。 下午的题目小分析一下： A题求一个有向图去掉一些边后有根树的总数，总共8个点，wsl枚举一个点的父亲是哪个，8^8的复杂度，AC B题是最水的一个题，确定是半圆就行了，略。 C题是一个计算几何题，放置一个给定三角形和圆，使相交的面积最大，这个题没有好的想法，到最后也没人交过。 D题是一个概率题，这个题卡了我们不少时间，当时过了4个题，排名靠前，但是好多队过了的D题我们没过，我和wsl都在一起想这个题，却没有好的想法，我们试了一些简单猜想（全修，全不修）但是都返回的Wrong Answer。后来wsl试了枚举中间点分别用不同的策略，又WA了一次后过了，这题过了，士气振了不少，赞wsl。 E题是求所有化简后不同的式子有多少种，感觉很复杂，没有好的想法，场外同步赛有人过了，现在还不知道解法。 F题是分解2^n-1，找到了很多小规律，是到最后快结束时才在讨论中Isun发现了一个关键规律（还不能证明），已经没有时间写了，而且我们的想法实现要用多项式除法，会比较麻烦。场内最后上交的排第一的队伍过了。 G题是一个枚举加模拟的题，就是常见的一个游戏“对对碰”，关键是要想清楚细节，我写的，很早就开始写了，过的也算早吧，就是麻烦和细节，没有太多技术含量。 H题我没有看，但是听他们说相当于在线段树的基础上变化一个操作，这个题感觉有难度后，就没有仔细考虑了，最后也没有人过。 I题是求一定范围内的每个数可表示成幂的指数和。方法是先求出1~n中的值，由i^k <= n，n <= 10^18，有k <= 59，那么就可以求出对每一个k底数i的种数。但是一个数能表示成某个数的50次方，那么也就可以表示成一个数的25次方，5次方...一个指数和其约数作指数时在统计时是重复的。那么从大到小处理时依次减去就行了，例如算指数50时，就将1，2，5，25，10对应的数量减去此时50对应的个数就行了。本题由Isun一次AC，赞~ J题也是Isun较早时间一次写过，求的是一个钟三根针重心随时间变化的轨迹长度。模拟的方法。 本次比赛最终结果如前面给的链接，我们最终rank3排在两个交大的队伍之后。应该说结果对我们CFOP队来说是至今最好的成绩吧。 |
最近读者：