Qingyu的博客

博客

Tags
None

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,计数的精灵在眼前跳动,他总是带着幸福的微笑。

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

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

OI 赛制比赛 emergency kit(2024 Winter Edition)

2024-02-28 14:20:38 By Qingyu

Useful Commands

Set memory limit: ulimit -v "${memory}"

务必使用题目规定的空间限制进行测试。该命令执行后 shell 内的程序一旦超出此内存限制便会被杀死。(教训:NOI 2022)

不要在同一个 shell 窗口内多次使用 ulimit -v。(事实上,可以多次使用 ulimit -v 来让新的空间限制变得更小,但变得更大会发生错误。)(教训:花花 in 2023 年广东省重点中学信息学邀请赛 (GDKOI 2023) 提高组 第一试)

Set stack limit: ulimit -s "${stack_size}"

不要设置为 unlimited,防止由于栈空间溢出导致系统崩溃。(教训:有很多。)

测量时间:time ./a < a.in

获取详细信息:/usr/bin/time -v ./a < a.in

Locate Overflows/Undefined Behaviors

使用 fsanitize:

  • g++ a.cpp -o a -fsanitize=address -O2
  • g++ a.cpp -o a -fsanitize=undefined -O2

推荐在任意时候都是用 fsanitize 编译你的程序测试样例,即使其返回了正确的输出。(教训:花花 in 1116 NOIP 模拟赛)

务必记得最终使用不含任何 fsanitize 选项的编译命令测试程序,以防止由于开启 fsanitize 造成的行为不一致。(教训:陈翰飞 in NOI 2021)

开启 fsanitize 后程序效率将会有所损失,在测速时请注意这一点。

Overflows of STL Containers

使用 -D_GLIBCXX_DEBUG 编译选项可以开启 STL 的 debug mode。

在这种模式下,会进行一些 STL 相关的检查,用于帮助定位 bug。

credits to 核仁 在 NOI2022 告诉我。

Other useful compilation flags

使用 -g-O0。credits to 日语酱。

使用 -Wall, -Wextra-Wshadow

The week before the contest

不要学习新的算法。

不要修改你平日养成的习惯(码风?编辑器?)

可以考虑编写一些模板(https://qoj.ac/contest/1536 )。几个 Common 的问题:

  1. 几个 tarjan 算法,会写吗(@alpha)
  2. 会树 Hash 吗(NOI 2022 P4)
  3. 会写 Z-Algorithm 和 manacher 吗?一遍写的对 SAM 吗?
  4. 会写 Pollard-Rho 吗?

可以考虑去回顾以前做过的题,或者随机看点课件。

应该去调整你的作息,考前一周你不应该在 00:00 后还不睡觉,不要在 01:00 后还不睡觉。失眠和焦虑是正常的现象,但你仍然应该去调整你的作息。

可以去和你想要说话的人聊天、说话,可以去想你喜欢的人,可以做一些你想要做的事情,但不要让你的心情过于激动。

不应该去在这个时间点思考比赛失利会怎样,不要在比赛前自暴自弃。

The Night before the contest

如果存在,你应该参加试机活动。不要错过任何可以适应考场设备的机会。

不要在这一天食用你不经常食用的食品。

应该尽早入眠,但如果你失眠,不要过于焦虑。一晚上的失眠通常不会显著影响你第二天上午的精力,just relax。

Contest Strategy?

Warning!:(2024 Feb 29 更新)由于帮助大家训练的时间比较短,我暂时不了解大家比赛时的策略。以下策略是我基于花花(黄洛天;Luotian Huang;https://oier.baoshuo.dev/oier/59311 )在参加统一省选 2023 与 NOI 2023 制定的策略。由于每个人的比赛策略与个人便好有所不同,因此本章节仅供参考。如果我所描述的建议与你日常训练与以往比赛的习惯不同,请不要显著修改你习以为常的比赛策略。大多数人类无法在很短的时间内适应一个新的赛时策略,请注意这一点。

  1. 必须阅读所有的题目。
  2. 应该在除极特殊的情况(NOI 2022 P3)外为每个题编写代码。
  3. 应该在每个题上投入不小于 20 分钟的思考时间,包括各档部分分。
  4. 应该在编写你认为会消耗你超过 30 分钟时间的代码前整理你的做法,并花费一定的时间验证正确性。
  5. 不应该在有其他事情可做时编写你认为会消耗你超过 90 分钟时间的代码。
  6. 不要编写你认为会消耗你超过 150 分钟时间的代码。
  7. 不应该在任何一道题目上花费超过 150 分钟,不要在任何一道题目上花费超过 210 分钟。
  8. 不要在比赛结束前 15 分钟内编写任何新的代码。
  9. 不要在比赛结束前 5 分钟内修改任何代码。
  10. 必须在距离比赛结束 15 分钟时,首先备份你的代码,然后检查所有题目子文件夹的名称,使用题面规定的编译选项编译测试所有代码,并测试所有的附加样例文件。
    • 如果你会编写 Shell 脚本,你可以编写一个简单的脚本来复制样例为题目规定的输入文件名,并使用你的程序的输出文件与 answer 做比较。
    • 2023.07 更新:有 self eval?省选有吗?
  11. 必须使用上述命令检查你的代码,必须进行空间限制的检查。
  12. 不应该在比赛时编写你从未编写过的算法。
  13. 不要在比赛时编写任何你没有信心能够完成的算法。不要依赖于奇迹发生。
  14. 如果你发现你编写某份代码所消耗的时间超过了你所预期的时间,你应该重新评估并考虑是否仍可继续完成。

Others

  1. 在第一场比赛考完后,你不要去打探其他人的结果。如果比赛在当日需要处理申诉,在公示后检查自己当日的提交文件。否则,不要思考任何第一场比赛的结果(NOI 2022)。
  2. 应该做好做不出当天比赛的第二道试题(NOI 2022)、甚至第一道试题(ZJOI 2022 Day 2)的心理准备。
  3. 应该做好你需要拿到当天比赛几乎满分的心理准备(NOI 2014,NOI 2015,NOI 2021)。
  4. 在有充足的时间时,你不应该放弃任何可以获得的部分分,哪怕它只有很少的分数(NOI 2022)。
  5. 在比赛前,你不应该思考其他人,包括你所认识或熟悉的选手的发挥,不要揣摩 XXX 能不能过这个题,不要揣摩做不出这道题目该怎么办。考场不是给你写回忆录的地方,请尊重你在漫长的训练中换来参加考试的机会。

暂别

2023-08-21 22:16:56 By Qingyu

一年接一年,又到了 UOJ 管理员的换届时刻!

我们这一届管理员(127, csy2005, ix35, qingyu)在过去的一年中举办了两场 UR,一场 UER,以及年度活动 Goodbye Round 与 UNR。多亏了 vfk vfleaking 与前管理 djq_cpp, he_____he, hehezhouskip2004 为我们提供的指导与帮助,以及这一年来为 UOJ 分享自己有趣的题目的 Alex_Wei, huahua, JohnVictor, Kubic, MelaniaSooke。在无数的命题、造题、传题与修锅的过程中,是这个大家庭对 UOJ 共同的热爱,指引着我们又走过了一年。

在我是刚学 OI 的小朋友时,我便与 UOJ 第一次邂逅。当时的自己对 UOJ 的感觉仅仅停留在「这个地方好厉害,这些题我怎么一个都不会!」。后来在偶然间,我读到了 vfk 所写的博客(csdn / uoj),并被其文字中的热情深深打动。随着我渐渐长大,一代一代的管理员用自己纯粹的热情传递着 UOJ 的精神,让 UOJ 成为一代一代选手的乐园。

在 NOI 2022 结束后,戴老师与 hhz 找到了我,问我有没有兴趣来当 UOJ 管理员。出于对这个伟大 OJ 的热爱,我毅然决定接下了这个大锅。在这一年的管理工作中,我们经历了各种跌宕起伏的时刻。还记得在 Goodbye Renyin 前,我与花花一起对着 C 题的若干份错误代码卡了一整个通宵,最终在 Polygon 上留下了 57 份 revisions 与 9 份不同的 generator;还记得在 UR #24 前,我们与 Sooke 一起针对这道趣题改编了若干不同的版本,并最终将我们最满意的版本放了出来;还记得许许多多为我们投题的同学,愿意将自己脑海中有趣的 idea 贡献出来,让大家一起享受其中的乐趣。最数我难忘的便是在每次比赛后,hos_lyric 老师都会告诉我自己比赛的心路历程以及对题目的评价,即使有着语言的隔阂,也无法阻挡大家对算法竞赛的热爱……这些历历在目的情景,也让我第一次深刻体会到了强子、钱哥、邓老师,以及无数 UOJ 的前辈在写下自己的暂别时对这些回忆的感情。

在这一年的工作中,我们也暴露出了许多问题。管理员们对题目往往有着强烈的个人喜好,这导致了在诸如 UOJ NOI Round #7 Day1 中大家对选题风格的不满;我们对题目准备的时间预留仍有不足,过去一年时有出现在比赛前一晚还在准备题目编写题面的事故;在如今 UOJ 比赛中大量使用的捆绑测试,也被大家认为是一种坏文明。在这一场 UNR 中的 Day 1 成为了 UOJ 历史上第一场被点到了差评的比赛,这让所有的出题人与管理员感到了深深的自责。我们在赛后邀请选手们填写了一份调查问卷,大家对此提出了很多一针见血的建议,例如部分分的梯度不足;使用捆绑测试让大家在无反馈的比赛中容易丢失大量的分数;一些「结论题」与当今 NOI 的题风有些格格不入…… 我们将所有的这些真诚的建议都看在了眼里,我们希望 UOJ 能够变得更好,大家能在 UOJ 享受到更多算法竞赛的乐趣。

又是一年的八月,我们这一届管理员的任期也要结束了。我们相信下一届管理员能够比我们做的更好,将 UOJ 的这份精神继续发扬光大,建设这一算法竞赛的圣地。在接下来的一年中担任 UOJ 的管理员的四位分别是:

1kri, huahua, JohnVictor, zhoukangyang

祝你们四位一切顺利,祝 UOJ 有更光明的未来!

非官方省队互测 Online Judge is running

2023-06-06 17:21:53 By Qingyu

whqsing。

QOJ 常见问题(Q&A)

2023-03-23 22:14:28 By Qingyu

什么是 QOJ?QOJ 由谁在维护?

QOJ 是由我(Qingyu)搭建、开发并维护的在线评测系统(Online Judge)。QOJ 希望整理、分类并维护世界各地的算法竞赛题目、比赛信息与排行榜等数据,并为所有人提供题目练习或模拟训练的平台。

QOJ 的系统、题目与比赛的维护工作均主要由我进行。同时几位其他管理员会辅助参与 QOJ 的管理工作,他们分别是 alpha1022, memset0Qiuly。感谢他们愿意抽出宝贵的时间来参与到 QOJ 的管理工作当中。

QOJ 基于开源项目 Universal OJUniversal OJ 社区版 进行二次开发,没有 vfk 与开源社区的劳动成果 QOJ 将不会存在,在此感谢整个 UOJ 开源社区对 UOJ 的开发与维护。

同时,感谢 AutumnKite, hehezhou, hydd, p_b_p_b, Qglin_ 为本站的设计提供了宝贵的建议。

注册后如何上传头像?

请使用 Gravatar。当然,你也可以直接在用户信息中修改头像,但是使用 Gravatar 仍然是我们最推荐的方式。

我忘记了我的密码,有没有方法找回?

请使用找回密码功能。

QOJ 是否允许修改用户名?

不允许。但是你可以向管理员申请修改昵称

QOJ 的编译器信息是什么?

  • Python2: Python 2.7.18
    • Python 会先编译为优化过的字节码.pyo文件。
  • Python3: Python 3.12.1
    • Python 会先编译为优化过的字节码.pyo文件。
  • C/C++: GCC 13.1.0
    • 编译命令为 g++ code.cpp -o code -lm -Ofast -DONLINE_JUDGE
    • 选择对应语言版本时会增加 -std=c++??
  • Java 8/Java 11: openjdk version "11.0.16"
    • 编译命令为 javac code.java
  • Pascal: fpc 3.0.4+dfsg-23
    • 编译命令为 fpc code.pas -O2
  • Rust: rustc 1.70.0
    • 编译命令为 rustc -o code -C opt-level=3 code.rs
  • D: DMD64 D Compiler v2.106.0
    • 编译命令为 dmd code -O -release -inline -boundscheck=off

QOJ 的评测机 CPU 是什么?

Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz

题目的时间限制与空间限制在哪里?

在题目标题的上方。

题目的附加文件在哪里下载?

在题目正文上方标签栏处。

是否对栈空间进行额外限制?

除非题目特殊声明,否则栈大小限制与该题的空间限制相等。

QOJ 的特殊题目标签含义是什么?

  • Interactive:这是一道交互题。选手可能会使用 I/O 或其他方式与交互库进行交互。
  • Output Only:这是一道提交答案题。选手不需要提交代码文件,只需要上传答案文件。
  • Communication:这是一道通信题。选手可能需要提交多个程序,或同一个程序会被运行多次。
  • Unavailable:题目不可用。可能是我们没有对应题目的数据或辅助测评程序,也可能是我们的硬件资源无法满足题目测评要求(例如在 100 个线程中并行评测的题目)。

Hack 功能是什么?

在 QOJ 中,所有拥有 validator 与 standard 的题目均支持 Hack。对于任意通过的提交记录,如果你发现其无法通过某一组测试数据,则你可以使用 Hack 功能尝试 Hack 此提交记录。如果你的 Hack 成功,该组数据将会被添加进入 extra test 并重测所有提交记录。

我不想公开我的提交记录,有没有什么方法?

你可以在个人信息 - 修改个人信息中选择 "不公开个人代码"。

QOJ 是否支持虚拟参赛(Virtual Participation)?

目前 OI/IOI/ICPC 赛制的比赛均支持 VP。在点击开始按钮后,即可开始虚拟参赛。

QOJ 的 IOI 赛制有没有注意事项?

请注意,QOJ 的 IOI 赛制(包括 VP)中,每道题目的得分为所有提交记录的最高得分,而非所有子任务的最高得分之和。在未来我们会支持取所有子任务的最高得分之和作为题目得分,但现在仍不可用。

QOJ 的 ICPC 赛制有没有注意事项?

QOJ 的 ICPC 赛制将在最后一小时进行封榜,最后一小时其他队伍提交的结果将在比赛完成后可见。

QOJ 的测评环境与 Universal Cup 第一个赛季中所使用的 DOMjudge 是否相同?

并不相同。二者的评测机运行在两台独立的服务器上。

自第二个赛季开始,Universal Cup 的比赛在 QOJ 上运行。在赛时你的代码所使用的评测环境与 QOJ 完全相同。

在什么情况下,我参加比赛会被计算 Rating?

请注意:与 UOJ 不同,在 QOJ 中,只有满足以下情形才会被计入 Rating。

  1. 你是对应比赛的正式选手,被移入非正式选手(用户名前带有星号)或 VP 参加的选手不会被计入 Rating。
  2. 你满足对应比赛的计分要求:
    • (OI 赛制):你提交了至少一份代码,且得到了非零的分数。
    • (IOI 赛制):你提交了至少一份代码,且得到了非零的分数。
    • (ICPC 赛制):你提交了至少一份代码,通过了对应题目的样例数据。

我在 Universal Cup 中注册了队伍,能否使用 Universal Cup 的用户信息登录 QOJ?

可以。你也可以使用 Universal Cup 的注册中获得的用户信息来登录 QOJ 并正常使用其他功能,但是无法接收与发送私信。

我在 Public Judge 中注册了账号,能否使用 pjudge 的用户信息登录 QOJ?

可以。

我在 Universal Online Judge 中注册了账号,能否使用 UOJ 的用户信息登录 QOJ?

不可以。QOJ 基于 UOJ 二次开发,但二者的实例无任何关系。

我在使用 QOJ 的过程中出现了问题,能不能联系你们?

你可以通过以下方式联系到我们:

  1. 站内私信 Qingyu
  2. 发送邮件至 [email protected]

我在使用 Universal Cup 的过程中出现了问题,能不能联系你们?

请联系 Universal Cup 组委会。

我在使用 Public Judge 的过程中出现了问题,能不能联系你们?

请联系 Public Judge 组委会。

我在使用 Universal Online Judge 的过程中出现了问题,能不能联系你们?

请联系 UOJ 管理员。

Public CTS Round #1 题解

2023-01-07 10:16:08 By Qingyu
  • 组题人:Qingyu
  • 搬题人:
    • 黑白点:flower, Qingyu
    • 博弈:Qingyu
    • 地雷:flower, p_b_p_b
    • 桥桥桥:Qingyu
    • 游戏:Qingyu
    • 知识:alpha1022, Qingyu
  • 题解:flower, Qingyu, LeafSeek, alpha1022

黑白点

Source:

特别感谢 Xmas Contest 的举办者 hos_lyric 与本题的作者 maroonrk 允许我们使用本题并提供了测试数据。

算法1

枚举选手选点,状压dp即可。

时间复杂度$O(2^n n^3)$,可以通过$subtask 1$,期望得分$6$。

算法2

考虑枚举先手的选点 $rt$,考虑第 $1$ 次只能染黑一个点的操作是第 $i$ 次。 那么有机会染的点是 $dis(rt, u) \le i$ 的点 $u$。如果令 $cnt_i$ 表示距离 $rt$ 小于等于 $i$ 的点(不包括 $rt$)的数量。如果有 $2i - cnt_i \ge 1$,那么一定满足这个选这个点的时候只能选他一个点。

如果最后只剩一个白点,也显然只能选一个点。

更具体的说,考虑最少的选 $1$ 的次数。那么答案至少为 $\displaystyle \left\lfloor\frac{n+\max_{i=0}^{maxd}2i-cnt_i}{2}\right\rfloor$,其中 $maxd$ 为距离的最大值。

接下来是一个构造,可以达到上界: 先拎出来最短路树,变成树上的情况。如果一个边两个端点都为黑点,我们认为他的边权是 $0$,否则是 $1$。 每次找到 距离 $rt$ 最远的点 $u$,把 $rt$ 到 $u$ 路径上的第一个白点染黑,除此之外如果还可以染,选择距离 $rt$ 最远且不在 $u$ 所在的白点导出子图的连通块里的点 $v$,将 $rt$ 到 $v$ 的路径第一个白点染黑。

可以证明每次上述式子会减少 $1$,方法是考虑 $cnt_i \ge 2$ 的时候,这个位置一定不会成为 $\max$,所以没有被的选的白连通块虽然 $dis$ 没有减少 $1$,但是除了$dis$为全局最大值(因为满足距离 $rt$ 最远的点的太多了),其他点与其 $dis$ 相同的点至少有 $2$ 个,因此不会不会成为 $\max$。而没有被选的全局最大值,如果前面至少有一个 $cnt_i\ge 3$,那么也不会成为最大值,否则对应了最后只剩一个点的情况。

时间复杂度 $O(nm)$,可以通过 $subtask 1, 2$,期望得分:$16$。

算法3

考虑加速刚刚的过程。把刚刚的构造方法对应成,把 $rt$ 到距离 $rt$ 最远的点 $x$ 路径上除了 $rt$ 的每个点,和不在路径上的点匹配,要求每个点能和他的匹配的必须不在他的子树里。

这样在路径上没有匹配的点就是 必须一次只能染黑一个的点。

因为 $x$ 只可能是树直径端点之一,令其为 $p, q$。因此我们考虑对于所有的 $i$ 计算以 $i$ 为跟是如果距离最远点是 $p/q$ 的答案,取 $\max$ 即可。

不妨只考虑 $p$,把树变成以 $p$ 为根的有根树。令 $f_u$ 表示最少使用 $1$ 的数量(不考虑$u$子树内点),$size_u$ 表示 $u$ 子树大小。

计算答案需要把子树内的点考虑进去,这些点可以根 $u$ 到 $p$ 上任意一点匹配,因此有 $ans = \max(f_u - size_u - 1, 0)$。

转移也是同理,每次把在 $fa_u$ 子树里,不在 $u$子树里的点加入,这些点可以与除了$fa_u$ 和 $u$ 的所有点匹配。

因此做两边 树形dp 即可,时间复杂度$O(n)$,可以通过 $subtask 3$,期望得分:$18$。

算法4

与算法3类似,考虑如何特殊处理环的问题。因为需要把最短路树拎出来,所以需要在环上断边。

先把环拎出来后,$p$ 对应在环上的点设为 $x$,那么可能被断掉的是 $x$ 在环上连的两个边。预处理出前缀和后缀的size之和,直接转移即可。

时间复杂度 $O(n)$,可以通过 $subtask 3, 4$,期望得分:$31$。

算法5

算法4带来的启发是,每次经过一个环长为 $len$ 的环,至少会带来 $\left\lceil\frac{len}{2}\right\rceil -1$ 的点可以用来和当前所有路径上的点匹配,而路径长度最多增加 $\left\lfloor\frac{len}{2}\right\rfloor$。这里我们认为的情况是环上初始有一个黑点,而取到上述式子的情况就是只有一个环不挂其他点的情况。注意到这两个式子之差最多为 1。

考虑由环组成的一个点双,也满足两者之差最多为1。假设要从点双的 $x$ 走到 $y$, 于是可以不需要考虑 $x,y$ 最短路上除了 $y$ 的节点有没有匹配(一定有匹配)。而判断 $y$ 能不能匹配上等价于,以及能匹配多少 $y$ 之后的点。设这个点双里 $x,y$ 最短路径长度为 $w$,点数为 $s$,那么能匹配 $s - 1 - 2w$ 个点,上式为 $-1$表示 无法匹配 $y$。 同样的这里认为 $x$ 已经是黑点了。

因此考虑建立圆方树,将 $p$ 设为根。与上文唯一的不同是,这个点双里的点,可以连向其他没用的点双(向兄弟子树里连)。 注意到转移需要查询的最短路长度 $x, y$ 满足 $x$ 为圆方树上,方点的父亲节点,$y$ 为方点的儿子节点。因此是单源最短路的形式,可以把每个点双挖出来之后 bfs。

我们令 $p', q'$ 为圆方树上,将边权视为 $1$ 的直径。算法5中提到过,每个点双最多会使染色一个点的次数加$1$。那么考虑 $u$ 到 $p$ 和 $p'$ 的最短路树上 $lca$ 以后的部分。因为 $p$ 到 $lca$ 距离(也就是最多有多少点没匹配)小于等于 $lca$ 到 $p'$ 的点数,因此可以把这些点匹配过去,是足够的,所以 $lca$ 之后不会产生任何贡献。

时间复杂度 $O(n)$,可以通过所有数据,期望得分 $100$。

博弈

Source: Кубок трёх четвертьфиналов 2019. Subregional 1. Moscow.

注意到,对于给定的 $(x, T)$,若先手希望 $x$ 最终尽可能大,而后手希望 $x$ 最终尽可能小,则一轮后 $T$ 变为 $T - 2\varepsilon$,$x$ 变为 $x + \varepsilon$。最终,$x$ 将会停在 $x + \frac{T}{2}$。

我们首先考虑二分答案,这样问题就变为了,$[0, n]$ 被划分成了若干段,有一些段 Min 获胜,有一些段 Max 获胜,问最后会停在哪一段。注意到对于 Max 而言,如果有一段的长度大于了 $A$,我们直接停在这一段中 Max 便直接取胜。否则,每一段在 $x-T$ 坐标系上构成了一块三角形区域,每个三角形是某一方的必胜区域。

现在,考虑最靠下的一个三角形区域,由于其不交 $y = A$,因此在这一部分区域内的胜负态可以合并为一块大的区域,如果某策略试图停留在这段区域,则另一方总可以将其移动到边界处,因此,此处形如 ABA 的胜负区域可被等效替代为一胜负态为 A 的三角形区域,故我们可以直接合并这整个区域为一个大的等腰三角形。我们可以使用 std::set 来维护所有的三角形并维护胜负态。

时间复杂度为 $O(n \log n \log \epsilon^{-1})$。

地雷

本题加强自 Potyczki Algorytmiczne 2022, Runda 4 的 Miny [A]。

算法1

预处理出每个点能到达的点,每次 bitset 优化 bfs 即可。

时间复杂度 $O(\frac{n^3}{w}+n^2)$,可以通过 $subtask 1$,期望得分$9$。

算法2

建出点分树,每个点能到达的点是距离重心 $rt$ 的一个前缀,前缀和优化即可获得 $n$ 个点 $O(n \log n)$ 的图。

缩强连通后,用 bitset 优化即可。

时间复杂度 $O(\frac{n^2\log n}{w} + n^2)$,可以通过 $subtask 1, 2$,期望得分 $14$。

算法3

我们希望点分治后,能求出来每个跨过 $rt$ 的点对 $(u,v)$ 求出 $u$ 能不能炸到 $v$。

但问题是,有可能存在 $u$ 先炸到当前点分树子树外,获得了了一个巨大的半径,再炸回来炸到了 $v$。于是有可能出现点分树上只考虑 $lca(u, v)$ 的子树(下文子树均指代点分树上子树),无法从 $u$ 炸到 $v$,但是考虑 $lca(u, v)$ 的某些祖先的子树能炸过去的情况。

因此我们接下来有两个思路:

  1. 我们在 $rt$ 处理爆炸路径经过 $rt$ 的点对 $(u, v)$,这意味着 $(u, v)$ 可能在 $rt$ 为根的同一子树。
  2. 我们仍然在 $rt$ 处计算所有跨过$rt$ 的 $(u, v)$ 能不能到达,但是为此我们需要预处理处一些连通块外的信息。

对于第一种思路,这种想法意味着一个点对会被统计多次,最直观的想法是用 bitset 去重即可。

令 $f(rt, x)$ 表示从 $x$ 开始炸只考虑 $rt$ 子树内只炸到 $rt$,能给 $rt$ 炸到多少半径(就是炸到 $rt$ 之后半径的余量,也就是 $\max r_u - dis(u, rt)$,$x$能炸到 $u$),如果无法找到 $rt$ 为 $-1$,也就是说要么 $f(rt,x)=-1$,要么 $f(rt, x) \ge r_{rt}$。

令 $g(rt, x)$ 表示从 $rt$ 开始炸,只能在 $rt$ 子树里,初始至少有多少的半径能炸到 $x$。

如果 $u$ 能走到 $v$,那么有 $f(rt, x) \ge g(rt, y)$。

从下往上考虑点分树。求 $g(rt, x)$ 的方法是逐渐增大 $rt$ 的初始半径,考虑哪些点直接被 $rt$ 一下炸死。对于每个被一下炸死的点$x$,需要考虑他怎么炸别人。也就是说找到 $v$ 使得 $dis(u, v) \le r_u$。可以通过点分树的方法做到,就是对于每个重心 $rt$,求出每个点到他的距离的 dis,rank 并且按照 dis排序,可以在 $O(n\log^2 n)$ 的时间复杂度内做到。

求 $f(rt, x)$ 即 $\max r_u - dis(u, rt)$。因为是取 max,所以不担心重复计算,也就是可以考虑出,对于 $u$ 的每个 点分树上祖先$rt'$,$u$ 经过 $rt'$ 能到达的点 $v$ ,这些 $v$ 能炸到 $rt$ 的余量。因此只需要 对 $f, g$ 双指针时,维护 $g$ 的当前前缀,对$rt$ 在点分树上每个祖先的贡献。

考虑到 bitset 的 or 操作,每次只有 $rt$ 点分树大小的点可能是1,因此 bitset 下标变成 点分树的dfn序 之后是一个区间里可能会有1。手写 bitset ,每个点可以做到时间复杂度 $O(\frac{n}{w}+\frac{n}{2w}+\frac{n}{4w} \cdots)$。

如果 $w=1$,可以直接使用的bitset的count,时间复杂度 $O(\frac{n^2}{w})$,否则为 $O(n^2)$。可以通过 $subtask 3, 4$,期望得分 $31$。

算法4

对于第二种思路,我们需要修改定义为:

令 $f(rt, x)$ 表示从 $x$ 开设炸,可以炸到任意点,能给 $rt$ 炸到多少半径。

令 $g(rt, x)$ 表示从 $rt$ 开始炸,可以炸到任意点,初始至少有多少的半径能炸到 $x$。

我们在点分树上从上向下做,假设对于 $rt$ 的所有祖先,$f(rt, x), g(rt, x)$ 都已经求出。

对于$f(rt, x)$ 我们需要枚举从点分树$rt$子树外炸回来时,是从哪个点分树的祖先的炸出去的,假设为 $rt'$。那么已知 $f(rt', x)$,如果存在一个点 $y$ 满足 $g(rt', y) \le f(rt', x)$ 那么从 $x$ 炸出去能回到 $y$,$y$ 对$f(rt, x)$的贡献为 $r_y - dis(y, rt)$。也就是说处理出 $g$ 的一个前缀对 $rt$ 贡献的 max 即可。因为刚刚的情况是经过了 $y$ 中转的,注意特判从外面一步炸回 $rt$ 的情况。

对于$g(rt, x)$ 几乎类似,同样枚举是从哪个点分树祖先炸出去的,假设为 $rt'$。那么如果有 $f(rt',y) \ge g(rt', x)$,那么 $y$ 对 $rt$ 的贡献为 $dis(rt, y)$,同样双指针一遍即可。一样要特判从 $rt$ 一步炸到外面的情况。

对于全局的重心的 $f, g$,可以通过用 算法3 的方法处理出来。

需要精细实现,否则会多 $\log$。因为枚举 $rt, rt'$ 之后 如果双指针之前不能多 sort。我的处理方法是将点分树按层处理,每个点的点分树子树,被当前层的儿子们划分了。所以需要每个点预先排序好,每层的时候处理一下划分。

时间复杂度 $O(n\log^2 n)$,可以通过所有数据,期望得分 $100$。

桥桥桥

注意以下判定图联通性的方法:

  • 取出 $G$ 的任意一棵生成树 $T$
  • 对于所有非树边 $e$,随机一个 $[0, 2^{64})$ 内的权值 $w(e)$
  • 对于所有树边 $e$,定义其权值 $w(e)$ 为所有覆盖它的非树边的权值的异或和。

则我们可认为,删去 $E' \subseteq E$ 后图不联通等价于 $E'$ 存在子集 $F \subseteq E'$ 满足 $F$ 的边权异或和为 $0$。

首先,我们考虑所有删除一条边后图已经不联通的方案,这可以通过求出所有的桥边来得到。我们预先处理出这些边的方案,这一部分是容易的。接下来,我们假设不会选择这些边。

注意到,当我们假设一条边不能被选时,我们总是可以认为这条边一定在最终的图中,因此我们在这一步后,将图中所有桥边对应的两端点缩为同一个点,在这一步操作后,整张图将变为一张边双连通图。

其次,我们考虑,如果一个顶点 $x$ 的度数为 $2$(上述操作后,图中必定不会存在 $0$ 度点与 $1$ 度点),那么我们删去 $x$ 相连的两条边以及任意一条其他边,图一定变得不联通。我们同样算出这样的贡献并预先处理,随后我们便可以删去顶点 $x$。

在上述操作后,图变成了一张边双连通,且每个点度数 $\ge 3$ 的图。

此时,我们求出新图的一棵 DFS 树 $T'$,并考虑应用上述方法。注意到我们选择的三条边有以下四种情况:

  • 选择了 $0$ 条树边,$3$ 条非树边。
  • 选择了 $1$ 条树边,$2$ 条非树边。
  • 选择了 $2$ 条树边,$1$ 条非树边。
  • 选择了 $3$ 条树边,$0$ 条非树边。

首先,我们特判掉所有选择两条边后图一定不联通的方案,将这些方案特判掉。这是非常容易的,只需要找到所有 hash 值相等的边。

对于第一种情况,这样的方案一定不合法,因为 $T'$ 一定足以使得图联通。

对于第二种情况,我们枚举删去的树边,此时一定包含了至多两条跨过它的非树边,这样的情况是平凡的。

对于第三种情况,我们枚举删去的非树边,注意到特判掉所有两条边即合法的方案后,选择的两条树边必定呈祖先-后代关系,且选择的非树边为 $e_1, e_2$ 跨过边的差中唯一的边,这种情形仍然容易处理。例如,我们可以自底向上用并查集维护所有可行的链,并check每个对应的 $e_A$ 是否合法。

cts-2a.png

对于第四种情况,由于我们不会选择树边,因此我们可以缩掉所有的非树边,并在缩完非树边的图上接着做。由于图中每个点的度数至少为 $3$,因此 $|E| \geq \frac{3}{2} |V|$,故被缩掉的边数至少为 $|E| - |V| + 1 \ge \frac{1}{2}|V|$。在缩完边后,我们重新执行上述算法即可。由于缩边只会被缩 $O(\log m)$ 轮,因此总的时间复杂度可以保证。

游戏

Source:

算法一

首先,题意等价于可以删除任意长度大于 $1$ 的同色连续段。因此考虑将原串划分为极长同色连续段后,长为 $1$ 的记作 1,长度大于 $1$ 的记作 2,则原串转化为一个 12 串。

考虑操作对 12 串可能的影响,一次操作只可能影响到某个 2 对应的连续段:

  1. 如果不删空连续段,则这次操作可能会让这个 2 变为 12
  2. 否则连续段被删空,如果 2 处于开头或结尾,则 2 消失。
  3. 否则 2 处于中间,2 会被删除且前后的元素会被合并,即 ?2? 会被转化为 2

不难发现,2 优于 1,因而 1 操作不考虑。而 3 操作可以放到所有 2 操作结束后做。因此题意等价于给你一个 12 串,可以将 ?2? 转化为 2,问串能不能转化为全 2。进一步的,串能不能转化为 $1$ 或 $2$ 个 2,取决于初始串长。

由于任意时刻,串中的每个字符都对应了原串中某个长为奇数的区间。若 12 串的长为偶数,则考虑最后剩下两个 2 对应的区间,这个串可以被删空等价于可以将串划为两个长为奇数的部分,两个部分分别可以被删空。

因此我们只需考虑串长为 $2k+1$ 的情况,一个简单的情况是第 $k+1$ 位为 2,此时只需将两边不断删除即可。若第 $k+1$ 位不是 2,一个直观的想法是找到左右最近的两个 2,然后删除中间部分同时调整两侧长度,将问题转化为 $k+1$ 位为 2 的情况,例如 11211211111 首先调整为 1122111,然后变为 11211,即简单的情况。可以发现按照这个思路,原串可以被合并至 2 等价于两侧最近的 2 中间不包含超过 $k$ 个 1。而对于包含超过 $k$ 个 1 的情况,由于一次操作最多消除一个 1,且头尾一定会剩下 2,序列会转化为 21(...1)2,显然无解。

对于奇数情况的判断是简单的,对于偶数情况寻找划分点也可以做到线性,因此总复杂度为 $O(n)$。

算法二

by LeafSeek

称能被删空的串合法,否则不合法。关键结论:串 $S\texttt{AA}T$ 合法当且仅当 $ST$ 合法或 $S\texttt{A}T$ 合法。

首先证明如果 $S\texttt{A}T$ 合法,那么 $S\texttt{AA}T$ 一定合法。考虑消除中间 $\texttt{A}$ 的那一步,如果删了 $2$ 个就改成 $3$ 个,删了 $3$ 个就改成 $4$ 个(分两步各删 $2$ 个)。实际上容易说明连续任意 $\geq2$ 个相同字符均可被消除。

然后证明如果 $S\texttt{AA}T$ 合法,那么要么 $ST$ 合法,要么 $S\texttt{A}T$ 合法。首先注意到中间的两个 $\texttt{A}$ 一定是一起被消的。如果是分别被消的,和这两个 $\texttt{A}$ 相匹配的两边各还要有至少 $1$ 个 $\texttt{A}$,一共是 $\geq2$ 个,可以让这 $\geq2$ 个自己消除,将中间的两个 $\texttt{A}$ 调整成一步删 $2$ 个的操作。考虑它们一起被消的那一步,如果是删了 $2$ 个的情况可归入 $ST$,删了 $3$ 个的情况则可归入 $S\texttt{A}T$。

考虑这么一个过程:对于一个串 $S$,每次找到 $S$ 中最靠前的 $\texttt{AA}$ 或 $\texttt{BB}$,你需要决定将 $\texttt{AA}$ 变成空还是变成 $\texttt{A}$。那么 $S$ 能删空当且仅当存在一种决定方式,使得最后得到空串。

不妨设原串 $=S\texttt{A}$,考虑任一种合法的决定方式(不一定要最后删空),一定是先决定 $S$ 里面的东西,之后再决定最后一个 $\texttt{A}$。决定完 $S$ 里面的东西剩下的结果一定是 $\texttt{AB}$ 交替的,根据其首尾分别是 $\texttt{A}$ 还是 $\texttt{B}$ 可以分为 $4$ 类。

所以可以动态规划,我们用首尾和长度表示一个 $\texttt{AB}$ 交替的串。考虑转移,每次加入一个字符,维护当前串可以被删成的 $\texttt{AB}$ 交替串的集合。比如说 $\texttt{ABABA}$,加入 $\texttt{A}$ 之后可以变成 $\texttt{ABAB}$ 或者 $\texttt{ABABA}$ 中的一种;又比如 $\texttt{ABAB}$,加入 $\texttt{A}$ 之后只能变成 $\texttt{ABABA}$。必须特殊考虑空串,空串不属于 $4$ 类中的任何一类。直接维护这个集合即可做到 $\mathcal{O}(\dfrac{n^2}w)$。

接下来是未经证明的猜测:串 $S$ 能删成的结果,在确定了首尾之后,其可行长度的取值范围一定是一段区间。这里区间指的是 $[L,R]$ 内所有奇偶性与 $L$ 相同的整数。比赛的时候对拍观察动态规划中集合的模样可以做出上述猜测。于是只需维护能否删空、$4$ 个区间存不存在以及其左右端点,容易做到 $\mathcal{O}(n)$。

还原方案也可以做到 $\mathcal{O}(n)$:先回溯转移的过程,维护一个栈,确定每个字符是新弹入栈中还是与栈顶消除。对每个字符,开一个 $\texttt{vector}$ 保存它作为栈顶负责消除的字符的下标,包括 $\texttt{A(A)}$ 变 $\texttt{A}$ 和 $\texttt{BA(A)}$ 变 $\texttt{B}$ 两种情况。可以看出每个 $\texttt{vector}$ 的大小都 $\geq2$。最后直接 $\text{Dfs}$ 即可还原出方案。

知识

Source:

特别感谢 Xmas Contest 的举办者 hos_lyric 与本题的作者 maroonrk 允许我们使用本题并提供了测试数据。

先来考虑对于给定的一个点数为 $N$ 的有向图 $G$ 如何计算其各个点为根的外向生成树权值和。

定义 Laplacian 矩阵

$$ L_{ij} = \begin{cases} \sum_{(k,i) \in E} w_{ki}, & i=j \\ -w_{ij}, & (i,j) \in E \\ 0, & \text{otherwise} \end{cases} $$

根据 Matrix-Tree 定理,以 $u$ 为根的外向生成树权值和即为 $L_{uu}$ 处的主余子式。 也就是说,我们需要计算 $L$ 的伴随矩阵 $L^*$ 的对角线。

注意到 Laplacian 矩阵并不满秩,因此其伴随矩阵的秩不超过 $1$。因此,存在列向量 $x,y$ 使得其伴随矩阵 $L^* = xy^{\mathsf T}$。

而注意到 $L$ 所有行向量之和为全 $0$ 向量,从而可以证明其同一列的所有代数余子式相等,因此 $L^*$ 的各列向量相等,$y$ 可以取全 $1$ 向量。

那么,我们只需要算出 $x$ 即可获得对角线上的值。

而根据 $AA^* = |A| I$,可知 $L x y^{\mathsf T} = 0$,也就是 $L x=0$。据此,我们可以解出一个非平凡的 $x$,但其与真正的 $x$ 相差常数倍。

幸运的是,这是容易处理的。我们只需要取一个非 $0$ 的位置计算出对应的余子式即可。

而题意中给出的就是两张图的 Cartesian 积。不妨记作 $G = G_1 \mathop\square G_2$。
为了刻画其 Laplacian 矩阵,我们引入 Kronecker 积

$$ A \otimes B = \begin{bmatrix} a_{11} B & a_{12} B & \cdots & a_{1m} B \\ a_{21} B & a_{22} B & \cdots & a_{2m} B \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} B & a_{n2} B & \cdots & a_{nm} B \end{bmatrix} $$

其中 $A$ 是 $n\times m$ 矩阵。

令 $L^{(1)},L^{(2)}$ 分别为 $G_1, G_2$ 的 Laplacian 矩阵,易得 $G_1 \mathop\square G_2$ 的 Laplacian 矩阵为 $L = L^{(1)} \otimes I_N + I_M \otimes L^{(2)}$。

接下来,我们注意到,若我们对 $L^{(1)}, L^{(2)}$ 求出了各自的 $x^{(1)}, x^{(2)}$,则有 $L (x^{(1)} \otimes x^{(2)})=0$。因此我们也只需要定出相差的系数即可。

我们考虑通过其和,也就是伴随矩阵的迹来定出这个系数。

设 $L^{(1)}, L^{(2)}$ 有特征值 $\lambda_1, \lambda_2, \dots, \lambda_M$ 和 $\mu_1, \mu_2, \dots, \mu_N$,则 $x^{(1)}, x^{(2)}$ 的和即为 $L^{(1)}, L^{(2)}$ 的特征多项式的 $1$ 次项系数乘 $(-1)^{M-1}$ 和 $(-1)^{N-1}$。

注意到 $L^{(1)}, L^{(2)}$ 必有 $0$ 这个特征值,不妨设 $\lambda_1 = \mu_1 = 0$,则这个值就是 $\lambda_2 \lambda_3 \cdots \lambda_M$ 和 $\mu_2 \mu_3 \cdots \mu_N$。

因此 $x^{(1)} \otimes x^{(2)}$ 的和即为 $\lambda_2 \lambda_3 \cdots \lambda_M \mu_2 \mu_3 \cdots \mu_N$。

而可以证明,$L$ 的特征值为 $\lambda_i + \mu_j$ $(i=1,2,\dots,M, j=1,2,\dots,N)$(证明见 [1])。因此,相差的系数即为 $$ \prod_{i=2}^M \prod_{j=2}^N (\lambda_i + \mu_j) $$

而我们知道特征值是特征多项式的根,因此我们借助 Resultant,可以得到这个乘积的值为 $\operatorname{res}\left(\frac{|tI-L^{(1)}|}t, \frac{|tI+L^{(2)}|}t\right)$。

而对于 Resultant 的计算,由于这部分并非瓶颈,可以直接 $O((N+M)^3)$ 计算行列式。

事实上,根据 wiki 上的结论,我们可以用多项式 Euclid 实现其求算。暴力实现就是 $O(NM)$ 的。 然而 wiki 上的结论疑似有误,其算法具体实现可以参考 std。

[1] 潘佳奇,浅谈线性代数与图论的关系,IOI 2021 中国国家集训队论文

QOJ 更新日志(2024 Jan)

2023-01-06 20:27:29 By Qingyu

01/16/2024

  1. 更新 GCC 版本为 GCC 13.1.0
  2. 更新 Python 3 版本为 Python 3.12.1

12/25/2023

  1. 添加对 D 的支持,采用的编译器版本为 DMD64 D Compiler v2.106.0,编译选项为 -O -release -inline -boundscheck=off

09/29/2023

  1. 添加对 Rust 的支持,采用的编译器版本为 rustc 1.70.1,编译选项为 rustc -o answer -C opt-level=3 answer.code
  2. 将提交记录的代码高亮库更换为 highlight.js

09/11/2023

  1. 主站的评测机数更改为 5 台。每台评测机的 CPU 均为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz。其中评测机 #1 的内存为 32 GiB,其余两台评测机的内存为 16 GiB。
  2. 修改了沙盒中的部分实现。由于此前编写的 judger 有部分不兼容新的沙盒,因此目前所有使用了自定义 judger 的题目均被暂时隐藏。他们将在确认兼容性后重新公开。

08/28/2023

  1. 增加了对可任意选择 Time Window 开始时间赛制的支持。
  2. 增加了对包含多个固定的 Time Window 的赛制的支持。
  3. 增加比赛管理员可以为某个用户单独延长比赛时间的特性。
  4. 比赛管理员现在可以取消用户的报名。
  5. 修复了在 Time Window 结束后的提交仍然会被算入比赛提交的 bug。
  6. 不再禁止用户选择开始时间比当前时间更早的 Time Window。
  7. 比赛结束后的提交现在也可以在比赛提交记录中查看。

08/22/2023

  1. 主站的评测机数更改为 3 台。每台评测机的 CPU 均为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz。其中评测机 #1 的内存为 32 GiB,其余两台评测机的内存为 16 GiB。

08/10/2023

  1. QOJ 开始记录评测记录的历史信息!

08/04/2023

  1. 在注册 Virtual Contests 时会弹出确认列表。
  2. 修复了在 VP 时可以查看题目统计信息的 bug。
  3. 修复了在 IOI 赛制的 VP 时可以查看测试点详细信息的 bug。

06/14/2023

评测机所使用的 CPU 由 Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz 更换为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz

04/27/2023

  1. 在 VP 时 Attachments 会默认隐藏题解。
  2. 在 VP 时禁止查看比赛中其他人的提交记录。

03/21/2023

Category 增加显示每个子类别比赛与题目数。

03/19/2023

进行了一些微小的更新。

03/04/2023

  1. 对应比赛的管理员可设置在比赛进行时排行榜的显示范围(是否显示正式选手/Virtual 选手,以及每类 Ghosts 的范围)
  2. 对应比赛的管理员可导出比赛的 Standings 文件(.dat / TestSys 格式)
  3. 在导入 Polygon 格式的题目时,使用标准校验器的题目将默认配置 use_builtin_checker,而不再使用独立的 checker
  4. 检验数据正确性不再要求配置 Main Correct Solution。

02/25/2023

  1. 修复了无开始时间的比赛 VP 后不会滚榜的 bug。
  2. 修复了 Category 对比赛排序时产生的问题。

02/18/2023

进行了一些微小的更新。

02/13/2023

进行了一些微小的更新。

02/03/2023

  1. ICPC 赛制现支持设定封榜。
  2. 修复了部分通信题出现 Dangerous Syscalls 的问题

01/09/2023

更新编译器信息如下:

  • Python2: Python 2.7.18
  • Python3: Python 3.10.9
  • C/C99/C11/C++/C++98/C++11/C++14/C++17/C++20/C++23: GCC 11.1.0
  • Java 8/Java 11: openjdk version "11.0.16"
  • Pascal: fpc 3.0.4+dfsg-23

Public CTS Round #1 公告

2023-01-02 23:12:06 By Qingyu

万能的 p_b_p_b 说:要有 CTS Round,于是 pjudge 有了 CTS Round。

大家 2023 年新年快乐!作为 pjudge 在 2023 年复活后的第一场比赛,Public CTS Round #1 将在 2023 年 1 月 7 日与 1 月 8 日 8:30 举行!

比赛将分为两日进行,每场比赛时间为当日上午 08:30 至 13:30,共 5 小时。每场比赛均为 IOI 赛制,且包含三道题目。

本次比赛的题目难度可参考 CTS 2022。 比赛的组题人为 p_b_p_bQingyu,搬题人为 alpha1022, flower, hehezhou, p_b_p_b, Qingyu

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

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