如何评价 NOI2018？

immortalCO · 2018-9-20 02:11:46

利益相关：D2T2 场外出题人。

这次终于出了一道有那么一点点思维难度而且暴力拿不了高分的题了！感觉这题的思路还是有一些妙的，不是那么平凡，而代码量却不大（短于 D1T1）。（看大家做不出来时看到题解后能心服口服的感觉真好。）希望今后的 OI 中能多一些思维题，少一些套路题和纯粹的知识点题。

总的来说，这次 NOI 的组题比去年好的很多，只是代码量偏大使得两天的划分不是非常合理、day2 思维和代码难度都过大。每道题也都有闪光之处和它的意义所在。

这场美妙比赛，无疑是出题人无私的馈赠。为命题组这一个月来的辛苦劳动点赞！

D2T2 题解：链接：https://pan.baidu.com/s/1YUJjFTpi1KYOoED55UxHBA 密码：w3tY

吴旋 · 2018-9-20 02:11:47

我看到rank 1的zzq是b类选手。。。这么多年了，福建省选还是这么的可笑

司公子 · 2018-9-20 02:11:48

结束了我高一的OI生涯

（被迫）完成了高一全Ag的记录

感觉大样例都很良心，D2T1都没写对拍

话说什么强行“本题是……，你可以利用这道题，为……，出题人相信，这个美妙的题目/样例，可以给……的你，提供一个有力的援助。” 是要开启毒瘤新画风吗？

是觉得“题出的好！覆盖知识点广，题目又着切合实际的背景，解法比较自然。” 被说过太多次了决定刷新一下以后毒瘤出题人的结束语吗

LN两位大佬因为spfa鸽掉了

yxd差一点可以去拿pku一本了，最后拿了60回去，但是这并不影响她考状元

我校其他两位同学一个有pku一本一个签了rua60感觉都很棒啊

（我似乎是唯一没学上的？）

感觉LN的希望gqh同学两天都非常凉，压线了一个Ag最后去了一直也没有招到人的fdu，丝毫没有体现真实水平

本来我以为我心态很炸发现别人心态炸得比我还厉害

想起来自己其实一直考得都不好，就是在LN里排名靠前而已

不管怎么样再来一轮死也不能扔题了

再也不能推个结论就以为自己能想出来

再也不能讨论出一种情况就以为自己能想出来

无数次的经验告诉我其实我根本想不出来

好好先把暴力写完不好吗

至少我从初三的LN拿牌分数倒数翻到第一了（有什么用啊喂= =）

感觉看着现状明年再<del> 当队长</del>选女生名额难度不大

（我怎么觉得我又插了一个flag）

年年送别人退役，明年送自己退役

真的当学姐辣qwq

罗哲正 · 2018-9-20 02:11:49

Update：

Day2考完了，我猜集训队分数线450左右。

update：集训队分数线出了，452，感觉自己厉害了

---------------分界线---------------

来了来了……

近年NOI没有vp所以不清楚考场上的真实难度，只能嘴巴bb几个解法。

总体评价：难度适中且适合NOI，区分度未知。比较符合我对NOI的预期，即没有特别难的神仙题也没有类似NOI2015D1T1那种noip都不考的签到裸题。

代码量过于集中于第三题（或者说总体偏小吧）

高分暴力分总和超过230但不到250，一般的暴力不超过200，理论上来说会有较好的区分度（或者说区分度主要依赖于难度梯度，因为部分分已经做了良好区分）

第一题考察可持久化并查集中在并查集的边上维护时间的做法（也可以直接建树然后用树上数据结构处理）。总之很送分，正常集训队应该在半个小时内做完一个小时内拍完。

第二题听说fix前缀找规律可以快速看出括号序列的对应和组合数，然后就不难写了，这题我场外没有打表找规律所以不知道实际难度如何。如果这个做法真的可行看起来也不是特别难。

第三题看起来是很typical的字符串数据结构题（有idea的那种），出题人好像是用了sam算法和代码都比较简单，比较考验对sam的理解。我这里说下我的做法：

首先建立出S的后缀数组并求出LCP，接着对于每个T我们分四步：

建立T的后缀数组，并求出LCP，令p_k表示从k开始的后缀在后缀数组中和后继的lcp。
对于T的每个后缀，在S的后缀数组中找出第一个字典序大于等于它的后缀，这里可以使用动态平衡树的思想按照字符从后往前加入，插入使用二分查找，那么在后缀k加入的时候，可以利用后缀k+1已经找到的位置来优化后缀k和任意S后缀的比较（先比较第一个字符，若相同则直接利用k+1的结果来比较后续）。
实现O(log|S|)判定T的一个子串T_[i,j]是否也是S的子串，这里我们考虑S的所有后缀中和T中i开始的后缀T_i的LCP至少为len=j-i+1的后缀，这些后缀在后缀数组中是一个区间，我们要求是判定其中是否存在起点在[l,r-len+1]的后缀，这可以用主席树按照起点位置从后往前添加，只要l号版本中区间中的最小值是否小于等于r-len+1即可。
考虑T的每个起点i，找到最大的j满足T_[i,j]也是S的子串，令q_i=j-i+1，则答案是\sum |T|-i+1-max(p_i, q_i)。考虑对于从小到大枚举i，j一定是递增的（因为T_[i, j]包含了T_[i+1,j]），所以twp pointers扫一下即可，时间复杂度O(|T|log|S|)。

如果想到这个做法的话，感觉考场上时间其实是够的，感觉正常国家队员不到一个小时能实现以上做法。

大胆猜测一下第一天集训队线200-220

wys · 2018-9-20 02:11:50

好难啊，老年选手表示只会做签到题啦……
第一题样例解释的 (5 + 0 - 1) mod 5 + 1 = 5 好评，听说有选手问“这不是4吗？”
Day2 T2 的暴力分比场上最高分多啊

（未完待续）

rsa · 2018-9-20 02:11:51

NOI2018 Day1

做题情况：

期望得分：100+100+68，T3只会2个log然后没写。

吐槽：

T2的冒泡排序伪代码是错的，还好我会冒泡排序。

T3题面写了两个样例然而只发了一个，同步赛选手表示测不了大样例，虚炸了。

T2数据还出锅了，有n=0的点，而且没有p[i]=i的点。据说明天会重测？

听说T3暴力乱搞能A？

评价：

题目难度比去年低一些，T1很简单，T2想一会儿也能做出来，T3送了68分。去年我前两题一共花了3h（T2还被卡了20分），T3只会40分，今年前两题只花了2h，T3也比去年容易拿分。

估计当天金牌线200左右，集训队线212左右。事实上近三年NOI Day1的分数线都差不多。

UPD：D1T3我想复杂的地方在于有个地方的二维数点只要判断有没有点而我用可持久化线段树来做，就2个log了。。。事实上可以按L从大到小处理询问，然后用普通线段树维护，在树上二分就行了。。。（本机接近4s，不知道官方机子能不能过）

NOI2018 Day2

做题情况：

期望得分：100+45+50，后两题只打了暴力，T2还有15分没调出来（UPD：我有个地方 i*2 和 i*2+1 打成 i 了）。

评价：

可能是近年来最难D2？除了T1依旧送分以外，剩下的两题，T2最高分45，T3最高分50，于是并没有人上200。

考场上看到T2意识到是猫题就开始对着部分分想，似乎部分分想完正解也不难了，可惜考场时间有限，连部分分都没调完更别提正解了。事实证明T2打部分分是最好的选择，听说国家队爷都去写正解了，结果因为各种原因挂了。

以及猫老师说好的不出最优化呢？

T3输出样例有10分？

估计当天金牌线和集训队线在150左右。因此今年NOI的金牌线和集训队线可能在450~462左右。

UPD：事实证明估得很准。

zzq 575分rk1，orz。福州三中连续两年B类捧杯。

感觉今年是rk1成绩和集训队线相差最小的一届NOI？

出同步赛成绩了，443，不知道哪里挂了20。

LOJ上测和预计得分一致。已发邮件反馈此问题。

UPD：回去改D2T2的时候发现我的程序有个可以卡成15分的致命漏洞，我是一边输入一边计算点的带权深度，只有全是0权或者b[i]刚好是拓扑序的时候才是对的，关键是我暴力也写成这个了。。。结果样例和数据都能过。。。真是感谢猫老师的不杀之恩了。

UPD：D1T1也有个能卡掉25分的漏洞。感觉数据强点我连前10都没了。

Galaxies · 2018-9-20 02:11:52

我只知道上次我奶ysy稳了ysy就捧杯了

去年我奶zzq今年稳了zzq今年就捧杯了

明年要奶谁呢……

如何评价NOI2017闫书弈取得第一名？

upd：我决定明年zzq ioi Au稳了

upd2：挂张照片就跑

Ciel · 2018-9-20 02:11:53

先挂CCF

住宿：条件还行都是下铺，独立卫浴，但是说好的牙具没有给；插座没有电，手机信号极弱，一层楼共用一个空调遥控器，淋浴只有热水快烫死了，还有半夜停电的神奇操作哦。

伙食：总体来说好评，辣的菜还是偏多，提早去排队有寿司吃。

开闭幕式：各种滥用照片未经同意涉嫌违法；口号养苟；灯光调音太菜；“太热了，不讲了。”

竞赛：D1题面反复出锅，T3 大样例还忘了发；D2好像还行；洗手间严重供不应求，排队甚至超过五分钟；键盘退格回车和|\键的位置有毒，无数次把\n打成回车n，或者退格的时候\\\。

社会活动：正值长沙高温天，已经有数位学生中暑的情况下，主办方强硬通知所有人必须去韶山活动，甚至以参赛资格相胁，难道病假也要取消资格？这是不是在践踏人权？学生中暑影响后续参赛谁来负责？某位老师在群内长期消失不回答问题，倒是欺压学生的时候积极得紧，我****。虽然后来在学生和家长的抗议下改为自愿参加，这仍是这次 NOI 的最大败笔。

其他：今年纪念品没有背包改成纸袋了，两件衣服 NOI 元素太少且质量一般；胸牌还要中途换带子；7:3O和NO1；清华宣讲全程扯淡；签约有部分高校出现占住学生最后不要的缺德事。