BJOI2019游记

直接进入正题吧……临模拟赛之前发烧了 ## day 1 一早上起来便感觉发烧烧的轻了些，于是莫名激动，虽然妈妈一直让我再休息几天……但最后还是让我去考场了。 到了考场，明明我记得上一届的学长说省选用windows啊？为什么一个大大的noi linux放在前面？我noip以后就把noi linux全删了来着…… 最开始说的是9:00开考，但是由于各种各样的原因，拖到了9:30，并且……让我们重启并再windows下考试？希望以后的几天也是这样，嘛。 一看试题pdf，写的是什么“山东一轮集训”，似乎是最开始的试题出锅了临时换掉的（虽说最后这套题的spj也出锅了233） 总之，今天的集训槽点好多…… 开始做题。 t1名字叫"弦形袋鼠"，最开始没有读懂这个题目名称啥意思……出考场一想，这玩意谐音一下不就是线性代数吗…… 题意差不多是给一个A\*B的矩阵，这个矩阵可以被拆成若干A\*1与1\*B的矩阵相乘再相加(每个A\*1的矩阵和1\*B的矩阵乘完都会变成一个A\*B的矩阵，之后再把乘完获得的矩阵加起来)，问你最少由多少个相加可以获得这个矩阵。（只要求输出个数，没有要求构造） 一脸不会。跑去t2 t2好像叫“圣城鼠”。 感谢神鱼的题意简述: 输入一个k，然后你输出一个n(n<=5\*k)，从n个点的完全图中找出k个生成树，使得： 1、任意两棵树没有重复的边 2、任意两棵树中u->v的路径经过的点集交集只有{u,v} 胡乱尝试各种方案……链，菊花图……似乎都不行…… 最后魔改了一下菊花图的情况……似乎可行？胡乱写写，感觉心里无比的慌，但是也没管这题去t3了。 差不多这个时候，把水瓶里的水全喝完了。 t3是原题，[洛谷P2282 [HNOI2003]历史年份](https://www.luogu.org/problemnew/show/P2282)，只不过没有多组测试数据，把n改成100000了。该过的依然能过。 想到了二分和hash，但是没想到先从头扫一遍再从尾扫回去的做法…… 只是想从尾扫过去，如何保证最后一位最小呢……二分呗……于是便把复杂度变成了n(log^3n)。应该1000的点还是可以过的吧……之后为了卡过时限，加了许许多多我也不知道正确性的剪枝（最后来看似乎把一些不该剪的剪掉了），自己造了一波数据，看起来跑的都是对的，测了下1e5的测试点也跑的飞起，于是便迷之自信……回去看t1…… 到考试结束也没玩出来t1,甚至都不知道样例是怎么构造出来的…… 中午饭挺好吃的，但是因为发烧……大概中午开始，就一直渴的不行。 下午讲题。t1居然就是输出线性无关的极大行向量个数，令人感到窒息。仔细想想……似乎也挺有道理的，但是我不会构造。 t2讲题的同学说了一个双菊花图的做法，并没听懂那种构造方法，但是觉得我自己没错(迷之自信+1) t3正解是从头扫一遍再从尾开扫。差不多理解了。挺巧妙地做法。 后面讲网络流，前面都（做过）还好，后面两个一到各种模型就懵掉了。一堆完全没有听说过的术语扑面而来。网上搜了一波，了解了个七七八八，但是就在网上搜题的工夫，题就讲完了…… 后来看成绩，t3莫名爆零，t2搞过去了(听说是spj有问题？)，t1乱搞同样爆零了。 出了首师附，紧急找水……一路走到地铁上，中间也再没见过卖水的地方。 地铁上看到自动售货机，那个激动啊……用手机仅存的电量买了售货机里仅存的冰红茶，咕嘟咕嘟往下灌（非规范操作，请勿学习），一瓶喝完了甚至还没喝够，又买了一瓶在路上备着。 地铁走到一半就开始有点肚子疼，并且似乎脑袋渐渐热起来了。一定要规范喝水啊。 回到家一测，就又是38度。 ## day 2 早上顶着病去的。 今天丝毫没有锅……noi linux是正常的，题目也是正常的，一帆风顺（？）的开始做题了。 似乎今天的题目神鱼传到洛谷题库里面了，那我就不简述题意了吧。 [t1](https://www.luogu.org/problemnew/show/P5297)看到题，各种炮台各种障碍还有反射的东西，看着就不怎么像可以做的题。当时直接过了。 [t2](https://www.luogu.org/problemnew/show/P5296)看着前40分都不难的样子……其他的像是个生成函数+矩阵树定理的题（事实证明正解确实是这个），但是式子写完了不会推。 [t3](https://www.luogu.org/problemnew/show/P5295)马上让我想到了去年北京省选的day1t3，就是在图上找规律呗……玩了将近半小时发现是V<2E-2，之后……判断每一个点双是否满足这个限制？还是边双啊？仔细(胡乱)分析一波发现似乎是点双，于是就写了。 回去看t1，每一个空地必须被上下左右之中的一个打到，并且不能被上下同时打到，不能被左右同时打到，这是个什么啊？ 在图上胡乱搜了一波，判了一下无解和炮台打炮台的状态……似乎题目的限制满足的差不多了？还有一个限制说的是空地必须被一个炮台打到啊……假设没有炮台打炮台，那么要不然左右的炮台横过来，要不上下的炮台竖过来，这是……2-sat? 于是自己就搞了个2-sat上去……2-sat忘了怎么输出方案了，于是出了好几个数据，dfn，low，col一个数组一个数组试，最后试出来了似乎是输出color编号小的那个。基础知识不过关啊。 再回到第二题的时候已经只有30分钟了，于是放弃推式子直接写了40分暴力分。 考完试似乎身体好了一些？实在好对不起旁边听我咳嗽一上午的仁兄们啊…… 下午还没有讲题评测结果就出来了。t3莫名爆零，本来慌得不行的t1反而a掉了？t2部分分似乎写炸了。我好菜啊部分分都炸。 拿了130分……居然排到了rk5？看着下面120一堆110一堆……并不清楚他们都哪里写错了。 似乎好多人的t1都码炸了……于是心里愈发感觉自己好幸运啊。~~比赛前这种细节题就没有不调炸的。~~ 讲题的时候，发现t3居然是E-2V最大的子图……凭什么找点双会爆零啊……明明好多人乱搞拿了不少分的……（被针对了.jpg） t2选择写暴力是正确的，反正那个式子我也推不出来。出题人讲了一遍也没听懂些什么。 希望考试的时候也能有t1这样的“细节很多”的题，并且我依然能凑巧a掉它吧。 之后讲了一些奇奇怪怪的数据结构，超哥线段树，fhqtreap内存回收，kd-tree。自认为数据结构还不算差就水过去了。炉石从4打到了2。 ## day 3 说是day2和day3……但其实中间是隔了一个星期的。周一在学校颓了一天，到了晚上体温又不受控制了，周二周三歇了两天才好。周四周五继续颓废地刷着题。 和前两天的流程差不多，直接说题目吧。后来听讲题人说是COCI 2019的题。 （upd:后来神鱼又把题目放洛谷题库了，编号从P5036到P5038） t1题目意思差不多是给一个n\*m的矩阵，每一步只能向下或者向右走，求从左上角走到右下角，并且经过的权值之积小于x的方案数。n,m<=100,x<=100000。 一脸不会做，直接跳了。 t2题意懒得简述了，差不多是一个细节讨论很麻烦的一道点分治。题目描述的非常明显，基本读完题就能看出来是个点分治。 （听说要纠正一些说法的问题：不能叫"是个点分治"，要叫"点分治可做"） t3题目意思是给一个n给一个k，表示有n个物品，k次拿物品的机会。n,k<=100000 每次拿物品，假设拿之前还剩i个，一下子拿走了j个，那样可以获得i/j的收益。求最大收益。 读完题了。看起来t2就像是之前所说的“细节很多”的题了……于是上来先肝t2 差不多一个小时不到就敲完了，一遍过了样例，心里想着待会再回来看又没有其他错误，于是跑去看t1。 t1smg啊……没有想出暴力以外的做法。到考试结束也没有。 t3有一个明显的O(nk^2)的暴力。也因为单调性，明显可以优化到O(nklogk)。但是因为我想AC啊，于是我敲了一个O(玄学)的随机化贪心。 后来t3就爆零了。 后来吃饭的时候听其他人在聊wqs二分。 wqs二分？ 似乎是可以做的诶……wqs二分，转移的时候二分优化下转移，就可以做到O(nlogklogs)了(s表示我也不知道应该log什么，总之是两个log级别的复杂度) 似乎就……可以过了？ 下午讲题。似乎t3正解确实是wqs二分+普通二分啊。t2全场A的感觉。 t1是一个整除分块，通过整除分块压缩状态，保证状态只有nmsqrt(x)个，复杂度就是正确的了。 t2似乎都没怎么讲，说了下是树分治就过了。 最后发现t1也炸掉了，于是只有t2的100分……排到了25名。（似乎考场有24个人切了t2） 之后选了一些其他COCI的题讲讲…… 有些比较好玩的事吧： 讲题的同学面对一道n<=1000的题，从容不迫的口胡出了一个O(n^12)的做法赢得全场鼓掌。后来被前排的某些同学优化到了O(n^8)，再次赢得全场鼓掌。大家都tql。 ## day 4 出了下十二省联考day1的原题。似乎大家都做过啊……似乎组织者也没有当作一次模拟赛，单独是“让大家练习一下”。 同时也把数据发下来了……不只是t3的数据，是所有的数据…… 看见前面的小伙伴打开了洛谷啊，loj啊等等网页，才发现机房是有网的。去loj交了下t1异或粽子。 后来自己摸索出了如何在noi linux上登陆新版洛谷。 干货:网页填(www.luogu.org/login)就可以了 肝了半天的t3，然后又去玩t2。写了180+行，第二天才调出来。 下午是出题人“之一”为我们讲题。这个老师比较能聊，似乎一下午除了休息，全程都在讲东西，课堂气氛也活跃不少。 有趣的事情自然也挺多的。 惊奇的发现noi linux上是有python的……并且如果胆子大还可以用system("python")这样稀奇古怪的操作水过去高精度的题。 因为各个省评测机速度不同，会给不同的限制时间，说到这里讲题人描述了下因某个省采用某6块钱的cpu而带来的奇妙遭遇。 下个星期就要真刀真枪开干了呢。这几场考试考下来发现自己dp真的太弱了。考了4道dp的题吧，4道全部爆零，连部分分都没。回去刷dp。 ## day 5 【BJOI2019题目解析】