/ GDKOI

GDKOI2017

赛前准备

GDOI和GDKOI的组委会都是广东省里面的,我猜测GDKOI会对GDOI有一定的导向作用。所以准备好GDKOI还是蛮重要的。

稍微翻看一下前几年的题目,总结起来,有一些考点是每年必考的,比如说线段树(魔卡少女、看门狗)、网络流(这个很正常)。去年的题目考了好几道模板,没能早些学习信竞,可以说是一大遗憾。

在准备的时候的另一收获是《算法竞赛入门经典》和它的《训练指南》,这两本书对算法竞赛的总结真的是非常全面的,可以让初学者少走不少弯路。我入门用的是《信息学竞赛一本通》,宋新波老师主编的,感觉没有那么权威,很多NOIP考的内容也没有提到,更别说省选了。

每次比赛前总会认识到自己的不足:还有多少题目没做,还有多少知识点没学,还有多少算法没练习模板;赛后,实力一时提升,却又在嬉闹中逐渐荒废。

于是我只能先在比赛前下定决心好好刷BZOJ的题目,为省选冲刺做好准备。BZOJ(现更名大视野在线测评)的定位比较高端,不是初学者能随便做的,每一道都有一定的难度和编码时间,感觉比较符合我现在的需求。Thus,如果还发现有没掌握的地方,可以边学边完成,查漏补缺。

Day1

早上6点钟醒了一次,也许是紧张,也许是习惯了学校的作息。最后是6点50起的,一切比较顺利。

进场之后发现了几个.pyc文件,看了说明之后发现是组委会为了防止选手因提交格式出错而丢分,留下遗憾,编写了几个检查文件目录的脚本。十分用心,给组委会点个赞。

GDKOI没有给测试数据文件,这样在赛前准备就不太方便了:因为不知到题目名字,我只能在密码给出以后再创建子文件夹。

我创建了几个compile.bat来快速编译。我一般要在IDE编写完代码之后立刻编译,所以事实上没用上那几个脚本。

扫视了一下隔壁的情况:C++,中山纪念中学,gpedit,名字挺熟耳的,但是不认识。

晚了15分钟开始,不过不怎么影响。密码是zha.xi.de.le~。前15分钟看完所有题目,第三题比较有思路。稍微推了一下,抽象出来是一个环,每个点可以往左往右跳P或Q格,找欧拉回路数量。然后就做不出来了。

再看看第二题,发现题目实际上是想让我们求一个最长合法括号匹配子串,easy模式感觉要用类似manacher或扩展KMP的思路。先过。

第一题一般来说应该比较水,题设是QQ堂,还配了两张彩色图片,让人感觉眼前一亮。炮弹数量是3000,感觉O(n2)O(n^2)会爆,所以没有用我弟弟使用的并查集合并可以互相影响到的炮弹。想起精确覆盖的DLX算法,我决定试试链表。预处理出每个炮弹横向和竖向最近的炮弹,把距离大于spread的边砍掉。把P也看作炮弹,从P开始广搜,寻找所有能广搜到的炮弹中的时间最小值即为答案。设炮弹数量为MM,复杂度就是O(N2+M)O(N^2+M),妥妥的。调试却出了大问题,调整了很多个小错误之后,发现有重复入队的现象,永远是死循环。调试了40分钟找不出问题,我翻看了无数次vis数组,但是找不到出问题的地方,以至于我开始怀疑编译器出错了。

再看第二题,尝试O(n)O(n)处理出从每个点最多往后多少。设fif_ i为满足[i,fi)[i,f_ i)为合法括号字串的最大值。考虑状态转移:

  • ii为右括号:怎么都不可能符合,所以fi=if_ i=i
  • ii为左括号:
    • fi+1f_ {i+1}是右括号:match,fi=ffi+1+1f_ i=f_ {f_ {i+1}+1}
    • fi+1f_ {i+1}不是右括号:没有办法括起来,不可能以ii为合法串起点,所以fi=if_ i=i

这样就顺利解决了easy模式。hard模式还要思考思考。一开始简单的认为正反处理一遍f[]f[]之后讨论在每个位置插入括号,直接向两边扩展,搞定。后来发现了这样的反例:

(((())()())))(((()*)()())))

选择在*号位置插入((,用上面的方法是不行的,因为插入之后整个字符串都是合法的了。

在这个时候我切换回了第一题,一看:

vis[x][y]==true;

这个错误必须给我一个深刻的教训,不然辜负了我那40分钟。

第一题样例过了,输入输出OK(NOIP的教训),脑补了几个可能的数据点也都过了。实在没有时间写对拍,借口无论是熟练度还是失误,都只能说明我的实力有问题。

第二题也打算水过了,还是按照上面的思路扩展,碰到两边的括号能match上就两边同时扩展,然后在加上合法子串。为了加快速度,我预处理了从某个括号开始有多少个连续的括号,应该能水掉绝大多数的点。有一种数据是过不了的:

(()(()(()(()(()))())())())())(()(()(()(()(()*))())())())())

时间复杂度会退化到O(n2)O(n^2)。但是管不了那么多了。

这个时候出题人才进来说,假如说S1,S2S_ 1,S_ 2是合法串,那么S1S2S_ 1S_ 2是合法串。但是我在做的时候已经假设这个条件满足了,如果没改的话我就彻彻底底读错题了。

最后一个小时,我先看第4题。感觉上像背包问题,但是没有办法储存状态。只能深搜了。估计第一个点都会TLE。

第三题,考虑了很多,最后发现从0开始,每次跳p格,选择一些时候跳q格。然后为了保证能跳到每个点,跳了一个q之后就要把跳p能跳到的地方跳完再跳q,所以区别仅仅是一开始跳几个p之后再跳q。还有跳到某一个p构成的环之后往左跳还是往右跳。这个算法连样例都过不了,但是实在没什么办法了。

考试结束后,经我弟弟提醒,发现不一定要跳完p构成的环才能跳q,说明整个都出了很大问题。而且第二题的特殊数据可能会卡掉几个点。200无望了。

下午应该是两点半开始讲评,但是照例晚了。

qqt

第一题的解法一是随机输出一个数,因为答案只有-1,1-9十种,所以随便数出一个,期望得分有10分。难道是因为这道题实在是太水了没有什么不拿满分的做法才把这种做法当作部分分做法吗……

几个思路:

  • 从P点开始广搜,找所有能够涉及到的炸弹中时间最小的。和我的很像,但是它没有预处理。本以为会比我的算法慢,但是想一想,好像还快点。
  • 两两枚举,如果能互相影响到就合并,并查集维护。我弟弟用了这种。
  • 其他不记得了。

request

第二题想讲的人很多。我比较喜欢的一种思路是栈,左括号是-1,右括号是1,维护前缀和,区间和为0的子串满足条件。对于hard模式,区间和满足1Σ1-1\leq\Sigma\leq 1的就是满足条件的。但是这种做法是有问题的,因为可以先右括号再左括号,区间和一样为0.但是这种思路中值得学习的地方是如何查找满足条件的区间,这事实上不需要O(n2)O(n^2)来找,只要二分答案即可达到O(nlogn)O(n\log n)

正解是把前缀和函数的图像画出来,一座向上的山峰就是满足条件的区间。找出拐点之后合并。hard模式下就是在山峰之间添加东西,瞎搞看怎么样最优。我没怎么花时间想。

出题人说验题人的思路很巧妙,验题人和我的做法是一样的,但是我没听清楚DP怎么高效处理hard模式。

queue

每个点连4条无向边,像什么?像什么?像一个网格!从形式上看PQP\cdot Q也的确是一个矩形!

把每个点这么放:

0 p 2p 3p 4p ... (q-1)p
q q+p q+2p q+3p q+4p ... q+(q-1)p
2q 2q+p 2q+2p 2q+3p 2q+4p ... 2q+(q-1)p
...
(p-1)q (p-1)q+p (p-1)q+2p (p-1)q+3p (p-1)q+4p ... (p-1)q+(q-1)p

这样每个点就可以上下左右动了。和一般的网格图不同的地方是这个图是无限平铺平面的,从右边出去会回到左边,从下面出去会回到上面,其他方向同理。

然后要考虑回路数量。题目中给出P6P\leq 6,不就是插头DP嘛。把插头DP处理成矩阵形式转移,快速幂即可。

christmas

前50%的数据点里面v=109v=10^9,也就是只有一维的背包,在DP的时候fi,jf_ {i,j}储存一个二元组<socks,rest>socks储存袜子数量,rest储存最后一个袜子剩下的空间。然后更新的时候socks作为第一关键字,rest作为第二关键字比较。

一个满分做法也是用二元组来做的,状态也是fi,jf_ {i,j},剩下[i,j][i,j]的物品,

另一个满分做法:fi,jf_ {i,j}储存使用了ii个袜子,左边取到了第jj个礼物的时候右边最多取到的位置。
ii不变的时候,fi,jf_ {i,j}是随j递增而不下降的,所以可以用two pointer一类方法来解决递推。从i1i-1推到ii时比较麻烦:[j,fi1,j][j,fi,j][j',f_ {i-1,j'}]\rightarrow [j,f_ {i,j}],其中[j,j]+[fi,j,fi1,j][j',j]+[f_ {i,j},f_ {i-1,j'}]需要满足能装在一个袜子中的约束。可以转化为[1,j][1,j][1,j]-[1,j'][fi,j,n][fi1,j][f_ {i,j},n]-[f_ {i-1,j'}]。维护一下前缀后缀和就可以O(1)O(1)算出[1,j][1,j][fi,j,n][f_ {i,j},n],再搞个什么区间数据结构就可以解决查找jj'的问题。

小结

今天考试开始的时候心态十分好,没有慌张,除了调试的40分钟外时间分配的还可以。但是还有题目的水分没有领完。

题目 得分情况
qqt AAAAAAAAAA
request AAAAAAAAAAAAAAAAATTA
queue WWAWWWWWWW
christmas TTTTTTTTTT

queue应该是P=1的特判拿了一点分。今天总分200,排43名,没有很前,但也还说的过去。

Day2

有了昨天的经验,自我感觉今天的发挥应该会更好。毕竟去年省赛就是Day1爆零,Day2才有分数。

开考后还是先扫了一遍题目。第一题一看就是数学题,疯狂的数学统计。稍微想了一下,分了三种情况:

  • 两条边平行x轴或y轴
  • 一条边平行x轴
  • 一条边平行y轴

感觉后面会很难算,所以先move到第二题。

第二题第一眼感觉是LIS,然后发现是双关键字的,联想起昨天的christmas,但发现没有任何关联。估计DP做不了。

第三题理解题意之后就是要我们求一个数论的式子。我肠子都悔青了,怪自己考前没有突击一下线性筛和莫比乌斯反演。估计是做不出来了,但是还是想用欧拉函数试试:

x=1n1yx,gcd(x,y)=1(x+1)(y+1)\sum_{x=1}^{n}\sum_{1\leq y\leq x,gcd(x,y)=1}(x+1)(y+1)

=x=1n1yx,gcd(x,y)=1(xy+x+y+1)=\sum_{x=1}^{n}\sum_{1\leq y\leq x,gcd(x,y)=1}(xy+x+y+1)

后面的步骤没有什么意义,也是这几个式子推来推去。第一、三项不会O(n)求。

第四题一看就是代码题,想着用splay来模拟操作,后来改成了STL的set。前60%总是可以水过的吧?

翻回第二题,觉得贪心应该没问题,于是把一个人分为两个分数排序,从小到大选择,选上一个人之后这个人后面的那个分数就不能再选了。很快就敲完代码了。

但是回头一想,会不会有反例呢?GDKOI第二题不至于这么水吧……很快我就想到一个:

3 0
1 2
1 3
3 3

根据贪心,我们应该先选择第一个人的1,第二个人因为选不了1所以要选3,第三个人就没得选了。

所以考虑调整。怎么调整最划算?我想起了《训练指南》上的处理器分配问题。考虑网络流建模,起点到每个人连一条容量为1的边,每个人到每个分数连一条容量为1的边,每个分数到终点连一条容量为1的边,跑一遍最大流就是答案了。

等等,这不就是二分图吗?直接上匈牙利!虽然很久没写匈牙利了,但是写的还是挺顺利的,一遍调过了。还写了一个数据生成器,大数据感觉挺快的。先不管了。

再来看第一题。第一题的每种情况还分了三种:

  • 横偶竖奇
  • 横奇竖偶
  • 横偶竖偶

对于每一种情况,我们要找出横着选长度为偶数的区间的方法数。试验了几下,对于区间[0,n][0,n],长度为偶的区间数量为

02+12+22+...+n2\left\lfloor\frac{0}{2}\right\rfloor+\left\lfloor\frac{1}{2}\right\rfloor+\left\lfloor\frac{2}{2}\right\rfloor+...+\left\lfloor\frac{n}{2}\right\rfloor

长度为奇的区间数量为

12+22+32+...+n+12\left\lfloor\frac{1}{2}\right\rfloor+\left\lfloor\frac{2}{2}\right\rfloor+\left\lfloor\frac{3}{2}\right\rfloor+...+\left\lfloor\frac{n+1}{2}\right\rfloor

那我就记

f(x)=02+12+22+...+x2f(x)=\left\lfloor\frac{0}{2}\right\rfloor+\left\lfloor\frac{1}{2}\right\rfloor+\left\lfloor\frac{2}{2}\right\rfloor+...+\left\lfloor\frac{x}{2}\right\rfloor

预处理一些东西,写一些公式,就把第一题搞定了。

幸亏我这么晚才做第一题,组委会已经把第一题的数据更正了,不然我不知道我要调试到猴年马月才能调试完。

我把第三题水了。最后一个半小时,我开始码第四题。写啊写,只剩10分钟的时候,我写完了。天灵灵地灵灵保佑我一遍写对。我想太多了。5分钟时间根本不可能调试完。我为什么不直接写前20%暴力呢?特判一下就有40%了!

中午和深中众神吃饭,突然想到,在第四题里面,因为光线穿越只有一种可能,所以可以用splay维护整个光线会经过的序列。开传送门和拆墙就是合并splay了,如果有环,打个标记就好。为什么这么晚才想出来呢……

下午的讲评开始的时候,组委会失物招领了一阵。有身份证,有清凉油,还有一条谜一样的红领巾。这些个人物品的遗失其实应该是个人责任,但是组委会还是很贴心的帮我们收集起来,然后根据位置找到人。全场掌声雷动。

今天测评出的很快,结果也打完了。为了吊着我们的胃口,每讲完一道题才发一部分的成绩。我的运气向来不好,最后一批拿到。

memeda

正解没有很多技巧,还是需要分类讨论然后用容斥原理排除重复情况。

讲解现场有同学尝试用DP做70%数据,其优美程度甚至还不如直接正解。

whatever

题目要求找出一个严格单调序列,也就是找出有多少个不重复的战斗值。经过变换之后得到的的确是一个二分图匹配模型,但是出题人__特殊说明__了正统匈牙利算法是会被卡掉最后3个点的。如果用Dinic或者优化过的匈牙利就可以AC了。

关于匈牙利的优化:砍掉战斗值小于等于H的边之后,有一些人的度数为0,他们可以直接忽略(正统匈牙利也可以做到);但是如果有度数为1的点,这些点可以考虑优先选上,然后把这个人连接的战斗值连接的边剪掉,再看剩下的人中度数为1的点,进行类似处理。最后会剩下几个连通块,对于每一个连通块,可以根据霍尔定理证明因为左边的点数比右边的少,所以总存在一种方案保证左边的点可以全部选上。时间复杂度优化到O(n)O(n)

另一种跑得比标程快的解法要用到并查集。因为是二分图,所以连起来要不没有环,要不就只有奇环。可以把整张图看成是环上有树支链,支链中的因为没有环所以就要尽可能选上,最后处理一下环。我还没有想清楚这种做法的实现细节,但是先记录在这里吧。

task

归根到底就是要求:

x=1n1yx,gcd(x,y)=1(x+1)(y+1)\sum_{x=1}^{n}\sum_{1\leq y\leq x,gcd(x,y)=1}(x+1)(y+1)

=x=1n1yx,gcd(x,y)=1(xy+x+y+1)=\sum_{x=1}^{n}\sum_{1\leq y\leq x,gcd(x,y)=1}(xy+x+y+1)

=4+x=2n(ϕ(x)2m2+ϕ(x)2m+ϕ(m)+m)=4+\sum_{x=2}^{n}(\frac{\phi(x)}{2}m^2+\frac{\phi(x)}{2}m+\phi(m)+m)

我简单证明第三步的第三项,其他就可以类推出来。设1a<b1\leq a<b,则gcd(a,b)=1gcd(ba,b)=1gcd(a,b)=1\Rightarrow gcd(b-a,b)=1。也就是说在上面与xx互质的yy是成对出现的,而且每一对的和均为xx。所以只要把所有东西O(n)O(n)预处理出来,询问就可以O(1)O(1)回答了。这样能拿前面两个点,50分。

100%数据的做法有两种方向,一种是用欧拉函数,另一种是用莫比乌斯函数。因为什么都没听懂,所以记下来的笔记也十分散乱,没有办法整理起来。等以后有实力了再慢慢琢磨吧。

忘了题目id的第四题

前20分其实应该模拟就能水掉。错误的策略枉费了我一个多小时的时间还一分没拿。

还是左左讲题。把每一个格子拆成4个点,分别代表四个方向。记为(x,y,d)吧。可以发现,这些点出度和入度均为1,所有的操作都是在对这些边进行更改,但是一直满足出入度为1(撞到墙的除外)。这说明要维护的是一个链表,可以用splay维护。我觉得这个是一个非常好的思路,区间、链表这些有序而且还要经常变换的数据结构使用splay再适合不过了,单次操作复杂度比分块算法略胜一筹,降到了O(logn)O(\log n)。这样前60%的点都能过了。

格子数量太多,我们要进行优化。因为询问数量是在可以接受的范围之内的,所以分裂和合并实际能影响到的格子数量并不是很多。那么就离线合并所有不会分裂的格子,就能把节点数量压下来了。

中山纪中的大神翁文涛上去讲了我中午想到的方法。只不过切割环的情况我没有想清楚,他把切环分为两种情况:

  • 切割序列的两边:只要删除环标记即可
  • 切割序列的中间:删除环标记,从中间切开,换个顺序再合并起来。

他还说,题目没什么,就是很难打。这个代码量,实在令人望而生畏,也只有这样Day2满分的大神才能在考场上码完吧。

小结

memeda AAAAAAAAAA
whatever AAAAAAATTT
task WRR

最后一题因为名字没有想起来所以也忘了记录成绩。

第二天的实际分数170比预想的要低很多,主要是第二题出题人卡了标准算法,还有第三题题目没水成功。第三题的失误实在是不应该,说明在水分的时候必须要从原始式开始再推一遍。

结语

两天加起来的分数370,竟然排到了省23名,这个是我真的没想到的。尽管如此,省队之路还很漫长,最后两个月更不能掉以轻心。只愿我能光荣退役时,能够对自己说,我没有_因为虚度年华而悔恨;也没有_因为碌碌无为而羞愧