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$的字符串，要求支持以下操作：
-
$l,r,d$：将$[l,r]$加上$d$
-
$l,r$：求$[l,r]$中后缀字典序最大的子串的起始位置
-
-
我的做法：直接模拟每个操作。
-
时间复杂度：$O(mn^2)$
-
期望得分：10
-
-
-
离开考场时，我突然找不到我的袋子了，一定是有人拿错了。还好在回去前，一个老师把袋子还给了我。我们坐车返回学校。
-
吃完饭后回旅馆拿包，然后在2点多返回，近4点到达学校。