UOJ Logo

NOI.AC

NOIP 2018 全国热身赛正在进行……

2018-10-19 16:17:58 By root

10月20日-11月4日

NOIP 2018 全国热身赛

将在 $ noi.ac$ 继续开战

热身赛第1场:10月20日8:30-12:00

热身赛第2场:10月21日8:30-12:00

热身赛第3场:10月27日8:30-12:00

热身赛第4场:10月28日8:30-12:00

热身赛第5场:11月03日8:30-12:00

热身赛第6场:11月04日8:30-12:00

NOIP 2018 全国热身赛出题人

IOI 2018中国队长杨懋龙

NOI/NOIP 命题人于纪平

江苏省队集训教练毕克

清华算协副主席李诗懿

清华姚班2016级王蕴韵

清华姚班2017级沈睿

本轮热身赛共六场

采用管理员邀请制

一律不接受个人报名

除$NOIP 2018冲刺营$选手外

现面向全国信息学教练(仅限)

免费开放部分参赛名额

我们诚挚欢迎并特别邀请

全国OI资源不均衡地区

教练和选手积极参与

让我们和 noi.ac 一起

为每一位有梦想的选手

提供更充足的训练资源

创造更丰富的交流机会

【NOIP 2018 全国热身赛】接受邀请办法

教练进《noi.ac教练群》:425345622

关于 NOIP2018 全国模拟赛第三场成绩的通知

2018-09-16 08:42:51 By root

第三场成绩现在公布

第三场比赛不计算排名和rating

成绩查看

点此查看

比赛公告、答疑、交流、题解,请加入 noi.ac 选手群:103017249

2018-09-11 13:19:24 By root

欢迎加入 noi.ac 选手交流群:103017249

本群仅用于比赛答疑、发布题解和标程、选手交流。

本群谢绝家长加入!

NOIP 2018 19场模拟赛、训练赛、热身赛9月8日开战!

2018-09-02 16:39:26 By root

NOIP 2018 19场模拟赛、训练赛、热身赛日程安排:

选手交流群:103017249(在群里发布题解)

第一场:09月08日8:30-12:00:NOIP模拟赛(免费、公开)

第二场:09月09日8:30-12:00:NOIP模拟赛(免费、公开)

第三场:09月15日8:30-12:00:NOIP模拟赛(免费、公开)

第四场:09月16日8:30-12:00:NOIP模拟赛(免费、公开)

第五场:09月22日8:30-12:00:NOIP模拟赛(免费、公开)

第六场:09月23日8:30-12:00:NOIP模拟赛(免费、公开)

第七场:10月01日8:30-12:00:NOIP训练赛(内部、封闭)

第八场:10月02日8:30-12:00:NOIP训练赛(内部、封闭)

第九场:10月03日8:30-12:00:NOIP训练赛(内部、封闭)

第十场:10月04日8:30-12:00:NOIP训练赛(内部、封闭)

第十一场:10月05日8:30-12:00:NOIP训练赛(内部、封闭)

第十二场:10月06日8:30-12:00:NOIP训练赛(内部、封闭)

第十三场:10月07日8:30-12:00:NOIP训练赛(内部、封闭)

第十四场:10月20日8:30-12:00:NOIP热身赛(内部、封闭)

第十五场:10月21日8:30-12:00:NOIP热身赛(内部、封闭)

第十六场:10月27日8:30-12:00:NOIP热身赛(内部、封闭)

第十七场:10月28日8:30-12:00:NOIP热身赛(内部、封闭)

第十八场:11月03日8:30-12:00:NOIP热身赛(内部、封闭)

第十九场:11月04日8:30-12:00:NOIP热身赛(内部、封闭)

NOIP 2018 19场模拟赛、训练赛、热身赛出题人:

一、NOI 2018冲刺营金牌教练

罗哲正

NOIP2013、2014、2015一等奖

NOI2014银牌、NOI2015金牌、NOI2016金牌

IOI2016国家预备队、IOI2017美国国家队

IOI2017金牌,全球第三名

吴瑾昭

NOIP2015、2016、2017一等奖

NOI2015网络赛铜奖、NOI2016银牌、NOI2017金牌

IOI2018 国家预备队,第十名

武弘勋

NOIP2014、2015、2016、2017一等奖

NOI2015铜牌、NOI2016银牌、NOI2017金牌

IOI2018 国家集训队,第五名,清华姚班2018级

二、清华大学姚班三届大神

王蕴韵

NOIP2013、2014、2015一等奖

NOI2015银牌 最佳女选手、清华姚班2016级

CCPC2017女生专场金牌,第二名

沈睿

NOIP2013、2014、2015一等奖

NOI2015银牌、NOI2016金牌

IOI2017国家预备队、清华姚班2017级

杨懋龙

NOIP2013、2014、2015、2016、2017一等奖

NOI2016银牌、NOI2017金牌

IOI2018第2名、国家队队长,清华姚班2018级

三、竞赛命题人、算协负责人

毕克

NOI2012金牌、IOI2013国家集训队

ICPC2015EC-FINAL金奖、NOI2016命题人

WC2017主讲人、2017、18江苏省队集训教练

于纪平

NOI2014金牌、IOI2015国家集训队

CCSP2017金奖、ICPC2017 EC-FINAL金奖

CCF优秀大学生、NOIP2016、NOI2017命题人

李诗懿

NOI2014金牌,最佳女选手

IOI2015国家集训队、ICPC2015金奖

清华大学计算机系学生算法与竞赛协会副主席

四、IOI 2019国家集训队队员

戴同学

NOIP2017提高组一等奖

NOI2018金牌,第5名

IOI2019国家集训队

杨同学

NOIP2016、2017提高组一等奖

NOI2018金牌,第12名

IOI2019国家集训队

杜同学

NOIP2015、2016、2017提高组一等奖

NOI2018金牌,第32名

IOI2019国家集训队

赵同学

NOIP2016、2017提高组一等奖

NOI2018金牌,第40名

IOI2019国家集训队

NOI2018 全国热身赛 榜单

2018-06-25 00:30:44 By root

请以下选手发送个人信息(地址、电话、姓名)给管理员,以便发放京东E卡和快递纪念T裇。

排名——用户名——总分——A——B——C

1——cz_xuyixuan——300——100——100——100

2——tqyaaaaang——245——100——100——45

2——diamond_duke——245——100——100——45

4——Sparrow——210——100——100——10

5——rainy_season——205——100——60——45

6——hanxiao——200——100——100——?

6——lovelyboy——200——100——100——0

6——starkmal——200——100——100——?

9——magolor——195——100——50——45

10——zyding——190——80——100——10

10——Hermenaut——190——80——100——10

12——nnezhb——180——100——80——?

13——zjczzzjczjczzzjc——160——100——50——10

13——yuanchengbo——160——100——50——10

15——liji——155——45——100——10

15——OBlack——155——10——100——45

17——lichangdongtw——145——0——100——45

17——Icefox——145——80——20——45

17——xht13127——145——100——0——45

20——lumingqi——140——100——40——?

20——Renatus——140——70——70——?

22——subowen——120——100——20——?

23——Zsnuo——115——15——100——?

24——VanishD——110——0——100——10

24——Blue233333——110——0——100——10

24——cz_helehan——110——?——100——10

27——ORZ_SC——100——?——100——?

27——jiaowotaidixiong——100——100——?——?

27——frustrated——100——100——?——?

27——Parity——100——0——100——?

31——igronemyk——80——60——10——10

31——windows xp——80——?——80——?

31——wangbenyu——80——45——0——35

34——visjiao——75——45——20——10

35——thc——40——30——10——?

35——hujianzheng——40——10——20——10

37——imalyd——30——0——20——10

37——lzq_——30——10——10——10

39——lhy——20——10——10——0

39——fansenran——20——0——20——0

41——mjx——10——0——10——?

NOI2018 全国热身赛 题解

2018-06-24 13:48:14 By root

小w、小j和小z

首先一个简单的事实是,两个人相撞当且仅当他们开始时的相对位置和结束时相对位置发生了交换。

假设现在我们有一个时间 $T$,我们要怎么保留尽可能多的人,使得所有人不发生相撞呢?

如果用 $(s,t)$ 来表示每个人初始和结尾的位置,这就等价于选出最多的人,使得 $s_1 > s_2$ 的时候有 $t_1 > t_2$,如果按照 $s$ 排序,容易看出,这其实就是一个最长上升序列。

既然现在我们已经会判断对于一个时间 $T$,最小的 $K$ 是多少了,我们只需要二分答案,就可以轻松地解决这个问题了。

小h的树

首先,我们先考虑一个较为简单的情况,即 $k=n$ 时的情形。

我们容易发现 $k=n$ 时,其实就是选择一个点作为起点,每次向相邻的点移动,遍历所有点的最小代价。

我们发现除了起点到终点那条链上的边只走了一次外,其他的边都经过了两次。

那么答案显然就是 $2\sum v_e-$ 最长链的长度。

我们考虑更一般化的情况。

我们相当于要寻找一个大小为 $k$ 的点集,然后最小化 $2\times$ 这 $k$ 个点虚树的总边长-这 $k$ 个点直径的长度。

首先易得这 $k$ 个点一定是一个联通子树。

因为我们只是要求最小值,我们可以直接枚举这个虚树的直径是哪一条,然后树上背包扩展出不在直径上的点。

这样暴力的做是 $O(n^4)$ 的,稍加优化就能做到 $O(n^3)$。

我们接下来考虑一个更优的解法。

令 $g[x][k]$ 表示 $x$ 的子树内选择了 $k$ 个点,并且这 $k$ 个点包含了 $x$,构成的虚树总边长的最小值。

$f_0[x][k]$ 表示 $x$ 的子树内选择了 $k$ 个点,并且这 $k$ 个点的直径有一端是 $x$,构成的虚树总边长的最小值 $\times 2-$ 直径的长度的最小值。

$f_1[x][k]$ 表示 $x$ 的子树内选择了 $k$ 个点,并且这 $k$ 个点的直径两端都不是 $x$,构成的虚树总边长的最小值 $\times 2-$ 直径的长度的最小值。

转移则直接按照定义转移即可。

这样的复杂度为 $\sum_i \sum_{j,fa(i)=fa(j)} size(i)\times size(j)$。

注意到任意两个点只会在他们的 lca 处贡献一次代价,所以总复杂度为 $O(n^2)$。

小x的城池

By C_SUNSHINE

我们采用线段树直接维护整个序列,每个节点代表一个区间,并在节点上记录:

区间内的答案:在区间内已经找到了更高的 B 的 A 的数目 $ans$

区间内有多少向左的道路和向右的道路 $d_0, d_1$

区间内能够到达左端点/右端点的人口为 $k(0 \leq k \leq 75)$ 的还未找到更高的 B 的 A 的数目 $HL_k, HR_k$

若存在则记录同时到达左右端点的还未找到更高的 B 的 A 城市的编号 $pos$ (最多有一个)

区间被整体取反时以上所有信息

接着考虑如何维护,其实只要考虑合并就可以了:

由于我们需要计算的只是能找到更高的 B 的 A 城市的数目,除了在两个孩子中的答案,只要考虑其中一个孩子中的 A 能在另一个孩子中找到更高的 B 的数目,而具体情况需要考虑中间的边的方向。

这里只考虑从左到右的方向,反之是对称的做法:

在线段树上查询出从右孩子左端点开始能到的最远位置,并统计出这段中人口数最大的B。

检查左孩子的 $HR$ 和 $pos$,更新答案。

若右孩子能从左端点直接走到右端点,用未找到更高的 $B$ 的 $HR$ 和 $pos$ 中的节点更新当前节点的 $HR$ 和 $pos$。

而对于翻转操作,我们只需要打标记就可以了,由于区间和区间被flip的信息是同时维护的,打标记和标记合并复杂度是 $O(1)$的。

注意更新的同时也要更新被反转的区间的信息。且更新的同时也需要用到查询。

时间复杂度 $O((n + Q \log n)(R + \log n))$,其中 $R=75$.

6月24日,NOI 2018全国热身赛即将开战!

2018-06-22 17:41:51 By root

比赛时间:6月24日(周日)上午8:30-13:30

比赛形式:在线,OI赛制

比赛等级:NOI+

比赛网址:NOI.AC

比赛奖品:京东E卡、纪念T裇等

适合对象:NOI 2018参赛选手、NOI 2019省选选手

支持机构:实验舱

加实验舱丹丹(QQ:2307343595),进选手交流群。

共 7 篇博客