HDU月赛——2010.4.4

这次我们比较水。。。

我们队一共A了3题。

A:http://hi.baidu.com/edwardmj/blog/item/9e475eec782c01252df53431.html

C:http://hi.baidu.com/edwardmj/blog/item/370c5fc87d889c8ac9176806.html

F:http://hi.baidu.com/edwardmj/blog/item/6ae33d344481423d0a55a901.html

这次没啥好说的。。。我把这3题AC了以后,我们队就没有再出题。。。

其实那个三国杀可以搞一下,但是CZM搞了将近3个小时。。。没有AC。

然后记录一下YY其它题的经历。

D:题的话第一反应是后缀数组,但是N太大了,可能令人垂涎的3xian大神的模板可以过吧。。。

然后pass掉这个想法以后,就YY一下类似自动机那种。

由于只含小写字母,字典序最小的话,每次从’a’开始尝试加入字母。然后判定这个小串是否在主串中出现。

然后加到小串长度为N的时候就结束。然后次数的话,就KMP一次就可以知道了。实现这个算法的前提是:能在O(1)或者平摊O(1)的时间复杂度内判定一个串是否在主串中出现。

很遗憾,我做不到。。。于是挂掉。。。

E:就是要将图旋转45°,然后并差集或者说BFS填连通块应该都可以。但是那个旋转不会搞= =。。。

G:几乎可以肯定是插头DP了。。。但是转移爆难。。。无人AC。

H:我没看过题。。。CZM一直在搞,没搞出来。。。

哎,比较餐具。果然我们太弱了。

rank:18

http://acm.hdu.edu.cn/vip/contest_ranklist.php?cid=276&page=1

ZOJ八周年纪念赛——2010.3.14

这次时间只有3个小时8分钟,比较蛋疼。。。

而且题目相对简单,所以,拼得是速度!!!

一开始我搞A题,搞很久,不断地TLE,无语了。。。

由于我程序的常数通常是常人的1.5倍,所以我让秒杀了F题正在浏览题目的CZM来做。

但是他也TLE,然后他就YY一下,加了点WS的预处理优化,AC了。。。

FHN也作出了G题。

然后我看向D题,自己YY一下,发现是费用流,于是写出来,终于1A。

我们围观B题,CZM说想到了,于是让他去做。

我再看E题,我晕,这个简单题够漏掉了,直接用双向链表模拟+个hash或者tire或者平衡树什么的定位就好了。

然后时间不够。好在CZM把B题做出来了。

最后,膜拜CZM,不愧是Pascal优化大师啊。。。

rank:27

http://acm.zju.edu.cn/onlinejudge/showContestRankList.do?contestId=306

话说rank4的好像是GDKOI自称路人乙的那位牛X人士= =

居然XT一队了。。。YM

HDU月赛——2010.3.6

这次月赛终于不是一个人单挑了。

CWJ&&FHN&&CZM组成了一队。

然后说说比赛经历:

一开始12点开始,FHN和CZM都没在。。。于是我开了第一题。

写了一会儿,好像很繁琐,然后FHN和CZM陆续回来了。

然后FHN一下就把最后一题秒了,YM。。。

然后我碌碌无为,第一题没搞定,跳过。

看第2题,一看出题人,AekdyCoin,是师傅那题防AK的题目,于是再次跳过。

第三题,看着是个最大独立集问题。但是好像是任意图的。百度一下,发现MS是NP问题?跳过。。

然后CZM大概浏览了题目,告诉我第四题是字符串,让我去做。于是我一看,KMP,1A。

然后CZM和FHN看后面的题目,发现都挺神,于是他们把目光聚焦在那题比较多人AC的题目上,然后CZM一个犀利的背包把它搞定了。

然后FHN出去买电脑

剩下我和CZM,然后我表示第一题突然有了想法,线段树,因为long long WA了两次,终于AC。期间肥闽各种看题目,不过MS没什么结果。

然后我回看第三题,推了一些性质,然后交了个贪心,WA。。。CZM犀利地给了我一个反例。。。

最后我推出一个重要性质:

∵出题人戴牛

∴必然可以网络流

于是尝试了各种二分图构图,终于WA了2次以后AC。

然后FHN回来了,和CZM一起在那里猜数字。。。

我去搞1009,发现应该是在AC自动机上的DP。但是空间好像卡着卡着。。。

纠结到剩下半小时,放弃,和他们一起猜数字。。。

然后得到的结论:

1、没有billion,million….and so on…

2、字符串长度14

然后我说:直接枚举吧,大不了(26+10+1)*14。。。

然后CZM就先去搞那个字符集,为我们枚举作为前提,后来很可惜,没有搞完,结束了。

一共就出了5题。。。。

其实和第一名的差距就是1009——AC自动机上的DP 以及 1005——猜数字。

猜数字其实想通了不难,但是一开始没有意识到是单case。。。

RANK:18

围观地址:http://acm.hdu.edu.cn/vip/contest_ranklist.php?cid=237&page=1

这次的猜数字,绝对NB,赞一个,不过在OI的话没法出。

ZOJ月赛——2010.2.21

【比赛经历】

这次月赛比较纠结,我大概1点半才开始做

然后一开始见到I题好多人A啊,然后就做I题去了,WA个不停。。。

最后发现,理解错了题目了,ORZ。。。于是重敲以后一交,AC。

无无聊聊的看了一下C题,不会做~

然后出来一看,F题AC人数暴增!

直接切进去,OH YEAH,原来是个排序+贪心,好像差不多10行的样子写完,交上去AC了。

回头看B题,AC人数也挺多的,再次切进去,然后看不懂continuous subsequence的意思。

金山词霸显示:n. 后继,随后

囧,到群里问了下,被痛斥了一下。。。终于知道连续子序列的意思。

然后仔细一思考,我只要搞到它满足所有的min,然后判断有没有超过max的即可。

所以如果只是想搞到他满足所有的min的话,用首尾指针维护即可。

一交,1A。

然后又去看了比较多人A的E题。哇。。。GDKOI出过这题的类似加强版!

于是就开敲,发现数据规模非常小,不需要用GDOI那种N^2的方法,直接DFS就行。

一交,居然WA了。。。检查了半天,发现是题目要求输出所有方案,而不是一个方案。。。囧。

改了以后终于AC。

然后剩下的时间已经不够8分钟了。索性不做,围观其他神牛。。。

最后rank:28

很大程度是因为睡懒觉。。。否则时间应该前移很多,5题也是有可能的。

rank围观地址:http://acm.zju.edu.cn/onlinejudge/showContestRankList.do?contestId=305

额,感叹一下,漆子超太无敌了。。。他还是单挑的。。。

表示对各路神牛的YM!

HDU月赛

今天被虐了5个小时。一整天就做了两道题。果然,ACM和OI差别还是非常大的。。。

一开始看到前两题,数学,直接放弃。然后看到第3题,感觉很简单,因为之前做过一个类似的,而且比这个还要难,算是加强版,所以1A秒杀。然后切出去看problem list。发现最后一题最多人AC,就去做最后一题。做了才发现代码量非常大,接近两百行,如果有模板,应该是水得。。。不过很可惜,我不是职业acmer,没有模板,所以。。。敲了N久,调试了大概1.5个小时,1A!

然后回看第2题,用等比数列求和公式把数列的通项先推出来,然后发现实际上是求x^n mod a0=1所对应的最小的n值,然后与肥闽讨论了N久,决定暴力。然后TLE,MLE。。。换了3种hash,全部挂掉了。。。于是,再次果断放弃。

然后最后看到第4题也比较多人A,然后就去做,写了个200+行的A*,还没调出样例,比赛结束了= =

虽然比较悲剧,但是也居然排到了13名。。。

最后发现一点,数学差得太远了,差得更远的是英语。。。

另外,YM DIY群的AC大牛和UranusX大牛。。。就是第一和第四那两只。。

Rank Team Solved Penalty 1001 1002 1003 1004 1005 1006 1007 1008 1009 1 AC&&ZT&&LCC 5 11:22:00 02:27:04
(-2) 01:43:33
(-3) 01:34:23 02:46:20 (-20) 01:10:40 2 yaya&zgmf_x20a&Arios 5 18:26:30 01:15:05 02:32:55
(-1) 03:30:25
(-4) 04:50:37
(-1) 03:57:28
(-1) 3 万物皆数 4 12:58:12 02:03:22 02:27:23
(-4) 04:12:18 02:55:09 4 UranusX 4 13:21:39 03:15:44
(-4) 00:57:45
(-1) 04:42:43 01:45:27
(-3) 5 whu_高云翔 4 13:30:39 03:06:27
(-2) 04:04:39
(-2) (-3) 03:08:40
(-1) 01:30:53 6 囧の軌跡 3 07:22:08 03:20:25
(-1) 01:33:08 02:08:35 7 z__jj 3 07:35:38 (-1) 04:35:08
(-2) 00:57:31 (-9) 01:22:59 8 majiaNO.1 3 08:50:19 03:28:09
(-4) 01:29:53 (-5) 02:12:17
(-1) 9 zsasuke 3 10:58:14 01:02:45
(-5) 04:25:05
(-2) (-2) 02:30:24
(-2) 10 ggcc11 3 10:59:01 03:19:09
(-3) 02:37:14 04:02:38 11 NewHorizon 3 11:41:02 03:04:23 04:05:31 (-1) 04:31:08 12 gtzygtzy 3 12:15:16 04:32:14
(-1) 03:41:52 03:41:10 13 cwj 2 03:31:25 (-5) 01:14:43 02:16:42 14 wccn 2 04:40:00 01:20:16
(-1) (-3) 01:59:44
(-3) 15 SHNU_FireStar 2 04:53:01 (-1) 02:09:08
(-1) (-1) 02:23:53 16 喔拉拉 2 05:08:49 (-11) 01:17:14
(-2) 03:11:35 17 依然紫轩 2 05:13:37 01:35:25 03:38:12 (-3) 18 seabao 2 05:29:00 03:35:46 01:33:14
(-1) 19 visitor00 2 05:31:44 (-8) 02:07:52 03:03:52
(-1) 20 Rexer 2 05:38:03 04:33:54 (-2) 00:44:09
(-1) 21 starvae 2 05:42:57 04:06:38 (-1) 01:36:19 22 WHU_123 2 06:16:57 02:03:51
(-1) 03:33:06
(-1) 23 foreverlin 2 06:47:24 (-7) 03:18:22
(-1) (-3) 02:49:02
(-1) 24 majia 2 07:02:44 03:38:15
(-2) (-4) 02:44:29 25 山寨队 2 07:30:31 (-2) 03:52:24 02:58:07
(-2) 26 ReDow 2 07:59:30 (-5) 03:03:34
(-1) (-5) 03:55:56
(-2) 27 kaka8 2 08:05:20 (-3) 04:49:39
(-1) 02:55:41 28 xxjx 2 08:34:33 03:03:48
(-2) (-4) (-1) 04:30:45
(-1) 29 UESTC-Arbiter 2 09:36:12 (-6) 04:02:13
(-3) 02:33:59
(-6) 30 yrjie 2 12:01:28 (-5) 04:52:28
(-12) 02:29:00
(-2) 31 rectaflex 2 12:23:55 (-2) 04:04:43
(-15) 02:19:12
(-3) 32 RaceBug 1 01:08:35 (-5) 01:08:35 33 luther 1 01:39:32 (-5) 01:19:32
(-1) 34 autumncat 1 01:49:49 (-3) 01:09:49
(-2) 35 PlayerII 1 02:08:41 02:08:41 (-4) 36 whu_fatboy 1 02:09:08 (-2) (-5) 02:09:08 37 zjshark 1 02:23:00 02:23:00 38 PrimeMusic 1 02:29:17 (-3) 02:29:17 39 tao 1 02:46:12 (-2) 02:06:12
(-2) 40 open 1 02:57:15 02:37:15
(-1) 41 qu317058542 1 03:13:38 01:33:38
(-5) 42 UESTC_09P27 1 03:26:50 03:06:50
(-1) 43 chenlie 1 03:28:35 (-1) 03:28:35 44 Jsky 1 03:31:10 03:31:10 45 kimhmguen 1 03:32:12 03:32:12 46 surffor 1 03:41:03 (-2) 03:41:03 47 弯弯陈 1 03:44:44 03:24:44
(-1) 48 cowmick 1 03:46:18 (-1) 03:06:18
(-2) 49 yudaer 1 03:55:46 (-9) 03:35:46
(-1) 50 skddj 1 04:03:49 03:43:49
(-1)