NOI前45天的机房日常

Recursion posted @ 2015年6月02日 12:50 in 杂文 with tags 日常训练 , 4475 阅读

~~其实不是机房~~

想想noi只有45天了...再不好好训练就真要滚远了...~~(虽然noi就是靠运气)~~

update:

7.14 完结啦

6.2

上午开了一套gym，neerc2013

f是个签到题...b还有点意思，注意到[tex]n \leq 1000[/tex]，所以可以dp。i是个挺有趣的交互题，然而并不会做，而且找不到题解...剩下来的题要么不可做要么比较无聊...

然后又开了一套neerc2008northern subregional，题目总体比较sb，最后还剩一道计算几何和一道读不懂的题无力了...

下午：

bzoj4037 感觉还是很有趣的，把矩阵作为dp值，然后预处理一堆矩阵就行了...

bzoj2286 虚树dp。我终于会虚树啦。

bzoj3611 裸虚树dp，这种题模型都好裸啊。

和pear，shanquan2膜拜后缀自动机，然而并没有看懂...

6.3

swerc2013

做了两道找规律题...

poi2014 couriers 裸主席树，炸空间不说啥了...

bzoj2118 有趣的题。对[tex]a_1[/tex]取模后变成一个没有拓扑序的dp，spfa。shanquan2一眼秒太神了。

下午和pear，shanquan2在教室乱搞要把教室搞炸了...

在pear的指导下学会了后缀自动机，感觉良好。

bzoj3926 trie上后缀自动机。其实跟串并没有任何区别...今年那个集训队论文完全不明真相...

bzoj3517 神结论题。好像证明很显然？

6.4

今天pear去打acm啦

cf305div1d 每一行每一列相邻两个点连一条边，然后二染色就行了。

然后围观shanquan2出胡策题，结论题是可怕啊。

bzoj3732 sb题。

poi2014 hotel 枚举根，dfs即可。感觉有[tex]O(n)[/tex]做法？

研究了半天主旋律，终于~~在shanquan2的指导下~~A掉了。陈老师的计数dp好神啊。

bzoj3996 js省选难度的最小割。

明天就是分组赛了呢。

省队胡策出了一道sb题...

6.5

上午不知道在干啥...然后附中神犇来了，果断膜拜。

中午的时候女队hrz也来了，太神了，满满的A队爷气质。

下午先是xuyi讲课(其实是xuyi不是xuyi)，好多无聊的经典题...然后jyy科普了一些有趣的黑科技(虽然好像没用？)，感觉我还是当理论计算机科学家吧...

晚上will讲计算几何感觉好无聊，大部分都是自己能yy出来的东西，然而感觉写起来很麻烦...像我这种嘴巴选手果然还是结论题适合我...

看到了初一小盆友来听课感觉好可怕，果然我要退役了吗...

听说hrz要出一场cf吓傻了，好想出一道题目啊~~(只要让我参加这场比赛就行)~~。

6.6

上午will接着讲计算几何感觉好无聊...

下午wzk讲奇怪的构造，脑洞太大而且感觉并没有什么用...一直在围观hrz打逗比之星...

分组赛day1 bless all(虽然我并不指望能进A队)。

~~(blog访问量破千啦...)~~

6.7

contest day1

左边坐着syf，对面坐着zl，右边坐着hrz，感觉亚历山大。

t1又是个大原题，非常开心地花了15min敲完了，看看感觉没错就扔一边了...

后4h一直在想t2，t3最后还是只有暴力分真是没救了...

下午一看成绩，t1只有50，发现数组开小了，真是*了狗了...做过的题都A不了还有谁能来救我。

本来180貌似还有点希望A队的说，自己弱没话说。

waltz260标准分太神啦！

晚上去打乒乓球，果断被虐爆了，泥萌都好神啊。

跪球明天答辩不被D...

6.8

原创题答辩...

泥萌都好神啊，各种大数据结构，各种生成函数，这年头不会数据结构不会fft真是没法混了。

貌似waltz的题让我对仙人掌产生了兴趣...虽然我这种懒癌晚期患者显然写不出来...

我的傻逼题没有被D感觉好开心...

常州众太可怕了，感觉没有一道我会捉的题。

~~我还是去捉hrz的乱搞题好了~~

下午pear讲课还是很资瓷的，zzj表示飞飞侠这种题二维线段树强行搞一搞就行了...

6.9

分组赛day2，感觉人生失去了希望。

看到题目就知道没有翻盘希望了...t1，t3看了半天感觉完全没法做，t2数据结构题一副傻逼题的样子然而怎么想都感觉要一个根号两个log，我打赌这跑得比暴力慢我会瞎说？

就这样3h过去了发现我还是处于1分没得的状态...

于是挣扎着去写t1暴力，发现好像有60的样子...

写完后发现错了...然后拼命yy怎么也想不到多项式算法...特判掉20分算了...真心绝望了...

最后一小时突然发现t2TM不真的是傻逼题吗，为什么我智商这么低T_T

抱着反正要滚粗了的心态在键盘上狂敲。

写啊写最后一分钟终于过样例了！

然后就结束了...

发现大家好像都会捉t2的样子，顿时感觉自己要B队垫底了...

最后奇迹果然没有发生在我身上...

t2 tle了...然后听说出题人把一个log的方法卡掉了...强行变成20分暴力分...

算了算了，至少没有WA掉，不说啥了。

然后听说star day2怒At2强行翻盘进A队了，数据结构是厉害啊。

感觉我现在这状态去noi估计也只能铁牌滚。

update：似乎star并没进A队？

6.10

上午做了一些奇怪的acm题...

然后接着bzoj...

把清华夏令营的t1A掉了，其实这种数据结构题还是挺好写的，为什么我当时会那么傻逼

下午csx来了，围观csx和pear打acm...

于是pear写了3题的最短路...

6.11

学习kd-tree，感觉自己智商好低T_T

pear在捉一道非常有趣的题...

6.12

bzoj3158 pear告诉我这种看上去是独立集的题要强行往二分图上搞...

bx2k跑来围观啦...

pear在讲奇怪的acm题。

dlh没带电脑电源线也是醉了...

下午打了几局三国杀...

6.13

今天是初三中考，祝都能屠场呢，虽然并没有什么意义...

在家感觉好无聊...

bzoj3743 练基本功的树形dp？

bzoj3586 感觉我是永远学不会高斯消元了T_T

6.14

bzoj3636 作为一名泉岭精神信徒，时隔半年终于把这个坑填上了...

看了一天的sam感觉trie上的情况还是没搞清楚T_T(明明就是自己弱)

6.15

来了好多人啊T_T

教室爆炸啦！

6.16

bzoj3569 挺神的随机化，然而bzoj上能过cf怎么都wa...考虑一棵生成树，给非树边随机一个权值，树边权值为所有覆盖它的非树边的异或和。那么如果不联通必须删掉一条边及覆盖它的所有非树边，也就是存在一个子集异或和为0，高斯消元就行啦。

bzoj2121 无聊的大dp...

bzoj4062 一堆奇怪的细节成功wa了5次，最后发现变量名打错了。set+树状数组乱搞。要注意左右边界及顶端的情况。

bzoj3489 kd-tree大法好，三维强行上，跑得飞快。把每个数前后与它最靠近的相同的位置记下来组成一个三元组[tex](i,pre_i,next_i)[/tex]。然后询问一个区间就是问在[tex](l,0,r+1)[/tex]到[tex](r,l-1,n+1)[/tex]中的权值最大三元组。用kd-tree维护一下，注意剪枝。

6.17

dlh生快！

bzoj1416&&1498 有趣的题，注意到摸球的顺序是不影响答案的，然后就是高精度了。

bzoj2648 kd-tree大法好！

bzoj4066 貌似出题人加了组数据把没用替罪羊重建的卡掉了T_T于是我就愉快地T到死了T_T

bzoj3918 找出欧拉回路，然后把环搞出来就行了。

6.18

大清早在noip吧水贴...

bzoj3930 网上有直接用容斥做的方法？

uoj21 连uojA题都不会感觉没智商了T_T

bzoj4152 球正确的dijkstra姿势T_T

6.19

上午在准备英语口试~~(为毛我要考这种奇怪的东西T_T)~~

bzoj4117 妈呀我竟然不会哈夫曼编码了T_T

bzoj3237 3569双倍经验...果然bzoj上数据比cf水多了...

bzoj3624 典型的不会证也能ac的题？

bzoj4144 多源最短路，然后离线并查集就行了。

6.20

pear生快！

今天一直在浪...

上午看了一下学军noi模拟赛，yyl打表找出了t2的规律，最后忘记特判40分滚粗了...

6.21

bzoj3677 感觉很有趣的树形dp。

bzoj2817 好神的dp...但想到要写高精度实在是不想写...

6.22

bzoj3806 正反建两棵trie，然后让每个串尽可能前缀长的时候统计。

bzoj3436 差分约束系统。

bzoj4004 显然是拟阵，消元搞一下就行了...卡eps差评...

6.23

bx2k天天压代码sxbk

bzoj3498 有趣的脑洞题233

bzoj4066 写了一发替罪羊重建的kdtree...

bzoj4154 本来写的按时间戳打标记，这样就不用下传标记了，结果wa到死，改成正常打标记就1A了T_T

bzoj4047 首先按价值排序，令[tex]f[i][j][/tex]表示后[tex]j[/tex]件物品使用[tex]i[/tex]次魔法的收益，转移即可。

6.24

bzoj3494 省选居然有PA原题...虽然是削弱版...居然没有人提交过...试图抢一血失败...强连通分量的情况感觉好麻烦T_T

bzoj4058 奇怪的找规律然后分治...

bzoj3625 挺简单的生成函数，贴了个多项式开方的板子就A了...

bzoj3240 感觉矩阵写起来很麻烦，于是就直接推公式了，忘记特判[tex]a=1[/tex]wa了一发。

6.25

上午vp了一发昨晚的cf，a题是个sb数学题，b题有点意思，注意到只有长度为1和2是合法的，拿fibonacci数列算一下就行了。c题是个脑洞挺大的图论，大家一起开黑也算是做出来了...最后还剩20min左右，看了看d，猜了个结论，感觉是二分答案+贪心，但来不及写了T_T后来一看题解，连二分答案都不用，直接贪心...我也是醉了...

下午作死vp了一下clj的round146，先写了ab(其实以前看过b题题解...)，然后看了c，发现是个后缀自动机，不会捉，然后看了d，发现是个奇怪的期望，不会捉，然后看了e，发现是约数个数和的三个数的版本，直接拿那题的结论在dlh帮忙推公式的情况下写完了，一下飙到了rank3太可怕了...Orz shanquan2

后来看了一下d题题解，感觉挺神的。把答案的期望变成每对点之间在删除一个点时连通的概率之和就很好做了。貌似可以推广到仙人掌上？

6.26

cfround285

a一开始看成了任意图被吓傻了，后来才发现是个sb题。然后看了b，完全没有想法，发现c挺sb的，就写了下。然后dlh来了，告诉我阶乘进位制的转换方法，然后他帮我写了45min终于写完了...

才发现b题500分，c题2500分，太可怕了...

cfround265

好像前面做过这场，只不过没有交代码...

A：由于给定的串没有回文子串，只需从后往前依次枚举即可。保证任意一个字符与前面两个字符均不同即符合要求。

B：暴力枚举所有方案，求出两两之间距离排序，显然前12个相等，中间12个相等，后4个相等。且中间的数是前面的数的[tex]\sqrt 2[/tex]倍，后面的数是前面的数的[tex]\sqrt 3[/tex]倍。

6.27

bzoj3175 sb二分图。

cf278div1c 只有质数才有解(4除外)，第一个数必须为1，最后一个数必须为n，然后每次除以[tex]i-1[/tex]就行了。

bzoj3994 同cf146e，不过这题多测要预处理+根号。

晚上打cf，果断被坑了...毛子的手速场，报警了

update:rating-=4，也是醉了...bx2k依靠手速直接上黄不能多说T_T

6.28

[tex]2\pi[/tex]节快乐！

bzoj4042 同训练路径，挺好的一道树形dp，可惜转移必须要状压dp一点也不优美...

bzoj3163 背包是可以倍增的。

bzoj3244 挺神的一道题目，虽然想清楚了也很简单...(这种题出在noi真的合适么...)考虑每个点对答案的贡献，只可能是0.5或1，分情况讨论一下...具体细节见uoj代码...

6.29

cfround228

A：经典贪心。

B：挺有趣的构造题，拆成二进制就行了。

C：一个有趣的结论是每一堆每个人一定至少拿一半，然后就是贪心了...

bzoj4128 随机一行暴力...

6.30

cfround225

A：sb题。

B：不会捉...感觉离散化后乱搞...

C：sb数据结构。

cfround236

A：写了个贪心，然后就A了...

B：显然从后向前操作，预处理搞一搞...

C：以前做过的题。判断强连通分量就行了...

D：想了半天感觉有个[tex]O(n^2)[/tex]的算法，然后看了下题解，尼玛[tex]O(n^3)[/tex]，[tex]n=1000[/tex]，cf不能多说...

bzoj3659 黑书公式题。

7.1

bzoj2169 挺好的一道计数dp...一开始去想容斥结果滚远了...

bzoj4155 第一问sb最小割，最二问sb背包。

bzoj3858 显然的根号算法。

cfround210 AB不说了...E是个有趣的贪心...

7.2

去常州啦！

在火车站，取票机无法识别bx2k的身份证比较囧...一定是bx2k太神了把它吓傻了...

下午和晚上随便刷了刷cf...

cfround172c 有趣的期望题...答案就是每个节点深度的倒数和...可以用期望的线性性证明...

7.3

上午滚远了...爆搜题不会捉...傻逼题还能写错...提答连规律都看不出来...还是退役好了...

下午是strongoier讲cdq分治，仍然只会原来会的部分...

cfround172d 同数据备份...线段树搞一搞...

bzoj4123 语文题...至少我看错题了...

7.4

上午t1是poi原题，结果出题人卡常数卡空间卡系统栈不能多说...t2又是个meet in the middle，正解居然就是一通瞎压位，不说啥了...t3是个无聊的状压dp...然而我最后10min才查出错，差点滚粗T_T

下午讲奇怪的随机化，仍然只会原来会的内容...

bzoj3160 回文子序列减去回文子串数，回文子串直接manacher，回文子序列可以fft。

bzoj4160 随机50000次dp出最长路。

7.5

t1是ctsc提交答案题...不发checker差评...果断上网下了个checker...随机化一通乱搞只搞出67分T_T

t2不会捉，t3bzoj的sb原题...

下午讲奇怪的数学，基本上啥都没听懂。

7.6

滚远了T_T

SG函数好久没写都忘了T_T

压位bitset被卡常数不能多说T_T

fft不会背板子不能多说T_T

下午讲带花树+仙人掌不能多说...

bzoj4056 kd-tree大法好！可持久化treap维护矩形，暴力统计答案就行了，跑得飞快。

7.7

t1数位dp，t2计数dp，t3star原创题。

晚上jyy科普了一些有趣的linux黑科技，~~虽然并没有什么卵用。~~

7.8

上午jyy讲线性规划，感觉还是挺有用的一个模型，可惜感觉以我现在的能力是背不动板子了T_T

下午围观bx2k抄写fft，决定noi之前一定要把fft倒背如流...

然后写了一发bzoj3456，分治fft[tex]n=100000[/tex]跑了20s真是好评，多项式除法那种不优美的东西我才不写呢~~(其实是不会)~~。

bzoj3820 有趣的hash，每次随机两个hash，将hash值相同的放一起暴力，每次可以将规模缩小[tex]\frac{1}{9}[/tex]，于是就是[tex]O(NL)[/tex]的啦！

7.9

bzoj2961 真是不说啥了...调了一个上午发现去掉个inline就A了...谁能告诉我这是啥情况...

bzoj3992 有趣的题。因为[tex]m[/tex]是质数，所以一定存在原根，于是可以将乘法转化为加法。列出递推式以后可以快速幂+fft优化。

7.10

bzoj3991 答案显然是dfs序相邻的点距离之和加上首尾两个点距离。

bzoj4173 神结论题...不说啥了...数学真是神奇...

uoj36 首先消元，然后暴力枚举选出来的[tex]k[/tex]位，用一个大状压dp计算贡献。

7.11

bzoj4158 建出最短路树，建最小生成树。

bzoj4003 打标记的左偏树，写起来还是很好写的。

7.12

决定补一发数论。

bzoj3434 好神的数论题...大概就是莫比乌斯反演搞一下，最后发现推出来的式子是一个[tex]n[/tex]次多项式，根据[tex]\lfloor \frac{n}{i} \rfloor[/tex]只有[tex]\sqrt n[/tex]种取值的性质预处理搞一下就行了。然而uoj上只要跑5s，bzoj上却10s勉强卡过去真是差评...

bzoj4184 感觉自己对分治的理解还是太狭隘了，这种静态很好做的题如果要动态维护显然直接套一层分治啊，时间复杂度[tex]O(30n\log n)[/tex]真是暴力。

bzoj3309 厉害的数论题。估计考场上我就只能打表找规律了？

7.13

bzoj3739 更厉害的数论题，复杂度真是神奇...

bzoj3560 sb数论题都不会做感觉没救了T_T

bzoj4116 有趣的图论题...我居然会写tarjan...

7.14

赛前无趣，随便想了点题。

回忆了一下前几年noi的题，发现好像都没有把握能Au，感觉我已经看到结局了。

下午pear，csx，yepro讲了一些OI相关的东西...

45天就这么过去了呢...虽然说不上充实至少是快乐的回忆吧...NOI bless all...