现在高二真的就我一个人没学上了……其他人全去清北了Orz

注:游记中涉及了较为详细的THUSC2018题面内容。如果清华大学的工作人员认为这样不妥的话请联系我删除。

Day -2

半天班。复习了一会板子,被Lijinnn和陈枫一顿奶,回家准备行李。回家累的一比,睡了几个小时。晚上去买了双鞋,十点集合就出发了。

上铺,空间狭小,空调还冷,难受得一比,没睡好觉。

Day -1

早上八点到北京。坐了好长时间的地铁前往西郊宾馆。下午步行去清华试机,发了衣服,狗牌和纪念品。计算机楼好nb……我试机的屋子里每台正常电脑的后面都有一台imac,一屋子的imac看着就特别强(可惜用不上QwQ)。简单看了看试机T1,推出了思路的一半左右,出来之后CKH简单讲了下后半段,感觉挺好玩的……要是真正考试也是这难度就好了……

Day 1

早上起来并不知道要吃啥,于是被CKH家长拉去吃了50元一位的早餐自助……我吃了个三明治就饱了Orz

坐着第一班车去的THU. 到的比较早,机房还没开。我们找了个隐蔽地区的座位,简单放松了下情绪,准备考试。

进场,八点半,开考。

考场电脑时钟分钟和秒钟是错的……OJ上的时间时钟是错的……拜托这样很过分的呀……

第一题,给你一个序列,多次求某个区间的最长上升子序列的长度。$n \le 10 ^ 5$,询问数量$\le 10^7$,序列元素大小$\le 1000$时间限制10s,强制在线。看完发现没啥头绪,就……跳过了。

第二题,询问有多少长度为$2n$的数字串,满足:其是由长度为$n$的一个数字串倍增得来,其仅可被分裂成$\le k$个模板串和杂乱无章的数字串的和。$n \le 100$,模板串个数$\le 200$,$k \le 3$.

$k \le 3$!这不分类讨论不是中国人!(掉坑)哇!$k=1$,$k=3$这两种情况大力DP就随便做啦!好强好强!

稳定了一下情绪,我就头也不回地努力思考$k=0$,$k=2$咋做……两个半小时过去了,草纸上密密麻麻的全是运算过程……但是仍然没头绪……

已经过去三个小时了,我还没分……弃疗(+心态崩坏),于是写了一个大DP,写完之后过了一个点,感觉对了(flag),开始写第一题。

因为T2想到大力DP所以T1似乎也是那么想……的?想到肯定是什么神奇的处理之后拿来用……离线!推推推推推……没啥结果。推出了一个离线方法后来发现强制在线,部分分有……然后解法又被叉掉了。

看到没啥进展,我就得出了“这道题是一道基本不可做的题,换题为好”的结论,开始看第三题。

第三题提答好玩啊……通过输出来猜读入,因为./ai特别良心所以整道题给人带来了很不错的印象……第九个点Galgame好评。

玩到手38分,看看时间发现还有半个小时,想想感觉得开始写T1暴力了吧……先回去看看T2……woc我A的不是我应该过的那个Pretest!

惊了……这种操作也有……那就改改吧半小时应该够……用……woc我看的是系统时间!用OJ时间换算了一下,还有不到15min……

当场石化.jpg

md考的跟省选Day1怎么这么像……(哭

最后38分滚粗了……连最基本的NOIP暴力都没写完……也是醉了Orz

CKH160+,第一题半小时切了,二三题“简单做了做“……OrzOrz

Day 2

第二天没啥心情考试了Orz但是还是要平复心情考一下……

还是坐的第一班车233

带了手表,但是决定到时候改一下时间防止自己再弄错了……

开考,打开设置开始调时间……然后发现自己不是管理员啥也不能干= =

行吧行吧,啥也不能干那就做题……

第一题:给你一个圆环,环上$2n$个点。奇数点之间有红色直线相连,每条红色直线有自己的权值。要求你在偶数点之间连一些绿色直线,每条绿色直线也有自定权值,满足:每条红色直线的权值小于等于与其相交的绿色直线的权值和。

最小数据范围$n \le 100,m \le 400$

……一眼就是网络流!(实际上是差分约束神题)想想想发现就算忽略时间复杂度这种东西我都做不出来……四十五分钟弃疗,去看第二题。

第二题:给你一棵树,对于任意节点有初值$f[i][0]=1$,请优化树形DP方程$f[pos][i]=f[fa[pos]][i-1]*g[pos]+f[fa[pos]][i]*r[pos]$并求出$f[leaf][0] \sim f[leaf][n]$的和,共$n+1$个数。$n \le 10^5$

一看就是一个一眼DP,式子是$O(n^2)$的,$n \le 10^5$……这还咋写了……怒写暴力15分,想了想后面……有几个点是在链上的,看起来像NTT优化(虽然不是很清楚咋写),有几个点看起来就像杨辉三角blabla……最后也没写,两小时结束T1T2,拿了15分。

第三题提答真的恶心……连爆搜也写不出来啊Orz第一个点给了解法(在题目描述最后面写明解法……非常强),第三个点枚举了一下再用一用人类智慧很快就过了,还有两个好写的点但是我尝试了各种排序方法无解……

最后35分滚粗……不过也算行了吧……

CKH比我多写了个分治NTT,多拿40分,75分。

下午讲题,通知面试……和预料的一样,没有通知到我。不过也没啥可说的了,结果已经预料到了……CKH无条件一本啦Orz

之后大概就结束了。