2018.8 安徽师大附中培训 游记

作者: wjyyy 分类: 随笔 发布时间: 2018-08-29 08:30

点击量:38

 

Day0

    南京南站真大啊——等出租车真慢啊——酒店旁边的吃的真多啊——我真菜啊

 

    晚上摸着摸着就到安师大附中门口了,附近娱乐场所挺多(雾

 

Day1

    早上在酒店吃自助餐,颓完了就去学校。白天才发现这个学校是跨街的啊!还有自己的过街天桥状元桥。然后去了神圣的机房。

 

    可能是第一天开学,老师派了一个人去拿钥匙,在教室机房外面等。不一会人都来得差不多了(第一次看到这么多学OI的妹纸orz)。于是得知这十天都是上午考试下午讲题没有晚上海星。就迎接考试吧~

 

    T1打开发现可以\(O(N^2)\)水到52分——至于为什么是52分,题目分了不多的点,但是每个点有多组测试数据,根据数据强度设定了不同的分数——接着一直信仰可以前缀和优化多骗21分,于是走上了不归路(ノ`Д)ノ。首先写了一个小时以为是正解的算法,被自己一脑子hack掉了。然后退而求其次去骗那21分,求了一个点的正上下左右前缀和,像这样:

    三个小时过去了……

 

    还是不服气,刚到最后把可能会错的代码交上去了,用五分钟打了T2可能能骗到的12分。。。

 

    中午来回学校的路上和yyx&yyfdalao们讨论的时候发现T2想错了(毕竟五分钟的脑子)就祈祷T1数据稍微水那么一点。

 

    下午去看T2题面果然挂了,然后在lemon评测结果瞟了一眼没看到自己,安师大附中人好多。。。过一会讲题了把评测结果翻了下来看到T1拿了1分总分1…排最后一个。。。算是没脸见人了,唯一能安慰自己的就是程序交上去了+没爆零吧。。。

    T1就算打一开始的\(O(N^2)\)也有52分啊。。。还是着急了没睡醒这题还需要一定的前置技能。然后讲T2的时候发现是个数据结构好题,思维假装记下来了。T3明明也很好骗分qaq。。。

 

    Day1可能来了不适应吧,或者说策略把握不得当。不过希望这种状况不要在正式比赛中发生了。。。同时也反映了自己的菜……

 

Day2

    上午还是考试。。。题目发下来之后看到三个题题面全是吃的……T1好像是个LIS或贪心问题,看上去会\(O(N\log N)\)的第一问(\(40\%\))和\(O(N^2)\)的第二问。于是开始数据分治,中途想到了几种可能能打的第二问\(O(N\log N)\)但都被我hack掉了。。。最后就打了\(O(N\log N+N^2)\)的79分。

 

    T2好像似曾相识,是ZJOI2012小蓝的好友加强版?数据范围特大+求方差感觉本来就是NOI难度的题一下子变得不可做了。。。打了暴力分就跑……

 

    T3是个字符串,特殊情况可以搞到12pts,先打了这12分就想到了接下来20pts怎么打。不过后来没时间了,也没调出来。

 

    出了考场才发现T1数据分治挂了,当数据范围较大时,就算第一问有输出,第二问也会T掉导致输出为空考试的时候怎么就没想到呢。。。T3更是一点希望都没有……然后T2的暴力优化25分也挂掉了……(好像是T了

 

    下午看成绩发现挂得和想象中一样……65+20+12=97——rk12(/34),依然是湖北省垫底

 

Day3

    今天的题目背景老长了但是还是跟题目描述没有半毛钱关系。

 

    T1感觉是个数论题,发现自己欧拉函数学得不好,于是想到了前缀和去骗50分。骗到50分不死心,于是输出了1到10的答案……

    这不是\(\sum\limits_{i=1}^ka_i\)么。。。于是用手推了一下发现所有数都满足这个性质,就大胆地打了这个结论写了个前缀和放那了。

 

    T2很难理解先放掉了;开始看T3。发现好像要用到康托展开,后悔自己之前没做相关的题,不过考场上还是推出来了。只不过300,000的数据需要树状数组维护+重复元素的处理需要除来除去……于是写了个exgcd以为万事大吉。结果发现2在\(\mod 4\)意义下的逆元怎么求啊[跪了]……发现前10个点是模数为质数,就想只拿那50分。写写造了几组数据发现没什么问题就放了一下。过了一会开始对拍,发现有的细节没有处理到位,这时候剩的时间也不多了,而且并没有想到良好的解决方法,于是T2GG,T3没刚完……

 

    出考场发现大家(dew/ouuan)T2都多多少少写了一点,开始发虚,不过没怎么重看题目还是抱了点希望的。dewT1没看出来有点可惜(不然又rk2了)

 

    这次是ouuan考了rk2,我还是rk12,dew稍微挂了一点到rk15了……下午一直听出题人吹题目orz然后T2第一问勉强能理解,T3后面CRT的部分反正是有点绕……数论这东西还是玄学。T1用到了一个结论就是\(\gcd (x,y)=\gcd (x-y,y)\),也就是与\(x\)互质的数是关于\(\frac x2\)对称的,f(i)=i的结论就这样出来了。

 

    今天至少A了一个题,比前两天要稍微好一些。

 

Day4

    这天T1是一个不难的二分答案,不过思维不好想。和之前做过的一道TJ/HEOI2016排序的思路很像。也许这种做法会成为趋势吧。

 

    T2是一道DP,不过现在还没搞出来。首先得想办法转移得到一个合法解,最后求最大子矩形就可以了。

 

    T3是二维树状数组,CF原题。考场上二维线段树写了出来,怕不保险写了数据分治。。对拍出锅。下午发现是暴力写挂了100->80。。。不过二维树状数组的思路貌似更优秀。

 

    这天讲课特别活跃;然后第二天是大质数节,就出现了各种mod。以及安师大附的讲课人互吹。。。

 

    分数还比较正常,前4天分数都是单调的(谁让我day1只拿了1分啊

 

Day5

    接下来几天都是安师大附学校组的题。T1可以用字典树水过去,因为只有0和1,可以构造出二叉树。而\(10^5\)不超过\(2^{17}\),时间空间都不会爆炸。

 

    T2是个最优比率生成树。题目明显提示是个分数规划可是就是推导不出来条件。。。于是敲了不知道能骗多少分的贪心////后来发现还是有良心20分的。

 

    T3看上去没什么思路,不过部分分还算好拿。后来知道这个是个肥肠好的DP。

 

    这天部分分不是很好拿,不过相较前一天还是有点提升的。如果T2最优比率生成树写出来就更好了。

 

    圣诞节晚上当然要吃华莱士啦

 

    最后吐槽一下这个

    都加<bits/stdc++.h>了怎么还加上面的头文件。。。反正我是只加了自己需要的头。。。

 

Day6

    T1是DP,思路貌似和我想到的一种比较吻合,但是我想的不是DP,于是挂掉了orz……

 

    T2是树形DP,不过还真没有看出来,以为是图论……不过暴力还算比较良心了\(O(n^2\log n)\)可以过2000。

 

    T3感觉可以建图,不过想不到特别好的解法还是放掉了,输出了样例和特殊情况……最后得了20分。

 

    T1改起来还挺快,只要组合数部分的公式代对了就没什么问题(再有就是状态转移方程。T2好像是利用了树的遍历序的一个性质吧,可以优化掉一个\(n\)。T3利用了倍增floyd,感觉听懂了不是很难,网上匹配两个字符串用的都是KMP,可能会卡掉暴力匹配?。。。

 

    这天是百度之星复赛,本来想到了一道题的做法想去实现一下,结果几个人一起关屏幕控制引起了老师的警觉于是就被罚站了……回来重新敲发现拿不到获奖资格了……后来想想也没什么大不了的,好好学习以后什么比赛都能打。

 

Day7

    天气预报报的雨没下下来。

 

    这天T1是个比较简单的有关LCA的题,感觉难度不大就过样例没管了。

 

    T2还看了半天,感觉是个贪心但是无从下手……推了半个小时发现有一种贪心可能是对的,多构了几个树发现没什么问题就写了,过了大样例。

 

    T3本来是想拿暴力分的,10000000的数据,发现给了6s,考虑\(O(n\log n)\)是不是能卡过去。不过编号在int范围内还让在线感觉不是很好做……于是手写堆感觉效率还可以,构造了一些大数据跑得不算慢。快结束了老师说那个int实际上还是10000000范围内,看样子脸白能A掉第三题。

 

FLAG诶貌似稳一点今天就AK了?感觉激动……

 

    下来和众巨佬交流发现T1没什么问题,T2好像有不同做法,T3看样子没毛病就看常数了。。。回宾馆百度一下发现T2有我这种做法……

 

    于是下午怀揣着激动的心情踢倒了我的flag……T1挂了30分,好像问题不算小,不过数据可能都卡特殊情况去了也不会在意这种加错了的状况吧……人生的第一次AK咕咕了……

 

    T2是一棵树所以可以树形DP…T3是可以单队做到线性的。有4个人AK吧羡慕%%%。

 

Day8

    T1考tarjan求边双,是POJ+USACO原题,下来测usaco数据强一点挂了一个点,POJ过了,出的数据也过了。

 

    T2是一个质因数之类的问题,考场上YY出了跟正解半毛钱关系没有的70分,正解至今还在咕咕(2018/8/26flag×1)

 

    T3居然考了2-SAT建模,不过是一个简化版,当时写了\(2^{m}\)枚举,混了20分。

 

    下午讲题的时候很认真很认真听了T2最后感觉有点眉目可是还是不会做orz;

 

    T3听起来比较轻松,给出的树没有用,直接并查集秒天秒地秒空气。

 

Day9

    这天是汪乐平讲的,不过题是吴作凡Newnode出的。三道题题目叫“苟”“富”“贵”,稍微奶一下明天叫“勿”“相”“忘”?

 

    T1是CF Div2A的难度。不过题面有点坑,就是要输出一个“二进制串”,但是不知道从左往右还是从右往左。恰巧样例是一个回文串,就不知道了,有人问,但是得到的答复是“这还用问”。。。写都写了正着输出就不管辣。

 

    T2感觉跟Day1T1有点像啊,不过还是有不一样的地方的。想到一种容斥感觉复杂度对就先做了,调了很久貌似还没过大样例就没管了。

 

    T3感觉怎么想都迎合不上题目的思路,甚至暴力分都拿不到……可能没理解题目的意思。

 

    分数还算正常吧,dew的T1输出反了,实际上还是要输出正的。T2的容斥有问题,因为一块区域不一定只出现一次。正解是扫描线,化周长为面积,用边长为\(k\)的面积减去\(k-1\)的面积就是边长为\(k\)的周长了。数据其实可以暴力扫描线,是\(O(n^2)\)的,而离散化可以用线段树做到\(O(n\log n)\)。T3数学推导+数据结构,思路到位的化堆就能解决问题,线段树暴力数据结构也是可行的。

 

Day10

    题面果真是“勿”“相”“忘”,第一题还是送的贪心,不过是Div2A+,贪心就可以。T2一时半会看不出来,好像需要数论知识?接着打答案表,发现没什么特殊的,找不着规律。先看了T3的题面,smg暴力都不好打,它合法的条件是什么啊……

 

    过了一会发现T2的f数组范围只有\({2,3,4}\)。,打出了这张表,就过掉了样例。(吐槽为什么没有大样例。接着写了写T3,发现可以枚举边,判断是不是生成树,并且只有3条链,随便造了点数据应该没问题。

    写了T2的暴力开始拍,上来就出问题,f(666)就和暴力不一样。一度怀疑暴力写错了(这种事干过很多次了),后来把表向下多打了一些才发现420出现了一个特殊情况,改了改,10000以内就拍过了。然后试了试1000000就又挂了。。。二分试了一下在哪里出的问题,发现是360360,打表出来又是一个特殊情况,调了一下1e9的数据就可以过了。但是数据范围是1e18的,感觉按这个幅度下去1e9到1e18之间还会出现一次特殊情况,接着开始枚举……就算考试刚开始就枚举估计也找不到,算了说不定比暴力分多一点……

 

    出考场交流了一下,果然是3个特判,经高人指点发现420是\(\gcd (1,2,…,7)\),360360是\(gcd (1,2,…,15)\)。按这个规律下一个就是\(\gcd (1,2,…,31)\)啊,回去算了一下发现没超过1e18。不过我想特判两个能过1e14,好歹比暴力要多一点吧。

 

    结果果真被卡成暴力分。。。数据都是极强的,不过T3\(2^n\)暴力拿到了还好,100+50+20…如果T2能混70就rk5了啊。。。

    T3居然是仙人掌???仙人掌出NOIp膜你题是什么意思啊。。。然后看上去题解还特别简单,只要“分情况讨论”就行了。。。

 

    完结。

 

Day inf

    总结一下就是 还有很多没学过但是很简单的知识点需要掌握,DP的思路还没打开,还有一些坑需要填,自己效率低下就是菜。

 

于8012年8月29日咕咕完毕

说点什么

avatar
  Subscribe  
提醒
/* */