2018.7武汉培训酱游记【随笔】
点击量:229
Day0
下午5点左右到武昌,又坐了一个小时公交(等都等了30分钟qaq),到了汉口火车站附近的某培训机构后晚上吃了一顿炒菜。鱼汤泡饭肥肠好吃,不过为什么@Dew 会认为鱼汤泡饭是在浪费鱼汤emmm。晚上随便水了水洛咕就睡觉了。
Day1
发现教室离房间只有10米不到的样子,但是还要去吃早饭绕上三四十米(严重的得寸进尺)。教室是有配台式电脑的,不过发现键盘是大回车,用得特别不爽,’\n’这种东西随手敲到空格……下午果断换了自己的设备。
上课课件为什么是英文的,不好玩。上午讲STL,下午考试。上午针对vector如何实现O(1)插入和删除进行了激烈(?)的讨论最终发现数组在改变长度(大小)之后长度总是当前长度的2倍。也就是说,设能放进去的元素个数为max_sz,当当前sz超过max_sz时,就把max_sz加倍,此时整个数组长度是当前长度的2倍;不过当删除元素时就不一样了如果要满足上面的条件,当元素个数不超过max_sz/4 时,把数组变为原来的一半……诸如此类实现方法感觉STL真的是神作。回去要补一补《算导》的摊还分析了。
7月18日是NOI2018 Day2,也就是考试日,同步赛本来8:30开始,结果到9点还加载不了,以为人比较多网络拥挤。于是开了4G发现…发现手机也登不上某网。还是考试开始一段时间@Mayfly才登进去把压缩包发了出来。话说身为中国计算机学会不专门架个服务器还用了北航08年的服务器??
看出T1的暴力怎么打之后,打算中午休息时间写一写,继续开始听讲。还没放学同教室的@ouuan (orz)已经把T1的65pts做法敲出来了(%%%),是不是感觉课程太简单了没什么意思hhh。
中午感觉良好骗了55分就去睡10分钟。下午是NOIp模拟赛(/▽\)。
下午一边考试一边看官网上同步赛成绩出来没有。下午考试的T1题意是线段树基本操作(区间加减,区间求和),不过随便看了一下数据范围
什么鬼直接稳稳O(N^2)啊。就水过了。T2是让维护前缀和的差,当时不知道在睡什么觉就没打出来,混了20分滚粗。T3数位DP还得自己调整,骗了20分也放掉了,感觉自己稳到140就开始颓。中间同步赛测出来了,只写了T1,40分。数据下下来一看,发现多组数据数组清空了但是ecnt(前向星计数)没置-1,T×m≥400,000的数据直接挂掉(省选也是多组数据忘记换行了/抓狂.jpg)。然后#15,#16纯模拟10分居然没看出来!#1是人口普查,不需要输出
(现场图片:)。
T2,T3一眼都没看。听说T1卡SPFA,大样例给的图SPFA就跑不过,还算良心了。
(现场图片:)
晚上膜你赛成绩出来之后@ouuan 果然rk1,除了被极特殊数据卡挂10分T2拿稳了90分。不过我只有100?T2,T3暴力分都没了?等了一会其他dalao也发现有问题果断反映。调了半天是lemon评测机出锅了,忘记调成(忽略行末空格和文末回车)模式,最后一行多换行的都gg。其实数据也出锅了,T3本来送了20分,数据扒出来只给了一个点(10分)?重测结果最后好像也没发出来。
Day2
这天讲数学,没有膜你赛,也没有NOI。感觉第一次听懂了什么叫逆元,什么叫期望,什么叫贪心。上午的状态要比下午的状态好很多,不知道是不是因为这天没有考试。学到了很多神题的解题技巧,眼界开阔了许多。
Day3
又是考试日,上午讲图论,对floyd的了解加深了一些,比如当两点间的最短路确定时,f[i][j]=min{f[i][j],f[i][k_1]+f[k_1][j]}和f[i][j]=min{f[i][j],f[i][k_2]+f[k_2][j]}是等价的。所以在一些题中,可以认为f[i][k]为最短路,f[k][j]为本来就存在的路径。以前不会的题感觉讲的时候一点,思路就出来了。还学会了线段树上跑最短路(雾),各种各样的题都有,即使是以前学过的知识点也有很多题型没有见过。(所有老师都不愿意讲正解 of 天天爱跑步?)不过GDOI的题好像在网上从来没有见过,纪中OJ也注册不了,感觉纪中有很多好题啊,不过是学校内部OJ也可以理解啦。
这天的NOI第一题送了20分的膜你,以及30分裸的扩欧。好像听说(扩展)中国剩余定理(excrt)可以过掉这个题。(感觉算法都听过今年是不是难度不高?[毒奶orz]),模数(题目条件)为质数的条件送了10分。第二题表示前15分可以模拟暴力乱搞,前两题仍然是多组数据,今天记得好好检查了。第三题不是多组数据就输出了rand()(雾)?数据发下来看到输出0是5分,输出1是5分,输出2是10分orz。
模拟考试给了一个送分题,有一道是用堆维护类似链表的东西(感觉听上一个老师讲过),这两个都没什么问题。还有一个题考了缩点+找结论,蒟蒻不知道怎么做只好混了40pts。orz
同步赛成绩没有出来,官网上挂的时间是2037年QAQ,是不是说明不用退役了?期望55~155(随机是不可能有的)分。
Day4
这天又换老师了,发现三个老师都是T大来的。随手查了一下该老师的资料发现某年NOI rk51?然后因为当时ysy上初三不能进队狗进了集训队最后一名,然后以集训队最后一名的身份进了队orz。
这是一个上课活跃热爱互动喜欢休息没事还会抓我们水群的老师,这天讲的是树形DP和记忆化搜索,感觉问题不是很大。下午讲了常见DP优化,前缀和优化是什么鬼好像还挺有用。斜率优化讲得不错,有点不明白去问还得到了详细解答ฅʕ•̫͡•ʔฅ。晚上继续问问题并get了一张T大作业纸?(kfdong:下午的东西很简单)
不过有些题是老师yy出来的,网上找不到地方交,可能可以找个标程拍一下再出个题(深藏功与名//雾)。
Day5
这天是玄学背包和能坑人一脸血的区间D(dǐ)P(pì)。知道了变量j可以叫“勾”(队列q是不是可以叫皮蛋),然后get了一个新名字叫-达不溜勾外外外(wjyyy)-。还是第一次知道背包中数据极限大和小时可以将变量调转,也是第一次知道多重背包这种东西可以用斜率优化,背包还能删除元素等等。区间DP只要脑洞比较大还是想得出来的(from一个脑洞奇小无比的人)。在讲了一下午的区间DP之后留了一道题,用区间DP复杂度太大,但是被思维束缚在区间DP中就没办法想到更优的序列DP了。还是要注意数据范围。(kfdong:OI其实是一门生物)
下午考试T1结论题送分,T2括号匹配(怎么上午讲的下午的变式就不会写/啪),用两个小时混了50分滚粗;T3什么异或根本没有头绪最后10分钟打了dfs枚举没混到分(脸黑);T4单向搜索85分,标算折半搜索/异或高斯消元,%%%@ouuan大佬又在考场上yy出正解并提前AK。结果考完发现还没有提前交卷2h的@cbj分数高
,晚上摸鱼般地讲完了四个题,海星都能听懂。
Day6
拓扑排序和tarjan还是比较熟悉的,学了几种这样的贪心?原来贪心还要推结论呐。
终于(貌似)会了树状数组区间求和/区间修改,发现还是线段树万能,而且线段树居然还能收!回!懒!标!记!mengbi地听了一下矩形面积并怎么求,接着引进了动态开点线段树这个坑之后就再也没有然后了。(kfdong:分块的本质是一棵√n叉线段树)
下午讲的是制胡窜,Trie、KMP、hash,bzoj上有几道hash killer,除了解释过标算的Ⅱ以外,Ⅰ是要推结论的,Ⅲ至今无人过。不过hash这东西挺有用的,生日悖论这个东西没想到会被用到这里。打开了KMP的新世界大门。
晚上填了一下下午的坑,之后开始做(伪)模拟赛。T1找了一道入门难度;T2读了读题发现可能可以线段树,开始猛敲,敲完之后发现自己凉了。2000的数据跑得比暴力还慢??找老师救了救孩子发现是自己的沙雕错误,不过终因线段树常数太大挂成70pts(正解单调栈)。T3直接无脑一波暴力40pts到手。(kfdong:省选题就是这么简单)
Day7
上午娱乐局,下午就要走了。老师准备了几个题目讲一下,于是每个题都开始佛系分析暴力复杂度,可能终于把@lcx的2e6×2e6=4e7悲惨数学救了回来。复杂度分析真是一个好东西,随机撒点也有可能是正解——“复杂度线性增加,错误率指数减小的随机算法”真强。原来e的定义就是(1+t)^(1/t)啊,“数学真奇妙”(雾)。或者一道看上去大力搜索的题目正解居然是简单搜完贪心?OI真是一个可怕的游戏。
发现今天同步赛成绩出来了,期望的Day2 55分摇身变成了35分
,不知道T2是不是哪里写的有问题,最终75分就没有然后了(铜牌线的尾灯都看不到)。
Summary
这七天的收获还是挺大的,主要是见了许多没有见过的题,也侧面反映出刷题量少的缺陷。还有就是讲课老师与我对知识点不同的理解方法,都是比较重要的。
在知乎上看过这样一句话,最大的敌人不是放弃,而是知足。我想,难道独立思考想出一道中档题就有资格高兴一整场考试吗?偶尔一次考得好就能开心一个星期吗?心花怒放一定会有,但是如果抑制不了自己的欣喜而变得狂妄,就会影响接下来的学习或考试时的心态。其实静下心来,就会发现,自己还有很多不懂的,还有计划没有完成,前方还有很多未知。因此,高兴只是一种情绪,让它闪动一下,再轻轻地把它放在心里,等哪一天真的成功了,再把它和痛苦一起挥洒出来!
希望以后的自己,不会对现在的我感到失望。
2018/7/24晚
说点什么