-03-09
终于痛定思痛的决定放弃了,遭不住了。
想说的很多,对不起的人,也有很多,我想继续逃避下去,我不想在面对了,也有想骂的人,总之要走了,ACM真的是非常好的地方,不得不说再见了,再见了赛场。
别人是退役,而我是太菜了,自己都不想看到自己。
再见!
退役博客以后再写吧,最近挺烦的。
.2.28总结
最近做题的感觉又回来了,等我长长情绪就回去接着甘数学,最近做DP的感觉很好,可能是因为学数学的思维有所提升的原因,但是做数学之后因为代码敲得少了,导致签到题一直调不出来,思路倒是挺快的,然后CF一直掉分,最近CF的分数有所上涨,现在就是很多题明知道会做,而且有思路,写代码不知道如何实现,就很难受。等这套CF做完之后,在弄一套D,思维就差不多了。接下来还是DP和数学。DP60题还没刷完,等这些完了之后就去51NOD板刷,不板刷,根本不能提高做题速度,即使是思维有了,但是代码实现和速度还是没有的,这些还是很影响自己。
然后是两个队友都退了,好在自己的数学学的差不多了,差点数据结构,和计算几何。先顾DP和数学吧,数据结构可能他还不如我,平时见不到人,早就该换队友,不然我也不会一寒假糟心成这个样。
说实在的对我打击挺大的,一路走了很久,突然就走了,那时候我一直逃避,不敢面对,只有自己变强,这个弱肉强食的世界才不会伤害到我丝毫。
-01-19
放假一周了,虽然知识都学完了,但是使用和会用还是很难,不能在按着这个情形发展下去,这样的话肯定完成不了自己的任务,所以必须要改变自己的学习方法和学习态度,学习态度,一个星期也睡够放松够了,也玩够了,该明白自己要去做什么。
学习方法吧,虽然一开始推导确实没思路,要是从看题解开始可能会知道很多方法,但是还是少那个过程,开始的时候还是忍一忍这个痛库,一步一步的才能走得更远。
先把题做熟悉,然后再看亚线筛,在同时开数据结构。
.11.4
今天还是在看网络流,网络流不会卡时间,除非丧心病狂,主要还是考察建图,这个我觉得可能会出到什么对偶图建图什么的,所以建图还是重点,大概思想的话还是通过限制流量出发的考虑建图,所以怎么限制流量是建图的关键,这是今天主要的收获,网络流的题目做到这,就可以了,明天开始看费用流的题目,再做几个题然后回头看二分图匹配的题目,我才做了6道网络流的题目,但是收获了很多,就是从题目中去挖掘什么是更重要的,这是我今天的收获!
.11.5
1.发现网络流的算法跟启发式搜索有点像,看到他们用启发式搜索解决网络流的问题,不是想以后用启发搜索做题,但是这个思想需要用来填坑!/坑🕳坑坑坑坑🕳/
2.最小割就是建立限流的模型,然后求最大流,这点问题不大,算是新的感悟。还是不太懂最小割,我比较喜欢直接转为最大流,通过限流建图,我打心眼里没觉得这是两种算法或模型。
3.做题遇到离散化建图,这个真的是没想到,确实欠缺思维,明知道100W的点,肯定超时,网络流不卡超时,那必然是自己建图的方法出现问题。
4.今天还是没看到费用流,效率有点低,有待提高。
5.今天看了看区域赛的题目,数据结构偏多,后缀树+书上倍增,还有一道pollard rho,这说是签到题,这不是我能力范围的,要提高效率,毕竟我也想学DP,想学数据结构,还得学数学。才能有出4+题的可能,而且很多算法都是比较少见的,也不是那种少见,就是那种基础题用不到的,那种,确实得等学完基础之后去探究一下。
.11.6
今天出了一个最小生成树,这个是学了网络流之后才会有思路做的题,也是建立源点的思路。然后其他的吗,今天没有空看题,所以今天晚睡一会,补上进度。
.11.7
今天看了JAVA大数,不是很难,就是两个类,看看函数就完事了,做了几道题水了一下。还可以。
.11.8
满课,没怎么看,比较浮躁,一天忙碌而无所得。
.11.9
费用流的解题思路也是建图,同样也能解决KM算法解决的最优匹配问题,有向环最小权值覆盖也是可以采用费用流去解决,某些最小割的题目也可以用费用流求解,但是费用流的效率比最大流的效率要低很多,所以,尽量将原图建立成最大流的模型求解,在求解,避免正解为最大流求最小割然而自己建立费用流模型。
.11.10
对于普通的模型拿捏的比较不错,但是不代表我能够独立处理很多没见过的模型,这里应该训练思维,接下来是去看网络流建模汇总,看看为什么这个题要这么建模,思路是什么,怎么想到这么建模,还有没有其他的方法建模,这个要尽快看完,因为发现很多之前的学的算法,开始忘了,这必须也要补。周三之前开始复习+DP双开。
.11.11
沙雕Win10升完级就开不开机了,装机修电脑。TMD一天课+一晚上修电脑。
.11.12
看了看多校赛,读题还是比较清楚,但是思路没大有,普遍只能出一个题。
.11.13
研究了一下2-SAT,比较简单,模板题,没啥难度,明天开始复习,多校赛,还是只能出一道题,但是题面几乎都能读懂。
.11.14
又做了几道题,发现建边和理解题目还是有一定难度的,不知道这个题为什么就是2-SAT,费解。看的头痛,没有网络流那么轻松,这个考察思维,跟数学知识。
.11.15
找到了一篇很不错的2-SAT详解,将2-SAT问题用离散的知识解释,觉得非常明了了,合取析取蕴含,这样一看就明白了,只要题目是可以拆分成2种情况,且可以用上面表示出来就可以用2-SAT判断是否具有可行解。
.11.16
有点感冒了,做了一场atcoder就接着睡觉去了,bad day。
.11.17
2-SAT开窍,结束了,做了很多题,这是一个NP完全问题,三元关系四元关系都可以手动枚举一下。
开始向前复习,做连通性的题目。
.11.18
复习差分约束,真正的理解了这个三角不等式,及超级源点,更重要的是我明白了题目中还有一些隐含关系,也必须加进去,不然容易出错,难点在于不知道怎么判断为差分约束的题目。
.11.19
发现自己的训练强度,和训练效率已经不能满足当前的形式,强队越来越强,弱队越来越弱,有点恍惚,有点迷茫,不知道自己这样做下去是否成绩有效,相比别的学校的我们只是在划水,怎样提高效率,增强自制力,也是接下来的训练目标,现在数字逻辑也要开始考试,其他科目也要进入复习阶段,怎样分配时间是比较苦恼的事情,在这些方面看来,我真的没有我自己想象的那么聪明,时间确实不够用了,怎样提高效率是我接下来所不得不面对的问题,不聪明,要学聪明,能耍小聪明的地方也一定要,要将投入产出的比率尽可能地低。有点困惑,有点难搞。
被A+B>B+A的题,卡了一上午,下午好像没学什么,不记得了,这时间浪费了,完全没印象。晚上跟航宇模拟比赛div1只出了一个题,很难,思维还是不行,快餐练习思维还是必要的。
-11-03
反思:
学习太过于较真算法的实现原理,而不是注重算法的使用,有点剑走偏锋的感觉。算法的实现过程知道个大概,在使用中,在做题中,慢慢的算法的的原理就很明了了,这点很成问题,所以浪费了太多时间去扣算法虽然是一种方法但是效率不高,图论始终考察的是建立模型,转化问题,而不是在与算法问题本身设计的问题。归根结底,就是模板+思维,然后花了好几天的时间扣算法,扣懂了,算法始终是一份模板,模板会用吗?裸题,其他题目不会。这就是这个月前期的状态,到了网络流,我就的就是找一个增广路的事,看的差不多就行,板子理解了,可以了,就到这了,然后开始做题,开始看题,找到了感觉,可能我上辈子就是网络流,感觉做网络流真的很有意思,因为建图的过程就是在脑子中形成一张图,非常有画面,我很喜欢。至于未来的学习,我可能找到了那种感觉,学的很快,网络流也很有感觉,看了一个星期,看题加做题,加看模板,相对于前面的知识点看的又快,我也觉得是我最熟的算法,所以我觉得这个学习的方式真的很适合我。
知识点总结:
二分图匹配:我觉得除了二分图带权匹配都可以转化成网络流用Dinic,反正都是找增广路。二分图带权匹配还是考察建图,建起图来,建完图直接模板就完事,淦。又是模板。
很相似的就是网络流了,也是建图,这个建图很有技巧,所以说网络流二分图考察建图,遇到的建图方式,拆点建图,限流建图,通过并查集建图,Floyd建图,也就能想起来这个,然后发现原来网络流又成了工具,原来图论就是个工具,各种奇奇怪怪的题。
然后双连通,求割点,求割边,双连通分量,然后根据这些可以进行缩点建图,完成题目的要求操作,添边之后的连通性等等。
LCA,LCA三种方法,都是模板,这个浪费了好长时间,结果就是个工具,当成STL用也行啊,花那么大劲做的题目都不用改板子的,真的是服气。
2-SAT还没学,这个在等等,现在还差一个最小费用流,基础图论就可已结束了,什么仙人掌、竞赛图,这个再等等,刷题再看,先把基本的东西吃透。
也就学了这些,这样看来自己学的挺慢的,该加点速了。
还测测了板子,根据自己的喜好,改板子。30多个吧。
规划:
再刷一周的题目,把2-sat和费用流学完,然后系统的刷一刷题,然后看题大概12号结束。剩下的时间开始时看DP,树形DP与背包都不用在学,接着主要是数位DP,然后状压DP,期望概率DP学习加做题到比赛。中间在上JAVA课看看大数怎么写。别的就没什么了。
-10-28
终于在学校第一场ICPC之后,明白了实力的差距,本以为他们已经够强大的了,但是他们还是出了问题。这让我的感觉即使自己是砧板上的任人宰割的肉,没有任何发言权,注定失败,想想,自己跟他们比起来真的是自惭形秽,更不要说,我们与强校强队之间的差距,好在我们还有半个多月的时间,这半个月可以做很多事,但是能变得多强,很难说,但是不会害怕,也要明白自己的定位是什么。
自我反省:
首先是根强校相比找差距,相比于那些没有OI选手的强队,我们跟他们差的是什么?是劲头,是拿牌的欲望,陈立杰都不用说什么情况了,但是我的朋友跟我说,每天做梦都是拿牌,作息时间是早上出门除了上课都在实验室,晚上才回宿舍。他说圈里有一句话,四六级没过,什么奖也拿不到(非ACM),这个时候ACM准能拿奖。我们是否可以抛下一切去努力?我为什么要在我会了的课上浪费时间?我为什么不能做到高度自律?我为什么不能找到可行高效的学习方式?为什么我经受不住游戏与Bilibili的诱惑?为什么我不能利用零碎的时间?才发现原来自己不拿奖的话是自己活该 !强队真的训练不积极?难道别人的牌都是天上掉下来的?所以聪明的人有很多,但是真正努力的人很少(假努力,天天很忙效率很低不叫努力),这也就是有行人成功,有些人注定会失败的原因,而前者在失败中总结失败的原因,寻找成功的路线,后者只会连连叫苦,怨天埋地。想要成功要做前者,无论什么领域什么行业。不假努力,骗自己。
其次是后劲不足问题,在FLS发了马拉松这件事之后,我想ACM就是一场马拉松,退役前的每一场比赛都是一次计分点,每次都能知道排在什么位置,但是没到退役前的最后一场比赛,结果都是未定的,但是,长跑的人,他们是老选手了,这种强度对于他们来说是家常便饭,对于我们来说是高强度,后劲不足,跑着跑着就像歇会,歇会意味着,你休息的过程会被后面的人超越,意味着你前期拼死拼活的努力追赶都付水东流了!看看自己,这不就是说的自己?像是坏掉的蒸汽机,一股一股的。别人又努力的低效的汽油机,又高效的柴油机,而自己却还是抵消不努力的蒸汽机,最终在时代潮流下被时代的洪流淹没。ACM不是心血来潮就可以做成的事,不是一蹴而就的事,前期却实划了一个月的水,发现自己好忙,但是,是真的忙吗?忙到一点空都没有?不可能。所以说借口很好找,骗过了别人不可怕,最可怕的是骗过了自己,我自己很忙呀,我训练不积极不是很正常吗?woc为什么很正常呢,ACM就是这么不重要?所以未来要正儿八经的安排一下班内生活,将自己的借口扼杀!只有努力与不努力,没有为什么不努力!
最后,我想告诉自己,低级趣味带来的暂时的快乐,只会让自己空虚颓废,烂在自己的井里。
计划:
1.看题还是继续,好久没进行了。
2.题还得做,题该怎么做。
3.复习之前学过的东西。
4.总结这个算法会有什么题型出现,之前最短路最小生成树做的不错,但是后期学算法,忽略了这一点。
5.提高专业课效率,讲得太慢就复习,往后学,把课下的时间省出来。
-09-10
最近真的是有点忙,身体也不好,没怎么学习,感觉有点后退,没有暑假的感觉,有点忙乱,但愿生活步入正轨,规律化的作息,规律化的学习,才是我想要的,打了这么多场比赛了,难题还是难题,没有一点进步,反而一道超级源点的题目做不出来,为什么换Floyd呢,因为我的板子装不下那么多条边,所以就很难受了,修改了板子直接A掉,Floyd为啥错,没处理好吧可能是。数据结构,一直没出题,见题太少,知道这需要数据结构处理,该怎么优化呢,用什么优化呢,很难说?所以只能我图论与数据结构双开,这样才能多出点题,最近什么课都水,除了数字逻辑离散有点难,一周四节课,其他科都想可以学算法,无奈的我只能听着JAVA的倒水,绝望。
面对高校的AK,天赋或者力压群雄的学习能力,NO只是他们比我们搞了很久,现在有一句话就是核心竞争力,就是我们有的他们没有的,我认为是目标,站在山顶,只能下山,而在山脚下才能勇攀高峰。
-08-26
这一周打了很多比赛,首先应该表扬自己,会的题手快看完题直接能够敲代码,1A过了,问有道简单题出在配合上,一个人读完题之后,我应该在读一遍,但是没读题,导致一个人读题认为自己传达的没错,做题的两个人认为自己听的没出问题,最后压根没想到出错在读题上,强化读题,强化配合。
然后是一场CCPC,认识到了自己的实力,也知道自己的努力的方向,FLS也一直鼓励我们,我想自己跟别人比起来,确实学习能力不行,不然不可能高考考不好,但是对于改变学习方法也不是没有办法,至少知道学习方法是有问题,对于成功我只想用西点军校的名言:“每个人都想上天堂,但是没人想死”,总是想着我拿牌的场景,却从不想去努力,从安逸区里走出来很难,一旦到了暑假,我很难说像上学时那样,因为我还在舒适区,我还没有下定决心走出去,太多的诱惑在这里,我最喜欢的学习方式,是一个人没有人,自己学习,没人影响,看不见别人玩游戏,自己才会好好学习,这只能说明什么?自己还没有离开舒适区,还是不成熟,成熟就是玩游戏分时候,就像老师家长常常说:该玩就玩,学习的时候就要好好学习。学习效率提上来了,确实玩一会无可厚非,但是真得做到了吗,小时候仗着自己聪明从来不去努力,那个时候自己能看到的只有那一片又窄又小的天空,现在遇到了很多人比我更聪明,比我对于某一些方面更有天赋,所以要想弥补就要通过后期的训练,我楼教主数学也不好,不也一样冠军吗?所以努力很重要,这是先认清自己。
其次是成功论,成功的要素是什么?天时地利人和?是有实力成功+一点运气,运气是玄学,那只能提高前者,实力是什么?天赋?天赋只是一方面,难道天赋就是一个人做事的所有依赖?不可能!那么肯定是通过后天学习才铸就了一个人?也就是说无论一个人多强他们都是通过学习来的,那么不同是什么?是学习时努力程度,天赋算吗?学习天赋固然有极大的帮助,但是那只能是说他们跑得更快一点,并不代表在一场马拉松中他们就能够不停下休息,总有一小部分很可气,又强又聪明还很努力,这些人不能比,但是在他们后边总会有要跑在前面的人,这个人的位置就是成功,那么跑去天赋,成功的本质是什么是努力,是后天的学习,那么我有了这两种特质我能成功吗?答案,很显然是可以成功。
喝够了鸡汤还是要上路,离开自己的舒适区,所谓的学霸,都是可笑的称谓,只有自己登上山顶才有一览众山小的感觉,众星捧月也就是没用的面子。永不服输,干就完事
-07-15 尘埃落定,以梦为马,不负韶华
开始的时候写出了这么文艺的标题,还有一点小羞耻,今天跟自己的朋友(山理工的)问他们省赛的事,不亏事OI选手,不够一OI加二白丁一样会拿银(七题)为什么大一别人可以拿银而自己只能手握铜牌呢,真的跟他们比起来自己简直什么都不是,别人在大一上学期就学完了线段数树状数组,而自己还是一个代码都调不利索的人,所以差距从这里就开始体现出来了,谁不是一个肩膀抗一个脑袋,干就完了!
.06.18
之前打了几场比赛,有很多题没做出来,这些题无论是知识点不会,还是说在当时时间和思路的影响下没有做出来,这都应该做出来,至少现在必须做出来,本来打算专心复习,分数高了,好保研,但是想了想如果局限于只把学习学好,那这就有点眼界小了,考试成绩是一个水到渠成的事情,所谓的临时抱佛脚,也就呢么回事,看了看ACM大佬,绩点一样4.5,人家也天天刷题,要想他们学习,况且,从现在到最后一刻考试也要一个月,那这一个月要是不做题,前几个月积累的虽不至于都没了,但是肯定会大不如从前,从前一阵比赛情况来看,自己都是被吊锤,不太甘心,倒不是自己多高估自己,而是觉得自己没有尽力,现在看一些题目觉得不难,但是当时确实没想到,事后诸葛亮确实不可取。FLS说保研是一件水到渠成的事,但是保的学校不是很好,但是有一点ACM无论是考研还是保研这都是亮点,为了保研每天都背负着很大的压力,但如此想来,这不是畏惧挑战吗?所以有得有失,看的保研太重了,有点过于功利心,这点也是不可取的,目标是要有的,但是学校是要自己要跑的,所以在那之前要有自己的亮点,才会找到一个好学校。看了看那些大佬(不是15保研的)而是某ACM现在,大一大二大三的专业课已经学完了,老师没讲的python什么爬虫啥的,也都会,为什么别人课余时间能做那么多东西,自己就比别人差很多吗?效率是自己的软肋,往往事倍功半,有点读死书的感觉了,要改,一定要改,感觉FLS成了信仰一样的东西(并不是吹捧某费老师 ),虽然有点固执,但是确实可取的东西很多,毕竟从C++一门课上就看出来了,计算机的代码虽然垃圾,但是比其它专业真的是强了不少,原本以为老师给学生高分,糊弄过去就是好的,仔细想想学费交了,老师哄着你学一学期,什么东西也没学会,这不只是老师师德有问题,学生也是糊涂蛋,宛如买东西付了钱不要东西,为什么不把学费捐到希望工程。中国社会步入小康,不愁吃不愁穿,一点斗志也没有,不用想去改变家庭的命运,父母把台子搭的太高,孩子就不知道这些是父母奋斗出来的。现代人从不会感恩,从不知道父母的辛苦,真的是垃圾人。所以好就是好,坏就是坏,没有太多解释,这是一个老师该有的品质。最近几天某老师把考试范围透露了,同学们开始有针对的复习了,哪还有学生去好好学习这么科目,反正最后好复习。挺可悲的!
我坚信自己能够在极大的时间压缩下,一样能对付期末考试。不得不向大佬低头,不得不给FLS一个赞,对于大部分的计算机的学生来说,真的是极好的。我在ACM课程论文中也说过,某些保研的学长学姐连STL也不会用,现在我要换一种说法,连代码都不会写了,到了大三一年没怎么写代码,宛如一个文科生,这是老师说的为什么再也保不到好学校了,没办法读死书的人太多了,大学四年不能只是水课水人水考试,不过听说大三保研成功的话,大四还能再打一年ACM。?怎么还是绕不开保研,可能是自己太懒了,不想考研,其实对自己来说保研的概念很模糊哦,挂在嘴边让自己努力,要是想某计算机耿JZ学长一样,北大计算机,加油,想耿学长学习,明天的我要比今天的自己更努力。
再来吹捧一下我FLS 如果没遇到FLS,我可能也会水三年,拿三年好点成绩,报个垃圾学校,然后大学跟高中一样,日复一日,没有一点让人记得有意义的事情。完了这成了商业吹捧了
奉劝君一句,欲穷千里目,更上一层楼,不要一叶障目,自欺欺人。
-05-25
昨天,交作业的时候发现之前写过的代码打比赛时被覆盖了,我想的是,我要在写一份,而不是给老师去解释,然后肝到四点也去写了,社会不会等一个人等到四点!做事要谨慎一些,看到自己交上去的丑陋的代码,竟有些恶心,构想的将近800行的代码500行草草收场。还有些同学交不上作业?扪心自问一下,这些作业很难吗?一个不交作业,告诉别人太难了,我不写了,然后半个宿舍的人就不写作业,不交了。南校有个经管的想要转计算机,每天12.00了还在敲代码,问我问题,这种魄力,你们有吗?在问自己开学的时候,确实1.00之前没睡过觉,这种魄力去哪了呢?你还是那个很努力想改变自己命运的ZJH吗?想着去重修,没有勇气面对这一切,见不贤而内自省,有时候面对问题是否退缩,敲算法一做不出来就像去看题解,破釜沉舟的勇气去哪了?当初组队的时候,我觉的我有狼性,我能拼了命的去拿我想要的东西,试问一下,到如今自己的效率,自己的投入是什么样的,不敢回头看,害怕自责后不能再放肆。我记得我跟航宇组队的时候,我俩默契的说了一句,“伴不上大佬,就做大佬”,你离大佬还有多远,跟学长交流,学长跟我说我很强!然后自己不认识自己了!什么是强,拿了奖是强,还是自己聪明就是强。省赛奖很水,没有一道算法题,动动脑子就能做,自己出题出的再多,只能证明一件事,思维还在这,算法等于没学。DP也忘了,单调栈,搜索学的不是很明白,也没来及去补。觉得自己好像很能学习,现在想想,这不就是昨晚写代码的时候,有人再打有些一样的道理吗,花同样的时间,做出的事不一样,得到的结果不一样。感觉花了大量的时间在学习上,容易见异思迁,效率低下,还不如别人打两把联盟来得实在,别人花了时间得到了乐趣,你花时间没学到知识,也不快乐,这不是浪费时间?表弟清华,表姐中科院,聚会父母牵强的笑着,他们不说但是我自己懂,父母不说我,觉得我尽力了,我就是一个演员,从初中混到高中,从高中混到大学,每天都在混,像是一滩垃圾,像是自己最讨厌的人,父母给的太多,反而不好,衣食无忧,哪里来的压迫感,受尽了沧桑,才有掀起海浪的能力,时间宝贵,覆水难收,在你玩的时候,总有人还在尽力的码着代码,等你松一口气的时候,有人还在咬紧牙关为梦想前进,有人说成功很简单只需要努力就好,谁有真正的去努力,好在这个社会不是每个人都去努力,才会有阶级的差距,才会有财富的差距,梦想是注定孤独的,拼了,操!
我他妈不想当社会渣子,我想考研,我想打ACM拿奖,我想改变自己的家庭,我想改变自己的命运。
.04.06训练日记
昨天队友回家,我拉上LJH跟我一起打体验赛,比赛难度比预想中要低很多,要因为错误的估计导致自我菲薄,没有考虑过是否为思维题,所以一开始没有认真去想这些题,总觉得这些题会是贪心、DP、搜索、或者还没学过的并查集、数据结构什么的,过了一个小时才刚刚进入状态,像楼教主可能不会再刻意套算法,解决问题就是思维,而算法是给了解决问题提供了一种思维方式,而不应该遇到题目就要考虑这是什么算法,我该套什么模板,本末倒置,忽略了思维的重要性,这是不可取的。
今天模拟赛没有打,主要是看区间DP快结束了,权衡一下今天只有一个人,还是做DP,在做DP的过程中,做到了一个五维背包的问题,用了六重循环,虽然样例都过了,但还是wrong answer,肯定是有地方没有考虑到,但是我想现在是给了限制是五维,要是10维那岂不是要写十一重循环,去查了一下,这是状态压缩DP,对状压名词不是很陌生,但是对题目及实现原理不是很清楚,还没来的及去学。区间DP已经有点开窍,这还是好的,DP还有很多没听过的树状DP,单调队列优化DP,斜率优化DP,知识有点多,也很难理解,不知道FLS讲不讲,如果不讲,一定要找机会学会他们,不放过任何知识,最近时间总是不够用,一晚上扣一个DP没扣出来,有点失落。
最近学习方法有点问题,或者说是思想懈怠,遇见题目直接套模板,比如区间DP直接套模板使用,压根不考虑实现原理,不理解实现原理,题目稍微变化很难再去套模板,所以清明这两天,做了很多DP简单题目,来理解区间DP实现原理,堆石子,能量项链,堆石子2,终于明白了实现原理,但是还是一个题从今天下午卡到今天晚上,今晚做不出来不睡觉。
所谓的努力不出成绩,就是无效努力和努力不够。
-08-06
今天看了很多,打了很多字,今天搜索看了前五中,深度优先,广度优先,优先队列优化的广度优先搜索,优先队列优化的深度优先搜索,权值不同的双端队列搜索。DFS BFS 是烂大街的东西,这个东西学不好简直该死,这是图论的基础算法,学不好搜索意味着放弃了大部分的图论,广搜是中规中矩的按顺序一层一层的递归进行搜索,深度优先所搜索是按某一分支向下搜索不撞南墙不死心,相比于优先队列优化的搜索来讲,每次都选最小的代价,但是当前最小不代表未来最小,当搜索结果在当前最大代价的分支下时,就会最后遍历,这个所要花费的时间要比一般的搜索花费的时间还要多,但是一般的搜索花费的时间也很可观,所以有了A算法,但是A的算法实在弄不懂他的f(x)估值函数,所以再等等,明天主要任务就是分清楚什么题用什么搜算算法,需要怎样剪枝。
-07-28
今天学了归并排序,采用了分治的思想,可以用那个来逆序对,逆序对的另个方法是树状数组。具体的知识点总结都写在了另一篇博客里在这里就不多赘述了,讲一下今天的心态吧。以往做题都还好都是思维题题,思维题出与不出这个跟个人的思维有关,或者说时遇到了一些没见过的算法,补补题跟上来也就无可厚非,但是今天看到一道DP,而且这个DP比之前做的都要简单,但是我就是写不出状态转移方程,一闭上眼你就是为什么DP也不会了,经典DP而已,不是很难想才对,但是没做出来,从比赛结束之后我就一直反思,这个确实要归咎于学习方法,学完不去用,后就不用就会忘,也不能老看,还有很多知识需要新学,随着学的越多,需要复习的东西也逐渐增加,这就需要找一个点,去权衡复习,与新学。最近我看到了很多人都在用工做ACM,这让我有了压力,好在正是这个压力,没有让我继续颓废,不能老是窝在后边,比赛干嘛不去争个第一呢?今天算是睡不着了,都是一个头凭啥你比我强,大家都心知肚明努力就会有结果,而不是划划水,玩几把游戏就能站在领奖台上捧杯的,一样在学习,我不承认他们比我聪明,但是我承认他们私下就对比我努力,因此喝了这么多鸡汤光说不干,那鸡汤不如去喂狗。明天醒来,找找自己的学习方法,讨论怎么提高学习效率,周天就是学习的加油站。
-08-08
今天做了几道搜索题,自己搜了一个专题,大概有二十个题,打算周四周五做完,周六看A*,这些启发式搜索,因为太难了,这个估值函数确实有一些挑战,而关于前面的知识,比较固定化,打算周天把模板型的东西给敲一下。今天没学新知识,就记录一下学习中遇到的问题,有的时候搜索的这个优先队列用的不习惯,不明白咋那么用上,还有就是条件判断的时候。我用了一个if(a[i]>max||a[i]<min||i<0||i>1e5)类似的判断条件,一直RE最后才发现他在判断边界条件之前就已经越界了。所有很多细节还是要注意。
-08-13
把最短路都手写了一遍,保证自己能够看到最短路,立马dijkstra,bellman-ford,spfa,floyd直接就能写出来,一点不含糊,昨天拿张纸默写了一遍,效果还可以,写一遍就会一个算法,手抄算法不会让你浏览的那么快,但是会看的很认真,简单高效,一遍就能想起来,一遍就会。
-08-22
马上就要上战场了,昨晚因为觉得有些题目太难,没敢作,等到想做的时候,时间结束了,很难受,B题在三个人的攻击下,硬是没搞出来,这就有点难受了,昨晚策略出了问题,觉得B是简单题,而忽略了F题,回宿舍没有半小时就过了,这就很让人难熬了。开题的顺序很重要,更不能按照一个题目干,没用。
-10-09
最近学习真的是到了瓶颈,学的很慢,虽然也在看题,看算法,但是算法到了一个学起来很难,学会了就要嘲讽自己,这不挺简单的,为什么学这么慢,我认为这是对知识的接受能力较差,难以有一个良好的心态,一开始看不懂,就开始抵触,然后不想学,不是真不想学,是自身静不下心来,看一个算法,就是说都快20的人了,内心还是小浮躁,急功近利,让自己慢下来感受学习的感觉,就是学会前,茅塞顿开的感觉,这个可以理解为开窍,现在生活步入正轨,慢慢的训练时间也开始多了起来,要把握住所有的空闲时间跟零碎时间,保不定那一天会来事干。 最近更新了算法学习的路径,按计划补完了K短路的板子,然后好像还有一个2分的方法,他的枚举方法很巧妙,对我的启发很大,这个整理成一篇博客,稍后放出来!
-10-04
国庆假期已经过去一半了,任务很多,没完成,时间紧任务重,好久不做题有点手生,现在感觉好多了,树形DP慢慢的有了感觉,做起了也有点上手了,在学习新的图论的知识的时候,发现之前学的不扎实,所以有点虚,学后边的时侯,有点吃力,回来补了一下,感觉还可以,后边的话,打算接着看Taijar然年回来再看LCA和联通分量,这样可以将两种方法对比着看一下,虽然Taijar很强,但是我觉得既然给了两种方法,就有道理,就该学。
-09-23
在一天天瞎忙活后,我终于有空写这个训练日记了,感想是,这个班长谁爱当谁当。这两天没看博客但是图论大的方向看完了,生了一些细节算法没处理,就是板子还不是很熟,但是算法已经理解了,图论剩的都是比较复杂的东西了,打算巩固一下基础再向下进行,像ZhuLiu算法,用的不收敛,Tarjar的功能太多还得看点博客,图论的题目还没刷,打算看完网络流之后,边板刷图论题边找自己不会的方向进行学习,像仙人掌图,在10月前,结束所有图论知识,刷题到10月15日,DP最近两天没做,等着上课做吧,上课水课还点名 ,比较服气,第六周了还在讲怎么写程序,给我造成了没学过C++的假象,不让使用辗转相除,因为这是科学家发明的,我们不会!行吧,简直了,好好学习吧。最近心烦意乱的
-09-19
最近再看欧拉图,最小生成树,还有朱刘算法,这些明天后天看完了,会写一篇详细的博客!
没啥好总结的,所有学的东西都以博客的形式体现了,分享一下感受吧,完不成任务,不睡觉,没这点魄力还想拿牌,做梦!完成任务了,睡觉了。
看不见凌晨的星光,又怎么能看见成功的希望!
-09-15
今天做题,签到题没出,思路太死,按着差分猛做,除此之外DP没出,这个确实很难,但是这个题应该出,跟别人对比做题的话,着实有点LOW,还是只能做水题,水题的思路好出,但是难题中档题,做不出来,这个需要改进,当时想刷完DP60题,还没腾出空来,奖学金评定,开学已经两周了,训练应该回归正轨了,每天没事就要来训练室,中午睡觉也尽量在这,除了下午有课,将学习生活分的层次分明一点,锻炼身体去健身,有革命基础,除了上课,做作业应该上课的同时昨晚,对于某些水课应该尽可能的避免时间浪费,只要今天不累死,题就得看10+,做题就要1道DP题,这个要说到做到,即使真的做不到明日也要补上,如果一个月后DP60题做不了30题,博客看不了300篇,我就退队!再也不打ACM,不配!
-02-13
昨晚的思路,丑数题,真的是卡了一天,头疼了去做点别的题,再回来做。
按理说,我的思路应该没错,别人告诉我这是一道队列题,可我还对队列,一无所知,去查了资料,队列是数于数据结构部分。看了看,觉得,自己不是幼儿,应该自己思考,应该用什么方法,去寻找方向,而不是人云亦云,程序的最优解不止一个,就算我前进的很慢,也不能去粘代码。
思考,这个题的解法,找到方向,去研究实现这个解法的操作,是否有现成的函数与算法,有,使用现成的算法和函数,没有,自己写函数去解决。
今天STL卡了一道题,还好FLS延长时间,要不然STL还没学明白,题目就要下架了。
不得不说,我确实有点菜,进步跟别人比起来有点缓慢,同样是set容器,我从学用,到会用用了一天,而别人用了半天就得心应手。
今天又遇到了队列的思想,看了csdn上大佬的文章,队列就像是一种特殊的容器
定义queue 对象的示例代码如下:
-08-16
昨天学了,0/1线性规划,线性规划不能使用贪心和DP,因为∑AiBi≠∑Ai∑Bii⊂N,前者最优推不出后者最优,列如这三个数31041039100,其次是最优比例生成树,最优比例生成树是树形01规划,用二分即可。其次生成树的数量,用基尔霍夫矩阵树求解。昨天学了,0/1线性规划,线性规划不能使用贪心和DP,因为\sum \frac{Ai}{Bi} \neq \frac{\sum Ai}{\sum Bi} \ \ \ \ i\subset N,前者最优推不出后者最优,列如这三个数\frac{3}{10} \ \ \ \ \ \ \frac{4}{10}\ \ \ \ \ \ \frac{39}{100},其次是最优比例生成树,最优比例生成树是树形01规划,用二分即可。其次生成树的数量,用基尔霍夫矩阵树求解。昨天学了,0/1线性规划,线性规划不能使用贪心和DP,因为∑BiAi=∑Bi∑Aii⊂N,前者最优推不出后者最优,列如这三个数10310410039,其次是最优比例生成树,最优比例生成树是树形01规划,用二分即可。其次生成树的数量,用基尔霍夫矩阵树求解。
-08-11
做题的时候忘记了uper_band lower_band这回事了,怎么优化也是超时,忘记了uper_band 是二分查找,而题目有给定有序,那么很显然的一个二分题目。当时还自以为是的剪枝,题意很快就看懂了,但是lower band 没想起来,所以WA了很多遍,这让我有点难受,看了广搜的的迭代加深,和A*,IDA相对于A来说简单不少,还有重点是位运算优化,真正学完搜索之后会发现,搜索搜的是状态,DP枚举的也是状态,找到搜索的状态,也就是找到了DP的状态,只不过是枚举方式不同,表示方式不同而已。
-08-15
问题:容易分心,时间紧不允许分心,必须调整状态提高效率,时间没少花,效率太低,这波很难受。学了最小环,最小生成树及其变形,图论的考察不是简单地单方面的,更多是多种知识的的叠加,就是一张图,我用一种法把他变成能用另一种知识可以解决的问题,转换过程有涉及到了另外的算法。图论不能是套模板了,更要掌握思想,只有熟兮思想才能改造出其他的解决办法。学长不用考虑图论了,比赛的时候出不了题的。有比较痛苦,先学吧,出不出题再说。
-08-10
这一周快过完了,时间很紧张,压迫感来了,动力干劲也都回来了,昨天还是依然在做搜索题目,今天稍微看看,看起了IDA*好学一点。对于昨天的比赛,要学会从数据量观察算法,显然朴素算法解决不了时应该,根据观察向想其他方式。昨晚的第二题,10^5位,一看就知道这是大数也做不了的,不识数论就是规律题目,首先想到的应该是打表。
-08-09
做了7道搜索题,有些搜索题目开始变形了,数据量开始增大,这时候剪枝就显得尤为重要,剪枝的策略是最优化问题,同代价次优化的子树减掉,超范围减掉,无法达到要求状态减掉,能在子树的根节点剪短的尽量不要进行递归搜索,因为子树的深度与子节点的树木很可观,容易报栈,超内存,超时,所谓搜索就是有技巧的枚举说白了就是暴力,但是好在有技巧,通过剪枝的技巧可以说完成一些时间复杂度估算很高的题目。
训练感受吧:强化思维,思维才是一切算法的基础,无论是哪种算法,他的执行与修改都离不开思维,所有的算法也都是在人们通过思维的强化,和算法的积累,慢慢的逐渐出现的,像是莫队算法,ZWK网络流,主席树,很多都是从赛场上发明的,可能孰能生巧是要从小学开始抓起,也不乏有一年半载封神的,我要做的就是不要忘记自己的初衷,因为感兴趣加入这个圈子,因为想拿牌坚持下来,因为想要去更高的战场上去看一眼,我也要拼尽全力,迷茫过,也想过搞点副业,坐拥更多的奖项,真正的王者只有一个,三心二意最后是无所得,很迷茫不知道自己这20多天干了什么,真的没有拼上全力,成绩没上去,体重上去了,强者从不畏惧失败,也不怕困难,知道ACM意味着吃苦,虽然在做着,但是身体上心理上其实一直在犯嘀咕,要是没有拿到大奖该怎么办,浪费这一年,我是一个想要把一切都算计好,让自己的利益最大化,但是这样的人,最后只是同学口中的的学霸,问自己真的是想要的吗?从今天开始抛出杂念,要相信自己有能力拿牌,也要有拼他一个无悔的气魄,我知道不去做我一定会后悔,这是从小到大我做过的自己喜欢的唯一的一件事。
未来目标吧,像上学期用实际行动感动队友,召回之前的干劲,永远年轻,永不服输,永不言弃。
在一些垃圾的SJ那里,ACM根本不值得一提,学校不主动给实验室,如果能够把舔人的表面工程做到培养人才上来,我也相信的一个学校的学科竞赛不会这样,有时候真的需要励志一波,无论是谁都想证明给他看,垃圾人你看不上的ACM捧回了学院的荣誉,你TM就是垃圾人。我?N?
-08-14
(1)当权值为非负时,用Dijkstra。
(2)当权值有负值,且没有负圈,则用SPFA,SPFA能检测负圈,但是不能输出负圈。
(3)当权值有负值,而且可能存在负圈,则用BellmanFord,能够检测并输出负圈。
(4)SPFA检测负环:当存在一个点入队大于等于V次,则有负环,后面有证明。
-08-07
昨天没看新知识,做了做题,题目很难,一个人题扣了一天,看着别人写的dfs,我就按照深搜的思路写,但是写到最后我开始慌了,因为一天写不出来的题,是不是难题,是不是我没见过的知识点,我后来想还是按照我最开始的想法去写,因为是从DFS找到题目,觉得这一定是搜索,回来用前缀的查分和做这道题目,就变得简单了,所以做题还是动脑子,答案不唯一,今天找点简单点的有代表的题目做一做。
-08-01
今天学了,字符串哈希,把大一上学期用Set做的那道题做了一遍,有用字符串hash+二分做了一道回文串的题,解决回文串有O(N)的算法manachar算法,通过过扩展,有点KMP的感觉 ,思维题做的有点少最近,读题能力下降,别人的都AC了,在我这还没有读懂题目,还有不到一个月的时间怎么最快的提高自身能力,是很重要的,思考也是比较有意义的,学习方法关乎努力与成绩的关系,虽然都是正比,但是系数不同。
定一下明天的目标,一套codefore div2尽量做三个以上,知识manachar做题,KPM,后缀数组。每个知识点找一个题目练习
-08-06
今天看了很多,打了很多字,今天搜索看了前五中,深度优先,广度优先,优先队列优化的广度优先搜索,优先队列优化的深度优先搜索,权值不同的双端队列搜索。DFS BFS 是烂大街的东西,这个东西学不好简直该死,这是图论的基础算法,学不好搜索意味着放弃了大部分的图论,广搜是中规中矩的按顺序一层一层的递归进行搜索,深度优先所搜索是按某一分支向下搜索不撞南墙不死心,相比于优先队列优化的搜索来讲,每次都选最小的代价,但是当前最小不代表未来最小,当搜索结果在当前最大代价的分支下时,就会最后遍历,这个所要花费的时间要比一般的搜索花费的时间还要多,但是一般的搜索花费的时间也很可观,所以有了A算法,但是A的算法实在弄不懂他的f(x)估值函数,所以再等等,明天主要任务就是分清楚什么题用什么搜算算法,需要怎样剪枝。
-07-28
今天学了归并排序,采用了分治的思想,可以用那个来逆序对,逆序对的另个方法是树状数组。具体的知识点总结都写在了另一篇博客里在这里就不多赘述了,讲一下今天的心态吧。以往做题都还好都是思维题题,思维题出与不出这个跟个人的思维有关,或者说时遇到了一些没见过的算法,补补题跟上来也就无可厚非,但是今天看到一道DP,而且这个DP比之前做的都要简单,但是我就是写不出状态转移方程,一闭上眼你就是为什么DP也不会了,经典DP而已,不是很难想才对,但是没做出来,从比赛结束之后我就一直反思,这个确实要归咎于学习方法,学完不去用,后就不用就会忘,也不能老看,还有很多知识需要新学,随着学的越多,需要复习的东西也逐渐增加,这就需要找一个点,去权衡复习,与新学。最近我看到了很多人都在用工做ACM,这让我有了压力,好在正是这个压力,没有让我继续颓废,不能老是窝在后边,比赛干嘛不去争个第一呢?今天算是睡不着了,都是一个头凭啥你比我强,大家都心知肚明努力就会有结果,而不是划划水,玩几把游戏就能站在领奖台上捧杯的,一样在学习,我不承认他们比我聪明,但是我承认他们私下就对比我努力,因此喝了这么多鸡汤光说不干,那鸡汤不如去喂狗。明天醒来,找找自己的学习方法,讨论怎么提高学习效率,周天就是学习的加油站。
-06-20
近来比较清闲,也没啥课,太热也睡不着觉,就多刷会题,今天早上,加昨天一晚上,就做出来了三个题,DP是真难,现在因为面临考试,只能做点题,要去花时间学知识点的话,可能真的没有这个魄力,但是DP一定要学,还一定要学好。做题好满足,大佬们都在刷题,打CF(穿越火线 )我怎么能落下呢!!干就完事。
-05-31
这是5月的最后一天,终于调整好了状态去写代码,去学习每一科目,不在浮躁,也不会在偷懒睡觉什么的。
今天看到C++作业自己拿的是C,自己虽然心里不是个滋味,但是那样的代码自己看了也恶心,能及格就不错了,明天晚上又要交代码了(今天),我要交出自己认为最完美的代码,图论套模板套的我恶心,单源的就果断Dijkstra,实在不行SPFA,看看数据量,查询量即可选出最优的方法,一题多解比较常见。今天晚上写了几道USACO,确实开始上难度了,有点难受,有个叫虫洞的题,真做不出来,看答案也是蒙蒙的,别人都给老师发了好几次截图了,而我第一大关还在卡关中。
队友的训练越来越勤,我快赶不上他们的进度了,以后中午又不能回宿舍睡觉了,成绩总是出在那些努力的人身上,而不是靠耍嘴皮子的人,实力制胜,今天虽然熬夜到一点多,但是这种感觉是真爽,获取知识的感觉,想起来了昨天打比赛,DPwa了一发简单的DP题,25行的DP,完全没有头绪,翻书有研究了一遍才有思路,写状态转移方程,不得不说DP还是很难想,我们队的DP跟图论是分给了我,目前图论还是可以应付,但是DP好长时间没练过,忘得有点厉害,图论跟搜索也是离不开的,之前说每天一篇博客,也好几天没发了,这个补没用,还是靠自觉,看看梦想跟垃圾想去选择哪一个,搜索题可以拿出来再做一遍,
以后给自己任务太多,确实不太可能。还是保证周三周六的博客不能停,每天两道题不多,也不少,多了不做,少了不睡。
DP USACO 搜索 三选一,FLS的作业跟上做就行,再加上比赛训练时间也不算少。
反思
刚才又 拜读他们那些得A的同学,写的很真实,有自己的想法,很干净明了,没用冗杂的东西就不写,不是机械的生搬硬套,不是每个Class都需要写满get set函数,没用写他干嘛?他们写的功能很少,但是写的很精,每一步数据都处理比我好,我属于贪多嚼不烂的死胖子,就是因为写的多,才骨头不顾尾,能力还是有点欠缺,所以慢慢来不要贪多,先把简单功能实现再去添加新功能,一点一点完善这个程序,而不是一个class完了他就死哪里,不动,不改变了,应该是需要调整,根据后续的功能去完善之前的类,在重新调试class,确实他们做的很好,MJG的代码简单明了,加上注释所有函数显得不能么苍白,当我打开自己代码时600多行的垃圾,实在时一点也不想看,那晚我为啥要睡觉不选择改完再睡,ls能看完就挺好的, 写出来的代码首先要自己愿意看,别人才会愿意看,应付老师的垃圾代码,始终是垃圾,谁看谁认为是垃圾,今天看到他们的代码受益匪浅,然我看到了怎么写一个不那么恶心人的代码。与以后也要加油学习C++,ACM跟C++虽然都是敲代码,但是方向确实不一样的,虽然我看到题,我就想给他简简单单的干出来,但是一个工程要的不是解决一个问题,而是一类,动则几千实则上万行的代码,要是每种数据都要定义,然后整篇的int string好几十行,这样的代码不能复用,可读性差,好几千行的代码写完就没用了,太浪费了,要不然学C++干嘛,那些C不都能干吗?scanf不还快吗?所以未来要改变思维模式,用更通用的方式写类写作业。
你若是天才,我便是疯子!
今天打比赛,会做的题比较简单,细节要注意,第一点String溢出问题
这是当前系统最长能存的字节数,所以改用Char[]还是得用char,没办法;
有一个题,是快速幂,还有一个题像是单调栈,但是卡了负数,单调栈遇到负数不知道怎么写了,所以今天就水了两个简单题。心里很难受,排到了600多名,连一些职业院校也排在我们前面,放眼大局,我们还是太菜,包括昨晚杭电的题,杭电18级也排到了很靠前的位置,这是最令人发怵的,有相当大牛的心,没这个实力这很丢脸,努力还是要继续的,看到这,就想到了省赛,之前想的是“谢谢参与”现在想既然参与了就要有点结果,奔着牌去,付出拿牌的努力,不在乎结果如何。
-04-13
今天打比赛,调整好了心态,不管rank榜,所以做的比上次好,今天A了四个题,都很水,memset的清零时间,需要好长,因为memset 跟cin超时了,它的数据量1e6,所以超时了还是多用scanf,少用cin。其次是区间dp,确实很难,不好想,明天要开DP,尽快做完,接着做区间DP,DP水很深,如果学不明白很吃亏,下一步学递归跟搜索,有助于理解DP,DP我认为是一种搜索加上特殊的剪枝方式,进而突出的状态转移方程,最近一直在做codeforce没怎么做dp都是在做思维题,因为自己的思维太弱了!这个是之前没有积累好,之前高中学习的时候也是按照应试模式学习,这点很是缺失,日后两方面都要抓紧做。
最后,最近数学建模分散了精力,做人要专注,不是自己感兴趣的东西,做做就有点想放弃,更喜欢的是码代码,码代码是一种乐趣,接下来,专心准备省赛,尽自己最大努力,不管结果如何,尽力去做,总会有收获
-04-17
终于我们的小队,站在了榜首,虽然实力跟他们相比还有一段距离,从第一次比赛被碾压,我的队友中午没有睡过觉,一直在做题,每天晚上训练到十点,可能我们还是没有变得很强,我们还要继续努力,自己弱小不是问题,怕的是认识到自己的渺小而不思进取!
最近开了DP,很难,学习任务越来越紧,时间被压缩的很厉害!最近要好好的规划时间。
今天,没有做出来的是一道大数模拟,JAVA做会简单点,c++学长不推荐我用,记下这个地方不会,有空学习!
-05-04
连续8天的做题,有的时候做题很顺,有的时候有一些问题:
1.找不到签到题;
2.题目分读,效率不高,三个人读题效率不高,差距也就拉开了,有时候自己读题读不出题意,别人又不能参与,换题的时候就有些晚了。
3.慢慢的有这样的默契,分读题334,我看四道题,他们精读我浏览,看到签到题之后就做。但是每天坐签到题,感觉难度像是上学期的OJ,做多了很多知识就忘了,别人做出来的题,又不想去补题,最近补题效率很低,不是线段树就是主席树优化,想去看但是能力有限,做好当下,不要贪,学过的知识题解不能落下,最近时间做的不好,值得反思。
(近期整理DP)
口水博客:
今天别的学校的同学问我,“你每天都打比赛学算法,弄得好像自己像一个ACMer一样。。。。。。”尽管我很弱,尽管我现在还是一无所知,我没拿过奖,没见过比赛,没能像大佬一篇一篇论文,一天十几道题的在做,但我是每天兢兢业业做题,除了学习全部的时间投入到ACM,就这么轻易被否定,拿奖就算是奢求,我也会尽我的最大能力去做,DISS你目光短浅,就会被说成自视清高,就当当发泄!!
-05-09
经过这一个月的做题训练,思维能力,跟做题感觉,都有所有能力也有所提高。没有太多感想,就是继续努力。
问题:
1.埃氏筛法
int a[maxx];int b[maxx+1];int gg(int n){int p=0;//记录素数个数for(int i=0;i<n+1;i++)b[i]=1;b[0]=0;b[1]=0;//准备完毕for(int i=2;i<=n;i++){if(b[i]){a[p++]=i;//记录素数和个数for(int j=2*i;j<=n;j+=i)b[j]=0;//剔除倍数}}return p;//返回素数个数}
2.精度计算
一、基础篇
1、一般浮点数使用double,范围为大概为-10^308 ~ 10^308,有效精度为15~16位10进制数。
2、一般没事(比如内存问题)不用float,而使用double,一个double占8个字节。
3、信息学竞赛一般使用scanf和printf输入输出,而浮点数的输入是scanf("%lf",
&x),浮点数的输出是printf("%f", x),注意两个是不一样的。使用printf("%lf",
x)来输出浮点数有可能会出错,因为标准中规定double输出是使用"%f"的,并非所有编译器都实现了"%lf"的输出(比如POJ的G++就没有)。
4、在实在没有办法的情况下可以使用long double,但标准只规定了其精度一定不小于double,有可能等于double请注意。
5、double的精度有限,并不是精确的存储数字,而且它是二进制存储,如下图,0.1 *
10不等于1,因为0.1在计算机中不是我们认为的1/10,下图有0.1在double下的值,可以看出并不完全等于0.1。
6、为了解决上面不能直接比较的问题,我们可以设置一个精度EPS,来辅助我们检验两个数是否非常接近。EPS的设置要看题目具体情况,一般情况下可以设成1e-8。
定义函数:
inline int sgn(double x) {if(fabs(x) < EPS) return 0;return x > 0 ? 1 : -1;}
用上述函数来判断一个数是否大于小于或等于0。
x = 0 写成 sgn(x) == 0
x < 0 写成 sgn(x) < 0
x > 0 写成 sgn(x) > 0
x > y 写成 sgn(x - y) > 0
x == y 写成 sgn(x - y) == 0
x >= y 写成 sgn(x - y) >= 0
以此类推。
7、上述函数的一种常数优化的写法:
inline int sgn(double x) {return (x > EPS) - (x < -EPS);}
二、进阶篇(陷阱篇)
1、在竞赛中,可能存在给一个double多次计算后,非常接近0的情况,但是,它可能是-0.000000000000000001(一下子举不出实际的例子……),这时输出会变成-0.00,在一部分精确比较的题目上可能会出错,解决方案为输出的时候加上一个EPS(当然不能排除出题人自己煞笔的情况……),即printf("%f",
ans + EPS)。
2、如果一个double,要把一个数组里的浮点数累加起来(即 double sum = accumlate(arr.begin(),
arr.end(),
0)),如果数组里的数相差可能会比较大,应该从小到大累加。否则可能会发生加了一个很大的浮点数之后,再加一个很小的浮点数,因为精度的原因,跟没加一样(比如一个极端的例子,1e100
1e-100还是等于1e100)。因为比较小的数多了,还是会影响到答案的,并不是可以简简单单被忽略的。
3、在计算一个数减去一组数的时候(即double sum = x - accumlate(arr.begin(), arr.end(),
0)),应该先把数组里的数全加起来,再用那个数来减。否则跟上面一样,可能会出现减去了一个很小的数,跟没减一样。
4、二分的时候,EPS设置不当,可能会出现奇怪的问题(特别是有多次二分而对着两次二分要求的精度不一样的时候),这时可以采取另一种写法:
double binary_search(double l, double r) {for(int i = 0; i < 100; ++i) {double mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}return l;}
循环次数可按需设置,一般100都够,对时间要求高可以设小一点。
5、在连乘的时候,浮点数可能会丢比较多的精度,此时可以利用公式x1 * x2 * …… * xn = exp(ln(x1 * x2 * ……
xn)) = exp(ln(x1) + ln(x2) + ……ln(xn)),取他们的对数相加,再求次幂。
比如在计算阶乘的时候,可以:
double Factorial(int n) {double res = 0;for(int i = 1; i <= n; ++i)res += log(i);return exp(res);}
当然有必要的时候(其实是大多时候)我们可以先不exp()先返回,作完后续运算再exp()
3.超时
数组过大每次都要memset初始化,导致超时。
有些时候,数组没必要memset,卡了我七次超时,一重循环。
4.素数筛打表的时候默认为1为素数
5. 昨晚微积分定积分公式忘记了,没做出来题。
6. acos(-1.0)=Π;精度很高,比手打的define精度高不少,用3.14159265,精度都不够。
放平心态,省赛加油。
-05-22
最近usaco的题卡的我十分难受,看不懂什么意思,做不出来,也不想去看题解,跟题干耗,问题的关键在于,读题能力太差,要是换成英文,那还了得,读题能力要训练,最近要干的事情太多,没有一个计划,效率过于低下,面临着诸多考试,程序设计作业也开始上了难度,电子也学不会,训练有点懈怠。
好的是,感觉自己学习ACM开始开窍了,之前学习算法那种费劲,难受,想不出来浑身难受的感觉好了很多,可能自己确实比较适合图论这部分知识。
下一步,不管多忙,每天抽空做1-2两道题,写一篇题解,尽量写1篇知识总结。
有的人效率很高,我比不过,我拼时间。
-05-18
首先反省自己状态,我可能是队伍中的毒瘤,今天比赛划水,觉得题目太难完全没有头绪(主要是静不下心来读题)三天打鱼看,两天晒网。自己可以犯懒,但是比赛是三个人的,就算不为自己的梦想,也不能对队友不负责。发现自己没有自己想的那么强,开始不自信,自我怀疑,我是不是有这份聪明劲?开始懈怠,向我最讨厌的那一类人转变,又要开始做咸鱼了吗?
反思:
从一开始到现在,真的投入ACM多少精力,伪学习,花大量的时间说自己在学习,投入度怎样?不全身心投入,效率低下,收获甚微,不想做下去就放弃,别浪费时间!!
最近总是忙忙碌碌的,都不知道自己在干啥?浑身的比较累,有时间就光想着睡觉,还是想写代码,但是效率不高,感觉精神不足,无法静下心来学习,浪费太多时间,自控力低下对自己失望到爆炸。生活混乱,黑白颠倒,做事没效率,像一滩无欲无求的垃圾。
花一天调整好自己的身体跟心态,备战区域赛,绝不会让自己失望,也绝不会辜负队友的期望跟信任。
-07-27
今天没学什么东西,补了补题,学了一上午的矩阵快速幂,从下午做那个题做到了现在,虽然最后还是做出来了,但是太费时间了,做题有点慢,思路出的也有点慢,最近做题有点吃力,需要再加把劲提高一下效率,只看书不做题,知识点记不牢,做题太多又影响学习难度,扣题也耗时间,这是一个比较难取舍的事情,所以必须要想办法提高效率。今天的博客只能划水了,没学太多东西
-04-25
昨天天碰到了博弈论的问题,没有头绪,还有什么主席树,完全没有听到过的名词。问题一天天堆积越来越多,之前的单调栈跟搜索还不是很明白,有点浑浑噩噩,突然发现题目一天道题一辈子也是做不完的,反思很重要,今天突然发现背包忘记怎么写了,果然不复习真的会忘记,这是自己的瓶颈,有很大的压力,今天想到ACM大佬的说的话:“你若是天才,我便是疯子。”,人十我百,人百我千的魄力真是学的目标。
知识点需要整理的:NIM博弈;
简单图论知识;
状态压缩,不只是DP可以用,搜索可以用很多地方都可以用状态压缩的思想做。
Hash 哈希散列表。