ZJSX2

一个月之后的省选二试

Day1

  • 大约12:15从学校出发,有些晚点

  • 我们没有走高速,经过上虞;中间有一段路很窄,因为在施工

  • 大约2点到达余姚中学,领取牌子和袋子

颐高科技楼……

  • 然后来到不远处的如家,很快就完事了,开始烧水

lzh把包落在车上了……

  • 快5点了前往学校吃饭,路比较远,而且开始下雨了;很多人没带伞,只好回去拿

  • 在路上我又拍了一些照片

虚拟大门……

门口的日晷

静湖夜色

  • 晚饭两荤两素和一个苹果,感觉还不错

  • 回来的路上fks去KFC买了些东西,还碰上了没赶上晚饭的同学们

  • 回来后看了会儿书,lzh很迟才回来,我已经睡了

Day2

  • 6:20起床,等其他人到6:50,然后去门口的大食堂。主要是包子、粥,还是很不错的,价格也不太贵。¥10

  • 早饭后继续走到学校,8点开始讲课。

    • 第一节内容为动态传递闭包。Floyd很常见,还提供了压位的方法来卡常,但我并没有搞懂。还介绍了很多其他方法,有的能部分支持动态,有的能完全动态。对Floyd改进后可以动态加点,同理可以得到动态加边的方法。当然,时间线段树就能解决删除问题。此外,还介绍了一种基于线性代数的方法,显然没有听懂。

    • 然后是水题选讲,内容并不太记得。

  • 刚上课,许多人涌进了讲厅,连位子都不够了。这讲厅确实很小,显得很拥挤,进出很不方便。

  • 讲厅里有无线网,但是要手机登录,又只好用流量了。

  • 中饭11点半开始,有点早,人群涌向食堂。出乎意料的是,门口就收取了餐券,原来食堂的每个座位上都已经放好了饭菜!这真是个很好的设计,节省了我们的排队时间,只要自己挑喜欢的菜就可以了。

  • 中饭后有的人回到旅馆,这在以前可不敢想,但现在路确实不远,完全可以睡上一个小时。我们则待在讲厅里。

  • 下午上课从1:45开始,内容为杂题选讲,并不太听得懂。

  • 晚饭5:15开始,还是很早,但没有中饭良心了,我们排了很长时间队,匆忙地吃完了。

  • 吃完晚饭,去社区学院试机,路比较远。我们很快就回来了,而且回来用了近半小时,比赛那天得早点出发了。

  • 晚上睡得比前一天好

Day3

  • 老时间起床,但是这次没有等,很早就去吃早饭了,比前一天稍贵。¥12

  • 到达学校还比较早,我顺便拍了门口的那棵神奇的树

  • 上午讲课

    • 第一节内容为陈题选讲(大概名字都得不一样),也不太容易,还没有讲完。

    • 下一节介绍了一些乱搞的算法和技巧,非常规,但难度不大,而且非常有趣。包括一些随机化算法。

  • 中饭照常,不少人又回了旅馆,包括fks,我还是待在讲厅里。开始时有传言回旅馆的人都不来听了,因为下午的内容太简单了,但后来还是都来了。

  • 下午由老师来讲课,内容比较基础(对于别人吧,反正不是我们);讲了树套树、CDQ分治和整体二分、dfs序、点分治等,有的我们不很熟悉,收获不少。fks还看了整体二分的资料,说是回去要去做。很多人中途离开了,应该是回宾馆了。

  • 晚饭照常,回来时我们去了旁边的超市,但是我没有找到我想买的特产,所以什么也没有买。

  • 明天就要比赛了,晚上早点睡吧。

Day4

  • 六点起床,没有等fks他们就走了,吃了¥10,并不太多。

  • 到达社区学院时才7:20左右,我们先来到机房1休息了一会儿。

  • 时间还是5个小时,并且提供了vi和emacs,然而显然不会用;同时附赠大样例,虽然比较水。

  • 面包比较小,我在12点多就把面包吃完了,水也喝了不少。

  • 题目

    • T1汉诺塔

      • 题意:有$n$种盘子,每种有$k$个,要求完成标准汉诺塔的操作,并且对于目标状态$k$个同种盘子顺序有规定,求最少的移动步数。($n\le50,k\le4$)

      • 我的做法:当$k=1$时,答案显然是$2^n-1$,使用64位整数保存结果即可;当$k>1$时,显然不会做。

      • 时间复杂度:$O(T)$

      • 期望得分:10

    • T2线段树

      • 题意:给定$[1,n]$的广义线段树(即左右子树可以任意划分),给定$m$个询问,求表示$[l,r]$的所有结点到特定点$u$的距离和。其中$u$为广义线段树按照前序遍历的编号。

      • 我的做法:直接建树并模拟询问过程,求距离用倍增lca实现。为了防止栈溢出($n\le2*10^5$),我手工模拟递归,花了近一个小时才调好。

      • 时间复杂度:$O(mn\log n)$

      • 期望得分:20

    • T3字符串

      • 题意:给出长度为$n$的字符串,要求支持以下操作:

        1. $l,r,d$:将$[l,r]$加上$d$

        2. $l,r$:求$[l,r]$中后缀字典序最大的子串的起始位置

      • 我的做法:直接模拟每个操作。

      • 时间复杂度:$O(mn^2)$

      • 期望得分:10

  • 离开考场时,我突然找不到我的袋子了,一定是有人拿错了。还好在回去前,一个老师把袋子还给了我。我们坐车返回学校。

  • 吃完饭后回旅馆拿包,然后在2点多返回,近4点到达学校。