所以说我这样的蒟蒻已经退役了 (大雾), 但是还是要去一波 CTSC&APIO 的, 毕竟是一次难得的做 (tui) 题 (fei) 机会. 虽然说 D 类买活还是参考这两个成绩的, 但是总觉得还不是很靠谱, 所以退役什么的, 也基本已经是铁一般的事实了. 然而古人所谓 “属予作文以记之” 也不过如此, 我便不写滚粗记了, 改写游记, 毕竟这一阵还是很开心的~
这应该说是第一次去 “外地” 参加比赛吧...... 所以对酒店的环境还不是很熟悉. 虽然说各种事情都在意料之中, 不是很奇怪, 但是毕竟是新环境, 还需要一段时间适应.
5 月 7 日: 报到
第一天没有干什么实质上有意义的事情, 大概就是体验了一下八十中 (NOIP 考场, 其实早就很熟悉了) 的环境, 去吃两顿饭, 然后试一下机房的机器. 顺便说一下, 为了准备这两场考试似乎系统都刷成了原生 NOI Linux.
吐嘈一下新版的 NOI Linux 竟然不自带 Atom 实在是不够良心
八十中的食堂与我校的食堂比起来虽然可能小了一点, 但是可能是新手上路再加上比赛的缘故罢, 这里的伙食感觉还是比我校的食堂略好的. 按道理说我们是不应该去别的楼层的, 所以一层就变成了这个样子 (图为 5 月 8 日补坑):
由于地处非市中心地带, 地价也应该相对便宜一些 (一年没有碰高中地理都忘了该说些什么了), 自然校园要比 RDFZ 宽敞一些:
这次参加的人比较多, 然后可能丽都酒店放不下, 所以其他的人被安排到了隔壁的珀丽酒店. 我当然是不属于放不下的人了 (因为省份的拼音首字母比较靠前的说), 就被安排在了丽都. 走廊不算很宽敞, 但是至少看起来还是不错的呢 (图为 5 月 8 日补坑):
总之大概就是这个样子. 试完机子我们就撤回到自己的屋子里, 然后我和同屋的 D 君 (姑且这么叫吧, 我也不确定他是不是愿意透露自己的姓名) 就开始组队打 osu!, 顺便把楼下的 xmcp 叫了上来~
其实酒店里最要命的还是信号问题. 同校一起来的人里, 基本只有我一个人用得联通, 其他的都是移动...... 于是在别人信号满格的时候我就在忍受一格到两格之间晃悠的感觉----好在酒店里有 Wi-Fi, 还有一个应该是假的的 High Speed Internet......
测出来的速度也很感人:
xmcp 似乎没有带鼠标, 所以三人开黑就只能打 osu! mania, 经典模式弃之. 那天几点去睡的觉不是太清楚, 但是令人记忆犹新的是从那一天开始的例行灯光检查. 由于本蒟蒻有强迫症, 在睡觉时屋子里不能有灯光, 所以所有光污染设备都要采取遮挡或关闭的手段.
床头的闹铃需要扣过来......
5 月 8 日: CTSC2017 Day 1
早上六点半左右被一阵异样的铃声吵醒...... 首先是 D 君的手机铃声, 然后是我的...... 本以为两个都关掉之后可以轻松地睡半个小时回笼觉, 结果被某科学的闹铃拽回到现实当中. 经过本人与酒店自带光污染闹钟的数番搏斗之后, 终于将响铃按住.
上午吃完早餐就是比赛, 赛制为 NOI 赛制, 本机评测. 其实我不是很确定如果遇到卡评测现象应该怎么处理, 毕竟 Linux 上的零日漏洞还是有几个的.
其他几位仁兄都被发配到实验楼的四五层, 然后我苦逼地去了图书馆......
到了才发现这里的机器和我用的是多么的相近...... 处理器应该是 Intel Core 2 T7600 一类的处理器, 然后图形显卡没有明确标出来, 但是 lspci 返回的结果大概是 NVidia GeForce 7000 这个系列的显卡. 考虑到本人有着多年与老爷机打交道的经历, 对付这些问题应该不是很难.
考试中间发的面包和巧克力还是可以撑一阵的, 也就是所谓的 “暂凭杯酒长精神” 吧~
第一题我不是很会做, 但是其他题目也不是太会写, 所以就只看了第一题. 闲得没事把暴力写出来, 然后发现后面的题不会拿分, 就接着去做第一题. 把对应的表打出来以后突然发现好像有一些比较明显的规律, 然后就去找规律, 找了差不多两个小时以后终于把第二个样例过掉了......
发现对于将所有可能的位置从 \(1\) 开始编号, 会构成一些循环节, 循环节长度为 \(8\). 相邻两个循环节之间两个对应位置的数差总不变. 发现这个规律以后我便试图暴力求出前 \(32\) 个特征值, 然后倒推循环节得到所求特征值对应的位置.
这样至少得到了样例 2 的正确结果, 但是面对更大的数据时发现根本过不了, 分分钟 TLE......
于是考场上就开始沉迷于卡常不能自拔~ 首先发现了其实只需要求出前 \(17\) 个即可, 因为除了第一个可能会有异常之外, 其他都严格遵循这个循环节规则. 做完这个之后就去瞎搞这个所谓的公差. 发现这个公差只可能为 \(1\) 或 \(2\), 并且循环节对应公差与 \(k\) 在模 \(8\) 意义下的值有关, 也就是说我们不再需要求出后 \(8\) 就可以知道这个公差了. 我们再次将这个常数缩短到了 \(9\).
最后就是暴力循环展开, 然后加上了各种记忆化的数据, 压了几个位, 强行把运行时间卡到了 \(2.7\) 秒左右. 突然后想起来之前某一次 xmcp 用 CodeXL 的经历, 然后把函数里的一些变量加上了 register, 结果硬生生把时间搞到了 \(1.9\) 秒......
这个实在是火爆----不过话说回来由于图书馆的机器比较缓慢, 所以评测时限都延长了两倍 (也就是原来的三倍), 这也为我的卡常提供了平台......
第二题随便写了个 Floyd 水了十分.
后来才知道第一题的 RNG (Random Number Generator) 出了锅, 生成出的数据是具有循环特性的...... 所以我的做法似乎卡掉了 \(65\) 分, 不容易~
评测机并不是洛谷的香港记者号评测机或者是美国的华莱士号所以速度比较慢...... 别的考场的人都已经撤退了我们还在静静地等待出结果:
吃饭的时候遇到了这个东西 (我并不是很清楚如何用 VR 来体验雾霾)
还有一些可弯曲吸管的正确打开方式:
下午讲题, 没怎么听懂, 然后恍恍惚惚回到了酒店......
应该说是第一次正经打太鼓达人, 所以还是比较生疏. 由于有了一些之前的 osu! mania 的经验所以也不是很难. 习惯了就好----
5 月 9 日: 集训队答辩
其实集训队答辩是给队员提供了一个展 (si) 示 (bi) 的机会, 在我校赵晟宇大神身上得到了深刻的体现:
观众: 《计算机逻辑与艺术初探----基于逻辑的钢琴演奏音符力度模型》很棒啊
评委: 你这个幻灯片字号太小了看不清啊......
zsy:. ......
评委: 你这个背景对比度太低了看不清啊......
zsy:. ......
......
评委: 你没有用到作曲家提供的东西?!
zsy:. ......
评委: 音乐本身就具有多样性, 作曲家只是给了一个参考!
zsy:. ......
观众:. ...... 这样说会不会给人一种内定钦点的感觉呢
质量不太好, 各位大神凑合看了~
突然老师说论文集还有剩余大家可以上来拿会场就变成了这个样子:
下午有一个《王选的世界》报告会......
当幻灯片上出现了熟悉的面孔时全场膜法师立刻鼓掌致敬......
当时我好像在走神所以没来得及照下来......
不过八十中的景色还是很不错的呢~
听说 xmcp 等人坐的大巴晚了一点然后遭遇大规模卡大巴事故
晚上由于第二天没有什么例行公事所以就继续打了一阵子 osu!
5 月 10 日: CTSC2017 Day 2
上午的题部分分比较好拿......
第一题可以预处理一个阶乘然后乱搞一个 \(O(n^2)\) 算法水过 \(70\) 分.
第二题写了一个 Dijkstra 堆优化最短路, 骗掉了 \(10\) 分.
第三题讲道理应该用更稳定一点的算法, 结果我手残用了模拟退火----居然还过掉了好多样例~ 本来期望得到 \(70\) 分的, 结果小强上来就说他卡掉了模拟退火, 然后就被卡掉了. 黄思同学用了一个千分法 (就是取 \(1000\) 份随机乱撒的样本取其中最好的一部分, 这样得到的可以卡掉极端数据) 然后过掉了 \(60\) 分左右. 当时我想到了这个做法但是为什么没有用呢 QwQ
所以这场考试拿到的分还是很少的......
下午是前六名基训队队员口试以及闭幕式;
参加此次会议的有: 毛啸、徐明宽、杨家齐、钟知闲、翁文涛、杨景钦.
上面那个就是毛啸无疑了~
评委一直都在问一些奇怪的问题, 比如对机器学习如何看待、Cortana 这类软件的优势劣势都在哪里、对 AlphaGo 如何看待等等问题. 虽然都是说了很久的东西, 但是总觉得他们应该在这些方面上增加一点姿势水平 (因为人工智能是玄学).
杨景钦原来一直在 rank 2 稳坐, 结果 day 2 莫名被卡掉到了 rank 6...... 于是评委问了大意如下的一些问题:
评委: 如果我们把你换到国家队里, 你认为你有什么优势?
杨景钦: 我认为 CTSC 应该和国际接轨, 采用 IOI 赛制. 考场时我没能注意到一个很低级的错误, 以我的代码水平是可以现场调出来的. 正如我所说, OI 赛制不适合我, 但是由于我有着高超 (雾) 的调试技巧, 可以在短时间内补救错误. 所以如果我参加 IOI 的话, 是可以发挥在 CTSC 中发挥不到的优势的.
评委: 所以...... ?
杨景钦: 我认为是赛制的问题.
观众:. ......
当然最后并没有把他换上来, 只是活跃了一下气氛而已.
铜牌和银牌都没有上台, 因为人太多了----这要发到十点才能结束的节奏----
但是拿了个铜牌还是蛮开心的呢 owo~
听说明天 (11 日) 不用回学校, 所以就可以在酒店里面乱写代码了...... 然而 xmcp 回家拿了一趟鼠标
(顺便晚上被卡大巴了)
5 月 11 日: 休息
今天没什么事情, 就简单把酒店的内饰贴上来占个楼
窗户是假的
窗户是假的
窗户是假的
重要的事情要说三遍
别人的窗户都能开开, 但是我们的可以用来提神或者早上起来使用 sun.enable() 加成提高起床速度
5 月 12 日: 讲课
秦老师的课算是比较有意思的, 比如各种神经网络学习算法等等, 应该说是实用向的算法----
但是坐看大家一起学膜法还是很有意思的
上面写的是 gou li guo jia sheng si yi
所以说拼音输入法还是要学习一发
下午会场地方不够大, 所以挪到了礼堂:
这个一带一路的会议一开就会出锅
听说 APIO 的评测姬放在了 AWS EC2 (Amazon Web Services: Elastic Computing) 上面, 国内访问可能不是很稳定, 所以大家都寄希望于应急预案
那么如果大家都对应急预案抱有信心的话, 我们就成功举办了一次 APOI
这一天可不敢晚睡觉
但是各地都在闹 445 端口的 WannaCry 也是没办法, 你们把 Services/Server 服务关掉不就可以了
5 月 13 日: APIO2017
这套题目拿到金牌应该不算太难的
第三题虽然我不会但是听 hld67890 大神说还是挺简单的
第一题是一个利用交互库特性强制在线的题目, 各种 \(O(\log n)\) 强行优化......
所以第一题我写了个 \(11\) 分暴力交了上去, 第三题看都没看就跳过了
然后乱搞第二题
第二题和去年的第三题做法有异曲同工之妙, 所以应该着手的思路也是一样的.
子任务 1
需要强行让 Koala 只能选 \(99\) 个最好的, 抛弃的那一个就是权值最小的. 我们只需将 \(A[]\) 数组赋值为 \(\{1, 0, 0, \ldots, 0\}\) 即可.
子任务 2
我似乎采取了瞎搞做法随便过掉了 \(15\) 分
第一次把所有数值 \(A_i\) 都赋值为 \(1\), 然后 Koala 选择的一定是这其中最大的一部分.
将这一部分取出来, 记其数量为 \(x\), 则它们对应的 \(A_i\) 权值为 \(\left \lfloor \frac{n}{x} \right \rfloor\). 其他的权值均为 \(0\).
重复这样的操作, 直到只剩一个. 不知道为什么这个做法就是能过去~
子任务 3
我只拿到了 \(14\) 分, 不过按照我的思路应该是可以拿到 \(18\) 分的.
给前两个数 \(A_0, A_1\) 赋值一个相同的数值, 取 \(1, 3, 6, 10\) 即可. 如果在某一次有一个被选中而另一个没有, 那么被选中的那个就是更大的数.
将这个算法优化的方法是采取所谓 “二分” 策略. 这样可以把情况缩小到 \(3\) 步, 也为后一道题奠定了基础.
子任务 4
此题乱搞, 发现 \(O(n \log n)\) 复杂度可做, 然后就随便写了一个二分查找算法, 虽然可能会爆, 但是把程序提交上去以后这个做法其实是对的.
子任务 5
用稳定的 qsort() 函数来进行排序, 复杂度 \(O(n \log n)\), 可以拿到 \(20\) 分左右.
如果发现可以用 \(50\) 次操作查询到前 \(50\) 小的数字, 那么复杂度又可以缩小到 \(O(\frac{n}{2} + \frac{n}{2} \log \frac{n}{2})\).
正解和这个做法类似, 只不过有了分块得思路直接把复杂度压倒了 \(O(n)\).
晚上 xmcp 给我 /np 了一首歌, 叫 Pre-parade (TV-size)
然后 D 君表示那个 OP 短片实在令人无法理解
所以 xmcp 说, 你们把番下下来看啊, 看了就懂了
我说除了头发脸都长一个样子怎么认啊
但是看了两集以后我就入坑了
这个动画叫「とらどら! 」
5 月 14 日: 闭幕式
随便看了几集「とらどら! 」然后去颁奖仪式.
大家都在挤兑饭票的过程中
现场有一些不是很有意思的节目
然而我并没有很专心的看
旁边有一堆人在玩切绳子
在食堂不知道哪个智障把水泼到椅子上还没有擦掉
在那一次之后我坐食堂椅子之前都会仔细看一眼因为长了教训
拿了一块银牌很开心呢~
结语
虽然手里还是只有狗牌
或者说是两块破牌子
却不能改变已经退役的事实
那么就听天由命吧
反正 OI 什么的, 也无所谓了
因为已经没有题, 值得去刷了
一口气写了这么多, 还真是很累呢