UOJ Logo jiry_2的博客

博客

第二届 “美团杯” 程序设计挑战赛

2021-05-20 14:47:11 By jiry_2

更新:已报名的队伍可以通过链接查询账号密码啦:https://www.wjx.cn/resultquery.aspx?activity=124013137

如标题所说,在去年的第一届美团杯大获成功之后,第二届美团杯终于来啦!

本次比赛的报名将于今天开始,至 2021 年 7 月 4 日周日中午 12:00 截止,具体报名方式见下方正文。正式比赛的时间为 2021 年 7 月 11 日下午 13:00 至晚上 18:00。希望大家多多来捧场。

本次比赛由北京大学学生算法协会与美团共同主办。非常感谢美团对我们再次的支持!同时比赛的平台会放在 UOJ 上,感谢吕凯风老师在百忙之中仍然抽时间给我们的比赛提供帮助!

想碎碎念的大概就是这些,接下来是正文部分,也就是关于这场比赛的介绍~ 因为我自己不怎么会排版,所以这儿就只放文字部分了。包含图片的版本可以移步我社的公众号 PKUSAA

赛事简介

“美团杯”程序设计挑战赛是由北京大学学生算法协会 & 美团主办的高质量程序设计竞赛,面向所有对计算机编程、算法感兴趣的大学生、中小学生及社会人士,旨在为编程爱好者们提供一个高水准兼具趣味性与挑战性的竞赛平台,来展示自己分析解决问题、快速吸收新知识的能力。作为专业的程序设计竞赛,本次比赛由国内外算法竞赛顶尖选手负责命题,由北京大学教授担任赛事顾问,以确保比赛的高质量与专业性。同时,北京大学学生算法协会也希望能够以此赛事为平台,在传统算法竞赛的基础上探索更多的题目类型与比赛形式,为算法竞赛的发展注入新的活力。

比赛赛制

比赛采用类IPSC赛制。

  1. 参赛选手至多三人一队,并以队伍为单位进行比赛。
  2. 比赛时长5个小时,包含10-13道正式赛题和1道热身题。热身题将在下方给出,正式赛题在比赛开始后才会开放。
  3. 正式比赛的最后一小时会封榜,在这个时候,所有队伍只能看到自己的提交结果,但是无法看到别的队伍的分数变化。
  4. 每一道正式赛题包含small和large两个独立部分,其中small占35分,large占65分,即一道正式赛题总分100分;热身题只有一个部分,不占分。对于选手的每一次提交,评测机都会分别对small和large进行检查,并按照情况给出0, 35, 65, 100分中的某一个分数。注意:只有在同一次提交中同时通过了small和large,才能获得100分;如果在两次不同的提交中分别通过了small和large,得分将被判定为 65 分。
  5. 队伍排名按照总得分降序排序,对于得分相同的队伍,按照罚时升序排序。罚时的计算方式如下:
    1. 每一道正式赛题的罚时等于最高分提交的时间(如有多个提交得分相同取最前面的那个)加上错误提交次数乘以 20 分钟。错误提交次数定义为:最高分提交之前的提交次数扣除掉第一次得分为 35 的提交、第一次得分为 65 的提交以及所有编译不通过的提交。
    2. 热身题的罚时等于负二十分钟,即通过热身题可以减免二十分钟的罚时。
    3. 一个队伍的罚时等于所有通过的部分的罚时之和。

奖项设置

获奖队伍的所有成员须均为在校学生(包括中小学、大学本专科及全日制硕士、博士研究生,含本年度应届毕业生),其余队伍不计入最终评奖。

  1. 一等奖:冠军队伍 3000RMB/人
  2. 二等奖:两支队伍 1500RMB/人
  3. 三等奖:三支队伍 1000RMB/人
  4. 优胜奖:九支队伍
  5. 最快解题奖:最快通过某一道正式赛题的large部分的队伍
  6. 顽强拼搏奖:比赛结束前最后通过某一道正式赛题的某个部分的队伍
  7. 阳光普照奖:从得分不为0且没有获得以上奖项的队伍中随机抽取五支队伍

后四个奖项的获奖队伍将获得由美团提供的精美定制礼品,奖品会在后续通知中公开。

在评奖过程中,所有有获奖资格的队伍会被分为两组:大学生组(所有成员均为大学本专科及全日制硕士、博士研究生的队伍)以及中小学生组(存在成员为中小学生的队伍,包括21年9月即将升学的高中生以及大学预科生):我们会保证大学生组至少有一支队伍获得二等奖及以上奖项,至少有三支队伍获得三等奖及以上奖项,以及至少有九支队伍获得优胜奖及以上奖项。

赛事流程

  1. 注册报名:即日起-7月4日中午12:00内填写下方问卷报名
  2. 加入交流群:北大算协&美团比赛交流群(入群方式见问卷末尾)
  3. 积极备赛:尝试并解决热身题
  4. 测试赛:7月9日晚上19:30-20:30
  5. 比赛时间:7月11日中午13:00-18:00
  6. 赛后交流:7月11日晚上20:00,由命题组直播进行题目讲解
  7. 获奖名单揭晓:7月13日中午12:00

指导与出题人

本次赛事邀请了北京大学的罗国杰教授和张勤健老师作为赛事顾问。

同时我们也邀请到了杜瑜皓、金策、周雨扬、The NANO团队以及其他很多不愿透露姓名的优秀出题人们来为这场比赛命题。

热身题

本次比赛的热身题是一道数回。作为热身题,欢迎大家在赛前讨论、并尝试用各种方式解决它。

热身题

规则

  1. 你需要在网格的格点之间用直线和横线相连,使得你连上的所有线恰好构成了一个不间断、不分叉的回路。
  2. 网格中存在一些 0~3 之间的数字,表示这个格子四周划线的数量。
  3. 对于没有数字的格子,周围的划线数目没有任何限制。

下图是一个数回的简单的例子:

数回

在正式比赛开始后,热身题的提交将会开放。提交格式如下:

  1. 你需要提交 $25$ 行数据,每行包含一个 $01$ 串,其中 $1$ 表示连线,$0$ 表示没有连。
  2. 数据的前 $13$ 行形成了一个 $13\times12$ 的 $01$ 矩阵,按照从上到下从左到右的顺序描述了每一条横线是否被连。
  3. 数据的后 $12$ 行形成了 $12\times 13$ 的 $01$ 矩阵,按照从上到下从左到右的顺序描述了每一条竖线是否被连。

选手须知

本赛事秉承公平公正的原则,严厉查处作弊行为。参赛选手需遵守选手须知,每支队伍独立完成比赛。在比赛结束后,我们会通过代码查重等方式来检测作弊行为,并取消作弊队伍的评奖资格。参赛选手应当认真阅读下述选手须知,一旦报名成功,默认参赛者接受并承诺遵守相关规定。

  1. 正式比赛过程中允许同一个队伍的多名选手同时进行解题,并允许选手自由使用各类辅助工具、互联网上的教程信息。
  2. 正式比赛过程中所有赛题相关的讨论只能在队伍内部进行。
  3. 比赛过程中禁止对评测系统作任何形式的攻击行为。
  4. 在比赛结束后的30分钟内,选手需要整理所有正式赛题相关的解题材料(包括代码、草稿等)并以指定的方式上传,以作为作弊处理工作的参考。
  5. 本次比赛的赞助商有权获得参赛者的报名资料。
  6. 北京大学学生算法协会对赛制保留最终解释权。

报名方式

扫描下方二维码或者点击此处填写表单,提交成功即视为报名成功。工作人员会在2021年7月7日之前对报名情况进行审核,并在审核通过后和您联系。

期待您的加入!

报名问卷

常见问题

Q:好感兴趣,怎么报名本次比赛呀?

A: 在本页最下方,扫描二维码,填写问卷信息提交报名即可。本次比赛以队伍为单位进行报名,一个队伍最多包含三名队员,当然我们也欢迎单人队伍与双人队伍的参加。

Q: 想和同学们在线讨论,可有组织收留?

A: 欢迎加入官方交流群“北大算协&美团比赛交流群”(入群方式见问卷末尾),如遇问题可以在群里进行讨论或者发送邮件至北京大学学生算法协会(pkusaa@yeah.net)

Q: 想和来自不同学校的朋友一起参赛,可以吗?

A: 本次比赛的队伍没有学校的限制,欢迎呼朋唤友参加赛事。如果希望深入交流,可以加入“北大算协&美团比赛交流群”(入群方式见问卷末尾)。

Q: 已经报名,想好好学习备赛,有推荐资源吗?

A: 本次比赛在传统算法竞赛的基础上,会包含形式更加灵活的题目。如果对算法竞赛的知识感兴趣,可以访问OI Wiki;如果想要练习多样化的题目,可以尝试一下往年IPSC的赛题。也非常欢迎来做一做去年美团杯的题目练练手~

Q: 还有其他问题想问,怎么咨询?

A: 加入官方QQ交流群(入群方式见问卷末尾),可以直接在群内咨询。

本次活动最终解释权归北大算协所有

赞助商信息

本次活动由美团独家赞助。

美团

美团的使命是“帮大家吃得更好,生活更好”。作为一家生活服务电子商务平台,公司聚焦“Food +Platform”战略,以“吃”为核心,通过科技创新,和广大商户与各类合作伙伴一起,努力为消费者提供品质生活,推动生活服务业需求侧和供给侧数字化升级。2018年9月20日,美团正式在港交所挂牌上市。美团将始终坚持以客户为中心,不断加大在科技研发方面的投入,更好承担社会责任,更多创造社会价值,与广大合作伙伴一起发展共赢。

“美团杯” 程序设计挑战赛

2020-05-01 00:57:06 By jiry_2

UPD:比赛报名已经截止啦,有兴趣的同学下次及时报名哦

UPD2:赛制更新,具体可以点击这个链接 https://mp.weixin.qq.com/s/VokLQG4mBgsXz1_xk3OnRw

UPD3:赛制与解题材料说明更新

规则补充

正式赛中,每一队只能在每题上提交不超过 $15$ 次(CE 提交不计入在内)

解题材料

每一支队伍需要在比赛结束后的 $30$ 分钟内,整理自己的解题材料并发送到邮箱 pkusaa@yeah.net。邮件标题为下发给大家的UOJ比赛账号,如 MTCup20T606。如果在时间期限内没有提交解题材料,或者我们在防作弊工作中认为选手提交的解题材料存在问题,我们会和选手进行沟通,视情况可能会取消选手的评奖资格。

解题材料以附件的形式附在压缩包中,压缩文件的要求为:

  1. 包含一个名为 password.txt 的文件,里面的内容是下发给大家的 UOJ 比赛账号的密码,我们会依此确认提交选手的身份。
  2. 选手每在一道题得分,压缩包中都要包含一个名称等于题目编号的文件夹(题目编号为 A - M 的大写字母),文件夹中存放对应题目的解题材料。热身题不需要提交解题材料。
  3. 压缩包大小不能超过 $5$ MB。

解题材料只会作查重使用,不会对外公开。

通常情况下,解题材料中只需要包含你对每一个部分的解题代码。特殊地,如果对于每一个部分你没有写代码,而是通过手算、借助工具的方法完成,你可以上传的有:

  1. 对你解题的时候的心路历程、思路的描述以及对你使用的工具的介绍。
  2. 草稿纸的照片。
  3. 其他任何你认为可以证明自己不存在抄袭的文件。

以下是原文

大家好这里是九条可怜。如标题所说,我们打算办个有赞助商的比赛!(Ohhhhhhhhhhh!

对于 OI 选手来说,每一年的春季学期通常都是排满了赛程,有 WC、省选、CTSC、APIO 等一系列的比赛需要选手们去参加;对于 ICPC 选手来说,春季学期也充满着各校校赛、各省邀请赛等大型线下面基活动。今年受到疫情的影响,这些赛事或是取消,或是推迟。在这样的大环境下,我们打算在线上举办一次规模较大、题型多样的程序设计挑战赛,希望能填补这一段时间的比赛荒。

本次比赛的报名将于 2020 年 5 月 1 日周五中午 12:00 开始,至 2020 年 5 月 10 日周日中午 12:00 截止,具体报名方式见下方正文。正式比赛的时间为 2020 年 5 月 17 日下午 13:00 至晚上 18:00。希望大家多多来捧场~

因为我个人的一些喜好问题(误),这一次比赛将采用类 IPSC 的赛制(具体的赛制会在下面的正文部分介绍),在以传统算法竞赛题为基础的同时,我们也实验性地加入了一些趣味性质的花板子题。希望大家之后能够享受这一场比赛~

本次比赛由北京大学学生算法协会与美团共同主办。非常感谢美团对我们的支持!同时比赛的平台会放在 UOJ 上,感谢 vfleaking 在百忙之中仍然抽时间给我们的比赛提供帮助!

想碎碎念的大概就是这些,接下来是正文部分,也就是关于这场比赛的介绍~ 因为我自己不怎么会排版,所以这儿就只放文字部分了。包含图片的版本可以移步我社的公众号 PKUSAA。

赛事简介

“美团杯”程序设计挑战赛是由北京大学学生算法协会&美团主办的高质量程序设计竞赛,面向所有对计算机编程、算法感兴趣的大学生、中小学生及社会人士,旨在为编程爱好者们提供一个高水准兼具趣味性与挑战性的竞赛平台,展示自己分析解决问题、快速吸收新知识的能力。作为专业的程序设计竞赛,本次比赛由国内外算法竞赛顶尖选手负责命题,由北京大学教授担任赛事顾问,以确保比赛的高质量与专业性。同时,北京大学学生算法协会也希望能够以此赛事为平台,在传统算法竞赛的基础上探索更多的题目类型与比赛形式,为算法竞赛的发展注入新的活力。

比赛赛制

比赛采用类IPSC赛制

  1. 参赛选手至多三人一队,并以队伍为单位进行比赛。
  2. 比赛时长5个小时,包含9-13道正式赛题1道热身题。热身题将在下方给出,正式赛题在比赛开始后才会开放。
  3. 每一道正式赛题包含small和large两个独立部分,其中small占10分,large占20分,即一道正式赛题总分30分;热身题只有一个部分,不占分。每一个部分,在选手提交的解题材料(可能是程序、答案等形式)通过测试后,选手可以获得对应部分的所有分数。
  4. 队伍排名按照总得分降序排序,对于得分相同的队伍,按照罚时升序排序。罚时的计算方式如下:对于正式赛题的每一个部分,罚时计算为第一次通过时间加上在这个部分上的错误提交次数乘以20分钟;热身题的罚时等于负二十分钟,即通过热身题可以减免二十分钟的罚时;一个队伍的罚时等于所有通过的部分的罚时之和。

奖项设置

获奖队伍的所有成员须均为在校学生(包括中小学、大学本专科及全日制硕士、博士研究生,含本年度应届毕业生),其余队伍不计入最终评奖。

本次比赛奖项设置如下:

一等奖:冠军队伍 3000RMB/人

二等奖:亚军季军队伍 1500RMB/人

三等奖:4-6名的队伍 1000RMB/人

优胜奖:7-15 名的队伍

最快解题奖:最快通过某一道正式赛题的large部分的队伍

顽强拼搏奖:比赛结束前最后通过某一道正式赛题的某个部分的队伍

阳光普照奖:从得分不为0且没有获得以上奖项的队伍中随机抽取五支队伍

后四个奖项的获奖队伍将获得由美团提供的精美定制礼品,奖品会在后续通知中公开。

赛事流程

  1. 注册报名:5月1日中午12:00-5月10日中午12:00内填写下方问卷报名
  2. 加入交流群:北大算协&美团比赛交流群(群号947064269)
  3. 积极备赛:尝试并解决热身题
  4. 测试赛:5月15日晚上19:30-20:30
  5. 比赛时间:5月17日中午13:00-18:00
  6. 赛后交流:5月17日晚上20:00,由命题组直播进行题目讲解
  7. 获奖名单揭晓:5月19日中午12:00

指导与出题人

本次赛事邀请了北京大学的罗国杰教授和张勤健老师作为赛事顾问。

同时我们也邀请到了杜瑜皓、金策、The NANO团队以及其他很多不愿透露姓名的优秀出题人们来为这场比赛命题。

热身题

本次比赛的热身题是一道数独。作为热身题,欢迎大家在赛前讨论、并尝试用各种方式解决它。

热身题

规则

  1. 数字 1-9 在每行每列以及每个九宫格内部都必须出现恰好一次。
  2. 对于每一条曲线,从带有圆球的一端开始,这条曲线严格经过(不包括角)的数字必须严格递增。

在正式比赛开始后,热身题的提交将会开放:提交格式是一个9行9列空格隔开的数字矩阵,表示这个数独的一种填法。

选手须知

本赛事秉承公平公正的原则,严厉查处作弊行为。参赛选手需遵守选手须知,每支队伍独立完成比赛。在比赛结束后,我们会通过代码查重等方式来检测作弊行为,并取消作弊队伍的评奖资格。参赛选手应当认真阅读下述选手须知,一旦报名成功,默认参赛者接受并承诺遵守相关规定。

  1. 正式比赛过程中允许同一个队伍的多名选手同时进行解题,并允许选手自由使用各类辅助工具、互联网上的教程信息。
  2. 正式比赛过程中所有赛题相关的讨论只能在队伍内部进行
  3. 比赛过程中禁止对评测系统作任何形式的攻击行为
  4. 在比赛结束后的30分钟内,选手需要整理所有正式赛题相关的解题材料(包括代码、草稿等)并以指定的方式上传,以作为作弊处理工作的参考。
  5. 本次比赛的赞助商有权获得参赛者的报名资料。
  6. 北京大学算法协会对赛制保留最终解释权。

报名方式

扫描下方二维码填写表单,审核通过后,工作人员会在五日内和您联系。

期待您的加入!

报名二维码

常见问题

  1. 好感兴趣,怎么报名本次比赛呀?

    扫描上方二维码,填写问卷信息提交报名即可。本次比赛以队伍为单位进行报名,一个队伍最多包含三名队员,当然我们也欢迎单人队伍与双人队伍的参加。

  2. 想和同学们在线讨论,可有组织收留?

    欢迎加入官方交流群“北大算协&美团比赛交流群”(群号947064269),如遇问题可以在群里进行讨论或者发送邮件至北京大学学生算法协会(pkusaa@yeah.net)

  3. 想和来自不同学校的朋友一起参赛,可以吗?

    本次比赛的队伍没有学校的限制,欢迎呼朋唤友参加赛事。如果希望深入交流,可以加入“北大算协&美团比赛交流群”(群号947064269)。

  4. 已经报名,想好好学习备赛,有推荐资源吗?

    本次比赛在传统算法竞赛的基础上,会包含形式更加灵活的题目。如果对算法竞赛的知识感兴趣,可以访问OI Wiki ( https://oi-wiki.org/ )。 如果想要练习多样化的题目,可以尝试一下往年IPSC的赛题 ( https://ipsc.ksp.sk/ )。

  5. 还有其他问题想问,怎么咨询?

    加入官方QQ交流群(群号947064269),可以直接在群内咨询。

本次活动最终解释权归北大算协所有。

UOJ Test Round #2 题解

2017-01-08 20:13:52 By jiry_2

直播看着看着发现题解还没写,反正题目比较简单,我就随便写一下题解然后就接着去浪吧。

P.S. 写好一句话题解被吕老师叫回来重写了,伤心到变形。

感觉这一套题虽然总体难度不大,但是细节比较多,套上捆绑还是比较恶心的..而且验题的时候感觉样例比较弱(造题的不是我我不背锅)

看了一下榜感觉这个难度挺兹瓷的?以后就按照这个出吧。

题目排列顺序

from jiry_2,数据 from cy

算法一

聪明的你肯定发现了把所有位置按照权值第一关键字升序,下标第二关键字降序排序,依次分配 $1$ 到 $n$ 这 $n$ 个数就直接 work 了。

咦我好像不会排序那怎么办办呢?只好写个冒泡排序了。

时间复杂度 $O(n^2)$,期望得分 $60$ 分。

算法二

哇我好像知道一个叫做 std::sort 的东西耶,赶紧来试一试吧。

时间复杂度 $O(n \log n)$,期望得分 $100$ 分。

题目交流通道

from jiry_2,数据 from SkyDec

算法一

先来考虑 $d_{u,v}>0$ 的情况。

对于边 $(u,v)$,我们先来看是否存在一个点 $k$ 满足 $d_{u,v}=d_{u,k}+d_{k,v}$,如果不存在这样的 $k$,那么这条边的权值就只能是 $d_{u,v}$,否则这条边只要大于等于 $d_{u,v}$ 就可以了,即有 $K-d_{u,v}+1$ 种方案。把所有边的方案乘起来就可以了。

时间复杂度 $O(n^3)$,期望得分 $30$ 分。

算法二

考虑边可以等于 $0$ 的情况,这时 $d_{u,v}=0$ 的边肯定在图中连成了若干个团。我们把每一个团给缩起来。

两个团之间的点对距离一定是相等的,考虑团与团之间的边,此时相当于有重边的 $d_{u,v}>0$ 的情况。假设这是一条 $a$ 重边,如果存在 $k$ 有 $d_{u,v}=d_{u,k}+d_{k,v}$,那么所有边只要大于等于 $d_{u,v}$ 就可以了,即有 $(K-d_{u,v}+1)^a$ 种方案。如果不存在,那么至少要有一条边等于 $d_{u,v}$,其他边都要大于它,即有 $(K-d_{u,v}+1)^a-(K-d_{u,v})^a$ 种方案。

考虑团内部的边,每个团肯定由 $0$ 的边连成了一个联通块,这是一个经典的容斥,令 $f_i$ 为 $n$ 个点的距离为 $0$ 的团的方案数,$g_i$ 为 $n$ 个点的图的方案数。则有 $g_n=(K+1)^{\binom{n}{2}}$,$f_n=g_n-\sum_{i=1}^{n-1} f_i \times g_{n-i} \times \binom{n-1}{i-1} \times K^{i(n-i)}$。

把所有部分的答案乘起来就好了。时间复杂度 $O(n^3)$,期望得分 $100$ 分。

当然最重要的是要判对无解的情况,大致有四种,分别是 $d_{i,j} >K$,$d_{i,i} \neq 0$,$d_{i,j} \neq d_{j,i}$,$d_{i,j} > d_{i,k}+d_{k,j}$,大力 check 一下就可以了。

题目难度提升

from jiry_2,数据 from cy

这道题还是挺简单的,本来是出给 hiho 的 A 题,后来感觉有点难了(其实是最开始想简单了)就出 UR 了,感觉主要难度在于细节稍微多了点。

算法一

按位枚举,判断合法性只需要把后面所有的数升序排序然后检查一下就可以了。

直接裸写时间复杂度 $O(n^4)$ 已经够了,期望得分 $20$ 分。

算法二

考虑没有相同的数的情况。那么这个时候假设中位数是 $m$,新加入的数是 $a$。如果 $a < m$,那么中位数减少;如果 $a > m$,那么中位数增大;否则中位数不变。

按位枚举,一个前缀有解当且仅当前缀的中位数 $m$ 小于等于所有还没有放的数。

最开始先放最小的数,每一阶段放两个数进去。阶段开始时因为有奇数个数,所以中位数一定落在某个数上。

假设开始时中位数是 $m$,大于 $m$ 的第一个还没有放的数是 $K$,如果 $(m,K)$ 中已经有数放了,那么这个数不管放什么都可以,直接放最大的数就可以了。否则新放入的数 $a$ 一定要满足 $a+m \leq 2K$,即 $a \leq 2K-m$,令 $R=2K-m$。如果 $(m,R]$ 中已经有数放了,直接放最大的数就可以了,否则找到 $(m,R]$ 中最大的数放进去即可。

假设此时中位数是 $M$,大于等于 $M$ 的第一个还没有放的数是 $L$,如果 $(m,L)$ 中已经有数放了,那么直接放最大的数,否则就只能放 $L$ 了。

可通过第 4 个子任务,结合算法一可获得 $50$ 分。

算法三

有相同的数其实也不难。令所有数的中位数是 $m$,如果小于等于中位数的数中没有重复出现的数字,那么算法一仍然适用,否则令 $R$ 为第一个小于等于 $m$ 的重复出现的数字。

那最开始两个数最大字典序的情况一定是两个 $R$。因为如果更大的话中位数就没机会落在重复数上了,这时就满足算法一的性质,然而最大的数还没有放,所以无解。

放了两个 $R$ 后接下来就可以贪心了,每次放一个最大的数和一个小于等于 $R$ 最大的数,这个时候中位数在两个 $R$ 中左右横跳,一直没有变化,直到小于等于 $R$ 的数都用完了。这时就回到了算法一的情况,接着用算法一就可以了。

如果暴力实现的时间复杂度 $O(n^2)$,期望得分 $40$ 分。

可以发现所有的操作都是可以用 set 方便的做到。时间复杂度 $O(n \log n)$,期望得分 $100$ 分。

后半部分直接按位枚举也是可以的,稍微优化一下可以做到 $O(n \log^2 n)$ 或者 $O(n \log n)$,细节会稍微少一点。因为要降难度,所以也没去卡 $O(n log^2 n)$ 的做法,感觉还是比较良心的。

暂别

2016-07-27 21:55:56 By jiry_2

众所周知智障少女九条可怜一夜之间就要变成大学生了。

虽然名字写的和 vfk 一样但是感觉自己并写不出来那样的文章,那就只好试试老干部流啦。

我大概是在两年前的这个时候第一次听到 uoj 的,应该算是第二批用户吧,那个时候 uoj 群里也只有不到 100 人,大家每天热衷于交个 A+B 然后自己 hack 自己;后来因为评测机压力太大,vfk 把这项娱乐活动给禁止了,大家就开始水群;再后来因为 uoj 群太水了,vfk 就搞了个叫三连击的东西出来,大家就开始专注举报三连击。

然后最开始的时候,uoj 首页除了 rating 排名,还有一个叫做通过题数排名的东西,然而没过两天,就有一大堆小号贴着别人的代码愉快到了榜首,然后这个功能就被 ban 了。

那个时候自己刚刚被 NOI 类别杀,心灰意冷,每天除了睡觉吃饭就想着出偏题报复社会。憋了一个暑假出出来三套垃圾题,DZY Loves Graph就是其中一道(其中还有一道放出来的题目是 DZY Loves Math VIII),当时出的时候标算是可持久化并查集什么的。后来听说 UOJ 要出 UER,然后自己就投了这道题,vfk 一眼艹了标算然后就把这题收了[捂脸]。而且后来好像还把标程写错了,如果没记错的话这题应该是 UOJ 上第一个被 Hack 的标程,在这之后这种事情好像就渐渐的多了起来2333。

我第一次给 UOJ 出题的幕后故事差不多就是这样的,那个时候自己出题的口味也是非常不正常,之前还出了一大堆奇形怪状的高斯消元题。后来跟着集训队爸爸们做了一百多道 CF 题之后渐渐知道了怎么出题,也渐渐的有了正常的评价题目好坏的观念,之后的两年也算是断断续续的给 UOJ 出了挺多题吧:

DZY Loves Graph怎样更有力气智商锁懒癌信息的交换决战圆锥曲线开学前的涂鸦量子态的棋盘元旦老人与汉诺塔元旦老人与数列最强跳蚤思考熊票数统计合唱队形奇怪的线段树

列出来发现居然有 15 道题,惊了,好多呀..然而翻了一下好像并没有人同时 A 了这些题 QAQ。

在这么多题里面我自己最喜欢的就是 懒癌 啦,简直就是出题生涯的巅峰。之后就是 元旦老人与数列思考熊 了,虽然后面那题出了出题事故有点小遗憾,但就出这些题的 idea 来说,感觉还是挺自豪的。最后就是 奇怪的线段树 啦,这道题应该是我出了这么久题第一道网络流题,感觉意外的不错 2333 考场上被稳爷爷直接碾过去吓得我瓜子都掉了。

有点小遗憾的就是 开学前的涂鸦思考熊 这两题了,它们都或多或少出了点出题事故。仔细一看好像到现在都还没有真正的勇士写前面这题的标算 QAQ 有没有老司机愿意来写一波大 DP 呀,要不第一个用标算 A 这题的人来找我我请他吃一顿饭吧 2333

再来讲讲自己出比赛的经历吧。泥萌问我 UOJ 管理员辛不辛苦,当然是辛苦的啊。感觉当了这么久管理员,学会的一个道理就是:没有什么 ddl 是通一次宵解决不了的!

在当管理员之前就为了调 开学前的涂鸦 熬到凌晨,这瘠薄题真的是怎么调都有错,当时真是意识模糊。后来造万圣节那场 UER 也是,数据各种有错,各种弱,万圣节的南瓜灯 的数据我造到了凌晨三点,最后好像还是太弱了,嗨呀这是最气的。然后就是 UNR 了,因为比赛时间正好和毕业旅行冲突,出发前一天晚上索性通了一波宵看了一波日出,把坑填了大半,后来实在来不及就随手丢到乐滋滋脸上拔腿跑啦。

还有一场不得不说的就是 UR#10 啦,在出这场之前我和乐滋滋突击学习了半个多月的抽代(为了看懂七爷的题解),然后在去清华集训的火车上我强忍着翔意写完了 Pascal 的交互库(咦好像大部分的时间是在看琅琊榜哎),直到比赛开始前10分钟才把所有东西做好。后来到了比赛结束前10分钟突然发现标程错了,还好数据造的机智大样例什么的都没什么问题,之后匆匆忙忙又是改标程又是改数据,等到题解发出来的时候已经十二点多了,意识模糊。

感觉造 UR 的故事实在太多了,一打开话题根本写不完啊..篇幅问题这儿就不写了,以后群里有讲故事活动的时候再说吧2333。

虽然造 UR 挺辛苦的,不过在看到大家愉快做(爆)题(零)的时候,感觉还是非常开心的!特别是在最后大家愉快讨(骂)论(我)题(毒)目(瘤)的时候,感觉一切付出都是值得的!

智慧的凝视

后来等到我 CTSC 身败名裂退役之后,因为自己沉迷守望先锋,所以投入在 UOJ 上的时间也少了很多,当时我和 vfk 的日常差不多就是:

vfk:jryjry 快来造 UR!jryjry 快去找题!

jry:好!我这就去问问!

啊守望先锋真 tm 好玩。

学习

所以实在是对不起大家了 QAQ 这段时间 UOJ 的比赛连续跳票的锅的确应该是我背。我印象当中有好几位想给 UOJ 投题的人,特别是有一道出题答题的小哥,真的是特别热心,题目改了一版又一版,但是那个时候自己处理的可能也是比较敷衍,草草了事,渐渐的就没了下文,实在是对不起了[鞠躬]。如果你们看到了这篇文章,如果还愿意的话,可以把题目发给下一代管理员们!我相信他们会认真处理的!(三句话不离甩锅)

说了这么多,也该说到正题啦!智障少女九条可怜已经成为了退役老人,也该淡出 UOJ 的出题圈了,之后也应该让现役选手们出一些有趣的题给大家了。当然如果有好的 idea 我自然也是会出题的,毕竟还是不想这么轻易的就让出出题数最多的 UR 出题人这个位置 2333。

接着就是大家期待已久的念 UOJ 下一代管理员名单的环节了!感谢这些勇士们义无反顾的接下了 UOJ 管理员的 debuff!他们是(之后可能会有补充):

matthew99, C_SUNSHINE, SkyDec, NanoApe, cy

最后就用 vfk 去年的话结尾吧。虽说博客题目是暂别,但是也不是暂别吧,因为UOJ 的团队一直在这里。我们会忙活 UOJ 的事,只是花的时间比以前少多了。

我很喜欢 UOJ,即使从 OI 退役了也如此,高三折腾 UOJ 的日子是最难忘的回忆,愿 UOJ 有更加美好的未来。

(话说是不是现在可以以“出比 noi 更像 noi 的比赛”为目标啦2333)

UOJ NOI Round #1

2016-07-13 19:03:19 By jiry_2

UOJ NOI Round #1 将于 7 月 16 日至 7 月 18 日举行。这是 UOJ 第一场 UOJ NOI Round。

Q:教练我只听说过 UER,UR 和打酱油的 UTR,这 UNR 又是什么呀。

A:因为马上就要 NOI 啦,既然大家都觉得 UER 太难了做 NOI 模拟一点都不清真,那么我们就彻底地来一次 NOI 全真模拟吧!

比赛时间

笔试模拟将于 7 月 16 日晚 19 点开始,将进行半个小时。

Day 1 的比赛将于 7 月 17 日上午 8 点半开始,将进行五个小时,共三道题。

Day 2 的比赛将于 7 月 18 日上午 8 点半开始,将进行五个小时,共三道题。

出题阵容

这次比赛的大部分题目来自于 IOI2016 国家候选队的队员,出题人有:

jiry_2xllend3, SkyDecmatthew99qmqmqmYJMWOI

这场比赛除笔试外将计入rating

比赛难度

比赛的难度将与 NOI2013 相近,相信对绝大部分选手来说题目是具有一定的挑战性的。

同时我们尽力确保了较多的部分分、较好的区分度以及考察内容的全面性,题目中还有着一道提交答案题,大家可以放心食用。

比赛奖励

这次比赛将会根据三次比赛的总分进行排序(如果存在同分将以两天的罚时总和作为第二关键字),其中比赛的前五名将成为这次训练的金牌得主,第六名到第十五名将获得银牌,第十六名到第三十名将获得铜牌。(得奖人数将根据参赛人数进行调整)

总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

UPD:比赛已经结束。

颁奖环节

经过管理员们的讨论,决定发放15枚金牌,25枚银牌,50枚铜牌,同时总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

恭喜获得抱枕的选手:

  1. WuHongxun
  2. xumingkuan
  3. WrongAnswer

获奖名单见排行榜

jiry_2 Avatar