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

获奖名单见排行榜

UOJ Easy Round #6 题解

2016-07-01 16:26:54 By jiry_2

票数统计

By jiry_2

这题数据是瞎随的,所以好像出现了一些奥妙重重的得分分布QAQ

算法一

爆枚所有可能的情况,检验每一个限制是否合法。

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

算法二

不难发现当 $x > y$ 时后 $y_i$ 位用户中,恰好有 $x_i$ 位投了通过肯定是不成立的,当 $x < y$ 时后 $x_i$ 位用户中,恰好有 $y_i$ 位投了通过也肯定不成立。

所以只有当 $x \neq y$ 时限制是唯一确定的。

因此如果有解,本质不同的限制最多只有 $O(n)$ 个,可以先把不同的限制去重掉,然后再爆枚所有情况判断。

时间复杂度 $O(T2^nn)$,期望得分 $50$ 分。

算法三

对于第六个点,所有限制都是针对前缀的。

不难发现这时限制把整个序列分成了 $O(m)$ 段并对每一段限制了 $1$ 的个数,因此每一段的方案数都是组合数,直接把它们都乘起来就好了。

时间复杂度 $O(Tn+n^2)$,结合算法二期望得分 $60$ 分。

算法四

先考虑 $x \neq y$ 的情况,这时考虑把对后缀的限制转化成对前缀的限制。

枚举所有人中投通过的人数,这样后缀的限制就变成了前缀的限制,直接用算法三求解就好了。

存在 $x=y$ 时,不难发现所有 $x=y$ 的限制中只需要考虑 $x$ 最大限制就行了,因为这个限制满足了剩下的 $x=y$ 的限制一定也满足了。

枚举限制 $x=y$ 被哪一边满足,答案就是前缀满足的方案数加上后缀满足的方案数减去两端都满足的方案数,这样就把 $x=y$ 转化成了只对前缀或者只对后缀的限制。

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

寻找罪犯

By sevenkplus,题解By C_SUNSHINE

算法一

暴力枚举每个人是否是罪犯,然后扫描所有证言判断是否为真,并判断是否满足条件,时间复杂度$O(2^m m)$。

算法二

对于每个人,建立一个$01$变量表示他是否是罪犯,对每一条证言,建立一个$01$变量表示它是否为真,那么就可以把要求转化为一些条件。

对于一条供词$i$,建立条件:“若此供词为真,则某个人是/不是罪犯”。

接着对于每个人,建立条件:“若此人不是罪犯,则其说的每一条证言都为真”。

由于一个人最多说一句假的供词,则对于同一个人说的任意两条供词,建立条件:“若供词A为假,则供词B为真”。

条件都可以写成“若$x_i=a$则$x_j=b$”的形式,这是一个2-SAT问题,可以使用经典的强连通分量算法求解。

时间复杂度$O(n+m^2)$。

算法三

对于完全图的情况,可以先特判所有人都是罪犯的情况,否则必有一个人不是罪犯,枚举任意一个人不是罪犯,则通过他的供词可以得知其他所有人是否为罪犯。

时间复杂度$O(n^3)$。

算法四

考虑推广算法二,对一个有$k$条供词的人,建立$3k$个$01$变量,分别表示第$i$条供词是否为真,前$i$条供词是否都为真,后$k-i+1$条证词是否都为真。

那么若前$i$条供词为真,则前$i-1$条供词也为真,且第$i$条证词也为真,对于后缀也是一样,这部分边数是$O(m)$的。

那么可以建立条件的时候就可以使用前缀后缀来优化,若一个人为真,只要长度为$k$的前缀都为真即可。

对于一个人最多说一条假的供词这个限制,若一个人的第$i$条供词为假,则前$i-1$条和后$n-i$条证词都为真,这部分的条件数就变成$O(m)$的了。

于是变量数和条件数都是$O(n+m)$的,总复杂度就是$O(n+m)$。

逃跑

By SkyDec

算法一

考虑化简方差,设d为每次经过的点的个数。

$$E=\sum (d-avg)^{2}=\sum d^2-2*d*avg+avg^2=(\sum d^2)-avg*2*(\sum d)+avg^2*all$$

根据平均数的定义,有

$$avg=\frac{\sum d}{all}$$

所以有

$$E*all=(\sum d^2)*all-(\sum d)^2$$

$all$可以很简单地计算,于是问题就变成了:求$\sum d^2$和$\sum d$,即经过的点的个数的平方之和,经过的点的个数之和。

我们可以$O(4^n)$枚举每次往哪个方向走,统计一下经过了几个点,就可以直接计算了。

时间复杂度$O(4^n)$,期望得分20分

算法二

考虑部分分$w_3=w_4=0$

即不可能往左右走,也就是说行走的区域只有一维了。

一维区域经过的点显然是一个区间,经过的点就是这个区间里整点的个数。

令$f[i][j][k][x]$表示走了$i$步,当前经过的区间为$[j,k]$,当前的位置是$x$的方案数,直接模拟下一步往哪儿走转移即可。

时间复杂度O(n^4),期望得分20分

算法三

考虑如何快速地计算$\sum d$。

考虑计算$\sum (n+1-d)$,也就是经过一个点时上次早已经过这个点的点的个数。

显然$\sum d=(n+1)*all-\sum(n+1-d)$。

考虑一段长度为$n$的序列$L$,每个元素是$(0,1),(0,-1),(1,0),(-1,0)$中的一种。

那么如果对于坐标$(x,y)$,设序列$c_1..c_k$为满足$(\sum_{i=1}^{t}L[i])=(x,y)$的所有$t$按顺序排列的序列

那么对应的,对于$1\leq i\leq k-1$,有($\sum_{j=c_i+1}^{c_{i+1}}L[j])=(0,0)$

可以发现,一个出现了$k$次的点产生了$k-1$段没有前缀$(0,0)$的和为$(0,0)$的序列。

而显然出现了$k$次的点对我们要求的答案的贡献是$k-1$。

所以根据期望的线性性,我们只要计算有多少段连续子序列满足和为$(0,0)$且没有前缀$(0,0)$即可。

设$f[i]$表示长度为$i$的答案。

设$g[i]$表示长度为$i$的和为$(0,0)$的序列有几种。显然$i$是奇数时,$g[i]=0$。

$$g[i]=\sum_{j=0}^{i/2}\frac{i!}{j!j!\frac{i-j*2}{2}!\frac{i-j*2}{2}!}*w_1^jw_2^jw_3^{\frac{i-j*2}{2}}w_4^{\frac{i-j*2}{2}}$$

相当于枚举每种向量的个数,排列组合了一下。

然后$f$的计算就很显然了。

$$f[i]=g[i]-\sum_{j=0}^{i-1}f[j]*g[i-j]$$

统计答案时只要算$\sum_{i=1}^{n}f[i]*all^{n-i}$就行了

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

算法四

在上个算法里,我们通过比较直观的转换将题目转化成了求无前缀$(0,0)$的和为$(0,0)$的段数。

然而当我们求$\sum d^2$时,就无法直接用期望的线性性计算了。

设$p=(n+1-d)$,即上个算法里的重复计算次数。有:

$$\sum d^2=\sum (n+1-p)^2=all*(n+1)^2-2*(n+1)*\sum p+\sum p^2$$

$\sum p$我们已经可以轻易地计算了,现在就考虑计算$\sum p^2$了。

设布尔数组a[l][r]表示$[l,r]$是否满足条件。

那一个数列的贡献就是$(\sum_{l\leq r}a[l][r])^2$

即$$\sum_{l\leq r}\sum_{x \leq y}a[l][r]*a[x][y]$$

然后现在就有期望的线性性了,我们只要对于每对$(l,r)$,$(x,y)$计算他们同时满足条件的方案数即可。

当区间不相交时,他们互相几乎不影响,直接计算即可。

当只有一段时我们可以简单地记录坐标$dp$,并保证中途不经过为$(0,0)$的点即可。

那么当有两个区间时,我们可以先$DP$第一个区间,然后中途加入一个区间,当一个区间和变为$(0,0)$时就意味着他终止了。

当区间相交时,考虑$f[i][x1][y1][x2][y2][2]$表示当前长度为$i$,第一段的和为$(x1,y1)$,第二段的和为$(x2,y2)$。当前有几个区间。每次转移考虑下一步走哪个方向,要不要加入区间即可。

时间复杂度$O(n^5)$,期望得分40分

算法五

考虑第七个点,他的$w_1=w_2=w_3=w_4$,显然$w$之间是一种比例关系,全部相等就等价于全为$1$,我们用上个算法的程序打个表即可。

期望得分10分

算法六

区间的相交分为两种情况:包含和不包含。

我们先考虑不包含的情况,这样肯定分成了三段:只属于第一段的,重合的,只属于第二段的,我们设他们分别为$A$,$B$,$C$。

考虑$A$,我们枚举$A$的和,设为$(Ax,Ay)$,那么我们可以轻易地推导出:B的和为$(-Ax,-Ay)$,C的和为$(Ax,Ay)$。

考虑$A$需要满足什么条件,由于只属于第一段,所以只需要满足没有前缀$(0,0)$即可。

设$g[i][x][y]$表示和为(x,y),长度为$i$,没有前缀$(0,0)$的方案数,这个可以用简单的$O(n^3)$dp得到。

考虑$C$需要满足什么条件,由于只属于第二段,所以只需要满足没有前缀$(Ax,Ay)$即可,即没有后缀$(0,0)$。

没后缀$(0,0)$跟没前缀$(0,0)$显然是等价的问题。

考虑$B$需要满足的条件,这个就比较复杂了,毕竟是重合的部分,他要满足第一段,所以他需要没有前缀$(-Ax,-Ay)$,即没有后缀$(0,0)$

他也需要满足第二段,即没有前缀$(0,0)$。

设$o[i][x][y]$表示和为$(x,y)$,长度为$i$,没有前缀$(0,0)$和后缀$(0,0)$的方案。

考虑容斥计算$o$。我们可以用$g[i][x][y]$作为总方案,那么考虑枚举最短的长度为$j$的后缀和为$(0,0)$。

那么前$(i-j)$的和就是$(x,y)$,他们只需要满足没有前缀$(0,0)$,也就是$g[i-j][x][y]$。

考虑长度为$j$的部分,他们的和为$(0,0)$,由于要求最短,所以他们也不能有后缀$(0,0)$,并且由于整段里不能有前缀$(0,0)$,所以他也不能有哪个前缀和前面的$(i-j)$构成$(0,0)$,即没有前缀$(-x,-y)$。

于是设$v[i][x][y]$表示长度为$i$,和为$(0,0)$,不能有前缀$(0,0)$和前缀$(x,y)$的方案数。

考虑容斥,设$f[i][x][y]$表示长为$i$,和为$(x,y)$的段数,那么可以以$f[i][0][0]$作为$v[i][x][y]$的初值。

考虑枚举第一次违反,设长度为$j$。

$(1)$当违反的是不能有前缀$(0,0)$时,相当于要求长度为$j$,和为$(0,0)$,不能有前缀$(0,0)$和前缀$(x,y)$的序列个数,可以由$v[j][x][y]*f[i-j][x][y]$转移过来。

$(2)$当违反的是不能有前缀$(x,y)$时,相当于要求长度为$j$,和为$(x,y)$,没前缀$(0,0)$和前缀$(x,y)$的序列个数,即前后缀都不为$(0,0)$的序列个数。可以由$o[j][x][y]*f[i-j][0][0]$转移过来。

而上面的$o$是从$v$转移过来的,并且每次转移长度都会变大,我们可以枚举长度从小到大后一起计算$v$和$o$。

考虑计算答案:

$$\sum_{l<=r}\sum_{(x,y)}\sum_{i=1}^{l-1}\sum_{j=1}^{n-r}g[i][x][y]*o[r-l+1][-x][-y]*g[j][x][y]*all^{n-(r-l+1)-i-j}$$

设$sum1[i][x][y]=\sum_{j=1}^{i}g[j][x][y]*all^{-j}$

那么答案就是

$$\sum_{l<=r}\sum_{(x,y)}o[r-l+1][-x][-y]*all^{n-(r-l+1)}*sum1[l-1][x][y]*sum1[n-r][x][y]$$

以上大多数$dp$状态数都是$O(n^3)$,转移都是$O(n)$容斥,所以复杂度是$O(n^4)$。

考虑包含的情况,类似的,我们把他分成三段$A,B,C$,并枚举$A$的坐标为$(Ax,Ay)$。

那么$B$的坐标和为$(0,0)$,$C$的坐标和为$(-Ax,-Ay)$。

$A$只要满足没有前缀$(0,0)$,$C$只要满足没有后缀$(0,0)$。

$B$要满足没有前缀$(0,0)$且没有前缀$(-Ax,-Ay)$,即$v[j][-Ax][-Ay]$。

考虑计算答案:

$$\sum_{l<=r}\sum_{(x,y)}\sum_{i=1}^{l-1}\sum_{j=1}^{n-r}g[i][x][y]*v[r-l+1][-x][-y]*g[j][-x][-y]*all^{n-(r-l+1)-i-j}$$

我们可以类似上面地优化一下即可。

时间复杂度$O(n^4)$,由于很多状态其实是没用的,可以在$1s$内通过

期望得分$100$分

UOJ Easy Round #6

2016-06-26 23:24:38 By jiry_2

UOJ Easy Round #6将于7月1日星期五晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第六场UOJ Easy Round。咦为啥在这个节骨眼上搞 Easy Round 呢?因为我们出不出来题了NOI即将到来,是时候来一场小清新的 UER 来给大家实战演练一波了!

Q:真的是 NOI 难度吗,看了前几场的 UER 感觉不像啊。

A:难度会略高于去年 NOI 的难度,和几年前的 NOI 较为相似。具体来说,A题是一道难度低于 UR A 的题,B题和C题都是 UR B 的难度或更低。

2016年6月24日6点,连夜进行的英国脱欧公投计票工作接近尾声。英国广播公司报道称,根据初步统计结果,约52%的英国选民投票支持英国脱离欧盟,英国脱欧已成定局。当日,英国首相卡梅伦发表声明,将辞去英国首相的职务。一时间,有关英国脱欧的话题,成为全球的焦点。

最近,由于 UOJ 管理员集体划水,UR 长期跳票,引发了 UOJ 广大用户的不满。于是,大家决定在2016年7月1日晚举行全民公投,废除 UOJ。

因此,本次 UER 将以全民公投为主题。

出题人:jiry_2sevenkplus, SkyDec

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕!08c79db829dda067511bbfba48e04997 是获奖条件的 md5 码。比赛结束后将公布条件。

UPD:比赛已经结束!

echo -n 罚时最接近6小时6分钟6秒的选手,如有多个,取排名最高的 | md5sum
08c79db829dda067511bbfba48e04997

恭喜获得前 5 名的选手!

  1. lbn187
  2. maijing
  3. bright_sun
  4. bzoj
  5. cy

恭喜 zxozxo 获得 UOJ 抱枕一个!

UOJ Round #14 题解

2016-04-22 21:12:19 By jiry_2

最强跳蚤

By jiry_2,题解By C_SUNSHINE

算法一

显然直接把边权乘起来是不现实的(当然你想写高精度开根我也是兹瓷的),我们考虑每一个质因子$p$,它的次数必须是偶数。

那么我们就有了简单粗暴的算法1:从每个点开始dfs,维护每个质因数的出现次数,预处理每个数的质因数分解即可,复杂度是$O(n^2 \log n)$,空间复杂度$O(w)$。 如果使用map存次数的话,可以做到$O(n \log^2 n)-O(n)$的时空复杂度,期望得分30分。

算法二

我们把$w$质因数分解,每个出现过的质数离散化一下,可以发现至多出现$O(n \log n)$个不同的质数(事实上当$w/n$不是很大的时候这个数目是$O(n)$的)。

那么使用bitset维护每个质数的出现次数,再dfs就可以做到$O(\frac {n^3} {32})$了,但是这样并不能跑出$n=3000$,事实上我们直接对离散化之后的质数开桶统计就能做到$O(n^2 \log n)$了,期望得分50分。

算法三

对于$w \leq 80$的数据,由于80以内的质数不超过32个,我们可以对第$i$个质数分配一个权值$2^{i-1}$,一条边的权值就是$w$所有质因子的权值的异或,一条路径的权值就是每条边权值的异或,从根开始dfs求出根到每个节点的权值,那么$u \rightarrow v$是可行的当且仅当根到$u$的权值等于根到$v$的权值,把根到所有节点的权值排序统计一下即可。

时间复杂度$O(n \log n)$。

算法四

考虑推广算法三,其实我们可以对于每个质数,给它分配一个$[0,2^{64})$内的随机数,于是一条合法路径权值一定是$0$,而不合法路径只有$\frac{1}{2^{64}}$是$0$,这个概率可以忽略不计。剩下的按照算法4将根到每个节点的权值排序统计即可。

至于质因数分解,可以预处理$10^4$以内的质数表,然后每次暴力分解,复杂度是$O(\sqrt{w} + n \pi (\sqrt{w}))$,可以通过全部测试点。

人类补完计划

By matthew99,题解By C_SUNSHINE

算法一

对于$m \leq 20$的情况,我们可以暴力枚举每条边在不在$S_v$里,并判断是否符合题目要求,把合法的方案的权值加入答案中。

时间复杂度$O\left(m2^m\right)$,期望得分5分。

注意到不同的连通块之间的贡献独立,对每个连通块分别处理,可以通过第二个测试点得到10分。

算法二

观察题意其实就是枚举所有的基环外向树,$w$是非叶节点个数,把$2^w$加入答案。

那么我们首先考虑基环外向树的计数,第一步是环的计数。 环的计数可以非常容易的通过状态压缩DP来实现设$cir_{i,S}$表示集合$S$组成一条以$j$开头$i$结尾的链的方案数(令$j$为$S$中编号最小的元素), 转移时枚举$i$的下一个元素即可,要求和$i$直接有边且编号$>j$,最后对于每对$i,S$,若$i,j$之间由有边,则将$cir_{i,S}$加入集合$S$的答案$f_S$中。 注意一个环从$j$开始有两种不同的顺序遍历,所以最后答案要除以$2$。

接下来考虑集合$V$组成的基环外向树计数$cnt_V$,我们可以枚举环的集合$S$,然后把环缩成点,直接套用Matrix-Tree定理即可,这样处理所有$V$的总复杂度是$O\left(3^n n^3\right)$的。

我们考虑给权值一个意义,假设每个节点可以染成黑白两种颜色,叶子节点只能染成白色,那么只要计算染色的总方案数,一个$S_e$就会被恰好计算$2^w$次。

对于染色方案数的计算,我们可以考虑容斥原理,用总方案数减去存在黑色叶子节点的方案数,注意到基环外向树删去叶子之后仍然是基环外向树。

令$val_V = 2^{|V|}cnt_V$,枚举叶子节点集合$T$,则方案数

$$g_V = \sum_{T \subset V,T \neq \emptyset} \ (-1)^{|T|} \times val_{V-T} \times ways(T,V-T)$$

其中$ways(T,S)$表示$T$向$S$连边的方案数,为$T$中所有节点在$S$中邻接点个数之积,容斥时暴力计算就好,这部分时间复杂度是$O\left(3^n n\right)$的。

于是这个算法总的复杂度就是$O\left(3^n n^3 \right)$,期望得分30分。

算法三

算法2的时间复杂度瓶颈在与求$cnt_V$上,我们考虑换一种计数方式,把$cnt_V$的计算和答案的计算放在一起。

首先考虑$V$集合的权值和计算,对于$V$的每一个子集$T$,我们都计算出叶子节点集合为$T$的基环外向树个数$g_T$,那么权值和就可以直接计算了。

依旧使用容斥原理,令$h_T = cnt_{V-T} ways(T,V-T)$,即$T$为叶子节点集合的子集的方案数,然后对$h$做子集反演得到$g$:

$$ g_S =h_S + \sum_{S \subset T} (-1)^{|T|-|S|} \times h_T $$

那么显然$V$集合对答案的贡献就是$2^{|V|}f_V+\sum_{S \subset V,S \neq \emptyset}\ \ 2^{|V|-|S|} \times g_S$。

接下来考虑$cnt_V$如何计算,对于每个$V$首先把单独为一个环的情况$f_V$加入答案, 然后既然我们已经求出了以任意集合$S$为叶子的基环外向树方案数$g_S$,直接把$cnt_V$加上所有$g_S$的和即可。

计算$h_T$的总复杂度是$O\left(3^n n\right)$的,子集反演可以使用$O\left(2^n n\right)$的快速算法,总复杂度也是$O\left(3^n n\right)$,期望得分70分。

算法四

我们采用一种新的思考方式,考虑树的prufer编码,每次选取最小的一个叶子删去并将其邻接点加入prufer序列。

具体令$dp_{V,S}$表示$V$集合组成的$S$不能为叶子的基环外向树数目。

转移时我们令$k$为$V-S$中编号最小的节点,我们有两种转移方式:

1.令$k$为叶子,并将$k$删去,那么我们在$k$的邻接点中选取一个节点$l$,将$l$设置为可以为叶子。

2.将$k$设置为不可为叶子。

当$V=S$时可以发现答案一定为一个环,即$dp_{V,S}=f_V$。

注意到这样的统计会有重复计数,因为对于一个基环外向树,令其点集为$V'$,非叶节点集合为$S'$,那么对于所有$V=V',S \subseteq S'$都会被$dp_{V,S}$计数一次, 共会被计数$2^{|S'|}$次,我们发现这恰好就是这个基环外向树的权值,那么对所有的$dp_{V,S}$求和即可。

时间复杂度也是$O\left(3^n n\right)$,期望得分70分。

算法五

考虑对算法2进行优化,算法2的瓶颈在于计算集合$V$构成的环套树的方案数,而这个方案数在算法3中我们可以枚举叶子节点的集合进行容斥,而算法3的瓶颈在于莫比乌斯反演。

我们考虑把算法2和算法3结合起来,我们直接枚举非叶节点集合$S$,在枚举$S$的超集$V$,枚举$V$可以使用dfs,在dfs的过程中计算$ways(V-S,S)$,使用如下容斥式子计算答案:

$$g_V = \sum_{S \subset V} (-1)^{|V|-|S|} \times val_S \times ways(V-S,S)$$

dfs之后统计$S$对于$V$的贡献即可,复杂度是$2^{n-|S|}$的,总复杂度就是$O\left(3^n\right)$了,期望得分100分。

matthew99的计数小课堂

大家好这里是matthew99,我来说一些更好的求每个子集组成的基环外向树的方法:

我们注意到算法二有一个很不优美的地方,为了求出每个子集的基环外向树个数,我们不得不使用了一个$O(3 ^ n n ^ 3)$的算法。后面的算法中给出了更好的求这个的办法,但我这里要扯一些其他的办法。

注意到我们如果求出每个点集中恰有$0, 1, 2, \cdots n$条边的连通图个数,那么我们就能求出每个子集的基环外向树个数,这个很容易用容斥得到。考虑记录每个点集边数为每一个值的任意图个数和连通图个数,我们用经典的思路,枚举$1$号点所在连通块是哪些点,然后再枚举这个连通块内的边数然后直接容斥即可,这样复杂度是$O(3 ^ n n ^ 2)$,期望得分50分。我们如果用二维集合占位多项式并实现对一个二元函数求$\ln$,我们可以将这一部分做到$O(2 ^ n n ^ 4)$,但其实际效率甚至不如直接容斥。

还有一个思路就是我们考虑有向图中的基环外向树可以看成就是每一个点恰好连出去一条边,无向图我们可以定向之后达到同样的效果。考虑记录每个子集,每个点恰好指定一条边连出去的图的个数,答案似乎是度数的乘积,这样我们似乎考虑直接套用前面所述的容斥算法就可以做到$O(3 ^ n)$了,但其实不然,由于是无向图我们可能会出现重边,但是我们注意到如果有重边,相当于一棵树上随便找一条边让它再被选一次,所以我们用Matrix-Tree定理$O(2 ^ n n ^ 3)$求出每个子集的生成树个数,然后在此基础上很容易实现$O(3 ^ n)$的容斥算法求每一个子集的基环外向树个数。

思考熊

By jiry_2

QAQ 这题的来源是我在做乐滋滋胡策的时候 YY 出的一个 idea,那个时候觉得这个 idea 还是挺厉害的,于是就接了这么一个 C 题的坑。

但是用 idea 造题这种事情毕竟不靠谱,在造题的过程中发生了各种各样的偏差..在经过了各种各样的挣扎之后,出出来这么一个题,有很多的不足之处 QAQ 求轻喷。

算法一

在询问时暴力枚举每一个可以使用的接应点,算出路径的权值和并更新答案。在计算路径的权值的过程中,需要计算两个点之间的 LCA。

如果直接使用倍增或者树剖计算,那么时间复杂度是 $O(nm \log n)$,期望得分 $7$ 分。

可以发现两个节点的 LCA,就是在欧拉序中,它们第一次出现的位置之间深度最小的节点。于是就可以用 ST 表来询问两个点之间的 LCA 。这样时间复杂度是 $O(nm)$,期望得分 $20$ 分。

算法二

如果只有插入的话,我们可以直接分块。在插入的过程中,一旦插满一块,我们就对每一个树节点预处理出到这个块中所有节点的距离的最大值,这是一个经典的树形 DP 的问题,我们可以在 $O(n)$ 的时间内求出答案。

在询问的时候,对于询问区间内完整的块,可以直接得到答案;对于块外的块,使用算法一中单次 $O(1)$ 的算法计算权值。这样的时间复杂度和空间复杂度都是 $O(n \sqrt n)$ 的。

那么现在问题来了,有删除的时候怎么办呢..有一种非常简单的方法就是不管..这样可以通过第三个 subtask,期望得分 $40$ 分。

肛道理

可能到这儿有人会说,出题人你会不会造数据,又偏题出出暴力放放..那么我们来肛道理..

如果知道了块的大小,卡这个做法是非常轻易的——只要在刚好插满一个块的时候反复重复插入和删除,这样时间复杂度就边 $O(n^2)$ 了。

但是问题来了..作为出题人,我根本不知道泥萌的块大小是多少 QAQ

在比赛的时候对着程序卡是一种可行的方案,但是我对着程序卡同样会被婊 QAQ 再加上如果写程序的时候加点奇技淫巧,比如拿输入数据 srand 一波然后随一个块大小出来,这样我即使是对着程序也卡不掉了..

所以最后想想索性都不卡了,因为如果我对着固定块长的卡了,却放了随机块长的过了,大家都不高兴是吧..反正只是暴力分嘛是吧..放过去了就放过去了..

难道就没有什么不存在被卡可能性的算法吗?难道就没有什么能卡这个的方法吗?当然都是有的..在后面会讲..

算法三

考虑 $w \geq 0$ 的部分分,我们来考虑一下如何快速求一个点到一个点集 $S$ 的距离的最大值。

我们可以发现,假设 $S$ 中距离最远的一对点是 $u$ 和 $v$,那么任意一个点 $x$ 到点集 $S$ 中的点的距离的最大值一定是 $x$ 到 $u$ 的距离或 $x$ 到 $v$ 的距离,证明还是很显然的。所以我们就可以使用两个点来代替一个点集。

我们可以使用线段树,对线段树的每一个节点来维护这个区间中的点集的信息。合并两个点集的信息时候,我们可以把这两个最远点对一共四个点放到一起,那么它们两两之间距离最远的一对点就是合并后点集中距离最远的两个点。可以合并信息,那么插入和删除操作就可以轻易地完成。

在询问答案的时候,只需要对定位出来的每一个子区间统计计算答案并更新就好了。

时间复杂度 $O(n \log n)$,可以通过第五个 subtask。

算法四

当 $w$ 可以小于 $0$ 时,维护直径的方法就不行了。

如果点集 $S$ 给定,我们可以先求出点集 $S$ 在树上的虚树,然后求出虚树上每一个点到它的子树中的关键点的最远距离 $d_i$ 和到子树外的关键点的最远距离 $u_i$ ,这个可以用两遍 DFS 预处理来解决。

现在要询问点 $x$ 到点集 $S$ 中的点的最远距离,我们可以先找到 $x$ 深度最大的祖先 $f$,使得 $f$ 在虚树的某一条边上,接着我们找到 $f$ 所在边的深度较深的端点 $v$,那么答案就是 $\max(dis(x,v)+d_v, w_x-w_v+u_v)$,其中 $dis(x,v)$ 表示两点之间的距离,$w_v$ 表示 $v$ 到根路径上所有边的权值和。

那么如何找到 $f$ 呢,我们可以在虚树中找到 DFS 序小于等于 $x$ 的最后一个节点 $l$ 以及大于 $x$ 的第一个节点 $r$(这个可以通过一次二分解决),那么 $f$ 就是 $x$ 和 $l,r$ 的最近公共祖先中深度较深的那个(这个可以通过脑补虚树的构建过程得到)。在找到 $f$ 后,我们二分出虚树中 DFS 序大于等于 $f$ 的第一个节点,那个就是 $v$ 了。

这个做法需要两次二分和两次 LCA,如果大家有更好的定位方法欢迎来和我讨论。

至于修改,我们先来考虑插入:在只有插入的时候我们可以使用二进制分组来解决。

我们可以对最普通的二进制分组算法进行一点拓展来支持区间查询操作:在把两个块合并成一个新块的时候,保留原来两个块,并把新块作为原来两个块的父亲,这样我们就得到了一个线段树结构。这样在查询的时候,就可以和线段树一样,先找到完整组成询问区间的 $O(\log n)$ 个块,然后分别在块中查询。

这样我们就把一个动态插入的问题转化成了静态的问题,时间复杂度 $O(n \log^2 n)$,空间复杂度 $O(n \log n)$,可以通过第四个 subtask。

算法五

最后我们来考虑删除操作,出这题的时候,核心在于一种将二进制分组拓展使得它可以在时间空间复杂度不变的情况下支持删除,这个虚树的背景只是我们为了找一道“只能用二进制分组做的题”的时候,硬套上去的。

普通的二进制分组之所以不能支持删除,是因为它的复杂度是均摊的,我们在它重建的时候,可以通过不停的删除和插入,使得它不停地合并一些非常大的块。

我们观察拓展后的二进制分组结构,它有 $t$ 层,从下到上第 $i$ 层的每一个块中有 $2^i$ 个节点。在原来的二进制分组中,我们相当于在每一个块插满后,立即重建这个块。

现在我们来考虑这个一个做法,在删除的时候,我们给所有涉及到的块(最右边一列)打上狗带标记,表示这个块的信息目前不对。在查询的时候,如果我们当前查询的块是狗带的,那么就递归对它的两个孩子进行求解。

当我们插满一个块的时候,我们不立即重建这个块,我们访问它的前驱块(同一层中相邻的前面那个块),如果它的前驱块是狗带的,就重建前驱块,否则就什么都不干。

接着我们来分析这个算法的复杂度。在这个算法中,我们相当于每时每刻都保证了每一层至多有一个块是狗带的,因此在查询的过程中,我们只会对 $O(\log n)$ 个块进行递归,因此需要查询的块的个数还是 $O(\log n)$ 的,于是查询复杂度还是 $O(\log^2 n)$。

接着我们对第 $i$ 层计算重建的代价,考虑这样两个事件:

  1. 给一个块打上标记,这个事件复杂度是 $O(1)$ 的。
  2. 重建一个块,这个事件的复杂度是 $O(i 2^i)$ 的。

令 $n$ 为序列长度,$len_i$ 为第 $i$ 层没有被打标记的块的总长度,令势能函数 $\phi (i)=|n-len_i-2^i|$。一次插入或者删除至多让势能函数增加 $1$,而一次事件会让势能函数减少 $2^i$,于是可以得到第 $i$ 层的均摊复杂度是 $O(ni)$。

让 $i$ 在 $1$ 到 $O(\log n)$ 范围内求和,那么就可以得到它的时间复杂度是 $O(n \log^2 n)$ 的。

因此这个算法的总时间复杂度是 $O(n \log^2 n)$,空间复杂度是 $O(n \log n)$。

算法二中,我们也可以一样,在分块的时候延迟重构,保证至多有一个块的信息是狗带的,这样时间复杂度就对了。

这就是这个算法的全貌了,当初在脑补出这题的时候感觉还是非常厉害的,但是在造数据的时候发现:根本没法卡暴力。

实际上面临的问题和算法二一样,如果选手在二进制分组的时候随机扰动一下,让出题人不知道你的代码的重构的位置,那么就没法卡了,实际上在期望情况下随机分组的复杂度的确是对的。

在这题的数据中,我对一些比较正常的重构位置附近卡了一下,而如果你在非常奇怪的地方分组的话,算法的常数会变得非常大,感觉随机分组的方法还是比较难通过的。

当然,硬要卡的话,这种随机分块和随机分组的方法还是可以卡的。我们可以用交互的形式,你的代码边运行,我的交互库边生成数据,发现你这几个操作特别慢,就赶紧删除回去再来一遍。

然而交互题实在是太麻烦了..要改成交互的话,我必须在交互库里内嵌标程,而交互库又必须要写 C 和 Pascal 的...

QAQ

于是只能选择狗带了QAAAAAQ

算法六

当然..上面这些算法基本没有最开始那棵树什么事..实际上在出题的时候我们也没怎么考虑那棵树..

本来想用凸包做这题的内容的,但是乐滋滋的胡策里已经有凸包了,后来又想用半平面交,但是半平面交和凸包又没有什么区别。再后来想用 mex,但是 mex 的题实在太多了,又不是很好。于是最后想了想发现虚树这玩意不是很好合并,决定就是它了。

然而在考前 10min 我突然发现好像可以在那棵树上直接做 QAQ 根本不关二进制分组什么事.. 感觉成功身败名裂了。

我们可以直接对最开始的树点分治,对每一层分治维护分治中心的的子树中的最远点(要维护最远点和扣除最远点所在子树后的最远点),这可以用线段树或者平衡树随便搞..

然后..就做完了..

QAQ

当然实际上要过这题也没有这么轻易..平衡树常数太大估计会 T,而最裸的线段树因为我们不知道值域,需要动态开节点,所以空间是 $O(n \log^2 n )$ 的,这肯定是过不了的。

但是我们可以用一些鬼畜技巧来优化掉空间的一个 $\log n$:对每一个节点,我们先规定它的线段树的值域为 $2^0$,然后在插满的时候,把值域修改为 $2^1$,然后暴力重构线段树并分配空间,再插满就修改成 $2^2$...

脑补一下就发现空间 duang 的一下变成 $O(n \log n)$ 了。

当然这样空间的常数比较大,具体能不能过这道题我不知道,这一块里的算法我也没有真正写过,都是我瞎 BB 的..(但是这样也已经掩盖不了这是一道垃圾题的事实了)

感觉出数据结构题实在太难了 QAQ 还是小清新计数题好..

这道题就当做是对一些奇技淫巧的推广吧..对我这种写不动数据结构的老年人来说这种方法还是挺 work 的,都是一些公式化的东西,也挺好写..

不过现在的科技这么发达,真正想要出又要新颖,又要只能用这种方法做的题目真的是太难了 QAQ

惨啊..

QAQ

UOJ Round #14

2016-04-19 15:46:13 By jiry_2

UOJ Round #14将于4月24日星期日晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第十四场UOJ Round。UOJ Round还是一如既往的省选及以上难度,欢迎大家来玩owo

公元前1184年4月24日,希腊联军巧施木马计攻破了特洛伊城,结束了持续10年之久的特洛伊战争。

在遥远的异世界,有一片跳蚤大陆,在跳蚤大陆上生活着人族与跳蚤族。经过了漫长的发展,跳蚤族在伏特跳蚤国王的带领下建立了自己的国家,而人族则以一个被称为pion吧的城市为中心,建立了城市联邦。千年来,人族与跳蚤族一直和睦相处,而且就在几年前,人族甚至还邀请了伏特跳蚤国王到pion吧中担任吧主的职位。

然而,就在人们都以为和平将永远持续下去的时候,灾难悄悄地降临了:一名叫做_叫我猪猪侠的人类,在pion吧中策划了兵变,将伏特跳蚤国王赶出了人族的领地并取而代之。很快,受到侮辱的跳蚤国王率领着百万跳蚤大军包围了pion吧——人族和跳蚤族的战争一触即发。

因此,这一场比赛将围绕着这场战争展开。

出题人:jiry_2matthew99, jiry_2

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕!805d8caf8307b6e26f0bc9e1e17cb84f 是获奖条件的 md5 码。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD:比赛已经结束!

echo -n 所有通过A题的人中A题提交次数最多的 | md5sum
805d8caf8307b6e26f0bc9e1e17cb84f

恭喜获得前 5 名的选手!

  1. r_64
  2. cy
  3. zhangzj
  4. YMDragon
  5. faebdc

恭喜 YMDragon 获得 UOJ 抱枕一个!

UOJ Round #13 题解

2016-04-10 20:19:58 By jiry_2

大家好这里是写题面的JRY。

最近因为种种原因,UR 跳票了半个多月的时间,不过终于,新的一场 UOJ Round 还是和大家见面啦。(在某学堂的提醒下,管理员们终于想起来还有UR这回事了...

因为写题面的人比较懒,所以这一次的标题就用了杜老师的格式:)

希望大家能够喜欢这一次的题目owo

Yist

By matthew99

算法一

直接状压每一种可能的子序列,时间复杂度$O(2 ^ npoly(n) + q)$,期望得分30分。

算法二

二分之后贪心每次删除最小的数,判断是否可行。由于删除一个数会让更大的数“更容易”被删,所以这个算法显然是正确的。

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

算法三

使用平衡树等数据结构优化算法二,时间复杂度$O(qn \log ^ 2n)$,由于常数大可能较难通过90分的数据。

算法四

我们考虑到对于一个数,删除它最小需要的区间长度是多少,如果我们在序列左右都加上一个无穷小且没有被删除,考虑找到它左边没有被删除的第一个比它小的位置$u$,右边没有被删除的第一个比它小的位置$v$,那么需要的区间长度就是$(u, v)$这个开区间的长度减去这个区间中所有比它小且需要删除的数的个数。答案就是所有数对于的区间长度的最小值。

从左往右扫一遍,并用set或者什么其他数据结构维护一下,可以求出所有的$u$和$v$,然后从小到大加入,用树状数组或者什么其他数据结构维护一下即可求出区间中所有比它小且需要删除的数的个数。时间复杂度$O(qn \log n)$,期望得分90分。

算法五

算法四中提到,需要的区间长度就是$(u, v)$这个开区间的长度减去这个区间中所有比它小且需要删除的数的个数,实际上,我们只需要用开区间的长度减去这个区间中所有需要删除的数的个数即可。

考虑一个数,假设区间中有一个数需要删除且比它大,那么显然这个比它大的数所对应的区间长度比原数短,所以这样显然不会影响答案(因为我们要求的只是最小值)。

所以我们只要求出$u$和$v$即可。

这样很多劣于线性的算法都能AC,这里列举几个:

维护A的单调栈,并在上面二分,由于常数小可以AC。

用ST表加上二分,然后加上一些优化$O(1)$去除一些显然不能更新答案的位置,也可以AC。

从大到小加数,所有被删除的和已经被加入的未被删除的位置记为1,其他位置记为0,则显然$u$和$v$分别就是左边和右边的第一个0,用并查集很好维护,如果不计读入的话时间复杂度为$O(qn \log n)$或者$O(qn \alpha(n))$。

算法六:

为了避免成为辣鸡卡常出题人,接下来我来讲讲线性做法,我的程序可以在时限的大约三分之一内出解。

其实很简单,对于所有被删除的位置,从大到小,每次暴力找$u$和$v$,并把所有访问过的地方标记,如果暴力的时候遇到了标记过的地方,那么可以发现原来访问到这个地方的数显然对应的区间更短,所以这个时候可以不用继续找$u$和$v$,直接考虑下一个位置即可,这样每个位置只会访问一次,若不考虑读入,则时间复杂度$O(qn)$,期望得分100分。

题外话:

我看到开场就有几个人交了正解的第一步:只找最大的一个数暴力找$u$和$v$更新答案,首先我样例是随机的所以你们很容易通过,其次我第一个点也是随机的所以你们也能过第一个点的十分,其他点应该都是过不了的,我想说的是你们就不会认真分析一下问题再提交么,实际上如果你们只找最大的几个更新答案也是很难有很多分的。考虑一下有两个阶梯,一个阶梯就是左右两边都是很小的未被删除的数,中间是比两边大的被删除的数和比被中间所有所有被删除的数都要大的未删除的数,那么如果第一个阶梯的数比第二个阶梯的数大而且第一个区间更短,那么更新答案的应该是第二个阶梯中的最大值,这样前面很多很多个数对应的区间都不是答案。

Ernd

By PoPoQQQ

因为A题和C题难度偏高所以出了道简单题平衡一下难度

ctb上瘾的出题人

算法一

对于subtask1,$n\leq20$。

暴力枚举接哪些水果,线性统计得分,时间复杂度 $O(n\times2^n)$。

用DFS的方式可以将复杂度降低至 $O(2^n)$。

期望得分 $10$ 分。

并没有什么卵用的算法。

算法二

对于subtask2,$n\leq1000$

我们定义“段”为满足对于其中任意相邻元素 $i$ 和 $i+1$ ,满足接到第 $i$ 个水果后可以接到第 $i+1$ 个水果的极长子区间。

考虑暴力dp,定义 $f_i$ 为以第 $i$ 个水果结尾的接水果序列的最大总得分,那么有:

$f_i=\max(f_i,f_j+1|\text{ 接到第 }j\text{ 个水果后可以接到第 }i\text{ 个水果})$

$f_i=\max(f_i,f_j-1+(i-j+1)^2|\text{ 第 }i\text{ 个水果和第 }j\text{ 个水果属于同一段})$

枚举 $j$ 进行转移,时间复杂度 $O(n^2)$,期望得分 $20$ 分。

算法三

我们考虑如何优化第一部分转移。

我们将水果都放在二维平面上,第 $i$ 个水果变成一个坐标为 $(a_i,b_i)$ 的点,那么容易发现,接到一个果子后,能接到的其他果子都在这个点的 $[45^\circ,135^\circ]$ 范围的方向上。

旋转坐标系,将每个点变为 $(b_i-a_i,b_i+a_i)$,那么接到一个果子后,能接到的其他果子都在这个点的右上方。

问题变成了一个二维偏序问题,用树状数组维护上升子序列即可。

观察subtask4,$n\leq5\times10^5$,答案不超过$10^4$,这意味着任意一段的长度都不会超过 $\sqrt{10^4}=100$。

第一部分转移使用算法三,第二部分转移暴力,时间复杂度 $O(n\log n+100\times n)$ ,期望得分 $40$ 分。

算法四

现在开始考虑如何优化第二部分转移。

注意到一段内的元素在按照 $b_i-a_i$ 排序后可能不连续,但相对顺序不会改变,因此我们不用担心转移顺序的问题。

这部分转移每段之间彼此独立,因此我们考虑对于每段内部分别计算。

观察转移方程 $f_i=\max\{f_j-1+(i-j+1)^2\}$,设 $P=f_j-1+(i-j+1)^2$ ,那么有:

$(f_j+j^2-2j)=2i\times j+(P-i^2-2i)$

我们发现这个式子可以斜率优化,将每个决策点 $j$ 化为平面上的点 $(j,f_j+j^2-2j)$ ,维护一个上凸包即可。

注意到我们维护的是上凸包而查询斜率 $2i$ 随 $i$ 单调递增,因此我们需要用一个栈而不是队列来维护这个凸包。

当然你要二分斜率也是完全可以的。

时间复杂度 $O(n\log n)$,期望可以通过全部测试点拿到 $100$ 分。

算法五

考虑用另一种方法优化第二部分转移。

观察到对于决策点 $j< k$,随着 $i$ 的增大,$(i-j+1)^2$ 的增长速率永远大于 $(i-k+1)^2$ 的增长速率,这意味着一旦某一时刻 $f_j-1+(i-j+1)^2 > f_k-1+(i-k+1)^2$,那么决策点 $k$ 将会永远不可能成为最优决策点,决策点 $k$ 可以删除。

由此我们发现了决策单调性,利用单调栈+二分的方法维护有效决策点,时间复杂度 $O(n\log n)$,期望可以通过全部测试点拿到 $100$ 分。

什么你问我subtask3是干嘛的?

照顾常数写残党/数据结构爆搞党/乱搞党。

以上。

Sanrd

By Stilwell

算法一

容易发现我们需要求的是$l\sim r$这段数的次大质因子之和,其中次大质因子定义为可重集的次大。

一个最简单的方法是将每个数都质因子分解,对于前50\%的数据,$r-l\leq 10^7$,这一段数的质因子总个数是$O((r-l)\log r)$的。

预处理出$\sqrt{r}$范围内的质数,考虑使用埃氏筛法进行分解,设当前质数为$p$,那么范围内第一个被$p$整除的数为$\lceil\frac{l}{p}\rceil p$,筛法消耗的时间和质因子总个数是相同的。

时间复杂度$O(\sqrt{r}+(r-l)\log r)$,期望得分50分。

算法二

原问题等价于求$1\sim n$的次大质因子之和。

考虑用$[1,n]$范围内的所有数做一个乘积背包,设$f[i]$表示现在乘积为$i$的数的最大质因子之和,升序枚举质因子可以保证当前质因子是转移后的最大质因子,转移前的最大质因子就是需要求的次大质因子,背包生成的每个数都是不重复的,所以可以直接计入答案。

容易发现$f[i]$的可能取值只有两种,0或$i$的最大质因子,取决于当前枚举的质数能不能组成$i$。这样表示状态明显非常浪费,可以尝试优化。

对于一个数$x(x\leq n)$,$x$的次大质因子一定$\leq \sqrt{n}$,所以$>\sqrt{n}$的质数我们可以考虑批量转移。

对于一个状态$i$,在背包时还能转移的质数需要$\leq\lfloor\frac{n}{i}\rfloor$,不妨直接用$\left\lfloor\frac{n}{i}\right\rfloor$来表示状态。

设$g[j]$表示$\lfloor\frac{n}{i}\rfloor=j$的数的最大质因子之和,由于$\lfloor\frac{n}{i}\rfloor$的取值只有$O(\sqrt{n})$种,所以状态数缩减为$O(\sqrt{n})$,原先$i\rightarrow ip$的转移变化为$j\rightarrow \lfloor\frac{j}{p}\rfloor$。

那么现在问题就转化为这样两部分:

  1. 求$\leq\lfloor\frac{n}{i}\rfloor$且$>\sqrt{n}$的质数个数。
  2. 用$\leq\sqrt{n}$的质数完成$g[j]$的背包。

先来解决第一部分,设$p_1\sim p_m$为$\leq\sqrt{n}$的质数,且$p_i < p_{i+1}$。

设$P[i][j]$为$[1,j]$ 范围内与前$i$个质数互质的数的个数,需要求的即为 $P[m][j]$。

设$l=\lfloor\frac{j}{p_i}\rfloor$,容易得到以下递推式 $$P[i][j]=P[i-1][j]-P[i-1][l]$$

递推时只需要计算$\lfloor\frac{n}{i}\rfloor$这$O(\sqrt{n})$个状态就能完成转移。

设质数密度为$O(\frac{1}{\log n})$,那么暴力递推的计算量可以估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{i}{\log i}\right)+\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{n}}{\log\sqrt{n}}\right)\thickapprox O\left(\frac{n}{\log n}\right)$$

当$p_{i+1}>j$时,一定满足$P[i][j]=1$。

所以,当${p_i}^2>j\geq p_i$时 $$P[i][j]=P[i-1][j]-1$$

因此,不必重新计算${p_i}^2>j$的情况,记录$j$最近一次被更新时的$i$的值,设为$pre_j$,在调用$P[i][j]$时,将编号$pre_j+1\sim i$间的质数计入。

考虑对于每个$\lfloor\frac{n}{i}\rfloor$计算有多少质数需要转移,计算量可估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{i}}{\log i}\right)+\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{\frac{n}{i}}}{\log\sqrt{\frac{n}{i}}}\right)$$

后半部分一定大于前半部分,故复杂度可以估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{\frac{n}{i}}}{\log\sqrt{\frac{n}{i}}}\right)\approx O\left(\frac{\int_0^{\sqrt{n}}\sqrt{\frac{n}{x}}\mathrm{d}x}{\log n}\right)=O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$$

完成了质数部分的计算,考虑$g[j]$部分的计算,暴力转移需要枚举每个质数再枚举每个状态,复杂度同样为$O\left(\frac{n}{\log n}\right)$。

回想前一部分是如何优化的,考虑如何省去$p^2>j=\lfloor\frac{n}{i}\rfloor$时的运算。

有$p^2>j\Rightarrow\lfloor\frac{j}p\rfloor < p\leq \sqrt{n}$,所以这些状态在以后的转移中只能再加入一个$\leq\sqrt{n}$的质数了,可以这样优化:

  1. 这一部分转移不再进行。
  2. 记录最后一次更新$g[j]$时的$p$,最后再计算相应的贡献。
  3. 当转移到这些$g[j]$时,不更新$g[j]$,直接统计剩下还能使用的质数个数,计算相应的贡献。

优化后复杂度和第一部分一样为$O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$。

时间复杂度$O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$,期望得分100分。

共 27 篇博客