分类： 游记

Day 0

报到去了，拿了一些材料和胸牌，还有一件酷酷的衣服，之后去酒店办入住了，晚上领了参赛的密码条，早早就睡觉去了。

Day 1

正式比赛的第一天，因为抱着已经退役就来玩玩的心态，还不算特别紧张，心想只要别空手而归，拿到奖就好。和同学聊了会天就前往考场了。

我所在的考场是篮球馆，只不过因为考试的缘故，摆放了一排排的电脑。我迅速找到自己的座位后，就翻开了纸质版试题。惊喜地发现竟然有一道提交答案题，看来今天的比赛有得玩了。

先看第一题吧，第一题的题意是，给定一个n*m*l的三位长方体，一个位置是极大的当且仅当该位置上的数，比至少有一维坐标相同的位置上的数都大。现将1至n*m*l这些数填入这个长方体，求恰好有k个极大位置的概率。

拿到这题后，感觉自己有点思路，又好像什么都写不出来，算了，先看第二题吧。

第二题的题意是，给定n个[1,D]的随机变量，求其中至少有m对变量值相同的概率。

怎么又是一道概率题？？不过相比于第一题，这一道题感觉更好做一点，于是花了一小会时间就写出了一个可以拿到48分的O(nD)的DP，发现递推式可以矩阵乘法加速转移，可以多获得12分，先放着，等之后有时间了再写。又发现了m=0和m=1这8分的特殊情况，好像非常简单，就把这8分拿到手了。

第三题是一道提交答案题，题意是，给定n个矩形，这些矩形可以不重叠随意摆放，也可以旋转90度，有两种问题类型。第一种是要求你给出一个范围，以及这n个矩形的放置方法，使得所有矩形都在你给出的范围之内，范围面积越小得分越高；第二种是给定一个范围，让你尽可能多的把矩形塞到这个范围里去，塞的矩形越多，得分越高。

这道题一共十个测试点，都已经给选手了。我先打开了第一个点，发现可以手玩出这个点，于是花了大约十多分钟，把这个点玩出来了，获得10分。

又看到了第四个点，这个点给出的矩形长宽都在一和四之间，给出的范围也是高度为4，感觉把边长出现3的矩形拼一拼就可以了，花了二十多分钟，获得10分。

接下来的点手玩就有点麻烦了，我就写了一个随机化算法跑其他的点。我先将所有矩形随机排序，随机旋转，然后把他们按顺序放入范围中，然后重复这个过程多次，取过程中最大值。

实际使用起来效果还不错，第二个点，第三个点和第六个点各跑出来了9分，第八个点和第九个点分别跑出来了4和5分，第5,7,10个点数据太大了，跑不出来，就0分。

最后总共得了10+10+9+9+9+5+4=56分，感觉还不错，今天就已经有112分了。

最后一个小时又回过头来看了看第一题，感觉第一题要是爆零感觉不太好，于是终于想出来一个30分暴力算法。

最后评测完发现，真的一分没丢，142分全部拿到，感觉考的应该还行？？

Day 2

既然day1考的还不错，那day2就稳一点吧，把所有暴力分拿到就收手吧。

去了综合教室考试，那里的电脑都是内嵌在桌子上的，感觉好奇怪，没见过。

翻开第一题，题意是，给定n条平面直角坐标系上的线段，求把这些线段包起来的最小长度。

糟糕，不太妙啊，一大早上来了个计算几何题，凸包的求法我也快忘了啊，于是我就暴力求凸包，配合状压DP枚举子集获得30分，又写了个随机乱搞上去，希望能得到比30分更多的分数。

第二题是给定一个整数m，以及字符串S，定义一个与S等长，并且字典序小于S的字符串是好串，让你求长度为m的串中，无限循环后存在子串是好串的串的数量。

没啥思路，只能获得10分，直接看第三题。

第三题题意挺长的就不说了，反正又是一道概率题，看了几个小时一筹莫展，获得0分，真的一点分都拿不到，我是不是凉了啊。。。

评测完了，第一题乱搞失败了，就获得30分，其他也一分没丢（就这么点分还能怎么丢啊？？），获得40分。

两天总分182，董哥总分200多。

Day 3

颁奖典礼。

感觉表演的节目效果不错，就是颁奖的时候一个个念名字也太蠢了。得知铜牌线九十多分，银牌线一百四十多分，金牌两百多分，我离金牌只差20多分，感觉d1t3和d2t1能搞出更多分就能金了。董哥有点幸运啊，正好就比金牌线多两分。希望接下来的APIO也能获得不错的成绩~

(后续：APIO2019和APIO2018一样，都拿了个铜牌

Day -4

市里训练的模拟赛，T1压根没看懂题，就先跳过看T2，T2裸的构造，半个小时就搞出来了，写了个正反鸡爪。T3是个限制条件挺多的DP，暴力写炸了，T1一直就没看懂题，不知道出题人想说啥，表示理解不了。最后就T2A了，获得100分。

Day -3

第二次模拟赛，T1题意是一个网格图，让你设定炮塔，炮塔可以选择横着打或竖着打，还有镜子可以反射炮弹，求方案让炮塔覆盖所有空地，且不会互相攻击。好像是个网络流，捣鼓了一会，发现好像不能表示选横着打还是竖着打，暴力只有状压DP有分，还挺难写的，于是跳过。

T2是完全图边权矩阵生成树什么求和，一看就不可做，什么多项式弄来弄去的，可能还得矩阵树一波，不会写，打了40分暴力，收手。

T3是给定一个图，问是否能将边黑白染色，使得黑白边都各自不成环。看完题依然先把暴力打了，发现了一个有趣的性质：只要存在一个导出子图不合法，整个图就不合法。逆命题好像也成立，利用这个性质配合最大权闭合子图写出了拿到95分的错误算法，跟正解仅有一步之差。

总分135，排名还挺高的。

Day -2

第三次模拟赛，T1是给定一个n*m矩阵，求左上角走到右下角经过数的积大于给定数的路径条数。拿到题就想到了一条性质，最多只会乘log次，围绕这个性质想了想，感觉值不会太多，就拿vector暴力转移，本地随机数据感觉快的飞起。

T2是统计路径条数，没想到点分治，就把40分的链写了。

T3是很显然的一个DP，加了点剪枝优化到了n方，应该能拿40分。

总分74，T3数据问题只拿到了34分。不过好像大家T2全A了！？有点丢人。。。第三题好像是什么wqs二分，我也不会。

Day -1

没有模拟赛 ，拿了十二省联考Day1的题给我们做，把T1异或粽子写了调了就溜了，下午听听讲课后就回家了。

Day 1

正式省选第一天，T1是给一个有残缺位的数字串，和一些匹配串，每种匹配串每次匹配都会使当前数乘上匹配串的权值，最后的权值是出现的匹配串的权值的积开总匹配次数次方，输出使最后权值最大的数字串。第一眼就是AC自动机上DP，写了半天突然发现好像转移有点问题，没法维护开n次方，突然想到将权值取对数就变成了求平均数问题，想到自闭也没想出来如何维护平均数，换了暴力DP分交上去了。

T2是什么斐波那契数列和一个神秘数列的组合数区间求和问题，没发现什么性质，加上T1心态有点爆炸，就写了10分就交上去了。

T3是一个网格图，有一些加墙和删墙的操作，询问两点之间扶着墙走的距离，这题暴力就写的我恶心的很，而且就10分，写完了过了样例交上去了。

最后T1暴力获得15分，T2 10分，T3果然暴力写炸了，总分就25分了，感觉凉成尸体了。T1维护平均数只要分数规划二分答案即可，考场上脑袋想炸了也没想到二分答案，想到了这题就做完了不是吗？？如果获得110分就勉强活了。。

Day 2

T1弱智DP，开场AC，本机跑的飞快。打开T2，光在镜子间无限反射问题，高斯消元法n三次方能搞出50分，写完了发现矩阵挺稀疏的能优化到n方，搞到70分收手了。T3从打开题到考试结束都没有想出任何靠谱多项式算法，都被自己hack了，写了7分问号复杂度暴力交上去了。

嗯，还挺稳。。写了177分就拿到了177分。不过，好像T2也是个弱智题，全场AC的那种，高斯消元矩阵稀疏到甚至能线性复杂度解方程，甚至还有更弱智的做法。T3正确的贪心好像能有47分，人均200+，屈辱退役。。看来还是我太菜了。。只能安心搞文化课了（哭哭。。

北京冬令营

冬令营的题是杜教出的，难度很大。我首先花了半个小时理解了一下题意，三道题的规则看起来都很类似，并且难度都很难。既然看不出难度顺序那就按部就班从第一题开始思考。

第一题是给出现有方案问最小改变几步即可让现有方案合法。我首先看了一眼部分分，还是有一些可以拿到的。我先试着自己出了几组小数据，了解了一下题目，尝试着先总结出一些规律，但是确实这一题没有任何规律可言。既然找不出规律那就先写暴力吧，看看后两题之后还有没有时间推敲一下正解。暴力已经打好了，样例调了半个小时，可是确实复杂度太高了，真的是n*m的n*m次方的广搜，但是得分太少了，我准备拿一些部分分再去看后两题，于是我写了一个特殊数据暴力就去看第二题了。

第二题是让你直接构造一组方案，并且合法性判断由加法变为异或了。拿到这题后真的是除了最暴力的暴力一点头绪也没有，打了一个暴力走去第三题了。

第三题是让你求出类似总方案数的值，此时还有一个半小时就结束了，而且这一题的暴力貌似非常好打，于是先把暴力打上，样例过了，然后尝试想正解。这种难度的考试要是A了一道题立马就能前几名了。但是杜教的题哪能这么简单让你A？我耗尽了时间也没能想出一点靠谱的方法，查了查文件名就只好交卷了。

结果我有点记不清了，好像是我拿了两个暴力分，一共30分，也就二十来名吧，省选努力A点题吧。

省选一试

抱着A题的信心步入赛场。

拿到题后立马看到了第三题，树上路径求和，打了多年树剖板子的我立马花了半个小时就打好了，样例一次就过了。心想这肯定正解了啊，复杂度肯定O能过啊，于是写了暴力和对拍保证了正确性后开始攻战前两题。

第一题是给你一个二进制的串，每次两个操作，修改某一位的值和查询一段区间有多少子串在重新排列后是三的倍数。我一想这重新排列其实有关的就是0和1的个数问题，马上打了个表把规律找出来了，那怎么利用规律呢，想到了n三次方预处理，那就是暴力分啊，于是赶紧了一下每次修改O1，每次查询On，总共复杂度n平方级别的，足够拿到前百分之五十的点了，那今天就已经有了150分了。处理完第一题已经过去两个小时了。

第二题是图染色问题，找了一个小时的规律，实在是找不到，于是打了一个最暴力的暴力，期望得分20分。

还有一个多小时，突然想到第一题带修改，查询，那么莫队应该可行！于是我立马开始思考这道题的莫队应当怎么实现。眼看着这题马上就能A了，但是我还是在处理一个细节时发生了问题。原来是变量定义的问题，我应当定义别的意义的变量。修改后开始调样例，调了一个半小时没调过！我这才发现莫队算法在这题的实现上有着致命的漏洞，有一些值是没有办法维护的，我只能放弃了写了一个多小时的莫队算法，交了50分的n平方算法。期望得分有170分。

吃饭时突然想到，第三题貌似树剖是nlogn的，我套的树状数组也带着一个logn，总体下来有nlog方n，最大的点三十万，再乘上题目里的常数可能会T！同学最后算了log方理论上是能过的，但是我蠢了，明明可以O1前缀和维护的，我却没看见没有修改操作而写了一个logn树状数组，当时还想着我还可以把树剖套的线段树改成树状数组常数可能小，简直是有点蠢了。

最后结果下来时，我看到我第三题其实是A了的，这我才放心了。但是下一秒，我看见了第一题的0分，我立马就悲剧了，讲题是我才明白这题细节贼多，而我考虑到的只差了一个细节，正好样例还不包含这个细节，一下50分变0分，悲剧了。第二题也因为图的染色细节丢了第二个点的暴力分，只得到了10分，讲题时说这道题部分分使用特判写的，也是贼恶心，正解也是贼恶心。省选一试就拿了110分，三十名。只有明天A道题来翻盘了。

省选二试

A题说的容易，做出来是真正困难。

拿到题后我惊奇地发现第一题是一道提交答案题！提交答案题非正解就是比谁更能手玩数据了呗。再一看题面，是一道纯种智商题，题意就是两个人猜数，裁判生成两个数，把两个数的积告诉A，和告诉B。A和B只要说了几次不知道就能猜出这两个数。让你出两个数，能让A和B说出指定次数的不知道。看完题我就有想法了，这不就是乘积和和有几种拆分的问题嘛。可惜这题思维含量太高了，我低估了这道题。A和B的思维是互相影响的，就是说A必须要猜到B的想法，而B也要根据A的回答脑补一堆情况。两层我就已经快要想不明白了，最大的层数有15层，那岂不是得和出题人心有灵犀才能A掉这道题啊？于是我把我认为的两层的解打出来了，之后就去看第二题了。

第二题是一道数据结构题，就是给你一条链，每次两种操作，把u到v的路径上的值都加上d和查询长度为l到r的路径的和的和。一开始我想用线段树维护维护，但是这个想法立马就被我否决了，每个点对于l到r的加权不一致，且每次询问的l，r也都不尽相同。要是真用线段树维护，那也得建n个线段树，空间时间保准爆炸。于是我先打了加了预处理每个点对于每个长度的加权，最后查询时On处理，总复杂度n平方，能拿到40分。我先去看看第三题。

第三题是一道期望题，期望题我做的不是很多，处理方法也只是略知一二。我开始研究这道题的概率DP方程。经过一个小时的奋战，成功推出了式子。既然推出了式子就可以尝试A掉这道题了，于是我开始展开这个式子，突然发现fn是关于fn+1到f0的，就是这些式子之间不能用递推来算f值。我又突然落入迷茫之中，既然无法递推这个式子，那么我不但写不了正解，连暴力都很难打出。我一直在想这道题暴力应该如何打，但就是因为这些式子互相影响，就算记忆化搜索也是无限递归下去的。但是这道题总不能不做，我开始对n小于等于3的数据每一组进行手动计算，也就2*2*3*3=36种。大概算到五六种时，突然发现我这就是在浪费时间！真正要算完全部36种结果两个小时也不为过，我急忙写了一些特判就关掉了第三题。我应当考虑如何在我现有的水平下拿到更多的分。于是距离结束还有一个小时的时候，我又重新关注了第二题的大数据部分分。其中确实有一些简单就能拿到的部分分，拿了大约10分左右的部分分，检查了文件名就交卷了。

第一题智商题我明显对于某些情况讨论错误，40分两层的分数中我只拿到了12分，而第二题是最坑的，由于是一条链，我就直接拿线性结构直接维护了。但是路径上的两个端点可能是逆序的，你需要swap一下即可拿到40分。于是第二题我只拿到了特殊数据的5分，只能说在今后的学习与竞赛过程中再长点记性吧。第三题我的特判就是完全失败了，屈辱爆0。讲题时我才知道这一类期望题的暴力是可以拿高斯消元法来解式子的，只能说我还是太年轻了。

总结

其实这次省选我的联赛分数并不突出，再加上缺乏对于真正难题的思考，这次省选我就屈辱滚粗了。希望在2018年还是要多刷题，见识多了，做题的方法才能显现出来。下次联赛和省选还是努力吧，争取明年光荣进队而不是屈辱滚粗吧。