GDOI

刚参加完GDOI2012, 也就是广东省信息学省队选拔. 考的成绩一塌糊涂. 我又拿到了三等奖; 自然, 之前设下的二等以上的目标没有实现. 庆幸的是, 我考得没比去年差.

这次比赛又是在二中举办, 于是我一个月内第二次住进那的女生宿舍, 真是… 我也算轻车熟路的在校园里游荡. 不过这回没了志愿者, 校园空荡荡的.

Day 1
tri(30)+string(70)+road(20)+digit(100)+magicka(没交)=220

第一题要求给出N根木棍(长度为整数, 不超过20), 取若干, 拼出面积最大的直角三角形.

我没想到什么好的办法, 直接状态压缩生成所有可能组成的边的长度(并记录使用的棍编号), 然后暴搜直角边查找长边, 用位运算判断有没有用重复的棒. 结果过了30%(?)的点.

正解好像是高级数学方法, 我没想到也罢. 不过一个小优化我竟然没想到, 太失败了. 程序应该预处理出所有合法的勾股数对, 然后f[i,j]={k(i^2+j^2=k^2)或-1(otherwise)}

第二题要求找某字符串的所有子串中第k大的串. 正解是用后缀数组找后缀的前缀. 我比赛时有些类似的想法, 可没实现出来.

我写了个堆来解, 将子串随机入堆. 因为串很长, 每个结点只记录了子串的起始和结束位置. 很可惜, 自己写的compareTo函数只是朴素的比较(甚至没有记忆化), 很容易就超时了.

第三题给出一个无向图, 要求给出一个方案, 加入最短的边使整个图成为双连通分支(删除任意一边不破坏整体连通性).

正解是通过对现有双连通分量缩点求出一无向图中所有的关键路径(桥边), 然后对这棵树进行处理, 给出方案. 我缩点不熟, 使用的是穷举删边的方法, 因为N<1000, 也能给出来. 然后正解用数学方法直接O(N)或者O(N*log(N))给答案(叶子节点交叉配对), 我却得用贪心的思想进行N次DFS找到树的直径并删除. 尽管低效, 加修正项后能出答案. 最后得了20%的点.

第四题很有趣, 给出1-N之间所有整数中0-9各个数位出现的总次数, 要求N.

我一开始看漏了条件”若没有N符合, 输出-1″, 想了一会后给出了很奇葩的算法: 10个数加起来, 用位数总和反推回数字个数. 对所有k位整数, 数位个数和是k*10^(k-1)*9, 很简单. 用输入的和减去1位, 2位, 3位…的位数和, 不够减时, 拿剩下的除以位数再加上999…9就ok了. 因为各个输入是10^512级别的, 我花了半个小时写出了自己的高精度对象和操作库(只有加, 减, 比较, 除普通整数, 再加上特意写的”bitShiftLeft”或者说”decimalShiftLeft”).

事实上正解也是先推位数, 然后从高往低逐位推, 时间复杂度和用N推出十个数一样. 可是, 能想出那样的公式实在难. 当我讲完算法后, 我坦白自己根本没写检验算法(其实也不好写), 输-1的点肯定就丢了. 这时, 卢彦丞大牛举手说: “没事的, 不可能有多少-1的, 他们不会给蒙-1的人骗到很多个点的.” 出题的人看着我露出了诡异的笑容, 我以为会有5个-1, 死惨了. 可成绩发下来时我惊呆了, 竟然一个都没有(而且大部分点都是0.01s或0.02s). 这样水过的感觉很像GDKOI那次, 水算法和奇葩思想骗到难题AC.

第五题是组合魔法, 不同的魔法之间的属性会互相影响. 我考试出来一直耿耿于怀的是, 自己已经想到了用位运算保存状态并用DP解决, 但敲完了没调完. 但是讲评的时候才知道, 那只是算法Level.1(比Level.0的穷举好一些), 后面还有Level.2, Level3的变态思想才能全过. 于是, 我也感觉好了些.

Day 2 stack(10)+mmm(没交)+daze(0)+game(50)+chess(0)=60

第一题堆积木, 要从顶上插入某个”颜色”(小写字母)的积木, 完成查询和删除操作.

我选择用平衡树实现. 因为对各个颜色都要处理, 每个节点记录了27个子树节点计数值, 我可能因此爆了不少内存. 有人是开了27个树. 更好的算法是用27个树状数组, 删除只做标记, 并且巧妙的实现在树状数组中的二分查找.

第二题是写工字, 要在方格纸区域中(每格有权值)写一个”工”, 上下一样宽即可, 粗细不限; 程序还要接受更新某格权值的指令.

我想自己写出来工字型的实现时间不够, 就直接放弃了. 讲题的时候出题者说他本来把这题当水题的, 谁之全场无人AC, 平均分四点几分. 正解每个状态要维护60个值, 5个工字形放法*12个分裂开的形状. 写完恐怕得几个小时.

第三题是”东方非想天则”, 我一开始还以为题目名是乱遍的, 没想到真有这个游戏. 题目要求出最大伤害值的连招, 每次 Di(伤害值)要乘以之前的R(初始1.0), Ri会稍后累乘到R上, Pi也会累加(不能超过100%).

实在想不出怎么用动归解决问题. 因为无法确定顺序, 我又不敢写穷举排列, 就写了个不断随即交换的暴搜, 结果啥都没过. 事实上, 顺序一定是按Di/(1-Ri)排列的, 黄施霖在考试时就想到了这点, 不愧大牛. 可是出题者表示其实有个坑, 连击的最后一招是不用管Ri的.

第四题是滚珠迷宫, 在4*4的方格内放几个小球(最多8个), 可以将迷宫倾斜使球往上下左右滚动(撞东西为止), 走若干步后掉进各自的洞里.

我已经想到了用状态压缩(x4,y4,8个球, 刚好压缩进一个32位整数), 也写出了BFS. 上台讲题时出题者表示这便是正解. 可惜我考虑不周, 有些细节没注意(比如球进洞后将不再影响他人滚动, 我只标记了忽略那个球, 忘了写忽略洞), 最后错了一半的点.

最后一题是AB棋, 规则是在一维棋盘移动棋子, 可以一次往左移独立的一颗或者让一颗跳过左边相邻的一颗棋子. 棋盘左侧有边界, 无法移动者输, 求最佳策略下先手赢还是后手赢.

数据规模是棋盘的宽度小于10000, 肯定不是模拟. 我画了半天也没找到规律, 只好放掉, 蒙. 有30%的数据规定所有棋子独立(初始时不相邻), 我也想到了算法, 写进程序. 可是不知怎么的, 输出文件名竟然错了. 复评时改了后答案也全错光了, 哎. 这次两天的考试一共280/1000, 真是挺令自己失望的. 如果第二天能冷静点, 说不定结果能翻倍. 不过不管怎么说, 成绩是多少就是多少, 吸取教训即可: 不要老想着做所有的题, 这可不是市队选拔第一天.

考完这次比赛, 对我们而言赛季结束, 而我也算是退役了. 郭教授今天还对我说”高二了? 没事, 大学继续玩吗.” 信息学虽然没给我带来什么荣誉, 但却让我学会了很多编程的思想, 我从中真的受益良多. 虽然这并非是一次完美的谢幕–更像是Crash&Burn, 但我依然觉得整个中学阶段玩信息学奥赛的过程是一段很美好的回忆.

2012 年 05 月 01 日

OI, 竞赛

叽叽歪歪