2018.8 安徽师大附中培训 游记

点击量：425

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日咕咕完毕