【AC大牛陈鸿的ACM总结贴】【ID AekdyCoin】人家当初也一样是菜鸟_舒哥的blog-程序员宅基地

技术标签: 算法  c++  acm  编程  大神……经验之作  

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都是经过严格管理,保证肉质鲜美,无毒无害,绝对不添加色素和激素!
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lsgqjh/article/details/44595945

智能推荐

spfa算法(优化版)_paranoidZ的博客-程序员宅基地_spfa优化

解决问题的范围:存在负边权的最短路问题时间复杂度:O(km)m是边的条数k是常数,算法是效率还算是比较高的,这个算法的时间复杂度的最坏是O(n*m)因此当没有负权的时候还是用dijkstra吧它和dijkstra的不同点在于spfa的标记数组是标记是否还在队列中(注意这个)算法的过程:加入初始的点,一般都是1,放入队列中,取队列的队首元素,遍历与队首元素相邻的点,如果距离变短则更新这个最短的值,如果这个点不在队列中就加入队列,如果在队列中就不用处理代码中由注释:给...

java大作业--邮件系统_weixin_52535875的博客-程序员宅基地

一、实现邮箱的登陆功能  邮件系统使用smtp协议发送邮件,使用POP3协议或者IMAP协议来收取邮件。SMTP属于推协议,POP3 ,IMAP属于拉协议。用户信息用mysql存储。  邮箱登陆时为了登陆进去就可以获取邮件列表,我们使用POP3协议来登陆邮箱。  (如果使用SMTP协议登陆的话,只能验证账号,密码是否正确,不能获取邮件列表,登陆进去之后还要再次使用POP3协议来获取邮件,南辕北辙~~~)  POP3协议并没有直接验证账号的功能,但是如果使用不正确的邮箱登录时会抛出异常..

php从入门到放弃,代码审计从入门到放弃(三) & phplimit_weixin_39818727的博客-程序员宅基地

原创:一叶飘零前言本次是phplimit这道题,本篇文章提供了3种解法,即如何利用无参数函数进行RCE/任意文件读取题目概述题目源码如下:if(';'===preg_replace('/[^\W]+\((?R)?\)/','',$_GET['code'])){eval($_GET['code']);}else{show_source(__FILE__);}代码非常清晰,首先preg_repl...

vue2设置保存自动执行run lint配置步骤_Saga Two的博客-程序员宅基地

分为三部1、安装eslint2、setting3、eslint文件

牛客练习-哈尔滨理工大学21级新生程序设计竞赛(同步赛)_辽宇的博客-程序员宅基地

比赛链接:哈尔滨理工大学21级新生程序设计竞赛(同步赛)文章目录前言正文A.考试周破防B.咖啡店C.kiki和bob玩取石子D.猴王kiki分桃E.很二的拆分F.构造字符串G.信号之旅H.小球滚动I.kiki看球赛J.跳一跳K.Jay的小弟总结前言昨天python考试没参加,于是乎今天做一做。虽说简单,但真正做起来花了我三个小时,没借助任何外力,包括自己debug,只想说单凭自己做真的不容易即使很简单,自己的问题会被无限放大。一共做了十一个,前十一个。有两道题目意思理解错了(D、K),有点影响心态

linux apache maven,如何在Debian 9上安装Apache Maven_松直的博客-程序员宅基地

Apache Maven是主要用于Java项目的开源项目管理和理解工具。 Maven使用项目对象模型(POM),该对象本质上是一个XML文件,其中包含有关项目,配置详细信息,项目的依存关系等的信息。在本教程中,我们将向您展示两种在Debian 9上安装Apache Maven的方法。官方的Debian存储库包含可以通过apt软件包管理器安装的Maven软件包。这是在Debian上安装Maven的最...

随便推点

C++——IO流基础_Damon_liufb的博客-程序员宅基地

IO基础  C++中经常使用cout和cin做输入输出,这实际上就是一种流的状态。正如生活中的流水一样,总是单维度、单方向的,从一个地方流向另外一个地方。C++中的iostream就是这种概念,从一个地方流入信息,然后以字节流的方式流向另一个地方。  传统的C语言中有printf,scanf,getch,gets等函数,他们自身具有一些缺点:1、不可编程,仅仅能识别固有的数据类型,不能输入输出自定义类型;2、代码的可移植性差。  C++中的I/O流istream和ostream等,可以编程,对于类库的

python中spider的用法_Spider-PyQuery基本用法(示例代码)_单身也是狗的博客-程序员宅基地

pip install pyquery2.引用方法from pyquery import PyQuery as pq3.简介pyquery 是类型jquery 的一个专供python使用的html解析的库,使用方法类似bs4。4.使用方法4.1 初始化方法:from pyquery import PyQuery as pqdoc =pq(html) #解析html字符串doc =pq("http:...

HTML中table边框的显示总结_TCH987551623的博客-程序员宅基地

http://blog.sina.com.cn/s/blog_90aad2c9010180cf.html一、1、显示表格的4个边框:&amp;lt;table border frame=box&amp;gt;2、只显示上边框: &amp;lt;table border frame=above&amp;gt;3、只显示下边框: &amp;lt;table border frame=below&amp;gt;4、只显示上下...

android popwindow 设计,Android开发实践:用PopupWindow实现自定义Dailog_油腻少年的博客-程序员宅基地

Android的PopupWindow是个很有用的widget,利用它可以实现悬浮窗体的效果,比如实现一个悬浮的菜单,最常见的应用就是在视频播放界面里,做一个工具栏,用来控制播放进度。本文利用PopupWindow来实现一个通用的Dailog,类似Android系统的AlertDailog,从中学习和掌握有关PopupWindow和Dailog的使用和实现细节。界面效果如图所示,点击 Click ...

单文档与多文档_deng19936的博客-程序员宅基地

百度了一圈,发现都是一些稀奇古怪的答案。因此在这里我个人来解释一下单文档与多文档的区别。摘自维基百科:A multiple document interface (MDI) is a graphical user interface in which multiple windows reside under a single parent window. Such sy...

Django学习_wei2023的博客-程序员宅基地

Django学习Django 本身基于 MVC 模型,即 Model(模型)+ View(视图)+ Controller(控制器)设计模式MVC 优势:低耦合开发快捷部署方便可重用性高维护成本低…Python 加 Django 是快速开发、设计、部署网站的最佳组合。特点强大的数据库功能自带强大的后台功能优雅的网址MCV 模型MVC 模式(Model–view–controller)是软件工程中的一种软件架构模式,把软件系统分为三个基本部分:模型(

推荐文章

热门文章

相关标签