UOJ Logo jiry_2的博客

博客

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

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$分

jiry_2 Avatar