acm总结帖_By AekdyCoin

acm总结帖_By AekdyCoin 各路大牛都在中国大陆的5个赛区结束以后纷纷发出了退役帖，总结帖，或功德圆满，或死不瞑目，而这或许又会造就明年的各种“炸尸”风波。为了考虑在发退役贴以后明年我也成为“僵尸”的可能性，于是改名曰“总结贴”，不提比赛细节，不提比赛流水账，权当是大学本科生涯中acm生活的点滴记录…… (1)入门篇甲 PS:以下内容为 Ctrl+a,c,v的产物 ========================================================================================================== 一张宿舍楼下墙上的通知吸引了我的注意力...是福州大学第五届程序设计大赛的 报名通知...那时我还完全不知道这比赛什么内容就傻傻的报了上去,只以为是考程序的函数的使用和调试.可是没想到没有我使用的语 言....vb/delphi,delphi和pascal差别太多了,那时我发现比赛居然可以用C语言,于是打开从来没打开过的C语言书开始了学 习... 学习的过程十分艰苦,对于上学期上课都没听的我来说,对于以前是面向对象编程的我来说这简直是恶梦. 哎好不容易把书啃完了来做题还是无止境的WAWAWA那时候最希望看到的就是:Accepted 我又找到了大一学VB时的感觉,于是在同学们的奇怪和不解中我开始做题. (其他同学还没开网号..所以上电脑的人比较少,我不玩游戏就十分惹眼..) 一个非计算机专业的人整天在电脑前面,他们都怀疑我是否报错了专业.. 在做题没几天以后认识了张大牛...感谢他在我入门阶段引导了我... 还认识了yayamao,让我知道了大一牛人也很多... 自卑感油然而生 那时面对那么多别人看来是"水题"的题,我只能无奈的一次次WA,顽强的WA着.... 面对小学就省赛冠军的人,我只能算是在人老珠黄的时候的无畏挣扎.. 很多次想放弃,还是张大牛安慰了,给了我信心... 最后总算买了自己的第一本算法书(好贵...) 突然发现一大堆看不懂... 这个时候又是张大牛给了我引导. 学习要慢慢来 看来他说的是有道理,baidu看了下他,牛牛事迹无数...orz...... 在yayamao的打击下我开始去水题了...其实我自己做的题还不到100.. 和yayamao的差距还是很大啊 orz...again... 最后还是把报名取消了,因为我完全不会算法. 我不相信后来者无法居上,我不相信god不会给努力的人一次小小的机会.我相信自己.........能达到yayamao 1%(开玩笑的-_-) 感觉这1个月来收获不少,懂的了一点点点点点点的毛(还没到皮呢...) but i insist on that everything will be better after hard work. 我想我努力以后就没遗憾了,虽然和牛人的差距是很大的,可是希望常在,未来是未知的,我十分相信这一点... 我,一个菜到不能再菜的鸟,在仰视前辈们的丰功伟绩后顿然觉的动力十足,在前辈们的努力下一个个成绩被书写了... 前辈们很努力,我想我会更努力.90包泡面是可以尝试的(VB就这儿过来的...) 说不下去了.. 大家祝福我这菜鸟 我也希望这个帖成为我自己的一个起点 以后来回味 最后感谢张大牛 顺便 orz.......yayamao ========================================================================================================== (2) 入门篇乙 09年寒假认识了sha崽 当时他似乎刚入HDU的校队么，似乎刷了几乎600题。(PS. 当时我似乎做了 60题) 一问他居然是08的，我的神啊，简直太神了。 寒假的时候HDU实际上是有许多次内部DIY比赛的(内部比赛),不过由于各种邪恶的原因我似乎也参与了一下，其实每次都是被屠的么…… 期间看到sha崽的实力还是很不错的. (3) 入门篇丙 回忆当初正是这个比赛使我知道了ACM 并最后使我接触了ACM，感慨时间过的好快哇.. 今天早早来到机房，发现黑丫丫的一片人-.- 问了一下才知道那是看座位号的~很神奇的与vge,yayamao同机房.... 比赛开始前适应了一下系统，发现居然要使用__int64...平常FOJ都是long long的说.....yx啊 总的来说题目难度还好，就是现场的气氛导致自己比较紧张，很久才出第一题，自己bs自己下.. 最后一题在ZOJ做过的，比赛的时候AC的题居然没想法。。。 A.众数问题 给定一个数的集合，求其中出现次数最多的数，如果存在多种答案，那么输出小的 数据规模是: 元素个数<=100 元素在[-100,100] 这题瞬间被无数大牛秒杀。。 可以直接Hash或暴力统计也可以，数据规模太小拉 MS题，可以说是这次比赛中最简单的题 做的慢被鄙视了-_-!! B.括号表达式 说给出一个字符串，就只有'(',')' 如果它本来就已经匹配好了，那就直接输出 否则输出那些没匹配好的，并把它匹配好之后的输出 ))(()) ans: ))(( //这些不能匹配 (())(()) //输出上面的匹配后的串  简单的栈的应用 怎么判断是否完全匹配这里就不介绍了 下面就介绍下如何匹配那些所谓的“无法匹配的字串” 拿上面的例子来说吧 这种串必然是 a.只有'(' b.只有')' c.分为2部分，前面一部分是')',后面是'(' 只有满足这3个条件，才不匹配 所以就很简单，简单的统计')'的个数，然后在输入这些')'前先输出对应个数的'(' 再统计'('的个数，在输出这些后，再输出同数目的')' C.等式数量 给定一个集合(大小最多5000），里面所有的数字都不相同，希望找到不相同的三个数a,b,c,满足a+b=c 并需要求满足条件的对数 For Instance 3 1 2 5 显然有1+2=3,2+3=5,so ans is 2 由于数字都是独特的，我用了Hash表来解决，既: 枚举a,b用常数时间来查询a+b是否存在，如果存在，是否等于a,b中的一个，如果不等，那么就可以算一种了 时间复杂度大约是O(N^2) D.二进制位数 给定一个数(N<=10^1000)，求不大于他的拥有最多1的M，并要M的2进制位数和N一样如果存在很多M，那就输出小的 首先先来看小数据 12->1100 那么显然11就是解，因为11->1011 那么考虑一下应该怎么处理？ 很明显吧，既把数转化为2进制以后，从最高位开始，找第一个'1'(最高位不算),把它变为0，为什么？因为这样以后保证变化后的数小于原数，然后把该位置后面的全变为1 于是得到了一个解M' BUT，还要和原来的N比较 Why? 15->1111 按照上面的规则得到的是1011 显然答案应该是15才对，4个'1' 所以比较一下既可 本题最最最最最(省略无数个"最")恶心的既是高精的实现，用到了除，求mod,加，乘... 敲的很吐血...用java交好象出啥问题，很�，这题浪费了大量的时间，导致悲剧 E.简单BFS F.没看,据说是简单不过很恶心的模拟题...还好没看:( G.奇怪的数组 计算[0..LCM(Asize,Bsize)-1]内的和,然后用等比数列求和公式计算(等比的关键就是幂上的i/Bsize) 注意用公式求的时候利用(A/B)%C=(A%(B*C))/B来做.. H.最大树高 这题是这次比赛最失败的地方，ZOJ的比赛做过，而且还是在比赛的时候过的，现在居然傻了。。 哎~ 直接枚举度数为1的点既可 最后节点编号取个min,深度取个max既可 (上面这个算法在某些情况下会TLE...继续想ing...) 下面是WZC神牛的算法 随便选个点，找从它出发的最长路，再从找到的那个端点来一次，就可以了。可以证明这是对的。 尴尬死了这题,*&%&^%^&(ignore 2^inf) 总的来说会比前几次的现场做题好许多，至少没那么紧张了.好正式的比赛~还发了题目本子,great,其间还看到了WS的LL...最后470分尴尬收场，也不知道是第几，等待最后的结果咯~ 接触ACM快1周年了，想想当初自己什么都不会，正是校赛使我接触了ACM，在这里谢谢一开始热心帮助我的daxia,vge,yayamao等...谢谢你们在我不厌其烦的追问下为我解答那些现在看起来很傻很天真的问题，谢谢你们：）A:-100<n<100 Hash计数 B:弄个栈,配对结束后如果栈空,输出原字符串,否则输出栈的内容,如果栈中有')',左边补'(',如果栈中有'(',右边补')'.输出即可. C:排序,枚举c,a取数组头,b取数组尾,两头缩进求出所有的a+b=c; D;高精度,转成2进制,从高位起找到第2个1,如果这个1后面没有0输出原来的数,否则把这个1变成0,后面全变成1,在转成10进制输出. E:简单BFS+简单DP... F:如果看不懂题目建议找个贪吃蛇游戏玩玩,写了这个题,你大概就可以自己开发个贪吃蛇游戏了... G:暂时还没做... H:拿原点来BFS求出最深的深度且编号最小的节点,在拿这个节点BFS出正确答案 (4) 入门篇丁 太疼了，闲的没事干和sha崽在hdu挂了个比赛 HDU第一届“老菜鸟杯”编程公开赛，可以说是我第一次出题吧…… 菜鸟长大了?D?DHDU第一届“老菜鸟杯”编程公开赛 这…… 第一次出题显然是比较�的么，各种形如数据规模不符合数据之类的错误层出不穷.导致这次比赛使不少人郁闷了 (5) 入门篇戊 fjnu校赛，入校队前的第一次现场组队赛 -_-原来的目的只是为了熟悉一下组队模式 下面非常简单的说说今天比赛过程 显然今天缺点暴露无疑，由于一开始还没有找到组队的状态，导致前1小时一题都没出.... 直到我在10:13:441Y了C才拿到第一个橙色气球 当然这个时候我旁边的很多队居然有过3题的了-_- yming... 随便如此不过还是没什么压力-_-毕竟来不是为了啥，就是为了体验一下气氛~ G我推出公式，提交1Y拿到黄色气球，当时已经有无数的队过了此题.... A，小波和我讨论以后，使用O(n^4)的算法1Y，得到了粉红气球:),其实完全可以O(n^3) 可是这时某队居然4个题了-_-...没过多久居然5题...继续yming.. PH写的B莫名其妙的WA了好几次.. 最后很神奇的水过，得到了蓝色的气球 12:47:05,F,Nim+求SG,1Y水过,得到了全场第一个紫色气球 最后仰慕一下xiaobo,调试几次以后AC了H,拿到了别人已经拿到很久的绿色气球 最后6题收场，我3，xiaobo 2,PH 1 第一次组队暴露出来的问题要当成经验-_- 同时ym某队，在最后2分钟水过F,直接登顶 PS.fjnu的志愿者很热情~感谢他们:) PS: 当时队友 xiaobo(zwb), chijing (ph) 其中第一头已经成功保到中科院，第二头目前似乎阿里了 (我目前三无中？……T_T) (5) 入门篇己 2次区域赛 又是一年退役时，昔日曾经请教过问题的无数大牛在今年区域赛以后就正式退役了，伤感一下... 10月29日 出发 买了一群零食带到火车上，突然发现火车的卧铺和YY中的完全不一样,那么小的地方我真不知道我是怎么挤进去的，去的时候还很热，晚上还被热醒了好几次,带去的东西几乎没怎么吃，头晕了一整天.于是睡觉完以后再聊天几小时以后就到了武昌,感谢大HH和刘阳的短信~ 10月31号 开幕式 whu的志愿者果然是MM少数，于是现在突然想起来某志愿者男出现在开幕式，闭幕词，现场...为什么一个人能被我看到那么多次-_- 好的，于是热身的题目果然是老题,显然只过了一个比较简单的题，至于B则是YY以后数次WA，C是完全没去看的说(Hash 没用武之地了~，严重仰慕小HH 勇猛通过C) 11月1日，好的这个日期确实很勇猛. 开场没多久突然看到了粉红色的气球，于是我马上去看C，可是突然发现题目的描述比较飘逸，看了好久没理解意思，后来队友在我还没看懂题目的时候就过了...于是接下来我们就去看一个比较简单的模拟题和G，模拟题很顺利的1Y，而G则由于题目看错，导致了一次WA。 下面就是B，由于队友YY出了一个相当orz的构造方案，于是用拓普排完恶搞2Y(第1次RE是细节问题),接下来的就是H，H我一看就发觉是DP，可是显然我是写不出来的，于是队长YY以后2Y，此时我们排名第10。。。我看到了金的希望... 发现E还是可以搞的，于是开始了杯具，到最后依然是没通过E。在郁闷中结束了我今年的ACM比赛 宁波和武汉的2次比赛2个银，其中有惊喜也有无奈.无论结果如何，这对我这新人来说都是一个很好的锻炼....于是接下来的目标就很明确了，多增加编码能力，再学点新的东西.自己还很菜，不过如果我什么都不做还是只能这么菜，可是我做了结果虽然可能是我依然很菜，可是我至少不会后悔bless2位队友，合作还是十分愉快的，曾记的暑假30多顿的饭，ACM真好玩. re.于是复习去了,先把欠的课补完. 明年期待AekdyCoin的表现咯~ (5) 入门篇庚 2010年的2次区域赛，简要总结为： 同志仍需努力~ 第一次哈尔滨的铜十分符合杯具的风格，至于第二次杭州赛区则是我的一坨屎坏了一锅好粥(T_T) 于是09，10算来，我似乎去了4次区域赛+2次邀请赛 似乎结果是3:2:1,这…… (6) 入门篇甲乙丙丁戊己庚辛 第一次接触OI: 路过任青OJ,加了一个内蒙古的MM询问01背包的实现 第一次出题办比赛:HDU 第一届老菜鸟杯 第一次现场赛:宁波赛区 第一次群聚: 宁波 第一次要到的签名:自己的(-_-) 第一个徒弟:narutoacm 。。。。 (7) 关于ACM_DIY( 群号: 48866438) ACM_DIY现在已经成长为了一个全国闻名的大水群,聊天记录数以万计.期间涌现出许多可歌可泣的故事和奇葩异常的语录.同时本群聚集了来至于全国几十所高校的ACMER,其中不乏类似hhanger,hl之类的高手。本群涌现出了各种baidu,tencent男,希望各位hr有兴趣可以来本群考察围观。本群的ACMER都是经过严格管理，保证肉质鲜美，无毒无害，绝对不添加色素和激素！