2012 ACM/ICPC Asia Regional Online Warmup总结
本次比赛由我、DTen和sssplk完成，一台机子进行。

本次比赛题目来自芝加哥邀请赛，题目挺全面的，也都有一定难度。这次比赛把我给虐残了，到现在还内伤中。全场比赛只A了两题最简单的题目，分别是1003和1007，一道置换群一道并查集。DTen在最后一个小时开始敲1006线段树到现在似乎还木有过，悲剧啊。sssplk则被一道几何卡住全场动弹不得。三个人都不在状态啊。

前两天的区域赛训练效果还不错，排名都挺靠前的，但难度一提升就萎了，各种卡题。

本场比赛由两个失误，第一个：我开场就开1005，我一看这不是四边形不等式优化dp，然后果断占机时敲，敲完O(n*n*k)大约1亿的计算量而时限是15s，竟然超时，当时就震惊了。然后放弃看其他题，可是后面的时间还是惦记着这道题，想着各种不可能的可能。而sssplk的几何则是从头卡到尾，卡得十分彻底。

还有一个失误：赛后算了一下三个人总共看了7道题，还有3道没看，这是本场比赛的一个失败点。当我敲完03和07也没问队友剩下来的题目的意思，队友正在卡位卡题也没和我讲，然后1002就没看，然后这道简单的斜率优化DP就被忽视了。赛后十来分钟就把它ac了，没个人专职看题目真是亏大啊。

今晚本来想乘郁闷之时怒A剩下来的线段树和hanoi和那道我本场比赛的处子题，但是明天还有浙大月赛，写写睡吧，月赛完再好好总结。

到现在我共A了3道题。现在说下这场比赛的题目（前面数字是题目在Hdu上的题号）：

Hdu 4257 CosmoCraft 没看。

Hdu 4258 Covered Walkway 斜率优化DP。状态转移方程为dp[i] = min(dp[j] + (arr[i]-arr[k+1]) ^ 2+c),dp[i] = dp[k] + arr[k+1]^2 + arr[i]^2 - 2 * arr[i] * arr[k+1],Y = dp[k] + arr[k+1] ^2,X = arr[k+1]，然后套个模版就过了。这一题如果n小那么一点点，用四边形不等式优化也可以过，代码超短的，但是常数大我写了超时。

Hdu 4259 Double Dealing 本场比赛过的第一道题，求置换群的循环周期，用k和(i,j)，（i，j）表示第k个牌分配完是第j个人的第i张牌，然后反复迭代直到出现之前出现的，转移迭代次数就是这个循环的循环次数设为cnti,那么答案就是Lcm(cnti)。

Hdu 4260 The End of The World 没看，但是比赛的时候同校的lasten几十分钟就ac了，目测不难。

Hdu 4261 Estimation 赛后看了某牛的解题报告，用堆来预处理，然后O(n*n*m)的

Hdu 4262 Juggler 线段树。

Hdu 4263 Red/Blue Spanning Tree 并查集+贪心。先构造一颗蓝色边尽量多的生成树，也就是每次找边并的时候遇到蓝色边并且两边不是同一个集合的就并起来，蓝色边数记为mmax，再构造一颗蓝色边尽量少的生成树，处理过程类似于上面，蓝色边数记为mmin。最后判断题目要求的k是否是否在【mmin，mmax】内即可。

Hdu 4264 The Red Gem 计算几何。

Hdu 4265 Science! 不知道是什么题。

Hdu 4266 The Worm in the Apple 三维凸包。

很无语地写了一篇只过三题比赛的总结，看完上面类似结题报告的文字想鄙视的就尽情鄙视的....

部分代码和数据见：http://blog.csdn.net/woshi250hua/article/details/7908148

未完，待续....

本文ZeroClock原创，但可以转载，因为我们是兄弟。

2楼ACM_Ted3小时前

同只过了2题，太弱了T-T

Re: woshi250hua3小时前

回复ACM_Ted:Orz回复的两位，特别是一人5题的大牛

Re: ACM_Ted2小时前

回复woshi250huan求QQ一起学习吧。

Re: woshi250hua2小时前

回复ACM_Ted:你们应该认识吧？

Re: ACM_Ted2小时前

回复woshi250huan嗯。

Re: ACM_cxlove1小时前

回复ACM_Tedn楼主和楼上都是DP王，ORZ

Re: ACM_Ted30分钟前

回复ACM_cxloven求全能王别黑了。YM一人5题的。

Re: ACM_cxlove5分钟前

回复ACM_Tedn我全程酱油，图神昨天DBL，我只能打下手

1楼ACM_cxlove7小时前

ORZ,当时03就卡得不能动

Re: woshi250hua5小时前

回复ACM_cxlove：求加qq...

Re: ACM_cxlove4小时前

回复woshi250huan私信给你了。