作者: KSkun

[CSP-S2 2019]树上的数 题解

[CSP-S2 2019]树上的数 题解

题目地址:洛谷:P5659 树上的数 – 洛谷 | 计算机科学教育新生态 题目 

[CSP-S2 2019]括号树 题解

[CSP-S2 2019]括号树 题解

题目地址:洛谷:P5658 括号树 – 洛谷 | 计算机科学教育新生态 题目背 

CSP-JS2 2019 游记

CSP-JS2 2019 游记

谁能想到一年后的 11 月我又来这个鬼地方了呢 233333 。

一年前对着屏幕上的试题懵逼的那个菜鸡,变成了看着别人对着屏幕上的试题懵逼的人。这种角色的转换还是挺有意思的,因此写了这篇博客记录参加 CSP-JS2 2019 考务工作的所见所闻。

谨以此文献给为 CSP-JS2 2019 贡献力量的工作人员们,也献给在比赛中与难题奋力搏斗的勇敢的选手们。感谢各位的合作与努力,让竞赛变得更好。

(由于敏感信息等原因,本文图片略少,图片部分位置使用了模糊处理)

11 月 11 日 Day -4

其实在 11 月 9 日就已经开始了竞赛的准备工作,但是因为我这周的星期五要期中考试,就只抽出了半天时间参加环境的验证和虚拟机的配置工作。

我和负责考务工作的研究生学长在南一楼 8 楼的机房检查机房机器的环境是否正确/一致,需要做的工作包括:

  • 检查 Windows 环境下是否安装了指定版本的 GUIDE 和 Dev-C++ ,是否都可正常编辑、生成、调试(这两款 IDE 是通知中保证可用的,因此重点检查);
  • 检查 NOI Linux 环境下组件是否正常工作;
  • 清点机房设备数量;
  • 检查备用机房的环境信息,后续将对备用机进行环境配置;
  • 验证是否可以在 Windows 下的 VMware 中安装运行 NOI Linux 。

检查每台机器不太现实,因此抽了几台做验证。没什么太大的问题,就是备用机器需要配置环境。

在虚拟机中安装 NOI Linux 费了好大的劲。最开始使用 VMware 的自动安装来安装 NOI Linux ,结果安装完成之后开不了机。之后用 VirtualBox 尝试安装,经过极其漫长的等待后终于成功了。随后重新尝试了 VMware 的自动安装以及更新版本的 VirtualBox (成功配置)、 VMware (由于需要重启,最终无法安装上)。

最后我提出在 VMware 中手动安装,结果居然成功了,而且安装速度完爆 VirtualBox ,欣喜若狂。被这东西折磨一下午是真的烦人。

在这之间,我在思考虚拟机跑 Linux 性能打折扣比较大,本来硬件配置就很一般,真的要拿这种环境给选手用吗?事实证明,我理解错了老师的意思,虚拟机是为了 Windows 选手验证 Linux 下程序是否会出问题用的, Linux 选手还是使用的在物理机上运行的 NOI Linux ,这一点还是很人性化的。

晚上找 zcysky 等一行人恰麻辣香锅,东一食堂麻辣香锅是好文明。

11 月 15 日 Day 0

下午考了微积分的期中考试,出来以后一算感觉自己要不及格。考都考完了管他的,得开始在南一楼忙起来了。

吃完了面约了 Margatroid 一起去南一楼做考前准备,又有一大堆事等着我们。

  • 再次验证机器上的环境是正确且可用的;
  • 清空机器上原有的数据,打扫机房,放置隔离板;
  • 下发试题,检查下发试题是否到位。

由于当天晚上还有机房在上课,只能等到 9 点半下课之后才能进入配置环境,因此大家应该是忙到很晚,真的很辛苦。

正在配置环境的机房
忙碌到很晚的工作人员

这里也顺便记录一下我总结的一些注意事项吧,虽说其他的选手也会有相似的经验。

  • 时间安排:一般是 1h 一题, 0.5h 机动,也可以根据实际情况调整;
  • 厕所:可以上,也可以作为调整自己的方式,洗把脸冷静一下;
  • 检查:检查代码、输入输出文件名、目录结构,最后 0.5h 可以在最终保存代码的位置做实际测试;
  • 策略:不要死磕,先打暴力,注意观察部分分,从特殊到一般逐层击破,难题可以直接扔;
  • 其他:有什么事找工作人员,题目理解工作人员无法解答但是自己可以验证样例来确定是否正确;
  • 放空心,干就是了,经过了这么多次模拟赛,要注意的事情自然会在合适的时候想起来。

睡得比较早,因为第二天 7 点之前要起床。

11 月 16 日 Day 1

早就到达的选手们
7 点的南一楼与门口的主席像

穿了件八重樱剪影的卫衣就出门了。拿了胸牌之后在场外维持秩序,很多人都是第一次参加正式比赛,难免有些紧张,希望他们好运吧。人都进的差不多了之后上 8 楼待机。在考试期间基本没有我什么事情,因此一直在办公室里待机,偶尔会去有需要的地方帮帮忙。

在整个比赛过程中,我们尽力创造良好的竞赛环境,希望大家能发挥出最佳状态。发现一个有趣的事实,虽然参赛选手的性别比例并不太夸张,但男厕所的使用频率确实高了不少。

真正开始忙的时候是考试结束之后,目送选手离开考场,然后封闭大门,开始收集代码。由于湖北尚未采用一些自动化的手段,我们仍然延续着人工 U 盘拷贝的方法,对机房分片,每个人收取二三十台。我的工作则是与第一遍收取代码平行的第二遍收取,收取两次之后做文件内容的比对,可以大大降低漏收或数据损坏的概率。只有收取比对结束后才能清空数据准备下去的 CSP-J2 比赛,因此中午的时间比较紧张,基本上是收取代码、清理考场、下发试题连轴转。点的外卖倒是早就到了,很多志愿者很晚才吃上饭,各位辛苦了。

在办公室整理文件资料的工作人员
正在布置考场的工作人员

下午的 CSP-J2 比赛参赛人数较少,就休息了一会。

晚上回到南一楼收集 CSP-J2 组的代码,依然是收集第二遍做代码比对,随后依然是清理机房、分发题目。只是晚上又有上课占用机房,又等到 9 点半下课才能开始准备。晚上见到了当年省队的 panda_2134 大爷,叙了会旧。

23 点西区停电门禁进不去,于是掐着点打车赶回了宿舍,由于 SAO3 更新睡的晚了一点,明天依然要 7 点前起床。

11 月 17 日 Day 2

Day 2 早上的事情与 Day 1 并无太大差别,依然在办公室待机。Day 2 大家都熟悉了环境,因此问题并不太多,大家都只是埋头敲着代码或者苦思冥想。瞥了一眼屏幕,看到题目中包含了许多 Σ ,有一种不好的预感。

和 Margatroid 讨论了有关自动收取代码这个需求的事情,我认为使用一个 HTTP 服务器上传代码是一种成本较低、可行性较高的方案,之后也许会试着做出一个雏形,让竞赛的体验更好。

临近考试结束,扫雷打纸牌的人数比昨天显著多了不少,估计题目难度确实提升了。

与昨天一样的收代码、比对,只是结束了之后不用为下一场考试做准备了,而是直接撤掉所有东西,把机房恢复原样。

Day 2 结束后,许多人可能面临着退役的现实,对于这件事情,我的观点可以用下面的一段话描述:

首先,祝各位退役愉快。

一年前,我也在华中科技大学的南一楼 8 楼结束了在役的最后一场比赛 NOIP 2018 ,我还记得,我没有灰心丧气,我的同学们也没有。我们开着商业互吹的玩笑,讨论着题目,从考场一路聊到回家的火车上。

尽管 CSP-JS2 2019 已经不叫 NOIP ,尽管题目的难度也无法和 NOIP 2018 相比,我相信大家最终也都是笑着结束的。我们努力过,热爱过,且直至今日依然热爱着 OI ,珍惜着 OI 给我们带来的知识、智慧、回忆。这也是为什么 OIer 往往会觉得 OI 的过程很有趣但文化课很无聊,且退役时都会有强烈的不舍、不甘——我也是如此。

一年后,对 OI 的热爱仍然在我的心中,让我回忆起那些可以被称为“青春”的时光。来到大学后,我发现我的热爱并不止局限于 OI ,当我有机会接触到更大的世界之后,这种热爱很快扩展到了其他的相关领域中:我了解过 ICPC、安全类竞赛、AI、工程开发,参加比赛、加入技术社团,成为 CSP-JS2 2019 的志愿者;我遇到了 zcy ,认识了社团里的学长学姐……这幅场景似曾相识,与 OI 时的“和一群志同道合的人一起,做些‘即使拿自己的未来做赌注也喜欢,也要去做的事情’”有几分相似——你看,对 OI 的感情是可以延续的。

只是因为年龄、教育等的限制,让各位在中学阶段只能接触到 OI 这一个狭窄的方面,其实,更大的世界在未来等待着各位来探索。所以,现在就放下过去的种种执念,抱着对未来的期待,做好当下的自己吧。

如果你热爱开发,这里有学生技术社团、开发比赛; 如果你热爱算法,依然有 ICPC 可以延续你的所学; 如果你想 make OI better ,欢迎继续关注 OI 这个小圈子,做学弟学妹的引路人,分享自己的知识或思考,或者像我一样,为竞赛本身做微小的贡献; 但无论你有着什么样的兴趣,最重要的还是要 enjoy your life 。

Have Fun & Good Luck.

欢迎来华中科技大学&冰岩作坊找我和 zcy 玩鸭

——by KSkun

在洛谷讨论主题 CSP后的一些寄语 – 洛谷 | 计算机科学教育新生态 里写下的一段话

选手们最终都回到了家中、学校里,工作人员也都结束了竞赛事务回归日常工作,我也回到了平常的生活中。只是,今日此时的体会和感受让我回忆起了一年前的我,那些在 OI 中挥洒青春的日子一去不复返了,如今或许已不再那样青春,但仍然会为那时的努力而欣慰、感动。

这两天很累,但也很棒。

11 月 18 日

我微积分及格了哈哈哈哈哈哈哈哈哈哈哈(flag 回收)

CSP-S2 2019 题目相关

由于写下该评价的时候我并未看到题目细节,评价涉及个人主观臆断等内容,可能与实际存在偏差。之后做完今年的题目后可能会更新评价的内容。

就算过了一年,OI 的知识至少还是留下了一点,简单地想了想今年的题目。

第一天的题目中,T1 是一个简单的模拟,T2 是经典 DP 模型上树,T3 发现了一些性质但找不出比较正确的搞法,感觉这一天的难度还算一般,但这个 T3 确实不太能想得出好的思路。

第二天的题目中,T1 感觉像是计数 DP ,并没有思路,T2 感觉很 DP ,只发现了一些性质,同样没思路,T3 一眼点分治,看到数据范围的时候我慌了,怎么还能卡常的。看完题目之后能够理解当时考场上大家的心情了。老实说,这种难度的题目在湖北大概是没有多大区分度的,我反而更希望接近 Day 1 的难度,至少选手不会因为题目在考场上出现心态问题,被折磨 3.5h ,希望大家都能有自己能做的事情,拼尽全力做完之后微笑着走出考场。

还没来得及详细分析题目读题解,如果哪天搞明白了再专门开一篇题解的博客吧。

结语

这是一段珍贵而难忘的经历,我获得了独特的感受,为了记录下这份感受,也为了将其分享给更多的人,我着手写下了这篇博客。

正因为曾是 OIer ,才更愿意为未来的 OI 贡献自己的力量;正因为曾热爱过 OI ,才更想要帮助同样热爱 OI 的各位选手们;正因为如今依然保存着对 OI 的感情,才拼尽全力想要 make OI better 。

在一场比赛的台前幕后,工作人员做了非常巨大的付出和努力,这不仅包括可见的准备工作,如打扫卫生或收取代码等,还包括对工作的认真仔细和热爱,长期的反思与改进。在考场的门外,隐藏着无数的细节,如今我终于亲眼见到了这一切,更参与到了其中。感谢所有对 OI 做出贡献的人们:实实在在组织一场比赛的工作人员、负责所有事务的特派员老师、提出建议积极交流反馈的选手、教练,OI 在大家的关注和努力下变得更好。

同样还要感谢各位选手,感谢大家的配合让我们顺利举办了这次 CSP-JS2 2019 比赛。大家在考场中发挥智慧、奋笔疾书或专心代码的身影是最美丽的,竞赛已经结束,此时我们不谈输赢得失,而是为自己的努力拼搏喝彩吧。

这篇博客把幕后的细节分享给了大家,希望大家能够继续关注和支持 OI 及计算机科学教育事业的发展,一如既往地努力学习 OI 知识,或者在未来关注支持 OI ,在力所能及的范围内为 OI 的发展贡献出自己的力量。

感谢组织方湖北省计算机学会的努力;
感谢全体工作人员的付出;
感谢选手的配合与优异表现;
感谢所有关注与支持 OI 的人;
感谢有你。

KSkun 2019/11/20 于华中科技大学

[CSP-S2 2019]格雷码 题解

[CSP-S2 2019]格雷码 题解

题目地址:洛谷:P5657 格雷码 – 洛谷 | 计算机科学教育新生态 题目描 

[IOI2007]Pairs 题解

[IOI2007]Pairs 题解

题目地址:洛谷:P4648 [IOI2007] pairs 动物对数 – 洛谷 

Web开发学习手记(四):MongoDB及mgo

Web开发学习手记(四):MongoDB及mgo

前言

学习手记(三)中的实例——简单的用户系统中,使用了MongoDB管理用户数据。这篇文章记录我对MongoDB的学习内容与Go中的MongoDB库mgo的使用内容。由于接触到的内容有限,这篇文章也只会提及有限的部分。

MongoDB概述

MongoDB是一种非关系型数据库,具有高可扩展性且灵活易用。它将数据存储于一个文档中,其结构类似于JSON。

MongoDB的使用:mgo

Go语言中可以使用mgo库连接、操作MongoDB。

连接

可以使用mgo.Dial(url)来新建一个Session连接到MongoDB服务器。如果这里的url设置为空字符串,则连接本地默认端口。

指定数据库或集合

使用session.DB("database").C("collection")来指定数据库或集合。这会返回一个DatabaseCollection类型的值,可以使用其进行查询等操作。

查询

使用collection.Find(bson)来按照条件查询,其中bson可以用bson.M来创建。这会返回一个Query类型的值,应使用query.One()query.All()来获得查询结果。对于接受查询结果的类型,应该使用反射标签bson来设置对应的key。

插入

使用collection.Insert(obj)来插入一个条目。插入的类型应该使用反射标签bson来设置对应的key。

Web开发学习手记(三):MVC架构

Web开发学习手记(三):MVC架构

前言 在Web开发实践中,我尝试使用MVC架构进行了一次完整的后端开发。 这篇文章记录我对 

Web开发学习手记(二):gin框架

Web开发学习手记(二):gin框架

前言 冰岩作坊的各种产品都与互联网相关,不可避免地会用到Go语言的网络框架,其中,gin就 

Web开发学习手记(一):Go语言

Web开发学习手记(一):Go语言

前言

加入冰岩作坊第一个新人任务就是学习Go并且用gin框架做一些小的实践,自然是要先学习一下Go的。

在此之前,我只对面向对象有了解,但Go作为一种非面向对象(更像C语言)的语言,它的设计模式等是我不熟悉的,实践的过程中也经常碰壁。

在这篇手记中,我主要记录下个人对Go语言的认识和一些需要注意的地方。由于能接触到的内容还很局限,这里只会提到有限的一部分。在学习的过程中也许会一直补充这个内容吧(咕咕咕警告)。

语法

  1. 不需要分号!分号只是用于分隔同一行的多条语句的,如果用换行分隔了,语句的末尾就不需要分号了。
  2. 变量声明的类型在变量名的后面!这是和很多语言都有区别的地方,Go的声明中类型应该放在名称后面,这里包括变量和函数。比如var a int
  3. 有指针类型,但比C的指针安全!在Go中,指针只是用于取地址用的,不能对它做加减操作,避免了加减越界的风险。
  4. 切片!大小可以改变的切片在使用时可以当做动态数组,而且可以类似Python那样取任意的一段出来作为一个新切片。
  5. 接口!虽然Go不是一个OO语言,但是却存在接口这种多态的特性。在Go中,接口是隐式实现的,即如果实现了接口中的所有方法,则认为实现了该接口。
  6. 类型转换与类型断言!在Go中可以做类型转换,与C的类型转换没有区别。但对于空接口interface{}来说它没有任何类型,需要用类型推断来对它进行转换,形如a.(int),返回两个值接口a的转换结果和推断是否可行。
  7. 错误处理和中断!在Go中一般会在可能产生错误的函数中把error作为返回值。出现了错误之后不一定会中断,可以手动使用panic等令其中断。这一点和Java的错误处理区别比较大。
  8. 并发!Go中的goroutine和channel真的很方便。虽然到现在为止还没有写过需要并发的程序,将来有机会可以实践一下。
  9. 命名规则!在Go里,一般使用大驼峰命名函数、变量等,局部变量会使用小驼峰。这与Java里到处小驼峰和C里到处下划线的规则区别很大。

开发环境和结构

  1. GOPATH!所有的项目都需要放在GOPATH中,不然会找不到导入的包。
  2. go mod!但是放在GOPATH里会很麻烦,于是可以使用go mod这种包管理器来帮你处理导入包的一系列问题,让你的项目可以放在任意位置。
  3. 更短的包名!Go的包名没有Java那样前面搞个很长的URL前缀,所以很短。
  4. GoLand!这里不做评价了。JetBrains牛逼!
C语言程序设计杂谈(一):星期计算问题

C语言程序设计杂谈(一):星期计算问题

问题描述 在星期计算问题中,我们将问题按照实现难度/复杂程度划分成若干等级: 已知2019