ZJOI2017
继WC2017后,我们再次参加的重要比赛
提示:
普通列表图片在文字下方
块引用图片在文字上方
Day1
-
接近12点时从校门口出发,乘车据说要5小时。车窗上有雾。
-
大约13:45到达磐安服务站,外面很冷,温差大到使眼镜上有雾。
-
在路上我为了试相机又拍了一些风景;天气逐渐变晴。
-
在路上我把我的创新题目中
prime
的标程和数据完成了。 -
实际上我们4点左右就到达了红太阳宾馆,并拿到了提供的资料袋。
但由于某些原因,我们一直谈判到5点多还没有解决房间问题。趣事:温州的旅馆都有一个有趣的基于安卓的地图,功能强大,但很快就被我们玩坏了。进入输入法设置后再也退不出来……
-
我们先去温州中学吃饭了:用掉了第一张饭票。每餐都是两荤两素,有时不太严格;晚上还有水果,这天是🍎。
趣事:车在温州中学门口绕了2圈,为什么呢?并不是脚本死循环,而是错过非机动车道而无法进入而已。
-
我们住进了对面的万融,
等着加价吧。我看了会儿书,又去串门,并没有做题。烧了2壶水,并没有洗澡。趣事:万融的一块显示屏更加高级;使用
Windows 7
和双显示器。我们打开了屏幕键盘
,然后调出了任务管理器,接下去是命令提示符。最终我们输入了shutdown /s /t 3600
,然后愉快的上楼了。 -
万融的无线网很不错
-
每个房间都有无线路由器 ,可以手动开关;
-
能连接其他房间的
-
不但有隔壁;
-
甚至可以连上下楼层的。
-
-
Day2
-
闹钟在6:30,然而6:20就被假的叫早吵醒了,实际上叫早应该在7点。
-
快7点才去吃自助餐,
并不太好吃。由于较迟,吃的很匆忙。-
牛奶是淡的,必须手动加糖
-
大部分座位上没有玻璃杯,只能用咖啡杯来盛牛奶
-
菜总体上比较少,有很多干的面包类
-
蛋炒饭也不太好吃
-
-
规定是7:40出发,但最终拖到7:50左右。
-
我们按时到达了温州中学,上午讲课内容为搜索
-
玄学搜索
-
A*
和IDA*
-
精确覆盖问题的
DLX
算法 -
各种搜索优化
趣事:zch称直接
Floyd
能通过文化之旅
(照片较差)以及正搜90反搜100
经测试,洛谷上
Floyd
会WA一个点
-
-
中饭12:15开始
-
下午有两节课
-
STL
的应用(包含ext/rope
,ext/hash_set&hash_map
,ext/pb_ds/priority_queue&tree
)实际上括号中的部分不属于
C++ STL
,甚至不属于标准C++
,而是GNU扩展库
-
杂题选讲:没怎么听懂
-
-
会场并没有无线网;有趣的是4G的大多变成2G信号了,而我好好的用着3G信号
-
晚饭水果是🍌,但我忘记拿了!
-
吃完饭之后我们步行去五十一中试机:我们本以为很慢,但还有人更慢
-
回到旅馆已经20:45,我匆忙的看了一章小说,然后又去串门了
-
这天晚上比前一天睡得好多了
Day3
-
把闹钟提早了10分钟,但是看到lzh把包拿了下去,我也只好收拾好包下去吃饭
-
吃完饭还较早,我又拍了一些照片
-
这天全是一中讲课,比前一天更加难懂
趣事:如图,十分有趣。我排队时拍摄,并且由fks画框
fks称用触摸板画图比鼠标方便,实际上并非如此
-
下午我在笔记本上使用
PCem v12
以及PC-DOS 3.30
实验Turbo Pascal 5.5
Turbo Pascal 5.5
是官方提供的最新免费版本,而不是大家熟知的7.0;5.5是最早支持OOP
的版本。-
研究发现
Turbo Pascal
(以下简称TP)数组最大能开64KiB不到一点单个程序的数据段
Data Segment
被严格限制在64KiB -
TP能使用的堆空间=min(可用内存空间,640KiB)
堆空间为动态内存分配所用的空间,单次分配也不能超过64KiB,不过可以分配多次以达到理论上限。
640KiB为DOS实模式能访问的内存上限
-
TP能使用的栈空间$\in$[1Ki,64Ki]字节
-
-
晚上整理行李时才发现笔袋和纸都落在会场了!拍了一些照片
Day4
-
闹钟再次提早到6点,不到6:20就来到楼下
-
再次抱怨自助餐
- 非到6点半才能进去吃
-
坐车来到温州中学,再步行到五十一中二楼机房
-
ZJSX1从8点到13点,持续5小时;中间有点心提供
-
在自选软件中我看到了Notepad++,然而居然是64位的,简直在搞笑
-
断网后出现了一些问题,影响了做题,因此最后允许推迟结束
-
-
题目
-
T1仙人掌
-
题意:给定一个无自环无重边的无向图,求出加边方案数使得该图为仙人掌
仙人掌指无自环无重边的无向图,且任意一条边都只被最多一个环包含(可能有误)
-
提示:题目不保证有解(即答案可能为0)
-
解法:
-
直接暴力枚举加边方案,就是判断是否为仙人掌较难;我随便
dfs
,很可能是错的。 -
另外,有20%的数据保证图是一条链,此时可以证明答案为$2^{n-2}$,可以骗分。不过我是用暴力找规律发现的。
-
-
时间复杂度$O(2^{\frac{n(n-1)}2-m}n)$或$O(n+\log n)$
-
最终得分:10+20
-
-
T2树状数组
-
题意:给定$n$个初始值为0的数,$m$个询问,包含$opt$和$l$,$r$
switch(opt)
-
在$[l,r]$之间等概率选取$i$,使$A_i=(A_i+1)\mod 2$
-
求$(\sum\limits_{i=l}^rA_i)\mod 2$
题目给出了一种错误的树状数组,即把
Add
和Find
的$x$顺序写反。求每个询问答对的概率$\frac xy$,只要输出$x*y^{-1}\mod p$即可,其中$y^{-1}$为$y$在模$p$域下的除法逆元。 -
-
提示:$p$是质数,因此$y^{-1}\equiv y^{p-2}\pmod p$
-
解法:
-
直接暴力枚举每次选的数,模拟两种树状数组计算概率即可
-
时间复杂度$O(n^mm\log n)$
-
-
最终得分:10
-
-
T3多项式
- 题意:给定一个系数为模2域下的$n$次多项式$f(n)$,由01串输入,求$nm$次多项式$f(n)^m$(也为模2域下)的01串表示中某一长为$k$的01串出现次数
-
解法:
-
我只想到直接展开+
kmp
-
时间复杂度$O(n^m+nm+k)$,没有得分
-
-
最终得分:0
-
-
离开温州中学时接近14点
-
回去的路上大家睡了较长的时间,我还看了大半小时的
wikipedia
-
最终我们于接近18点半回到学校,乘公交车回家