ZJOI2017

继WC2017后,我们再次参加的重要比赛

参考largecube

提示:

  • 普通列表图片在文字下方

  • 块引用图片在文字上方

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%的数据保证图是一条链,此时可以证明答案为2n22^{n-2},可以骗分。不过我是用暴力找规律发现的。

      • 时间复杂度O(2n(n1)2mn)O(2^{\frac{n(n-1)}2-m}n)O(n+logn)O(n+\log n)

      • 最终得分:10+20

    • T2树状数组

      • 题意:给定nn个初始值为0的数,mm个询问,包含optoptll,rr

        switch(opt)

        1. [l,r][l,r]之间等概率选取ii,使

        题目给出了一种错误的树状数组,即把AddFindxx顺序写反。求每个询问答对的概率xy\frac xy,只要输出 即可,其中y1y^{-1}yy在模pp域下的除法逆元。

      • 提示:pp是质数,因此

      • 解法:

        • 直接暴力枚举每次选的数,模拟两种树状数组计算概率即可

        • 时间复杂度O(nmmlogn)O(n^mm\log n)

      • 最终得分:10

    • T3多项式

      • 题意:给定一个系数为模2域下的nn次多项式f(n)f(n),由01串输入,求nmnm次多项式f(n)mf(n)^m(也为模2域下)的01串表示中某一长为kk的01串出现次数
    • 解法:

      • 我只想到直接展开+kmp

      • 时间复杂度O(nm+nm+k)O(n^m+nm+k),没有得分

    • 最终得分:0

  • 离开温州中学时接近14点

  • 回去的路上大家睡了较长的时间,我还看了大半小时的wikipedia

  • 最终我们于接近18点半回到学校,乘公交车回家