标签存档：acm比赛

这次我们比较水。。。

我们队一共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

这次时间只有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

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

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的话没法出。

【比赛经历】

这次月赛比较纠结，我大概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！

今天被虐了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)