参加了为期3天的 thusc 2017, 在这里记录一下经过. # Day 0 为什么选择thu呢? 许多我所景仰的人毕业于thu, 就读于thu, 或者即将就读thu. 预期是, 能进面试就很开心了.
和我妈一起坐火车去北京, 情绪比ctsc那次稳定. 虽然CS跟我说, 这天就不要再做题了, 但是前一天已经看过了thusc 2015的题面, 而且不怎么会做 QAQ 按捺不住好奇心啊......
下火车之后坐地铁到五道口, 入住汉庭酒店. 联系上了班主任东哥多次提起的以前的学生 - 陈师兄. 我, 我妈, 和陈师兄以及他的两位同学一起吃了晚饭.
晚上辗转难眠. 北京的空气十分干燥, 这一点在前几次北京之行中也深有体会. 被子的厚度和床的硬度同样不适宜. 吹风换成空调, 无济于事. 我试图控制情绪, 但仍然会不时地突然紧张. 我妈也被我弄得有点烦躁, 于是又遭了一顿吼 TAT 最终调了调参, 三四点左右, 在18摄氏度的空调下入睡, 睡得不熟.
想起WJMZBMR在一篇blog里说, 他参加thusc, 受干燥气候的影响, 平均睡眠时间≤4h. 不同的是, 他肯定不会紧张.
Day 1
早上补了会儿觉, 吃了妈妈带回来的早饭, 然后去报道. 发现我省只有两人: 我和人生赢家. 试机, oj 502, 于是先搞了些其他事情. oj的问题解决了, 咦, 试机赛前两题怎么这么多人AC ? 啊, 被长长的题面欺骗了......打着摧毁"树壮图" (没错, "状"是错别字) 旗号的a+b problem......诶, 上次清华校赛练习赛的摧毁"树状图"不会也是这样吧......感觉网络流可能考, 敲了敲很久没写的Dinic. 发现VW神犇是工作人员~
中午试图补觉未果, 下午拎着灌装咖啡和湿纸巾进考场, 时间有点赶, 比赛开始, 一些准备工作还没有进行.
T1, 题面有点长, 轮廓线DP? 不会啊......中位数二分一下?
T2, 题意清晰明了, dls甩锅? 有点眼熟, 但没什么思路. NTT模数?
T3, 这个模型怎么有点熟悉......
完了, 这暴力都不会写......绝望 TAT
考试须知: "难度参考往年面向中学生的活动".
......
上次老师跟我说, 考场上光想怎么写暴力是行不通的; 不要总是按题号顺序做. 我也知道光靠暴力分是不能使成绩出彩的. 于是, 想研究一下题面最短的T2. 但是, 连暴力都不会写, 叫人怎么想正解......QAQ R≤30来一发meet-in-middle?
又返回去看T1. 想起十连测某题, 把多种颜色随机映射到一个较小的集合, 多跑几次, 答案取min/max. 本题是不是也可以这样呢? 有5分是送给指数级暴力的, 另外5分用two-pointer扫一扫?
稳妥起见, 先写了指数级暴力, 花了一会儿才过样例. 不爆零的概率变得大于0了, 冷静了一点, 发现另外5分可以三次方暴力.
比赛进行了2.5h后, 我成功地获得了10分!
稍微清醒了一点......
去看T2, 诶? 不就是异或吗? 高斯消元好像可以拿不少的分. 大白书上有一道类似的题 (但是更一般, 同时数据范围也更小), 是说怎么眼熟......QAQ 结果把高斯消元写错了, 调了一会儿才过小样例.
去看T3, 诶? 不就是带权的二分图匹配吗? 暴力费用流好像可以拿不少的分, 是说怎么眼熟......QAQ 好久没写费用流啦, 有点虚......修改了一处错误, 过了样例.
还有半小时, 做一些检查工作吧. 发现T1在网格图上DFS没判越界. 如果全没写挂, 暴力费用流的玄学复杂度可以跑过T3的那些点, 也只有100分.
出考场, 听到这样的对话:
A: 我做了两百多分, 你呢?
B: 一百多分吧.
生无可恋......
不过总算考完了一场.
晚上, 爸爸也来北京了, 三个人一起吃了晚饭. 看了会儿书, 就睡觉了. 今天换住西郊宾馆, 睡得比昨晚好.
Day 2
今天下着雨.
上午是开营仪式, 听领导/老师讲话. 合影放到了室内, 大家坐在报告厅的座位上. 吴文虎老师的讲话相对来说有意思, 但是根据前辈们的游记, 他讲的内容和去年相似, 好好锻炼身体, 为国家健康工作50年......于纪平学长来分享了他的经历. 他说, 可能很多同学昨天考完, 产生了对OI和人生的思考.
中午只休息了10分钟就前往考场. 在厕所碰到一位朋友, 两人隔着挡板讲了一会儿话.
T1, 题面很中2, 待求的量是什么呢? 模拟这个过程? 好像会做啊......
T2, 看到了B君的身影. Burnside引理是什么来着的? 回忆了一下, 记在了纸上.
T3, 看到了阿米巴的身影. fhq老师好像很喜欢几何啊. TAT 这次......十维计算几何?
碰到会做的题有点开心. 把操作写成矩阵. 根据题末的hint, 算了算空间; 根据数据范围, 算了算时间. 常数略大. 只存矩阵的前3列似乎好一些. 开始写. 写完, 上了个厕所.
小样例过了, 大样例全不对......检查了一下矩阵乘法, 没有问题. 我输出的数怎么这么长? 有个地方相加没取模.
大样例还是全不对......还是来对拍吧. 实现一个心愿, 在考场上用对拍脚本检查正解的正确性. 对一组足够小的数据单步运行......
我写了这样两个函数:
void down(int);
void down(int, const Matrix&);Matrix的构造函数:
Matrix::Matrix(bool b=true);参数用来指定初始化为单位矩阵还是0.
一开始, 我想把区间长度当作参数传进down, 后来感觉不方便, 对down进行了修改, 调用的地方却没改:
down(o, r-l+1);然后就匹配上了第二个down......
大样例还是全不对......TAT 距离比赛开始已经过去了2.5h, 难道得弃疗吗? 我决定再给自己半小时.
原来, 我把区间长度和a,b,c一起写了个struct Data, 重载加号却忘记处理区间长度......和第一处错误的位置一样.
大样例对了! 和暴力拍上了! 去上了个厕所. 此时离比赛开始经过了3h.
试一试最大范围跑起来速度如何?
13s+......
看了一下编译参数, 要开O2.
怎么还是13s+? TAT 原来运行错程序了......2.8s左右, 时限3s. 在oj上自定义评测一发, 只用了1s多一点.
还有两道题没动, 时间只剩1小时50分钟. 决定先搞T2, 然后去做T3二维的情形.
先回忆了一下麦克马宏和式 (项链可以旋转, 给珠子染色). n是质数的情形, 两档分应该分别是给暴力递推和矩阵乘法的.
时间不太够了, 还是想想最裸的暴力吧. 最小表示法可以用来给暴力枚举判重. 最小表示法怎么求呢? 好像可以用后缀自动机......算了还是暴力求吧......担心set太慢, 想手写Hash, 还打了个质数表. 又觉得, 对于字符串哈希而言, 这个模数太小好像不靠谱, 删掉, 还是用set吧......实际效果不算太慢.
发现m=2输出2就可以了, +15 pts? 修改了一处错误, 去看T3.
1.in 有5组数据, 前3组手玩, 后面......还是写个程序吧. 虽然只有几分, 但这是目前最有可能得到的分......此时离考试结束还有半小时.
又写了几行, 做了 2.in 里的1组数据.
考试结束.
果然不少人说自己会T1.
听到这样的对话:
A: 你T2多少分啊?
B: 70分吧.
......
不管怎样, 考完了, 心情比较轻松.
今天有一道会做的题, 然而得分似乎和昨天相比没有太大的进步......
和父母一起去中关村的一个影院看了 <摔跤吧! 爸爸>. 影片中的一些观点我不赞同 (也许有我所不理解的文化/时代背景), 但它的确不错.
为了防止自己太失望, 就没怎么提前想自我介绍. 好像也没啥好介绍的......
Day 3
早上有点紧张. 妈妈出门买早餐. 大约8:15, 我正在吃包子, 妈妈接到面试通知的电话, 要我8:40之前就位.
Wow......
到了一个大厅, 很多同学坐在那里. 人群中发现了一位朋友, 坐到了她的左边, 开心地聊了一会儿. 数数凳子, 共80个. 全场共有3个妹子, 某个预想中的身影没有出现. TAT
面试分5组进行. 捏着工作人员发的草稿纸, 我有一点紧张, 虽然先前一直觉得自己面试不会紧张. 发了草稿纸, 看起来是要考排列组合计算题, 有点虚.
朋友面试结束时, 我正在对面的房间门口等候. 她与我击掌, 露出灿烂的笑容. 感觉好受了些~
房间是个会议室, 桌子对面坐着三位老师, 两位男士在两边, 女士在中间. 她拨下12分钟的计时器, 并告诉我开始自我介绍, 时间3分钟.
询问她该介绍哪些方面后, 我开始一条一条地说. 临场组织这类内容好像不是太容易......好像没什么亮点......
然后问了我信息学最近的大事件, 竞赛经历, 文化课成绩, 遇到困难怎样克服, 搞OI的契机是什么. 我答的条理性欠佳, 但是着实讲了几个独一无二的故事......一个开放性的数学问题: 给一个等概率输出0,1的随机数生成器, 怎样构造一个等概率输出1,2,...,7的随机数生成器? 右边的男老师问出这个问题, 左边两位老师轻声交流, 貌似在说他们也不太会 QAQ 我的想法是生成一个3位01串, 遇到000重新实验, 二进制转十进制.
12分钟到, 女老师仍让我讲完了去年进入省队的故事. 自我介绍中提到过这个. 虽然是出于考察目的, 但是说的话被记下来, 仍然有一种被尊重的感觉. ovo
和父母去前门逛了逛.
下午先听讲座. 以为是讲题, 结果是介绍thu贵系本科生的创新, 科研成果, 还有算协. 原来VW神犇现在是算协平台组的一员. Cool!
到了此次体验营的尾声. 发协议. 进入面试的人都有协议, 念一个名字上去拿一个. 我猜测协议的实惠程度随时间非严格单调递增, 希望自己的名字晚点出现.
叫到我了. 还没仔细看, 被同省某校教练拿去拍了张照, 不知道这是要做啥. QAQ
无条件60分, NOI前100一本线.
签了一份协议交上去, 然后就散场了.
和老师汇报了一下, 告诉了一直关心着我的几个朋友.
心情比较平静, 爹妈比我激动. >_<
晚上去三里屯逛了逛, 晚饭吃比萨, 去书店买了本费曼的自传.
回宾馆后, 以及第二天上午, 重温了 <霍比特人3: 五军之战> 的电影.
尾声
考试还是先看一遍题面, 确定一个顺序, 依次来做比较靠谱.
离NOI还有不到两个月的时间. 可能是OI生涯的最后两个月, 之后会回到学校.
一位我一向钦佩的朋友鼓励我, "求其上者得其中". 真是一个与众不同的人. 两个月难以带来天翻地覆的变化, 但心怀梦想总是好的.
佛罗多愈发预感到自己将死于这场旅途, 却仍然义无反顾地向前. 我也感觉自己在走向已知的未来, 但还是得好好欣赏沿途的风景.
希望在最后的日子里, 我能享受OI.
Bless All.