Qingyu的博客

博客

Tags
None

现在用户主页会显示 List of Authored Problems

2024-09-13 17:06:25 By Qingyu

现在,每个用户的主页会显示所有由本人命制的题目。

QOJ 会在每道题目的题面开头显示这道题目的作者(如果有多个,则会按照字典序显示所有作者),作为对命题人的致谢。由于该列表为手动更新,如果你希望出现在你命制的题目的题面中,请联系我将你添加到对应的页面。

花言花语

2024-09-04 06:30:26 By Qingyu

2024 年 9 月 5 日更新:

这篇文章发出来后,引起了一些激烈的讨论,也有很多来自竞赛圈子内的家长、教练,以及一些非竞赛圈子内的朋友的阅读。无论你对我或是对花子持有什么态度,我很感谢大家能花费自己宝贵的时间来阅读我这篇充满个人情绪的拙作。

有许许多多我的朋友以及陌生人在我发出这篇文章后向我表示了支持,也有很多花子的朋友向我表示震惊,很难相信花子是这样的一个人。每个人为人处事的态度都是复杂的,无论花子对别人的态度与处事风格如何,我只能分享出我在过去几年与他交往的真实记录。

当然,也有一些不了解我的网友们质疑我的动机,甚至认为我在 IOI 赛前发出这样的博客,影响到中国队的成绩,是一种对集体荣誉不负责任的小人表现。此时此刻,我就坐在 IOI 2024 Day 2 的赛场旁,看着这些选手参加第二试的比赛。从 2022 年开始,IOI 中国国家队的训练工作,每年都有找到我进行帮忙。无论是在 2023 年国家队集训的选题与评测,还是在今年直接提供了平台进行训练,在哪怕我和一位国家队队员有私人恩怨的情况下,我也对这届国家队提供了我力所能及的帮助。这届国家队的每一轮训练,我都有所参与来提供技术支持。除了没有直接选择训练题目外(我在去年参与负责了训练试题的选择,而今年则仅仅提供了技术支持),我对这届 CHN 的支持丝毫没有因为这个人的存在而受到影响,请大家来评判,到底是谁的行为是在道德败坏,是在置集体荣誉如不顾。

  • 这些文字写在 9 月 4 日。由于此时我正在参加 IOI 2024 第二试选题大会,因此在第二试比赛开始后我才将这些文字公布出来。

I know this post won't add much value to the community. These stories might already be well-known in some parts of the Chinese CP community, but I always believed that it's not ideal to share the darker aspects and troubling history of someone who was once my best friend — and indeed, I tried my best to forget the existance of such people.

However, after a year filled with depression, suffering, anger, and inner turmoil, my emotions were ultimately ignited by a comment. Yeah. I can no longer suppress my feelings, and I feel so compelled to share my thoughts, even if they might come across as a bit of a rant.

写在本文的开头:我承认,本文的写作目的非常简单。在他又一次的抛开自己的承诺,选择装死希望将整件事情冷处理后,我不会再试图处于保护我们这段关系最后的遮羞布。为了减少本文的主观色彩,我会抛开我的主观情绪,只通过客观事实,不作评价地列举我在与来自中国人民大学附属中学的黄洛天同学交往的过程中,所发生的几件令人印象深刻的事情。
处于本文的篇幅,以及保护部分当事人隐私的考虑,我不会将其所做的所有事情与精彩发言全部包含在这篇博客之中。希望各位能从我列举的几件小事之中,体会到亲爱的花花是一个怎样的人。此外,本文涉及到了大量我与当事人的聊天记录。*于部分聊天记录篇幅过长,在正文中我会将所有相应的聊天记录全文引用。在每处引用中,我也会附上整段,无剪切的聊天记录全文,供读者进行参考。
本文仍在编写的过程中,有很多部分我只上传了部分图片或聊天记录,也有很多部分相关的证据有所缺失。由于有许多网友比较迫切的想要知道具体发生了什么,因此我特意提早将该草稿发布了出来。这些缺失的材料将会不定期在可预见的未来进行更新。

引子

今天是 IOI 2024 的第一个比赛日。在比赛期间,我在 UOJ 群内对中国国家队队员黄洛天(flowerMagicalFlower)的一些评价引来了一些网友的不解。

在我与这位同学的关系彻底爆了以后,很多网友们在私下里或公屏上都对我与他发生了什么事情感到好奇,而我则基本只对自己比较熟悉的网友们讲解了事情发生的经过。半年都过去了,不少人问我为什么不把他的所作所为公之于众,让大伙们看看这位光鲜亮丽的国家队员,是怎么在对待他亲口所说“最好的朋友”与“对我的 OI 帮助最大的人”。我当时没有这么做的原因非常简单 —— 当事人在其处于风口浪尖的那个下午,向我做出了承诺,让我请求我的朋友们不要将他的所作所为公之于众。

2.jpg
1.jpg

六个月过去了,也许是我的这位好朋友承诺的作品注入了过于真切的情感,以至于半年的时间都无法让其完成。因此,不如由我来亲自帮他回顾回顾,我与他到底都有哪些故事。

故事的起点

我与花子的相识起源于 2022 年的年初。在那时,其在 UOJ 群内询问有关 Petrozavodsk Programming Camp 的信息。作为可能是近几年与 PtzCamp 接触最多的几个人之一,我对国内还有其他的高中生对如何参加毛营感兴趣感到无比的惊讶。在第一次聊天中,我便向其介绍了作为当年算法竞赛头号强国,俄罗斯的各大派系的 Camp 以及其年度活动 Open Cup 的相关信息。

这里应当有一段我与花子相识时的聊天记录。由于这段聊天记录存储在我的另一台设备之中,我会在 IOI 2024 返程后补充这一段聊天记录的详细信息。

很快,我们成为了无话不谈的挚友 —— 也许不仅仅是挚友。凭借我对算法竞赛训练资源的理解,我甚至成为了他算法竞赛的教练。在他高一省选前,省选失利后返校期间,以及整个暑假训练的过程中,我都付出了我的全部来帮助他。

为什么我会这么做呢?老实说,我并不知道。也许我当时并没有什么朋友,因此我希望付出一切来维护这个我仅有的朋友的友谊。此外,我确实对哪怕是陌生人也抱有强烈的善意,希望我能发挥出自己的价值。这也是我在未来几年持续运行小青鱼训练中心2023, 2024)的核心原因 —— 既然算法竞赛训练是我为数不多具有深刻理解的 area,那我就以此创造一些自己的价值吧。

5.png

从每日在各种来源为他准备的题单(Open Cup/PA/PtzCamp/MWCamp/...),从各种渠道(在此具体列举就不太合适了)为搞来的模拟赛,以及与他一起进行的个人与组队训练(1, 2, 3, 4, 5,... 怎么搞了这么多不同的号,都记不全了),包括为他单独搞来的 opentrains、Open Cup、Bytedance Camp、Moscow-Workshops 的账号(对这些资源熟悉的同学自然十分清楚这些资源的含金量如何)…… 如果我要详细讲出我为他做出的贡献有多少,作用有多大,可能又是一篇长文才能讲清楚的内容(“深度揭秘小青鱼训练中心”)。因此,我不妨在此直接引用其在删完我好友后亲自做出的评价。

3.png
4.png

可以说,我为这位好朋友倾注了无限的情感,甚至产生了感情寄托 —— 无论是语音通话,还是文字交流,彼时的小青鱼几乎所有的时间都在与花子聊天。他成为了 QOJ 除我外唯一的管理员(https://web.archive.org/web/20221203224544/qoj.ac/user/profile/flower ),我们也相约一起为下一年的 ptzcamp 准备了一场比赛(这也成为了后来的 Qingyu, flower, and their friends' Contest)。除此以外,而我也在生活的各种方面试图对他提供一些帮助。举一个小例子,其在暑假集训期间问我能否给他点外卖,于是便有了以下几段记录。

除了订单外,这里还应该有一段我和花子的聊天记录。由于这段聊天记录存储在我的另一台设备之中,我会在 IOI 2024 返程后补充这一段聊天记录的详细信息。
6.png
7.png
8.png

9.png
10.png

11.png
12.png

也就在此时,我和高一的花子定下了约定,那就是双方如果进入了集训队,便一起去 PKU,未来成为 XCPC 的队友。

13.png

黑化

随着我与花子关系越来越发展,花子这个人也逐渐变得越来越黑化。在这里我不做任何评价,单纯复述几件这个时期发生的事情。

(1) THUPC 组队

简单来说,He_Ren 曾询问我是否要一起组队参加 THUPC。当时,我跟核仁说,我提前说好了要跟花花组队,所以如果要一起的话就要带个花花。核仁当时觉得我与花子的水平都不够高,不想要同时和我们两个人一起组,因此我便拒绝了整个请求,不了了之了。

随后,我把这件事情告诉了花子,过了几天,我发现花子抛弃了我加入了这支队伍,成为了新的 THUPC 代表队。整件事情过于痛苦以至于我不想再回忆起任何相关的事情,因此我只把相关的聊天记录置于此供大家欣赏。

在 CTS 2024 时,时隔一年我又在重庆向核仁提起了此事。核仁表示既然是花子当时主动找的他,他就以为他与我以某种原因商议退队了,才接受了与花子一起参赛。整个故事现在看来,我只感觉无比的色情。

14.jpg
15.jpg
16.jpg
17.jpg

这件事情让我感到无比难受,但我当时只是认为花子觉得我水平不行才故意警告了我,没有觉得这个人的人品有什么问题。

(2) Universal Cup

在俄罗斯与乌克兰之间的冲突开始后,毛子的年度活动 Open Cup 便陷入了停滞之中。在 2023 年 2 月,我与陈靖邦 Co-Founded 了 Universal Cup。我自然也把我一切的想法都告诉了被我当做最好的朋友的花子。花子坚持想要来管理 UCup,加入组委会。由于 Committee 内我需要考虑到每个人的身份,我便对花花直言 “我可以把你拉进去,但是像cjb和杜老师可能会对你的加入存在意见”。于是,便得到了下面这一段名场面发言。

c.jpg

当然,在我看来,相比起后来其针对 ucup 与我本人的人身攻击而言,这个时期的花子仍然是以一种相对正常的方式与人类进行的交流。

(3) QOJ 管理员

2023年,在花子参加位于潍坊的国家队集训(注意是2023年)时,刚好他会在潍坊过生日。当时,花子告诉了我这件事情,我便询问花子我是否可以前往为他庆生。在得到了肯定的答复后,我与潍坊一中的冷老师进行了联系,并携带着送给他的生日礼物来到了潍坊一中。

结果,在我的礼物被收下后,我被冷暴力了整整一天。我完全不能理解花子是以一种什么样的心理状态,认为我总是试图与他说话让他感到很烦,因此刻意选择不与我说话。

  • 什么?我怎么知道这是刻意的?在下文我会提到,花子在我与他关系第一次爆完后,是如何亲口承认这一点的。

这一次的经历让我不解。原本我向核仁说我会在潍坊待若干天,最后我一天也没有多留,当天晚上就决定离开这个不欢迎我的到来的人。我仍然无法理解为什么我们的关系成了这个样子,在未来的几天多次试图与花子交涉,问问他到底是对我有什么意见。然而,每次与花子的质问,我都没有得到他的任何理解。花子认为我对他诸如 “能不能不要总是不理我”、“为什么你不回我消息”、“为什么线下我去找你你都不搭理我的问题” 是过分的请求/亲密关系,而他不想对我这样做。

我对花子这种态度感到非常的难受,我迫切想要知道他到底是一种怎样的精神状态。而恰巧我也知道,当时他使用 QOJ 的管理权限看代码下数据的事情。在有一天,我发现花子把他向我索要 qoj 管理员时设置的 qingyutietie 的 motto 移除了。我感到是时候要问个明白了。于是在那天的中午,我撤了花子的管理权限,要求他与我对话。

那么,亲爱的花子,做出了如下的反应。

22.jpg

至于他说的 “晚上再说”,我也全文把我们晚上的谈话刊载出来。

23.png
24.png
25.png
26.png
27.png

(4) CCPC Finals 小作文

2022 年的中国大学生程序设计竞赛决赛(CCPC Finals 2022)在 2023 年 5 月 15 日举办。当时,在杜老师的邀请下,我成为了比赛命题组的一员,参与了这套题目的命制与裁判工作。

而针对这场比赛,花花同学曾在知乎上写下了这样一篇小作文(在我发出这篇博客之时,此回答已被删除)

29.png

花花口中的 D 题,便是 Flower's Land 2。花花在自己的回答中声称

赛后交流了一下,发现我H的做法比出题人简单很多,也就成为了讲题ppt里的做法。然后d题要换,我就正好把屯了的idea扔了过去。 D其实是在脑子里很久的一个idea,在报道前两天晚上忽然说缺题了就把这个题跟杜老师说了说,幸运的成为了最后一个确定的ccpcf题。当晚就开始狂暴造题,为了能赶上第二天的验题队。

针对 “我H的做法比出题人简单很多,也就成为了讲题ppt里的做法” —— 最终讲题 PPT 的做法是戴江齐给出的,而且让戴老师写题解他还不写,彻底没法要了戴老师。整个做法的基础与 New Equipments III 相同(值得一提的是,这场 Bytedance Finals 在很长一段时间内都没有公开,还是我 py 了一个账号带花花打的比赛)。不过嘛,花花自己有这种做法,认为是 “成为了讲题ppt里的做法”,倒也能够理解,无可厚非。

但是花花自称 “然后d题要换,我就正好把屯了的idea扔了过去”,以及 “当晚就开始狂暴造题,为了能赶上第二天的验题队”,实在是过于厚颜无耻。

当时,花子正在忙着自己的训练(以及,当然,给自己的女朋友过生日),而他又迫切希望自己的题能够被选入。因此,花花在一次我与他的语音通话中让我去跟杜老师推荐这道题,希望能够让这道题被选入比赛。在原先的 D 题被爆了(后来变成了 Be Careful 2)以后,最终这道题目被顺利选入了比赛之中。然后,花子便告诉我自己很忙,要我帮他造这个题。在 5 月 10 日夜里,花子与我通宵连麦,开始了造这个题的过程。

30.png
31.png
32.png
(由于这个时期只有通话记录,没有聊天记录,所以只能随便发点当时文字交流的内容了)

不出所料,这个题造到一半,花子的代码就倒闭了。随后,花子陷入了暴躁模式,狂暴问我应该怎么办。最终,花子率先一步退出了这个题的造题过程,让我自己看着办。

那天夜里,正好杜老师在北京街头随机游走寻找酒店,最后就只有我和杜老师在拯救这个题。这个题救活了以后,花子也没有参与哪怕一点的造题任务之中。整个题从题面到数据,一切工作,全部都由我一个人完成。

33.png
34.png
35.png
36.png
Polygon 上的 Commit 记录

最让我觉得不可理喻的是 “虽然标只跑了400ms,但是还是开了4s。于是理所应当的被验题队的根号log干过去了,然后在我的怒喷下,这个题最后还是改成了 $n = 5 \times 10^5$,5s的样子”。亲爱的花子,你也清楚根本不是你自己在干活,甚至连改个数据范围,改个 generator,都还得是 “在我的怒喷下”。最关键的是,你在这里打嘴炮的时候,真的有考虑过哪怕自己亲自造一下数据,亲自测一下代码,亲自改一下时限吗?你的算法竞赛水平比我高得多,我自然不敢跟您争论对数据结构都理解。但我知道的是,在标算使用 $2 \times 2$ 的矩阵,加上 I/O 优化与其他常数优化的情况下,跑出了 400ms,你确定应该用这一份代码来设定时间限制吗?你在那里安排别人干活的时候,锐评数据造的烂的时候,作为你自己口中的为了赶上验题进度连夜造题的自己,为什么就不能自己来造哪怕一组数据,测试哪怕一组 constraint 吗?

(5) “你能不能好好给我造数据”

待更新。

(6) “我进了集训队你给我这么训练,我把你好友删了”

待更新。

第一次删好友

待更新。

NOI 2023 期间的聊天记录

待更新。

背叛

待更新。但我先把相关的聊天记录发一段出来,可以自己感受一下。
28.jpg

如我上面所讲,我们在两年前所定下的约定,在花子的嘴里,一句轻飘飘的对不起就可以当作一张白纸。在我收到这段消息的时候,我恰巧在 HZNU 的草坪上躺着发呆,于是我就干脆一翻身,抱着这片草地开始痛哭。这期间他给我发的所有的消息,我都尽我所能以我认为体面的方式进行了回复。

同样,我不会在这里做出主观的评价,请你来定夺这是不是一个正常人该说出来的话。

从 CTT 到 CTS

(1) 锐评 Universal Cup

待更新。但我先把相关的聊天记录发一段出来,可以自己感受一下。
a1.png
a2.png
a3.png
a4.png
a5.png
a6.png
a7.png
a8.png
a9.png

(2) 怎么写集训队论文

待更新。但我先把相关的聊天记录发一段出来,可以自己感受一下。
b1.png
b2.png
b3.png
b4.png

(3) 你怎么不带我做 research?

待更新。但我先把相关的聊天记录发一段出来,可以自己感受一下。
18.png
19.png

20.png
21.png

(4) 我是这些题目的出题人

这段故事实在是过于离谱,导致我到今天也不能理解怎么能发生这种事情……

简单来说,花子干了一件极度学术不端的事情。他拿了别人投给他的题投给我们,并称这是其自己出的题,最终导致我们在不知情的情况下对题目产生了错误的判断。

这是我们在命制今年 EC-Final 时发生的事情。你可以思考一下,在一场正式比赛,隐瞒题目的来源使其成为正式赛题是一件多么恐怖的事情。所以在事发后,我们出题组赶紧与这个人进行了切割。

正如上文所提,我在 2023 年参与了 CCPC Finals 的命题并进行了现场裁判工作。花子对当时我没有提议带他去现场感到不满,并想要在下一次的 EC-Finals 与 CCPC Finals 的命题中前往现场。

37.png

同时,花子想要努力进入 IOI 2024 的中国国家队。在选拔方案中,国家队队员会被要求命制一道题目,作为作业的一部分(即 “集训队互测”)。因此,花子主观上想要参与命题工作,客观上也有命题任务需要参加。

首先加入战场的是花子的集训队互测 落日珊瑚。这道题目的 idea 的基础是我在 EC-Final 命题期间枚举出来的,本来打算出成一道签到题。

【一段聊天记录】

对不起,写到这里心情有点爆炸了,未来有空再写吧。

38.png
39.png
40.jpg
41.png

(5) 你有没有想要感谢的人?

待更新。

2024 年 9 月 13 日更新:

本来自己情绪稳定了一点,不打算再继续写这个人的小作文了。直到今天发现自己被一位热心网友喷了,我还是把喷我的评论与回应在这里贴一下。

>

不明白花花做错什么了,就因为我把你当唯一的朋友对你好,你也得把我当唯一的朋友,对我秀尽恩爱,否则就是道德败坏? 甚至,爆掉之后还要在 IOI 的节骨眼发文,让圈内都来讨伐花花?这是什么朋友......

<

My Reply: 请问,我有攻击过这个人不理我之类的问题吗?我当然能够接受你不把我当唯一的朋友,甚至不把我当朋友,但你选择既当婊子又立牌坊,前脚骂完娘后脚又来找我帮忙,你觉得这是一个正常的人能做出来的事情吗?偷别人的题目来投,不给别人 credit,这种事情说成道德败坏已经够给面子了,本质上这就是学术不端。 至于我发文,还要怪我,那就更搞笑了。他本人向我承诺跟我道歉,换取我不要将他的事情公之于众。他自己不尊重他自己的承诺,难道我被欺负了我就只能忍着?一个人自己做过的事情,难道不敢向大家承认吗?圈内的人来讨伐他,是因为我攻击他,还是因为他自己做的事情?既然你不把我当朋友,对我的帮助视而不见甚至恶语相向,那我为什么还要把你当做我的朋友?

>

圈外人看完后表示,就是一段畸形的、一厢情愿的友情。

花花这边,讲真没啥问题,要说有也就是心直口快,以及一些沟通方式的选择。可以看到即便爆了之后,他也依然可以说出“青鱼对我水平帮助很大”,愿意私下处理,愿意给予道歉和祝福,很成熟的体现。

反观 Qingyu 这边,他交朋友的初衷,是“付出一切来维护这个我仅有的朋友的友谊”,所以“几乎所有的时间都在与花子聊天”,又是点外卖又是帮着出题的。这其实是个很大的隐患,因为他也会反过来要求花花把他视为唯一的、最好的朋友,来倾尽一切地对待他,稍有不如意就会“问罪”。比如,生日不理他了、把 motto 删了,让人感觉很难沟通。自然,后面组队、去THU的事,花花也不愿意和他去沟通了,导致了更大的分歧。

但他最大的问题,还是选择 IOI 的节骨眼,把这篇檄文爆出来,让圈内的人都来讨伐花花,让花花在比赛时还要承受来自 OI 圈的压力,好像在说“我不好,你也别想好”(那条评论,感觉像是花花的 npy 留的)。至此,他已经失去了作为朋友的任何包容性。

真朋友,永远在心里,不在面儿上。

<

My Reply: 我比较好奇,为什么你会觉得这是 “一些沟通方式的选择”。哪怕你认为花子的沟通方式是他自己说话的风格,我也不能理解在喷完我之后继续找我帮忙,不愿意给帮助自己的人致谢,甚至要对其恶语相向。也许我的性格有缺陷,但对不起,我到今天也不能接受,在要我帮忙完成他的互测题、解题报告甚至帮忙完成集训队论文的同时而不肯致谢。抛开人品不谈,这就是赤裸裸的学术不端。

我还是那句话,我不强求花子做我的朋友。作为当事人,如果你认为我和你的关系你不能接受,你在第一次违背我们的约定,删了我的好友以后,为什么还要把我加回来?为什么找到我的第一件事是问我能不能帮自己写集训队论文?为什么第一句话是拜托我能不能加入我们的出题组?为什么第一天就要问我要 QOJ 的管理员?嘴上说自己承受了多少多少的压力,到头来还是要利用我为自己做事,我攻击他难道他是冤枉的吗?

我觉得我的忍耐能力已经足够强大,但对不起,在 EC-Final 这种借别人的题来骗自己的 credit 的行为,这种拿正式比赛命题开玩笑,丝毫不尊重我们的比赛的行为,我无法理解,无法接受,也有责任将他的所作所为公之于众。

由于我最近比较忙,有一些重要的事情要做,不出意外的话短期应该不会更新了。

IOI 2024 日程

2024-09-03 22:39:06 By Qingyu
9 月 1 日(周日)
报道与注册
时间 选手 领队、副领队、组织者
全天 报道与注册
08:00 ~ 10:00 早餐
14:00 ~ 16:00 午餐
18:00 ~ 22:00 华为展台 自由活动
20:00 ~ 22:00 晚餐

9 月 2 日(周一)
练习赛与开幕式
时间 选手 领队、副领队、组织者
全天 报道与注册
06:00 ~ 08:00 早餐
08:15 ~ 08:30 进入比赛大厅 GA Meeting(大会) 1:
比赛规则
投票表决
08:30 ~ 08:45
09:00 ~ 10:00 练习赛
10:00 ~ 11:00 练习赛
11:00 ~ 12:30 领队与选手交流
12:45 ~ 14:00 前往亚历山大图书馆
14:00 ~ 15:30 开幕式
15:30 ~ 16:30 图书馆之旅 GA Meeting(大会) 2:
讨论热身赛
16:30 ~ 17:00 自由活动
17:00 ~ 18:00 返回 AASTMT
18:00 ~ 19:00 晚餐
19:00 ~ 20:00 (选手隔离) GA Meeting(大会) 3:
第一次竞赛试题选题表决
翻译
20:00 ~ 22:00
22:00 ~ 00:00

9 月 3 日(周二)
第一次竞赛日
时间 选手 领队、副领队、组织者
06:00 ~ 07:00 早餐
07:00 ~ 08:00
08:00 ~ 08:30 进入比赛大厅 早餐
08:30 ~ 09:00
09:00 ~ 13:00 第一次竞赛 IOI Conference
13:00 ~ 14:00 自由活动
14:00 ~ 15:30 午餐
15:30 ~ 17:00 Jane Street Hub 第一试·申诉
17:00 ~ 18:00 自由活动
18:00 ~ 19:00 晚餐
19:00 ~ 20:00 Jane Street hub GA Meeting(大会) 4:
处理申诉
投票表决
20:00 ~ 22:00

9 月 4 日(周三)
第一次活动日
时间 选手 领队、副领队、组织者
07:00 ~ 09:00 早餐
09:30 ~ 10:30 前往 Montazah
10:00 ~ 15:00 游览与海滩活动
15:00 ~ 15:30 返回 AASTMT
15:30 ~ 16:30 午餐
16:30 ~ 18:30 自由活动
18:30 ~ 19:00 晚餐
19:00 ~ 20:00 (选手隔离) GA Meeting(大会) 5:
第二次竞赛试题选题表决
翻译
20:00 ~ 22:00
22:00 ~ 00:00

9 月 5 日(周四)
第二次竞赛日
时间 选手 领队、副领队、组织者
06:00 ~ 07:00 早餐
07:00 ~ 08:00
08:00 ~ 08:30 进入比赛大厅 早餐
08:30 ~ 09:00
09:00 ~ 11:00 第二次竞赛 讨论环节
11:00 ~ 13:00 Jane Street Brunch
13:00 ~ 14:00 自由活动
14:00 ~ 16:00 午餐
16:00 ~ 17:30 Jane Street Hub 第二试·申诉
17:30 ~ 18:00 自由活动
18:00 ~ 19:00 晚餐
19:00 ~ 20:00 Jane Street hub 自由活动
20:00 ~ 22:00 GA Meeting(大会) 6:
处理申诉、投票表决
投票确定最终排行榜
22:00 ~ 00:00

9 月 6 日(周五)
第二次活动日与颁奖
时间 选手 领队、副领队、组织者
07:00 ~ 09:00 早餐
09:30 ~ 12:30 前往大埃及博物馆
12:30 ~ 14:30 博物馆之旅
14:30 ~ 15:30 午餐
15:30 ~ 16:00 前往金字塔
16:00 ~ 18:00 金字塔之旅
18:00 ~ 19:00 狮身人面像·晚餐
19:00 ~ 21:00 闭幕式·颁奖典礼
21:30 ~ 00:30 返回 AASTMT
22:00 ~ 00:00

9 月 7 日(周六)
第三次活动日与华为挑战赛
时间 选手 领队、副领队、组织者
08:00 ~ 10:00 早餐
10:00 ~ 12:00 娱乐环节 GA Meeting(大会) 7:
投票表决
休会
12:00 ~ 14:00
14:00 ~ 15:30 午餐
15:30 ~ 18:00 Huawei Arena
18:00 ~ 19:00 晚餐
19:00 ~ 22:30 Huawei Arena

9 月 8 日(周日)
返程
时间 选手 领队、副领队、组织者
All Day 送机
07:00 ~ 09:00 早餐
14:00 ~ 15:30 午餐
18:00 ~ 19:00 晚餐

IOI 2024 如何呼唤你的名字

2024-08-24 20:53:40 By Qingyu

大家晚上好,IOI 2024 还有一周就要开始了。小青鱼将作为神秘身份的嘉宾出现在 Alexandria。有很多趣味的国外网友约了小青鱼见面,因此小青鱼希望制作一个很有 CNOI 劲的留言集合,给外国的趣味网友们看!

因此,小青鱼邀请大家在这个 thread 下随机说话,展示大家的 ~魔怔~ 劲,让小朋友们感受一下感受,理解一下大家的精神状态。

谢谢大家,剩下的忘了。

The 2nd Universal Cup Semifinals Analysis(草稿)

2024-07-02 21:29:59 By Qingyu

The 2nd Universal Cup Semifinals: Analysis Report

This is the draft of the problems of the 2nd Universal Cup Semifinals. We expect to officially release a version of this document in a few weeks. If you find an error, please send an e-mail to [email protected] or a private message to me (@Qingyu) about it.

Summary

To be added..

A. Records in Chichén Itzá

Proposed by bulijiojiodibuliduo. Prepared by Qingyu and quailty.

Additional acknowledgement to xyz2606, kostka and xiaowuc1 for their contributions to the improvement of the problem statements.

Consider the number of non-leaf vertices, i.e, vertices with degree $\geq 2$, and there are some cases as follows:

  • If there are at most $2$ non-leaf vertices: the tree must be a star or a double star (formed by two stars via joining two of their centers by an edge), and it is unique.
  • If there are at least $3$ non-leaf vertices, and their degrees are not all the same: in this case, there are at least two different orders in which $3$ of these vertices can be joined, so the tree is not unique.
  • If there are at least $4$ non-leaf vertices, and their degrees are all the same but not $2$: in this case, there are at least two different structures in which $4$ of these vertices can be joined, so the tree is also not unique.
  • Otherwise: all non-leaf vertices form a unique chain, and therefore the tree is also unique.

B. Almost Convex 2

Proposed by quailty. Prepared by quailty and xyz2606.

Additional acknowledgement to xyz2606 for his contributions to the improvement of the statements.

This problem is a fun variant version of Almost Convex, which was used in The 2nd Universal Cup Stage 17 Jinan.

Choose the lexicographically smallest point as $p_1$, count the number of points inside all triangles $p_1p_ip_j$ in $O(n^3)$ time complexity, which allows us to determine whether a triangle $p_kp_ip_j$ has points inside (excluding the boundary) in $O(1)$ time complexity. Now consider each possible value of $|Q|$:

  • $|Q|=|R|$: it is the convex hull $R$;
  • $|Q|=|R|+1$: cut an edge $vw$ on $R$ and find a $u \notin R$, where no points are inside the triangle $uvw$ (excluding the boundary), then link $uv$ and $uw$ to obtain $Q$. There are $O(n^2)$ candidates;
  • $|Q|=|R|+2$: on the basis of $|Q|=|R|+1$, cut an edge $v'w'$ on $Q$ and find a $u' \notin Q$, where no points are inside the triangle $u'v'w'$ (excluding the boundary), then link $u'v'$ and $u'w'$, and ensure that the resulting figure is a simple polygon. There are two cases here:
    • $v'w'$ is not an edge on the initial $R$: there are only $2$ such edges, and it is possible to enumerate the edges and $u'$ for checking in $O(n)$. Since there are only $O(n^2)$ $Q$ satisfying $|Q|=|R|+1$, the time complexity is $O(n^3)$;
    • $v'w'$ is an edge on the initial $R$: it is equivalent to selecting the aforementioned $uvw$ and $u'v'w'$ in $R$, requiring that there are no points inside the triangles $uvw$ and $u'v'w'$, and these two triangles do not intersect. Consider enumerating $u$ and $u'$, the line passing through these two points divides $R$ into two sides, and only when $vw$ and $v'w'$ are on the same side, the two triangles may intersect. To calculate the answer, enumerate $vw$ and use two pointers to maintain the range of $v'w'$. The time complexity is also $O(n^3)$.

C. Space Station

Proposed by Kubic (a.k.a. vme50). Prepared by Lynkcat and Qingyu.

Additional acknowledgment to xyz2606 and xiaowuc1 for contributions to improving the problem statements, and to Kevin5307 for further testing the problem.

Analysis will be added a bit later.

D. Solar Panel Grid Optimization

Proposed by lanos212. Prepared by lanos212 and Qingyu.

Additional acknowledgement to bulijiojiodibuliduo and Lynkcat for their contributions to the improvement of the problem.

Analysis by cmll02.

首先考虑下面过程:

从左往右枚举每一列 $c(1\le c < n)$,先对 $a_{n,c}=b_{i,c}$ 的 $i$ 执行 row i,然后执行 $n$ 次 column n ,再把刚才没操作的行 $i$ 执行 row i。容易发现,对于一个 $c$ 执行完上述操作后,$a$ 的第 $n-1$ 列会与 $b$ 的第 $c$ 列相同。

执行完后,最后一列可能不满足要求。

观察到执行完上面操作后,$a$ 每行 $1$ 的个数的奇偶性的变化是固定的:row 操作不会改变行奇偶性,连续 $n$ 次 column n 会同时改变每行的奇偶性。所以如果能够先处理 $a$ 的行奇偶性和 $b$ 的行奇偶性完全相同/相反(取决于 $n$ 的奇偶性)即可。

这样就可以先计算出每一行需要将 $a_{i,n}$ 调整为多少,记这个值为 $A_i$。

现在只要调整奇偶性。先把第 $n$ 列和第 $n$ 行变成全 $0$,然后再把第 $n$ 行 column n $n$ 次变成全 $1$。由于将所有 $01$ 反转实际上没有区别,下面假设第 $n$ 行和第 $n$ 列的 $2n-1$ 个数中 $1$ 比 $0$ 多。

考虑将第 $n$ 行和第 $n$ 列先全部变成全 $0$,然后再由全 $0$ 还原出目标奇偶性。

要将第 $n$ 行和第 $n$ 列先全部变成全 $0$,可以先把第 $n$ 列清零。这一步的做法是执行 $n$ 次“不断执行 row n 直到 $a_{n,n}=1$,然后 column n”。这样会把 $n$ 个 $1$ 变成 $0$ 并放到第 $n$ 列。

接下俩把第 $n$ 行清零。这一步只要不断把第 $n$ 行的 $1$ 用 row n 放到 $(n,n)$ 的位置,然后 column n

完成到这一步之后,column n $n$ 次,把第 $n$ 列变为全 $1$。此时 $a$ 会长下面这个样子

???...?1
???...?1
???...?1
???...?1
.      .
.      .
.      .
000...01

先忽略掉 $A_n$,解决掉 $A_1\cdots A_{n-1}$。类似最开始说的东西,依次考虑 $A_{n-1}\cdots A_1$,如果是一个 $1$ 就从第 $n$ 行拉一个 $0$ 过来然后 column n,否则直接 column n。对于第 $n$ 行的奇偶性,调整是简单的。

前面部分的操作次数是 $2n(n-1)$,调整奇偶性的次数是 $O(n)$ 的。可以通过。

E. Fast Median Transform

Proposed by djwj233. Prepared by djwj233 and Lynkcat.

Additional acknowledgement to xiaowuc1 and kostka for their contributions to the improvement of the problem statements.

我们考虑怎么对于单次询问求出 $\text{FMT}(a,b,X)$ 的值。

sub1 可以直接输出 $0$,sub2 可以直接暴力模拟题述过程。

显然通过二分答案可以以一个 $\log V$ 的代价(也可以通过离散化变成 $\log (n+m)$)把问题转化为 $V=2$。

有一个观察:

  • 在 $V=2$ 时,若一次操作中 $a_i=b_j=0$,那么就是 $X\gets 0$,同样 $a_i=b_j=1$ 就是 $X\gets 1$,而 $a_i\ne b_j$ 不会改变 $X$。

对 sub3,答案就是 $X$;对 sub4,只需判断 $y$ 中有没有 $0$ 即可。

对 sub5,我们设 $a$ 中 $1$ 的位置分别为 $p_1,p_2,\cdots,p_k$($k\le 5$)。

考虑从 $nm-1$ 倒着找到最后一次赋值操作,设 $b_{p_1}$ 最后一次被操作到是 $(a_{p_1},b_{q_1})$,那么如果它不是赋值操作一定有 $b_{q_1}=0$。

我们考虑 $b_{q_1}$ 的最后 $6$ 次操作,由于 $\gcd(n,m)=1$,所以这 $6$ 次操作操作到的数两两不同,而且其中一定有一个不在 $p$ 中。

也就是说,这里可以证明最后一次赋值操作离 $nm-1$ 的距离最多是 $6(n+m)$,我们倒回去找这么多步就可以确定 $A$ 的值。

对 sub6 我们猜想也有类似的结论。

具体地,取出最后的 $d=2(n+m)$ 次操作,我们证明其中必有一次赋值操作,否则所有 $nm-1$ 次操作中都没有赋值操作。

反证法,我们取出一个 $i$,可知最后 $d$ 次操作中一定有两次操作到了 $i$,不妨设操作的是 $(a_i,b_{j_1}),(a_i,b_{j_2})$。

这样如果 $a_i=1$ 且这不是一次赋值操作,则必有 $b_{j_1}=b_{j_2}=0$,反之亦然。

我们以此建立一个二分图,对于这 $d$ 次操作,对左部点的 $i$ 和右部点的 $j$ 连边即可,显然每个点度数至少为 $2$。

我们只需要证明,这张二分图必然是连通图即可。

(因为假如最后 $d$ 次操作中没有赋值操作,那么可以推得左部点都是 $1$,右部点都是 $0$(或其对称情况),答案就是 $X$)

我们考虑二分图中的任意一个连通块,设其中右部点的集合为 $S$。

对于 $S$ 中的任意一个 $j$,设最后一次操作到它是 $(a_i,b_j)$,考察包含 $a_i$ 的前一次操作 $(a_i,b_{j^\prime})$。

易证这在最后 $d$ 次操作中,即 $j^\prime\in S$,而且有 $j^\prime\equiv j-n\pmod{m}$。

也就是说,$\forall j\in S, (j-n)\bmod m\in S$,而由于 $\gcd(n,m)=1$,所以一定可以不断“跳跃”直至证明 $S$ 就是全集。

左部点是同理的,也就是说整张二分图必然是连通图,证毕。

简单地说,我们证明了如下事实:

设 $\varnothing \ne S\subseteq \{0,1,\cdots,m-1\},d\perp m$,则 $S\equiv S+d\pmod{m}$ 当且仅当 $S$ 为全集。

对于一般情况,设 $c=\gcd(n,m)$,判掉无赋值操作后可以证明操作一定在最后 $2(n+m)$ 次中。

设 $n,m$ 同阶,复杂度 $\mathcal O(n\log n)$ 或 $\mathcal O(n\log V)$。

此外也有一个思路比较朴素且套路的 $\mathcal O(n\log^2n)$ 做法,大致是在二分答案后从解方程的角度入手。

事实上若我们仔细分析一下这个二分的本质,是可以把这个二分省去的:

我们只需要直接顺序模拟后 $2\max(n,m)$ 操作也是正确的。这是单次 $\mathcal O(n)$ 做法。


在 $n,Q\le 5\times 10^5$ 的部分,我们显然无法每次都重新求一遍答案。

下记 $U(x,y)= \begin{cases} [x,y] & x\le y\\ [y,x] & x>y\\ \end{cases}$.

考虑 sub11,这里我们不会做任何修改,只是对不同的 $X$ 求答案。

我们维护一个区间 $[L,R]$,初始为 $[0,+\infty)$,之后倒着枚举所有操作,每次把维护的区间和当前区间取交。

若某时刻交为空则答案已经可以确定,否则当且仅当 $X_0\in [L,R]$ 时答案为 $X_0$,否则视 $X_0$ 的大小为 $L$ 或 $R$。

上面的证明过程已经给出只需枚举后 $2\max(n,m)$ 次操作即可。

这样我们可以求出一个区间 $[L,R]$,然后按照 $X_0$ 的大小确定答案。

在 sub12 中,我们观察到这个区间可以直接合并,构成了半群。

我们取出后 $2\max(n,m)$ 次操作,直接使用线段树维护之。由于 $n\ge m$ 所以每次操作只会修改至多 $2$ 次操作,复杂度 $\mathcal O((n+Q)\log n)$。

考虑 sub13,依然沿用与上面相同的思路,但是考虑根号分治。在下面的复杂度分析中我们记 $N=\max(n,m)$。

下面我们需要用到一个引理:

  • 引理:对于一些区间 $[l_i,r_i]$,设 $L=\max l_i,R=\min r_i$,它们的交为 $\bigcap_i [l_i,r_i]=\begin{cases} \varnothing & L>R \\ [L,R] & L\le R \end{cases}$.

证明:

我们先分类讨论证明 $n=2$ 时成立,细节略。

然后使用归纳法,对于 $n=m+1$ 时的情况,可以由归纳假设转化为 $n=2$ 时的情况。

具体地,若 $n\ge B$ 则每次操作只会修改至多 $\mathcal O(\frac{N}{B})$ 次操作的信息,直接使用线段树维护之,可以做到 $\mathcal O(\frac{N^2\log N}{B})$ 的复杂度。

否则有 $n\le B$,我们考虑对每次询问 $\mathcal O(B\log N)$ 地求出答案。

具体地,我们先考虑如何判断所有区间的交集是否为空集。

容易发现,对于一个特定的 $a_i$,在所有与其配对的 $b_j$ 中,只有 $\ge a_i$ 的最小值和 $\le a_i$ 的最大值(如果存在)这至多两个是有效的。

这是可以在直接 $\mathcal O(n)$ 次二分查询出这两个数然后对区间求交得到,复杂度 $\mathcal O(NB\log N)$。

若区间不为空则答案可以直接确定,否则我们考虑找到一个最大的 $d$ 使得只考虑 $i\in [d,nm-1]$ 中的操作时所有区间的交不为空。这样我们直接讨论第 $d-1$ 次操作的位置关系即可得解。

不难发现,这个过程可以由两部分实现:

  • 给定一个 $d$,求只考虑 $i\in [d,nm-1]$ 中的操作时所有区间的交:

    我们可以对于每个 $a_i$ 把所有涉及到它的 $b_j$ 找出,按时间排序后作后缀最大 / 最小值。

    在每次询问时对每个 $a_i$ 找到 $d$ 及之后的第一次操作,$\mathcal O(1)$ 地查询对应位置的最大、最小值即可做到总复杂度 $\mathcal O(n)$。

  • 求出 $d$:

    我们二分一个 $d$,每次判定使用上面的算法,可以做到 $\mathcal O(n\log N)$。

取 $B=\sqrt{n}$,总复杂度可以做到 $\mathcal O(N\sqrt{N}\log N)$。

(若继续优化上面 $n\le B$ 的过程或许也可以做到 $\mathcal O(N\sqrt{N\log N})$)


如何做到 $\mathcal O(N\log N)$​,通过 sub14?下称 $MX = nm-1,L=2\max(n,m)$。

自然地,我们对 $n\ge m$ 和 $n< m$ 分类讨论。对于 $n\ge m$ 由上可以直接维护,下面认为有 $n < m$。

考虑把操作倒过来考虑:对 $i\in [0,L)$,设第 $MX-i$ 次操作的数为 $(a_{p_i},B_i)$。

我们考虑维护 $n$ 个数列 $A_{0\cdots n-1}$,生成方式是依次对于每个 $i\in [0,L)$,将 $B_i$ 将其插入 $A_{p_i}$ 末尾。

举个例子,样例中 $n=2,m=3,a=[1,3],b=[4,2,3]$ 时,有 $L=6$,那么:

  • $B=[3,2,4,3,2,4]$;
  • $p=[1,0,1,0,1,0]$.
  • $A_0=[2,3,4]$, $A_1=[3,4,2]$.

由于 $b$ 数列不会改变,容易发现 $B,p,A_i$ 都是确定的。

容易发现 $A_i$ 非空,且长度在 $\left\lfloor\frac{L}{n}\right\rfloor$ 和 $\left\lceil\frac{L}{n}\right\rceil$ 之间,所有 $A_i$ 的长度之和为 $L$。

我们考虑先判断是否对于全部的 $L$ 个区间,其交都不为空。

这个问题是容易解决的,容易发现有: $$ \forall i, \bigcap_{x\in A_i}U(x,a_i)=U(a_i,\max_{x\in A_i,x < a_i} x)\cap U(a_i,\min_{x\in A_i,x\ge a_i} x) $$ 也就是说,对于我们只需要对于每个 $a_i$ 维护至多两个区间然后求它们的交即可。

这可以通过维护左端点的 $\max$ 和右端点的 $\min$ 解决,而这可以直接使用 C++ STL muliset 在 $\mathcal O((n+Q)\log n)$ 内维护。

若全部区间的交不为空,那么依据上面的分析我们可以直接得到答案。

否则,我们依然采用上面的思路:找到一个时间点 $T$ 使得:

  • $\displaystyle \bigcap_{i=0}^{T-1}U(A_{p_i},B_i)\ne \varnothing$.
  • 设 $\displaystyle Z=\bigcap_{i=0}^{T}U(A_{p_i},B_i)$, 有 $Z=\varnothing$ 或 $\exists u, Z=[u,u]$.

无论是哪种情况,我们在找到一个这样的时间点 $T$ 之后,求出 $Y=\displaystyle \bigcap_{i=0}^{T-1}U(A_{p_i},B_i)$,讨论 $U(A_{p_T},B_T)$ 与 $Y$ 的位置关系即可得到答案。(因为此时答案一定是 $Y$ 的一个端点)

类似 $n\ge m$ 中的那样,我们对于使用线段树维护 $\displaystyle \bigcap_{i=0}^{n-1}U(A_{p_i},B_i)$ 的值。

(由于每次操作只会修改线段树中维护的至多一个区间,这部分的复杂度是 $\mathcal O(N\log N)$。)

设 $\displaystyle Z_0=\bigcap_{i=0}^{n-1}U(A_{p_i},B_i)$,若 $Z_0=\varnothing$ 或 $\exists u, Z_0=[u,u]$ 那么我们可以直接在线段树中确定答案。

否则,考虑推理此时的性质。

对于 $i\in [0,n-1]$,显然 $a_i\ne A_{i,0}$。若 $a_i < A_{i,0}$ 那么我们记 $c_i=0$,否则 $c_i=1$。($c_i$ 可以在修改时直接维护)

若 $\exists i,j, a_i\le a_j,c_i>c_j$ 则可以证明 $Z_0=\varnothing$ 或 $\exists u, Z_0=[u,u]$,矛盾。

因此,$\exists V, \forall i, c_i=[a_i\le V]$。我们可以使用 multiset 维护 $LB=\max_{c_i=0}\{a_i\},RB=\min_{c_i=1}\{a_i\}$,这样一定有 $LB < RB$。维护的复杂度是 $\mathcal O(N\log N)$。

对于 $t\ge n-1$,记 $\displaystyle Z_t=\bigcap_{i=0}^{t}U(A_{p_i},B_i)$,可以证明,$\exists u < v, Z_t=[u,v]$(下称其为符合条件)当且仅当: $$ \min(RB,\min_{i\le t,c_{p_i}=0} B_i) > \max(LB,\max_{i\le t, c_{p_i}=1} B_i) $$ 由于 $Z_{n-1}$ 符合条件,至少应有 $\min_{c_i=0} A_{i,0}>\max_{c_i=1} A_{i,0}$ 成立。

我们把 $0\cdots n-1$ 按照 $A_{i,0}$ 升序排序后得到 $q_i$,也即找到一个 $\{0,1,\cdots,n-1\}$ 的排列 $q$ 使得 $\forall i\le j, A_{q_i,0}\le A_{q_j,0}$。再记 $w=q^{-1}$ 为 $q$ 的逆排列。

那么由于 $Z_{n-1}$ 符合条件,因此必然有 $\exists K, [c_{q_i}=0]=[i\ge K]$,其中 $K=\sum_{i=0}^{n-1}[c_i=1]$。

我们考虑如何求出 $\min_{i\le t,c_{p_i}=0} B_i$ 的值。

不妨设 $t=xn+y$,其中 $y\in [-1,n-2]$,我们考虑把问题分成两个部分:

  • 求 $\min_{i < xn,c_{p_i}=0} B_i$.

由于 $p_{0,\cdots n-1}$ 构成了 $\{0,1,\cdots,n-1\}$ 的排列且 $p_i=p_{i\ \bmod \ n}$,因此根据上面的结论,可以证明: $$ \min_{i < xn,c_{p_i}=0} B_i=\min_{w_{i}\ge K,j < x} A_{i,j} $$ 对 $A$ 预处理出二维前缀 $\min$ 后,单次查询可以做到 $\mathcal O(1)$.

  • 求 $\min_{xn\le i \le xn+y,c_{p_i}=0} B_i$.

可以发现 $\min_{xn\le i \le xn+y,c_{p_i}=0} B_i=\min_{i\ge n-1-y,w_{i}\ge K} A_{i,x}$.

这是一个二维偏序问题,可以使用可持久化线段树维护。

由于 $x\in[0,\left\lceil\frac{m}{n}\right\rceil-1]$,我们在这里可以维护 $\left\lceil\frac{m}{n}\right\rceil$ 棵可持久化线段树实现上面的查询,这部分的代码实现难度较大。

求 $\max_{i\le t, c_{p_i}=1} B_i$ 是同理的。

综上所述,我们可以在一次二分后以单次 $\mathcal O(\log N)$ 的时间判断 $Z_t$ 是否符合条件。因此我们可以 $\mathcal O(\log^2 N)$ 地找到上面的 $T$,从而求出答案。这是 $\mathcal O(N\log^2 N)$ 的做法,进行一些常数优化后可能可以通过。

要优化到 $\mathcal O(N\log N)$ 是很简单的。

  • 我们可以先二分出一个 $x$ 满足 $xn\le T<(x+1)n$。

    在这部分二分中,我们可以单次 $\mathcal O(1)$ 地判断 $x$ 是否合法,所以复杂度是 $\mathcal O(\log N)$。

  • 然后我们再二分出 $T$ 的精确值。

    这可以通过在可持久化线段树上二分实现,所以复杂度依然是 $\mathcal O(\log N)$。

F. Colorful Graph 3

Proposed by 5ab. Prepared by 5ab.

Additional acknowledgement to Lynkcat, xiaowuc1 and xyz2606 for the contributions to the improvement of the problem statements, and to Kevin5307 and cmll02 for further testing the problem.

若有一个 $c_i\ge 2$,则构造对应颜色的菊花即可。

考虑计算理论最小的边数。设颜色 $i$ 的边数为 $a_i$,并定义 $t_i$ 为:若 $c_i=0$ 则 $t_i=0$,否则为最大的满足 $t_i(t_i+1)\le a_i$ 的整数。则为了保证连通,对于任意 $1\le i\le n$,以下不等式需要满足:

$$ \left(\sum a_j\right)-a_i+t_i\ge n-1 $$

注意到 $a_i-t_i$ 随着 $a_i$ 变大单调不降,所以存在一组最优解,满足 $a_i-t_i$ 的极差不超过 $1$。

假设我们求出了一组最小的 $a_i$,我们考虑两种策略:

$c_i=0$:每次从每种颜色中取出一条边,组成一个环并连接在任意点上,重复直到没有边。这样断掉任意一种颜色的边都是一些连起来的链。

$c_i=1$ 的 exact case:设 $T=\max \{t_i\}$,则先构造一个 $T$ 个点的完全图,然后将每条边替换成每种颜色各一条的链。

对于一般的情况,我们先执行 $c_i=1$ 的策略,并将 $c_i=0$ 的边也插入完全图的链中,但要除去一棵生成树。剩下的边数极差不超过 $1$,沿用 $c_i=0$ 的构造策略即可。可以证明这个构造可以取到下界。

G. CNOI Knowledge

Proposed by Kubic (a.k.a. vme50). Prepared by Kubic (a.k.a. vme50) and quailty.

Additional acknowledgement to kostca for the contributions to the improvement of the problem statements.

Analysis will be added a bit later.

H. Exchanging Kubic 2

Proposed by Kubic (a.k.a. vme50). Prepared by Kubic (a.k.a. vme50), Lynkcat and Qingyu.

Additional acknowledgement to djq_cpp and kostka for the contributions to the improvement of the problem statements.

Analysis will be added a bit later.

I. Nightmare

Proposed by ix35. Prepared by ix35, cmll02, Kevin5307 and Qingyu.

题意即为在维数 $m$ 尽量小的 $\mathbb F_p$ 上线性空间中找到 $n$ 个向量使得 $G$ 是它们的 Gram 矩阵。

$G$ 可以考虑为一个二次型,具体地,假设它是 $\{v_1,\ldots,v_n\}$ 的 Gram 矩阵,则对于 $x=\sum_{i=1}^n x_iv_i$,设 $X$ 是 $x$ 的坐标,那么

$$X^TGX=\sum_{i=1}^n\sum_{j=1}^n x_ix_j\langle v_i,v_j\rangle=\langle x,x\rangle.$$

假设对 $G$ 作合同变换得到 $G'=A^TGA$,其中 $A$ 是 $\{w_1,\ldots,w_n\}$ 坐标到 $\{v_1,\ldots,v_n\}$ 坐标的坐标变换矩阵,则设 $X$ 是 $x$ 在 $\{w_1,\ldots,w_n\}$ 的坐标,那么

$$X^TG'X=(AX)^TG(AX)=\langle x,x\rangle$$

因此 $G'_{i,j}=\langle w_i,w_j\rangle$,我们可以根据 $A$ 反求出 $\{v_1,\ldots,v_n\}$。也就是说,求出任意一个与 $G$ 合同的矩阵的答案,就可以求出 $G$ 的答案。


Part 1:$p>2$

在特征不为 $2$ 的域上,任何二次型都可以合同对角化。具体地,若存在 $G_{1,1}\ne 0$,则令 $v_1\leftarrow \sum_{i=1}^n\langle v_1,v_i\rangle v_i$ 就可以消去第一行第一列所有的 $1$。否则,如果对角元全为 $0$,设 $G_{1,2}\ne 0$,则令 $(v_1,v_2)\leftarrow (v_1+v_2,v_1-v_2)$,则有 $(v_1+v_2)^2-(v_1-v_2)^2=4v_1v_2=\dfrac{2}{G_{1,2}}\cdot 2G_{1,2}v_1v_2$,因此操作后至少有一个对角元非零(注意这里要求 $\dfrac{2}{G_{1,2}}\ne 0$,这需要在特征不为 $2$ 的域上才总是成立)。

设对角化后的矩阵为 $G'=\operatorname{diag}(g_1,\ldots,g_k,0,\ldots,0)$,其中 $g_1,\ldots,g_k\ne 0$。

若 $G'$ 对应的答案为 $\{v_1,\ldots,v_n\}$($v_i$ 是列向量),我们断言:

  • $v_i$ 的长度 $m$ 的最小值为 $k$ 为 $k+1$。
  • $m$ 的最小值为 $k$,当且仅当 $g_1,\ldots,g_k$ 中有偶数个非二次剩余。

$m\ge k$ 是显然的,下面首先证明 $g_i$ 有奇数个非二次剩余时 $m>k$:假设 $m=k$,令 $B=[v_1,\ldots,v_n]$,则 $G'=B^TB$,因此 $G'_{[1,k]}=B^T_{[1,k]}B_{[1,k]}$,那么

$$\det(G'_{[1,k]})=\prod\limits_{i=1}^k g_i=(\det(B_{[1,k]}))^2$$

应当是个二次剩余,但是奇数个非二次剩余的乘积是非二次剩余,这导出矛盾。

接下来考虑构造。

  • 若 $g_i$ 是二次剩余,则令 $v_{i,j}=0\ (j\ne i),\ v_{i,i}=\sqrt g_i$ 即可。
  • 剩下的非二次剩余两两配对,不妨设 $g_1,g_2$ 是二次剩余,令 $v_1=[a,b,0,\ldots,0],\ v_2=[c,d,0,\ldots,0]$。考虑确定 $a,b,c,d$,使得: $$a^2+b^2=g_1,\\c^2+d^2=g_2,\\ac+bd=0.$$
    + 事实上,任意求出一组 $(a,b)$(容易导出存在 $p$ 组这样的 $(a,b)$),再令 $c=a\sqrt{\dfrac{g_2}{g_1}},\ d=-b\sqrt{\dfrac{g_2}{g_1}}$ 即可。
  • 最终若剩下一个非二次剩余 $g_i$,单独凑一个 $a^2+b^2=g_i$ 即可,此时维数会变为 $k+1$。

至于 $(a,b)$ 的求法,显然只要对于某个特定的非二次剩余求出来就行了(别的情况可以类似于求 $c,d$ 的方式归结为求平方根),由于有 $p$ 组这样的 $(a,b)$,随机枚举 $a$ 并检查是否存在对应的 $b$ 即可。

时间复杂度为 $O(n^3+p^{0.25}\log p\log\log p+n\log^2 p)$。


Part 2:$p=2$

在特征为 $2$ 的域上,二次型不一定能对角化,所以上面的做法不再生效。

定义 $J=\begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}$。我们断言,$\mathbb F_2$ 上的矩阵一定合同于某个分块对角矩阵,每个对角块为 $[0],[1]$ 或 $J$。

为了实现这一分块对角化,我们首先类似于 $p>2$ 的情况解决对角线上有 $1$ 的情况,接下来规约到了对角线上全为 $0$ 的情况,我们要证明此时一定可以将矩阵合同为以 $J$(以及占位的 $[0]$)为对角块的分块对角阵。事实上假设 $G_{1,2}=1$,那么可以用 $G_{1,2}=G_{2,1}=1$ 把所有其他的 $G_{1,i},G_{2,i},G_{i,1},G_{i,2}$ 都消成 $0$,然后归纳即可。

令得到的分块对角阵为 $G'$,其中对角块为 $[0]$ 的个数为 $a$,$[1]$ 的个数为 $b$,$J$ 的个数为 $c$,我们知道如下事实:

  • $a+b+2c=n$,显然。
  • $b+2c=r=\operatorname{rank}(G')=\operatorname{rank}(G)$,因此 $a$ 是确定的。
  • $b\ne 0\iff \exists i,G_{i,i}=1$,因为如果对角线不全为 $0$,则不可能消成全零;反之亦然。

以上这些事实已经足够充分。若 $G'$ 对应的答案为 $\{v_1,\ldots,v_n\}$($v_i$ 是列向量),我们断言:

  • $v_i$ 的长度 $m$ 的最小值为 $r$ 为 $r+1$。
  • $m$ 的最小值为 $r$,当且仅当 $b\ne 0$。

$m\ge r$ 是显然的。下面首先证明 $b=0$ 时 $m>r$:假设 $m=r$,那么 $\{v_1,\ldots,v_n\}$ 就构成空间的一组基,然而由于对角元都为 $0$,所以它们都含有偶数个 $1$,故无法线性组合出有奇数个 $1$ 的向量,这与它们是基矛盾。

接下来进行构造。

  • 首先我们构造 $2c$ 个 $2c+1$ 维向量解决所有形如 $J$ 的对角块:首先令 $v_{i,j}=1\iff j\leq i+1$,然后再将所有的 $v_{2i,2i}$ 改为 $0$ 即可。
  • 若 $b=0$ 则已经做完,否则,令第 $2c+1$ 个向量为 $v_{2c+1,i}=1\iff i\leq 2c+1$,第 $2c+i\ (i\leq b)$ 个向量为 $v_{2c+i,j}=1\iff j=2c+i$ 即可。总维数为 $2c+b$。

时间复杂度为 $O(n^3)$,可能可以 $O\left(\dfrac{n^3}{w}\right)$。

J. Guess The Sequence 2

Proposed by Kubic (a.k.a. vme50). Prepared by Kubic (a.k.a. vme50) and Kevin5307.

Additional acknowledgement to Lynkcat and xiaowuc1 for the contributions to the improvement of the problem statements.

对于一种选择区间的方案,我们考虑怎样可以还原排列,或说明对应的排列个数大于 $1$。

从小到大考虑每个数。设当前考虑到了 $x$,观察所有满足 $m_i\leq x$ 的区间,若 $1,2,\dots, x$ 中有至少两个数均没有被这些区间覆盖,那么对应的排列个数一定大于 $1$。这是因为,原排列一定是一个满足限制的排列,且在原排列的基础上交换这两个数,仍然满足所有限制,故这种情况是不合法的。同时,在所有没有被 $m_i < x$ 的区间覆盖的数(排除掉上面的情况后,这样的数最多只有两个)中,一定有恰好一个位于 $m_i=x$ 的区间的交中,否则两个数都在 $m_i=x$ 的区间的交中:我们同样可以交换这两个数,使得所有限制仍然被满足。

容易证明,如果同时满足这两个条件,那么一定可以唯一确定排列。于是可以考虑 DP 状态 $f(x,p)$ 表示考虑到了 $x$ 且数 $p$ 没有被覆盖时的方案数,若 $p=0$ 则表示所有数都被覆盖了。分析该 DP 数组的转移。下面令 $x$ 为当前考虑的数,$a$ 为一个满足其在原排列中和 $x$ 之间的所有数都 $\leq x$ 的数,$b$ 为一个满足其在原排列中和 $x$ 之间有至少一个数 $>x$ 的数。

  1. $f(x-1,0)\to f(x,0)$:这一类要求 $x$ 被覆盖。
  2. $f(x-1,0)\to f(x,x)$:这一类要求 $x$ 不被覆盖。
  3. $f(x-1,a)\to f(x,a)$:这一类要求 $x$ 被覆盖的同时 $a$ 不被覆盖。
  4. $f(x-1,a)\to f(x,0)$:这一类要求 $x$ 和 $a$ 都被覆盖,且要能区分 $a$ 和 $x$,即所有区间的交不能包含 $a$。
  5. $f(x-1,b)\to f(x,b)$:这一类要求 $x$ 被覆盖。

考虑优化这个 $O(n^2)$ 的 DP。由于数据随机,所以每个 $x$ 要考虑的 $a$ 的总和是 $O(n\ln n)$ 级别的,且每个 $x$ 的所有第 $5$ 类转移的系数都相同,所以可以用全局乘法 tag 做到 $O(n\ln n)$。

K. Game: Battle of Menjis

Proposed by gyh20. Prepared by gyh20.

Additional acknowledgement to xyz2606 for the contributions to the improvement of the problem statements, and feecle6418 for showing in the problem statements.

给出结论:无论游戏进行多少轮,其结果总是和只进行一轮的情况完全一致。

Alice 可以在游戏的第 $2,3,\dots, k$ 轮均选择上一轮中 Bob 选择的位置,也就是将被 Bob $-1$ 的数复原,此时等价于只进行一轮的情况,所以进行 $k$ 轮的答案不会小于进行一轮的答案。类似地,Bob 可以在游戏的第 $1,2,\dots,k-1$ 轮均选择同一轮中 Alice 选择的位置,也就是将被 Alice $+1$ 的数复原,此时同样等价于只进行一轮的情况,所以进行 $k$ 轮的答案不会大于进行一轮的答案。故结论正确。

此时我们可以枚举 Alice 的选择,然后考虑 Bob 的选择。容易发现,Bob 选择的数对最终所有数的异或和带来的改变只取决于他选择的数二进制下末尾 $0$ 的个数,于是可以统计每个二进制下末尾 $0$ 的个数为 $x$ 的数是否存在,然后暴力枚举 Bob 的选择。时间复杂度 $O(n\log a_i)$。

L. Slay the Spire

Proposed by xtqqwq. Prepared by djq_cpp, Lynkcat and xtqqwq.

先假设所有边都能够取到。相当于对于每条边,我们可以支付一个代价,更换其起点。最后要形成一个完整的欧拉回路。那么对于每个点,我们至少要支付 max(0, 出度 - 入度 - 是否是起点 - 到它的药水个数) 条以它为起点的边的代价。我们直接选权值最小的那些边。可以证明这样选之后一定存在一个更换边的起点的方案可以使得最终图上所有点 (入度 + 是否是起点 + 到它的药水个数 = 出度)。唯一问题就是这个最终图是否是一个可以连续走完的连通块。可以发现,只有在存在一个初始图中入度 = 0 的强连通分量,且这些边全都被保留的情况下,才会出现孤立的连通块。这种情况下,我们就需要至少再支付这个强连通分量中一条边的代价。但与此同时,我们就可以少支付一条连出该强连通分量的边的代价。对于所有的这些强连通分量,枚举这样替换的最优解即可。

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

M. Puzzle: Summon

Proposed by Qingyu. Prepared by Lynkcat and Qingyu.

Additional acknowledgement to bulijiojiodibuliduo for the contributions to the improvement of the problem statements, and quailty for the adjustment of the original problem idea.

Analysis will be added a bit later.

一段故事的结束

2024-06-03 20:33:16 By Qingyu

可我真的没法忍住不哭...

QOJ 最新表情

2024-05-11 23:15:34 By Qingyu

在评论区使用对应 Command 即可输出对应的表情。

Command Image
/djqlgm
/djq2024
/duide
/duima
/budui
/hhz
/hehezhou
/akshen
/dyh_young
/jiehun
/zdjd

The 2nd Universal Cup Schedule, Summer Summit, and Finals Team Selection

2024-03-19 11:56:44 By Qingyu

We are excited to announce the onsite final competition for the 2nd season of the Universal Cup. This document outlines the season's structure and the criteria for progressing to the Finals.

Online Stages

The online stages last from September 2, 2023, to April 20, 2024. For details on the rules, schedule, and ratings, please visit the following links: rules, schedule, and ratings.

The online stages of this season will end on Apr 20, 2024. The ratings of the online stages will be finalized and published on Apr 23, 2024.

Note: As we mentioned in the rules, if you participated in the onsite event of an online stage and would like to add your onsite standings to the ratings, you must reach out to the organizing committee before April 22, 2024. We will not accept submissions after the publication of the results.

Semifinals

The 2nd Universal Cup Semifinals will take place online, in order to select teams for the Final Contest. The contest is scheduled on one of the last two weekends of June (June 23 or 30), with the same rules of the online stages, except the time windows part. There will be only one window for the Semifinals and it will be an original, fresh contest, which was not used in any other events. The exact time will be announced soon.

Universal Cup Finals

The 2nd Universal Cup Final event will invite at least 20 teams. The promotion process will start at least three months before the event. The promotion process is as follows.

Part 1: Online Stages (up to 10 teams)

The top 10 teams from the season's ratings will be invited to the Finals. The teams will have to choose whether to accept the invitation in the first week of the promotion process.

Part 2: Contributors (up to 2 teams)

In appreciation of teams contributing contests during the online stages, up to 2 slots are reserved. This applies to teams that submitted at least one contest but didn't qualify in Part 1. The highest-rated two among them will advance to the onsite finals. In cases where a contest is contributed by multiple teams, only one may advance using this contribution. Teams that would like to compete for the contributor slots will have to apply within the first week when the promotion process begins.

Part 3: Semifinals (at least 8 teams)

Subtracted by the number of teams promoted from Part 1 and 2, all other finals slots will be distributed through the Semifinals. Excluding teams that are already invited, teams will be invited in the order of the semifinals result. Each team will have up to 3 days to decide whether to accept the invitation. This process will start after the promotion process of Part 1 and 2 finishes and terminate when all slots are distributed.

The total number of onsite slots will be at least 20. However, the Universal Cup committee reserves the right to distribute slots if there are more.

The 2024 Universal Cup Summer Summit

The Summer Summit event will have 10 slots in total and it will only be based on the season rating. Teams will be invited in the order of the season’s rating. Each team will have up to 3 days to decide whether to accept the invitation. Note that being invited to the Summer Summit doesn’t guarantee a slot for the onsite Finals.


我们很高兴地宣布 The 2nd Universal Cup 的决赛(Finals)。本文将概述本赛季的结构、以及晋级总决赛的标准。

线上赛

本赛季的线上赛从 2023 年 9 月 2 日 到 2024 年 4 月 20 日。有关线上赛的规则、日程、排名,可见:rules, schedule, and ratings.

本赛季的线上赛将于 2024 年 4 月 20 日结束。本赛季线上赛的 Rating 将于 2024 年 4 月 23 日被汇总并最终发布。

请注意:正如我们在 rules 中所提及,如果你参加了线上赛的现场比赛,并希望将你的现场排名加入排名中,你必须在2024 年 4 月 22 日之前联系组织委员会。结果公布后,我们将不再接受提交。

Universal Cup Semifinals

The 2nd Universal Cup Semifinals(半决赛)将会在线上举办,并选拔出部分进入决赛的队伍。这场比赛计划于六月的最后两个周末之一(即 6 月 23 日或6 月 30 日)举办,并具有和线上赛除 Time Window 外相同的 规则。本场比赛将只有一个 time window,且会是一场全新的,没有在任何其他活动被使用的比赛。半决赛的具体日期将在稍后被公布。

Universal Cup Finals

The 2nd Universal Cup Finals(决赛)将会邀请至少 20 支队伍。晋级的过程将在活动前至少 3 个月开始。晋级的流程如下:

第一部分:线上赛 (至多 10 支队伍)

本赛季 Rating 排行榜的前 10 名将被邀请进入决赛。所有队伍都必须在晋级过程开始的第一周内确定是否接受邀请。

第二部分:贡献者 (至多 2 支队伍)

为了感谢贡献比赛的队伍,有 2 个 Finals 的名额被贡献给了出题人。这适用于提交了至少一场比赛但在第一部分中未能晋级的团队。其中排名最高的两支将晋级到 Finals。如果一场比赛由多支团队共同贡献,只有一支可以凭借这一贡献晋级。所有申请以这种方式晋级的队伍必须在晋级过程开始的第一周内申请。

第三部分:半决赛 (至少 8 支队伍)

通过半决赛分配的名额即为总名额减去第一部分和第二部分已晋级的队伍数量。除了已经被邀请的队伍外,其他队伍将根据半决赛的结果被邀请。每支队伍有最多 3 天的时间决定是否接受邀请。这个过程将在第一部分和第二部分的晋级过程结束后开始,并将在所有名额分配完毕时结束。

决赛的名额将会至少有 20 个。然而,如果会有更多的名额,Universal Cup 组委会将保留分配剩余名额的权利。

The 2024 Universal Cup Summer Summit

The Summer Summit(夏季峰会)总共有 10 个名额,且仅通过本赛季的 Rating 进行邀请。队伍将被按照在本赛季 Rating 的排名从高到低进行邀请。每支队伍将会有 3 天的时间来决定是否接受邀请。请注意,被夏季峰会邀请并不代表获得保送 Finals 的名额。

kenji's life 2 真结局 解题报告

2024-03-10 21:12:23 By Qingyu

以下为一种可能的 AK IOI 的方案。

TLDR:攒鏼的好感度,去 THU 才能进国家队,需要攒够所有人的帮助才能打出 TE。

关键点:

  1. 非必要不学习新算法。
  2. 最重要的是思维能力,其次是代码能力。在 IOI 代码准确度没有用。
  3. 防止挂 CTSC,需要在 NOI 后签 THU(+2/+2/+2),这需要买菜否的好感度 < -4。
  4. AK IOI 的必要条件:
    • 思维能力 >= 12
    • sy2006 的帮助:乱搞。
    • jcvb 的帮助:贪心。
    • Ruchiose 的帮助:树套树。
    • Ruchiose 的帮助:决策单调性。
  5. 获得 jcvb 的帮助需要好感度 >= 4,而要达成的唯一方法只能是在 ZJOI 卡线掉出省队并购买 C 类。
  6. 购买 C 类需要刷 ppfdd 的好感度
  7. 获得 szy 的帮助需要在 NOI 中通过 D1T1 和 D2T3。

Stage 1: NOIP 普及组

1

"你叫kenji,是一名初中生。你想进入传统弱校zhzx(复刻者注:浙江省镇海中学,很强)。你有三种方式进入zhzx:一、NOIP拿到一等直接保送。二、通过提前招生考试,对文化课要求较高。三、通过中考(怎么考都能进)",

"当然,保送后将会比中考多出几个月的时间学习OI,而中考会多出几个月时间学习文化课,所以你要思考清楚.",

"NOIP马上就要到了,你要加强训练争取拿到一等。",

无选项。

2

Kenji: 马上就要NOIP了,我要好好利用这次机会。

今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习中考

这里如果学习新算法,会得到 dijkstra,但在你的整个 OI 生涯中没有任何用途。

选择复习中考(思维能力+1)。

3

Kenji: 明天就是NOIP了,他们都在打隔膜。我该干什么呢

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习中考
  • 打隔膜

这里如果学习新算法,会得到 kruskal,但在你的整个 OI 生涯中没有任何用途。

选择打隔膜

4

UsedToBe: kenji跟我打隔膜

Dccxx: kenji跟我打隔膜

  • 跟UsedToBe打
  • 跟Dccxx打
  • 烦死了不打了

选择烦死了不打了

5

虽然不打隔膜了但是也没心思刷题了。要不逛会贴吧吧。

咦,这个叫做ppfdd的人好像很活跃的样子?我跟他聊一会。。。

(ppfdd 好感度 +1)

6

马上要进考场了,好紧张啊

第一题大水题10min直接秒了。

第二题无脑模拟,应该直接撸过去就好了。

第三题看起来很难只会暴力。60分暴力应该可以很快写完。要是想出标算应该也不难写。

第四题50分暴力不算好写,70分暴力超好写但没什么把握,标算大概搞个栈就没了但是要写一会。

由于一等奖分数线只有 240 分,只需要写第二题标算与第三题 60 分暴力,接下来选择睡觉。

7

你拿到了一等,同时也获得了保送资格。但是你可以选择放弃保送去中考。

  • 去 zhzx
  • zhzx传统弱校还不如自己刷题

选择去 zhzx

8

kenji:终于到了传统弱校zhzx。

zyh:kenji你千万不要跟耒阳大神szx坐啊,否则会被坑死的。

  • 管你干什么,我要向szx学习新知识
  • 有道理的,szx太坑了

选择 管你干什么,我要向szx学习新知识

一个学期后你的能力大幅提升(代码能力++,思维能力++,代码准确度++)

(代码能力 +1,思维能力 +1,代码准确度 +1)

(此时代码能力 2,代码准确度 1,思维能力 2)

Stage 2: NOIP 提高组

1

kenji: 进了zhzx,要选竞赛了。我选什么呢?

  • 数学竞赛
  • 物理竞赛
  • 化学竞赛
  • 信息竞赛

这里需要注意的是,如果选择学习其他竞赛,必定会触发结局 高三的kenji曾经参加过两次竞赛,第一次在市里的选拔里跪掉了。第二次好不容易进了市队,又在省里的选拔里跪掉了。但是在 NOI 前,如果其他三门竞赛的老师好感度为正,会触发在 NOI 前被带去学习其他竞赛的剧情。因此在这里,我们需要依次选择其他三个竞赛,并在询问你是否确定要学习时选择拒绝。这样会降低其他竞赛老师的好感度,防止 NOI 前触发该剧情。

kenji: 我从小就对编程感兴趣,我要选信息竞赛!

2

fsygd: 谁还没有被啊过? zyh: 我!

  • 关我鸟事我要刷题
  • 不如我们啊ppfdd吧
  • zyh你们都敢啊?
  • 我也要啊zyh不如我们一起啊吧

这里如果选择选项二,会导致 ppfdd 好感度下降;如果选择选项三,会导致 Ruchiose 的好感度下降;如果选择选项四,会导致 zyh 的好感度下降。无论哪个支线都不利于接下来的走向,因此我们选择 关我鸟事我要刷题,这样什么都不会发生。

3 - NOIP Day 0

kenji: 明天就是NOIP了,他们都在打隔膜。我该干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期中考
  • 打隔膜

这里如果学习新算法,会得到 exgcd,但在你的整个 OI 生涯中没有任何用途。

如果选择复习期中考,可以获得思维能力 +1,但会凑不够 ppfdd 的好感。

因此这里需要选择打隔膜

kenji: 跟谁打呢?

ppfdd: kenji跟我一队吧

qwer_zcc: kenji跟我一队

跟谁一队

  • ppfdd
  • qwer_zcc

当然是选择 ppfdd

ppfdd: 好感++

(ppfdd 好感度 +1)

4 - NOIP Day 1

为了让 jcvb 加你的 QQ 膜拜你,你需要达成:

  1. 在 NOIP 两天的 T1 中均获得 0 分。
  2. 在 NOIP 两天的 T3 中均获得 100 分。

kenji: 马上要进考场了,好紧张啊

第一题“转圈游戏”无脑快速幂,从来没写过有可能会写残啊。不过暴力应该写不残吧。,

第二题“火柴排队”60分挺显然但是有可能写残。标算没看出来,

第三题“货车运输”搞个最小生成树就没了LCA估计还得写一会。不写LCA的60分非常好写但是说不定最小生成树就biubiu了。

比赛策略:做 T2 正解(需要做四次,前两次会想不出来,第三次会得到做法,第四次会写出来),做 T3 正解(但是会写挂),写 T3 暴力,对拍 T3,睡觉。

最终得分:0+100+100=200

明天就是Day2了,我应该打隔膜还是好好学习呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期中考
  • 打隔膜

学习新算法会触发 这个叫做多叉树转二叉树的算法挺有趣的,但是没用。

为了做出 D2T3,你需要思维能力大于等于 3,因此在这里需要复习期中考

(思维能力 +1)

(此时代码能力 2,代码准确度 1,思维能力 3)

5 - NOIP Day 2

kenji: 马上要进考场了,好紧张啊

"第一题“积木大赛”无脑差分,从来没写过有可能会写残啊。但是暴力很难写",

"第二题“花匠”70分n^2 DP挺显然。标算没看出来",

"第三题“华容道”暴力最短路再搞几个小优化就好了。不过标算有点难写而且容易写残。",

与第一天类似,写 T2 正解,写 T3 正解(会写挂),写 T3 暴力,对拍。比赛最后只剩 5 分钟。

最终得分:0+100+100=200

6

jcvb: orz A 掉后四题的大神不屑于做水题的 kenji 大神

(jcvb 好感度 +1)

你的回复

  • 跪舔JCUB
  • 强之跪跪膝
  • orzAK爷
  • 你骂我,enr?
  • 我看你生辰八字,你好像进不了省队

选择 我看你生辰八字,你好像进不了省队

jcvb: 好啊咱们走着瞧

这样在 ZJOI 后会触发 “jcvb:果然被你说中了”并增加好感度。

Stage 3: ZJOI

1

LHY大帝: kenji啊,最近AEC有个活动你有兴趣参加吗?

  • 好啊
  • 算了最近有事

选择第一个选项会增加 xudyh 与 Ruchiose 的好感,但也会增加其他竞赛老师的好感,会爆,所以我们要选算了最近有事

xudyh: kenji不跟大帝搞好关系以后怎么混!(好感-=3)

Ruchiose: 到时候你就会后悔了(好感-=3)

(xudyh 好感度 -3)

(Ruchiose 好感度 -3)

2

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期中考
  • 巡视机房

这里如果学习新算法,会学会 FFT,在 ZJOI 和 CTSC 中有用。但是因为我们的目标是卡线不进队,所以不会也无所谓。

选择复习期中考

(思维能力 +1)

(此时代码能力 2,代码准确度 1,思维能力 4)

3

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期中考
  • 巡视机房

这里如果学习新算法,会学会最小二乘法,在 ZJOI 中有用。但是因为我们的目标是卡线不进队,所以不会也无所谓。

选择巡视机房

xudyh: 给你一个二分图,怎么求完备匹配个数啊?

fsygd: 水题!这不是有多项式做法吗?

  • 有道理的,看起来是有
  • 这怎么可能有多项式做法?
  • 这题法海都会做!
  • dyh你有没有证明怎么知道?
  • 关我屁事

这里是唯一一处可以增加 sy2006 好感度的地方,因此要选择dyh你有没有证明怎么知道?。选择第三个选项虽然也可以增加,但是会降低 ppfdd 的好感度导致买不到 C 类,所以只能选择第四个选项。

sy2006: 有道理,好像不是很好证的样子(好感++)

xudyh: 哎,连kenji都鄙视我(好感--)

(xudyh 好感度 -1;目前 xudyh 好感度 -4)

(sy2006 好感度 +1;目前 sy2006 好感度 1)

4 - ZJOI Day 0

kenji: 明天就是ZJOI Day1了,我应该打隔膜还是好好学习呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期中考
  • 打隔膜

这里如果学习新算法,会学会 DLX(Dancing Links)。在 ZJOI 中有用。但是因为我们的目标是卡线不进队,所以不会也无所谓。

选择打隔膜

kenji: 跟谁打呢?

  • qwer_zcc ppfdd
  • UsedToBe Dccxx

选择 qwer_zcc ppfdd

ppfdd: 好啊好啊(好感++)

qwer_zcc: 我要打隔膜!打隔膜!打隔膜!打隔膜!打隔膜!(好感++)

Dccxx: 哎又缺一个人(好感--)

UsedToBe: 只能1虐4了好不爽(好感--)

(ppfdd 好感度 +1;目前 ppfdd 好感度 3)

(qwer_zcc 好感度 +1;目前 qwer_zcc 好感度 1)

(Dccxx 好感度 -1;目前 Dccxx 好感度 -1)

(UsedToBe 好感度 -1;目前 UsedToBe 好感度 -1)

5 - ZJOI Day 1

冷知识:以前 ZJOI 的 Day 1 与 Day 2 间隔一个月。

kenji: 马上要进考场了,好紧张啊

这里显示的消息会根据你的技能树不一样而不同。

T1

如果会 DLX:第一题“消棋子”无脑模拟,感觉可以用类似DLX的东西。但是超级难写。不过暴力也不好写,可能写标算划算一点。

如果不会 DLX:第一题“消棋子”无脑模拟,感觉搞个set会好写一点但还是超级难写。而且暴力也没有什么可写性。还是弃疗吧。

T2

如果会FFT:第二题“力”数据范围好大,为什么看起来像FFT?

如果不会FFT:第二题“力”好像除了暴力没办法了?或者可以试试泰勒展开?

T3

如果会最小二乘法:第三题“星系调查”好像就是最小二乘法加个斜率,小学数学推一会就好了。然后环加外向树也不难写。看起来可以秒?

如果不会最小二乘法:第三题“星系调查”好像暴力都不会?感觉要滚粗

比赛策略

这里其实不会 DLX 可以硬做 T1,然后写 T2 暴力即可。

写 T1 正解(会写挂) - 写 T1 暴力 - 对拍 T1(此时还剩 50 分钟) - 写 T2 暴力 - 睡觉。

总分 100+30+0=130

6 - ZJOI Day 1 后

xudyh: kenji马上二试了你停课吗?帮我把停课申请交一下吧。

  • 为什么要帮你交?

这里杜老师的好感屁用没有,选择为什么要帮你交?

xudyh: 王仓你不帮我交(好感--)

Ruchiose: 王仓你不帮我交(好感--)

(xudyh 好感度 -1;目前 xudyh 好感度 -5)

(Ruchiose 好感度 -1;目前 Ruchiose 好感度 -4)

7 - 化学竞赛

WDH: 还有两天就要市化学竞赛了,kenji你一定要来啊

xudyh: kenji你去化学考考没希望的,别去了。

  • 我爸说了(此处省略……
  • 化学竞赛纯粹是浪费人时间毁人一生的——玩意儿

这里如果选择不去陪杜老师打游戏,可以获得 xudyh 的好感,但是会失去扣 WDH 好感的机会,因此要选择 我爸说了(此处省略……

kenji: 哎,考场上好无聊啊,好想睡觉,可是又在考试,要不要好好考呢?

  • 绝不睡觉
  • 睡觉不睡还有力气打隔膜?

这里需要选择睡觉不睡还有力气打隔膜?让自己化学竞赛考试爆了,降低 WDH 的好感度。

WDH: 这次kenji考这么差?哎,看来kenji也不是这块料(好感--)

(WDH 好感度 -1;目前 WDH 好感度 -2)

8 - 物理竞赛

HGL: kenji啊,科技创新节到了你要不要写篇论文啊,这是锻炼自己的好机会

  • 好啊好啊
  • 我哪有时间搞这些乱七八糟的事情

选择第一个选项会 +3 思维能力,但会导致 HGL 好感度过高导致你必须找 JCVB 帮忙,触发比较黑恶的剧情,因此这里选择我哪有时间搞这些乱七八糟的事情

9 - 联考

zyh: 杜教快给我发一份今天的题解!!!

xudyh: 好好好马上给你发

zyh: 为什么我还没收到?

xudyh: 噢,因为我选的定时发送,你今天晚上11点就能收到了

zyh: 。。。

一天后

xudyh: 为什么我这题T掉了?不合理啊求发数据!!!

zyh: 太好了终于拿到数据了

xudyh: 为什么我没有???

zyh: 因为你没加讨论组

xudyh: 王仓!!!

  • 发个定时发送给xudyh
  • 直接发
  • 关我鸟事

选择 发个定时发送给xudyh

xudyh: 。。。(好感--)

Ruchiose: 蛤蛤,kenji太机智了(好感++)

(xudyh 好感度 -1;目前 xudyh 好感度 -6)

(Ruchiose 好感度 +1;目前 Ruchiose 好感度 -3)

10 - ZJOI 省选讲课

kenji: 要去听省选讲课了,又要被国家队爷们虐了,真悲伤。

xudyh: kenji你认识JCVB吗?

如果你在 NOIP 时没有成功认识 JCVB,会触发:

kenji: 那是谁?没听说过

哎,真悲伤。

说明你前面做错了一些东西,重开吧。

如果你在 NOIP 时两天 T1 爆零认识了 JCVB,会触发:

kenji: 认识啊,人家三个国家队

xudyh: 你看JCVB就在那里快去orz

  • 终于见到真人了我要orz
  • 可以跟他当面讨论学♂术问题了
  • 他都不知道我是谁orz了也没用啊

选择可以跟他当面讨论学♂术问题了

xudyh: 王仓你们怎么聊起来了(好感--)

没想到kenji的知♂识♂水♂平这么高(好感++)

(xudyh 好感度 -1;目前 xudyh 好感度 -7)

(jcvb 好感度 +1;目前 jcvb 好感度 1)

11 - ZJOI Day 2 前

kenji: 明天就是ZJOI Day2了,我应该打隔膜还是好好学习呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期中考
  • 打隔膜

为了让 ppfdd 给你买 C 类,你需要最后一次攒 ppfdd 的好感,选择打隔膜

kenji: 跟谁打呢?

  • qwer_zcc ppfdd
  • UsedToBe Dccxx

选择 qwer_zcc ppfdd

ppfdd: 好啊好啊(好感++)

qwer_zcc: 我要打隔膜!打隔膜!打隔膜!打隔膜!打隔膜!(好感++)

ppfdd: 哎呀我们已经开了要不然你等下一局?

kenji: 哎没隔膜打了我去好好学习了

(ppfdd 好感度 +1;目前 ppfdd 好感度 4)

(qwer_zcc 好感度 +1;)

另外,如果在这里选择学习新算法,你会阅读一篇关于 SG 函数的博客,学会 SG 函数。

12 - ZJOI Day 2

kenji: 马上要进考场了,好紧张啊

T1

第一题“2048”题答题,感觉乱搞搞一会能有点分

T2

如果会 SG:第二题“取石子游戏”好像跟SG函数有些关系?

如果不会 SG:第二题“取石子游戏”连题目都看不懂待会再说

T3

第三题“璀璨光华”是sb题就是有点难写而且不给部分分

做 T3,做两次 T1,然后睡觉。总分刚好卡到 15+0+100=115

(这里如果做 T2 会有个趣味支线 “出考场后发现第二题结论是错的?不过骗到了全场最高60也不错了”,感兴趣的网友可以自己试试。)

13 - 省选出分

NOIP 总分:0+100+100+0+100+100=400,标准分 600

Day 1:100+30+0=130,标准分 300

Day 2:15+0+100=115,标准分 195

总分:400 0.3 + 130 / 300 600 0.3 + 115 / 195 600 * 0.4 = 339,省队分数线 345,刚好卡线不进省队。

kenji: 滚粗了真开心

jcvb: 还真被你预言中了我果然滚粗了23333(好感++)

(jcvb 好感度 +1;目前 jcvb 好感度 3)

jcvb: 听说你也刚好被线踩?我344也被线踩了真悲伤。好在今年有C类,我们一起努力吧(好感++)

(jcvb 好感度 +1;目前 jcvb 好感度 4)

kenji: 哎,滚粗了。难道我的OI生涯就此结束了吗?

qwer_zcc: 别怕,有钱就能买C类

(这里如果 zcc 好感不够的话会触发劝退你的支线 hhhhh,你就直接爆了)

  • 问问我妈肯不肯买吧
  • (大声吼)求赞助一个C类啊啊啊
  • (悄悄说)能不能给我买一个C类?
  • (跪舔)我的前途就掌握在你手上了,求C类
  • 反正对你来说也就一平米你也不在乎吧

这里需要吸引来 ppfdd 的注意,因此只能选择(大声吼)求赞助一个C类啊啊啊

qwer_zcc: 要买自己买去

ppfdd: zcc你这么小气干什么不就一平米吗?

qwer_zcc: 有钱你给他买啊

ppfdd: 买就买,kenji进国家队了我还能有回扣

kenji: 太好了我又可以进队了

Stage 4: NOI

1 - 竞赛教练

Ruchiose: kenji啊,NOI前的停课申请写了吗?帮我交一下吧

  • 为什么要帮你交?

选择

Ruchiose: 对了杜教不在你帮他也交一下吧

  • 两份够多了烦死了

这里如果只帮 Ruchiose 一个人交可以获得好感,都帮就不会收获好感(?)。所以选择两份够多了烦死了

Ruchiose: (好感++)

xudyh: 王仓kenji怎么不帮我交(好感--)

(xudyh 好感度 -1;目前 xudyh 好感度 -8)

(Ruchiose 好感度 +1;目前 Ruchiose 好感度 -2)

SHY: kenji同学停课了想来已经进队了吧?有前途的(好感++)

(SHY 好感度 +1;目前 SHY 好感度 0)

Ruchiose: kenji啊,你觉得WDH厉不厉害啊?

  • 厉害,太厉害了!
  • 他是谁我不认识
  • WDH不是个,b吗?

选择 WDH不是个,b吗?

Ruchiose: kenji你真是太机智了。(好感+=2)

WDH: kenji居然敢骂我,有潜力!(好感+=2

。。。

(Ruchiose 好感度 +2;目前 Ruchiose 好感度 0)

(WDH 好感度 +2;目前 WDH 好感度 0)

xudyh: 今天HGL要开会啊,马上就开始了你们还不过去吗?

Ruchiose: kenji陪我把这局隔膜打完。

  • HGL开会怎么能迟到?
  • 你问我支持不支持约大爷打隔膜,我当然支持了

选择 你问我支持不支持约大爷打隔膜,我当然支持了

Ruchiose: 爽爽爽爽(好感++)

HGL: kenji同学现在才来?想来是在用功学习。(好感++)

(Ruchiose 好感度 +1;目前 Ruchiose 好感度 1)

(HGL 好感度 +1;目前 HGL 好感度 0)

2

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

这里如果学习新算法会学到“这个基于概率判矩阵 $A \times B$ 是否等于 $C$ 的东西挺有趣的”,但其实多学文化课即可,没必要在这里点这个技能。选择巡视机房

zyh: 买老师这道题怎么做

买老师: 这不是显然莫队一下就好了?

fsygd: 什么?莫队算法不是用来求曼哈顿距离最小生成树的吗?

kenji:

  • 范高达你怎么连这种东西都搞不清楚?
  • 问问cenbo就知道了
  • 买老师每天游戏打打还会知道这种东西?

选择 问问cenbo就知道了

买老师:kenji你显然是不相信我嘛(好感--)

cenbo: 看来在kenji眼里我还是很厉害的(好感++)

fsygd: cenbo肯定支持我的(好感++)

(买老师 好感度 -1;目前 买老师 好感度 -1)

(cenbo 好感度 +1;目前 cenbo 好感度 1)

(fsygd 好感度 +1;目前 fsygd 好感度 1)

3

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

这里如果学习新算法会学到“这道在树上推乱七八糟性质的题目挺有趣的”。

选择巡视机房

zyh: sad sad sad sad sad sad sad不出来!!!

买老师: zyh你又当街l(uo)g(an)?

  • 就是就是

  • zyh如此正直怎么会干这种事

  • 买老师你连zyh都要管?

选择zyh如此正直怎么会干这种事

买老师: 哎被kenji鄙视了(好感--)

cenbo: zyh多么正直(好感++)

fsygd: zyh多么正直(好感++)

(买老师 好感度 -1;目前 买老师 好感度 -2)

(cenbo 好感度 +1;目前 cenbo 好感度 2)

(fsygd 好感度 +1;目前 fsygd 好感度 2)

4

如果你的 SHY, WDH, HGL 的好感度大于 0,会触发:

jcvb: 我感觉最近SHY、WDH、HGL可能会来找你,让你无法进行后续的进程

在任意情况,均会触发:

jcvb: 我可以帮你做一些鏼鏼的事情,但是你的结局会发生变化

  • 好啊
  • 不要

由于我们的路线保证了 SHY、WDH、HGL 的好感度均为 0,因此直接选择 不要

如果你的 SHY 好感度大于 0,会触发 MO 结局(Bad End):

SHY: kenji同学这几天没事吧?过来上数学竞赛吧我很看好你的。不要以为进队了就能金牌啊,来学数学才有希望。你要是不来以后课不要来上了。

kenji: 哎那只能去了

高三的kenji曾经参加过两次竞赛,第一次在市里的选拔里跪掉了。第二次好不容易进了市队,又在省里的选拔里跪掉了。

否则,会触发:

SHY: kenji同学好好学习啊,我现在感觉你学数学应该没什么前途的。

(同理,WDH、HGL 会分别触发 PhO 结局与 ChO 结局)。

5

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

(这兄弟 NOI 前就没训练过)

这里如果学习新算法会学到“这道码农DP的题目挺有趣的”。

选择巡视机房

kenji: 要去参加THUSC了,感觉面试过不了啊,买老师你去年是怎么样的?

买老师: 你只要回答“我关心时政”然后他就会问一堆你答不出来的东西然后只要你考试考得好就可以过了。

  • 买老师教导的是
  • 买老师你骂我
  • 我好像曾经在哪里失败过,却又总是想着去逃避

选择买老师教导的是

买老师: kenji加油A掉两道就没问题了(好感++)

zyh: 买老师教导的是(好感++)

fsygd: 买老师教导的是(好感++)

(买老师 好感度 +1;目前 买老师 好感度 -1)

(zyh 好感度 +1;目前 zyh 好感度 1)

(fsygd 好感度 +1;目前 fsygd 好感度 3)

6

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

这里如果学习新算法会学到“这个叫做最近点对问题的东西挺有趣的”,但是在你的 OI 生涯中完全没用。

选择巡视机房

CMG: 我来讲一下这道题。。。

fsygd: 咦你怎么也能和我一样一笔画出两道线?

CMG: 有道理的。。。我好像拿反了。。。

  • 我重默歌我重默歌daladilidaladu!
  • 想当年fsygd拿反的时候。。。
  • 你看看买老师从来不会干这种事

选择我重默歌我重默歌daladilidaladu!

买老师: 我重默歌我重默歌daladilidaladu!(好感++)

zyh: 我重默歌我重默歌daladilidaladu!(好感++)

fsygd: 我重默歌我重默歌daladilidaladu!(好感++)

CMG: 。。。。。。

(买老师 好感度 +1;目前 买老师 好感度 0)

(zyh 好感度 +1;目前 zyh 好感度 2)

(fsygd 好感度 +1;目前 fsygd 好感度 4)

7 - NOI Day 0

这里是触发 szy 支线的关键地方。为了让 szy 劝你签 THU,你需要在 NOI 中通过 D1T1 与 D2T3 让他认识到你,而由于我们没有在之前学习怎么随机判定矩阵乘法,因此我们只能把思维能力刷到 5,才能现场发明出来。

kenji: 明天就是NOI了,该好好复习吗?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 打隔膜

这里如果学习新算法会学到单纯形,但是在你的 OI 生涯中完全没用。

这里如果选择打隔膜,会触发 JCVB 教你具体数学的剧情。

选择复习期末考

(是的,从 ZJOI 到 NOI 你从来没有训练过)

(思维能力 +1)

(此时代码能力 2,代码准确度 1,思维能力 5)

8 - NOI Day 1

kenji: 马上要进考场了,好紧张啊

T1

第一题“向量内积”感觉是乱搞题,超级大暴力有60分"

T2

如果你之前学习的时候学到了 “这道在树上推乱七八糟性质的题目挺有趣的”:

第二题“树的计数”感觉和上次碰到的那道题差不多,估计推一会能推出来。

否则:

第二题“树的计数”根本没看出性质?10分暴力都难写

T3

第三题“小Q的修炼”是提答题

比赛策略:

因为你思维能力有 5, T1 T2 都可以直接使劲做出来。

比赛策略为 写 T1 正解(写挂) - 写 T1 60 分暴力 - 对拍 T1 - 写 T2 正解(写挂) - 写 T2 10 分暴力 - 对拍 T2 - 比赛还剩一个小时,睡觉。

这里可以做 T3 获得个 60 多分,但不做也能进集训队。

最终得分 100+100+0=200。

9 - NOI 活动日

kenji: 明天就是Day2了,该好好复习吗?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期初考
  • 去社会实践
  • 找JCVB玩

这里如果去社会实践,会遇到 xudyh 让你打游戏,什么都不会学到。

如果去找 JCVB 玩,JCVB 会教你具体数学,让你思维能力在下一场比赛 +3,但还是通过不了 D2T3。

这里是唯一你可以学到 NOI D2T3 怎么做(?)的地方,因此要学习新算法。

kenji: 这道在环+外向树上DP的题目挺有趣的

10 - NOI Day 2

kenji: 马上要进考场了,好紧张啊

T1

第一题“矩阵游戏”大水题不说了

T2

如果你之前学习学到了 “这道码农DP的题目挺有趣的”,那么:

第二题“书法家”码农DP,上次写过应该能写出来

否则:

第二题“书法家”好像是码农DP,根本不会。20分可以通过观察性质推出来吧

T3

如果你之前学习学到了 “这这道在环+外向树上DP的题目挺有趣的”,那么:

第三题“快餐店”环加外向树上DP

否则:

第三题“快餐店”好像只会60分暴力?

比赛策略:

这里直接做 T1,然后做 T3(写挂),写 T3 暴力,对拍。

比赛还剩三个小时,直接睡觉。

你醒过来了,发现还没有考完

接着睡觉。

最终得分 100+0+100=200。总分 100+100+0+100+0+100=400,集训队分数线 358。

kenji: 进队了真开心

Stage 5: NOI 颁奖,签约,CTT - WC

1

szy: 你就是那个全场唯一一个A掉向量内积和快餐店的人吧orz

kenji: 跪跪跪跪跪跪跪跪跪跪跪跪跪跪

(szy 好感度 +1;目前 szy 好感度 1)

kenji: 马上要签了,好困啊要不睡会?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期初考
  • 睡觉

这里如果学习新算法会学会 CRT,但在你的 OI 生涯中完全没用。这里选择睡觉

如果上述操作没有问题,正确攒够了好感度,那么会触发以下剧情:

kenji: 好像听到了一点声音?

kenji: 我出去看看

szy: kenji啊你会打以撒吗?

kenji: 这种隔膜随便秒

szy: 我们一起来打吧(好感++)

(szy 好感度 +1;目前 szy 好感度 2)

2 - 签约

kenji: 我该签PKU还是THU呢?要不问问买菜否吧

这里 szy 的好感度攒够了,走的支线是:

szy: 买菜否很不靠谱的,他初中的时候就不靠谱,现在估计更不靠谱了。你还是直接问大牛哥吧。

kenji: 好

(这里如果 szy 的好感度没攒够的话,会触发以下支线)

如果买菜否的好感度 >= 4

买菜否: 我觉得你很有希望的,你还是慎重考虑一下,比如问问大牛哥什么的

kenji: 好

否则,如果买菜否的好感度 <= -4

买菜否: kenji同学每天游戏打打保送啦?好厉害啊

kenji: 买老师不理我我去问问大牛哥吧"

否则,即 -4 < 买菜否的好感度 < 4

买菜否: 我觉得THU太kenji了,周围的人都这么弱,PKU可能有更好的前途

kenji: 好吧去PKU吧(代码能力++,代码准确度++,思维能力++)

2.5 - THU

这里如果没签 PKU,会触发:

sy2006: 要不是THU当时太难考我怎么会去PKU呢?保送了当然去THU了!

kenji: 好吧去THU吧(代码能力+=2,代码准确度+=2,思维能力+=2)

(代码能力 +2,代码准确度 +2,思维能力 +2)

(此时代码能力 4,代码准确度 3,思维能力 7)

如果 sy2006 的好感度攒够了,会触发:

sy2006: 对了顺便宣传一下我的期末论文吧。你看看

kenji: 哦是关于图形识别的啊。不愧是压位帝+乱搞帝+人类智慧之神

sy2006: 。。。。。。

这一条分支非常重要,直接决定了你能否在 IOI 通过 Art Class

3

kenji: 这首歌挺好听的,我把它发到空间上去吧

kenji: 咦,有个叫memphis的人回复了我?

Ruchiose: 王仓那不是在贴吧炸鱼的小哥吗?快D他

  • 懒得管了
  • 这人好厉害,我要跟他聊聊

这里如果选第三个选项可以和 mephis 疯狂学数据结构(代码能力 +3),但是会凑不够 Ruchiose 的好感度。所以要选择

[图片]

Ruchiose: 爽爽爽爽(好感++)

4

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

这里如果学习新算法会学会左偏树,但是在你的 OI 生涯中完全没用。所以选择巡视机房

这里如果 cenbo 的好感度攒够了,会触发:

cenbo: kenji你对置换的了解怎么样啊?这篇关于置换的论文挺有趣的你看看吧

kenji: 好啊好啊(思维能力 +3)

(思维能力 +3)

(此时代码能力 4,代码准确度 3,思维能力 10)

否则:

cenbo: kenjikenjikenjikenji

5

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

这里如果学习新算法会学会二项堆,但是在你的 OI 生涯中完全没用。所以选择巡视机房

这里如果 zyh 的好感度攒够了,会触发:

zyh: kenji我们一起坐做TC吧。

kenji: 好啊好啊

(75 minutes later)

kenji: 在生牛哥的帮助下,我成功AK了拿到了RoomWinner!我感觉我的知识水平又提高了!(代码能力++,代码准确度++,思维能力++)

(代码能力 +1,代码准确度 +1,思维能力 +1)

(此时代码能力 5,代码准确度 4,思维能力 11)

否则:

zyh: kenjikenjikenjikenji

6

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

这里如果学习新算法会学会斐波那契堆,但是在你的 OI 生涯中完全没用。所以选择巡视机房

这里如果 fsygd 的好感度攒够了,会触发:

fsygd: 写暴力可以让你走得很远。比如说暴力hash偏分超级爽的。有些题目你看起来觉得不可做就不要做了暴力撸过去就A掉了,真实的故事。

kenji: 太神了orz

这条支线非常重要,必须触发才能够在第二年的 CTSC 暴力过题进国家队

如果好感度没攒够,会触发:

fsygd: kenjikenjikenjikenji

7

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

这里如果学习新算法会学会后缀平衡树,但是在你的 OI 生涯中完全没用。选择巡视机房或者复习期末考都可以。这里按照选择复习期末考来做。

如果选择巡视机房:

如果这里巡视机房,CTSC 前就需要多复习一次期末考,不然 IOI 的时候思维能力会不够

kenji: 约大爷为什么您这题的代码这么短?

这里如果 Ruchiose 好感度攒够了,会触发:

Ruchiose: 哦这道题时限很松我直接map+树状数组乱搞过去了

kenji: 原来还能这么搞,太神了orz

如果好感度没攒够,会触发:

Ruchiose: 我会缩代码我自豪

如果选择复习期末考,可以思维能力 +1。

(思维能力 +1)

(此时代码能力 5,代码准确度 4,思维能力 12)

8 - WC

这一年的选拔中 WC 和 CTSC 全部都是 OI 赛制,所有题目都需要对拍,而且一次对拍消耗 30 分钟,很容易爆。

WC 候选队分数线是 121 分,而 T1 即使对拍也一定会挂分,因此几乎没有容错。

kenji: 马上要进考场了,好紧张啊

T1

第一题“时空穿梭”数学题。10分显然,然后就不会了?

T2

如果再上一次和 Ruchiose 学会了乱搞:

第二题“紫荆花之恋”数据结构题。1~4直接秒。9~12搞个splay好像可以过。5~8好像可以用map+树状数组直接秒?

否则:

第二题“紫荆花之恋”数据结构题。1~4直接秒。5~12搞个splay好像可以过。\"}",

T3

第三题“非确定机”提答题

比赛策略

做 T1(挂成 0 分),写 T1 10 分暴力,对拍 T1(这样最终 70 分,此时比赛过去了 200 分钟),写 T2 的测试点 1~4,做 T3 做到 34 分,睡觉。

最终得分:70 + 20 + 34 = 124,分数线 123,卡线进队。

Stage 6: CTSC

1

kenji: 今天好无聊啊,去干什么呢?

  • 学习新算法
  • 写码农题
  • 做比赛
  • 复习期末考
  • 巡视机房

这里巡视机房会遇到 xudyh 让你打游戏,什么都学不到;学习新算法会学会 KM,仍然没用。因此选择写码农题

kenji: 代码能力+=2

(代码能力 +2)

(此时代码能力 7,代码准确度 4,思维能力 12)

写在 Qiuly IOI 夺冠的时刻

2024-03-01 17:04:42 By Qingyu

别急

写在戴江齐ioi夺冠的时刻

六月徂暑,晚夏绚丽。此刻的南京,因为酷暑而变得不同寻常。即使是从小在南京长大的我,也不曾有如此炎热的记忆。

号家军们的内心,似有盛夏的骄阳一般火热。伴随着蝉鸣,大家都坐在电脑面前,期待这个属于我们的盛夏的果实。 人生是美梦与热望。三年前,我们一起坐在电脑前看着杨骏昭在巴库ioi的表现。 我问初二的戴江齐“你想进ioi吗?” 他说:“想!” , “你就正常发挥。”师兄谭竣文在一遍鼓励着他。戴江齐自信地点点头。

戴江齐同学是2015年进入号家军学习,今年已经是整整第8个年头。从他进入号家军开始,他的天赋,刻苦和执着感染着每一个人。大家也都确信——他终有去ioi的那一天。每一天他都在刻苦学习,把自己天赋兑换成能力和才华。

2016年他进入noi班(号家军最高层次班型)和 杨骏昭,陈孙立等师兄们一起听课,一起讨论。即使题目百步九折萦岩峦,他也从不畏惧。在刚刚小学毕业的那年他就成为了codeforces红名,并在初中阶段成为了cf黑红。

梦里依稀有泪光。成功绝非易事,2021年12月的国家队选拔第一轮在深圳他摔断了脚。回南京后他在家中躺在床上和张隽恺,程思元进行训练,仍保持闻鸡起舞,日出而作。伤好之后,他们大年初二就开始进行训练。戴江齐最终凭借自己的努力如愿进入ioi国家队。今天他成为世界冠军。

清华北大的录取曾是竞赛生梦幻的神灯,似乎只要神灯点燃,就可以照亮一切的梦想。而对于戴江齐来说,算法设计是生命中最绚烂最宽阔的风景。当dp,计数的精灵在眼前跳动,他总是带着幸福的微笑。

我想成功一定是属于这样的人的。

天赋,努力和执着完美的结合,这就是戴江齐。

共 48 篇博客
  • 1
  • 2
  • 3
  • 4
  • 5