【NOI 2019】同步赛 / 题解 / 感想

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

非常颓写不动题怎么办……

写下这篇博客警示自己吧……

游记

7.16

我并不在广二参加 NOI，而是在距离广二体育馆一公里远的包间打同步赛（其实就是给写不动题找个理由）

上午身体不舒服，鸽了半天才看题。

T1 题意这么长？懒得看啊，但还是硬着头皮看了

这……dp？$Ax^2+Bx+C$？这个式子怎么处理来着？斜率优化？会了

（其实我tm验证了一小时这个做法）

然后发现直接做的复杂度是 $O(nq)$ 的？

时间上倒没问题，可是开一个大小为 $1e8$ 的 $dp$ 数组和斜优数组，空间不就爆了？

当时想了一下，只需要考虑每趟列车的起点和终点状态，并且每个状态只需要被斜优更新一次，就得到最优答案了

可是我脑抽了以为代码不好写，于是没用 vector

直接码 $70$ 分斜优去了，降智

由于身体不舒服，码得比较慢，式子都写了半天

写写写，测了一发，然后瞎调了几分钟，测第一组样例……

输出 $94$？

这就过了？爽

然后第二组样例输出了 $31$

我就手算了一下第二组样例，发现手算的答案是 $(2^2+2\times 2+3)\times 2 + 9 = 31$ 啊

样例错了？我翻了一下公告栏，没说啊

于是我又读了一遍题，发现等 $0$ 秒也会加 $C$ 的烦躁值……

然后又脑抽瞎改了十几分钟，总算过了第二组样例

然后第三组和第四组样例跟着直接过了

第五组样例是 $1e5$ 大小的数据，我数组开不下，没测

T2 是什么玩意？数数？$3s$？那估计又是一堆大常数卷积跑跑跑，rqy 肯定已经切了

我不可能会的，准备最后再写这题

然后因为身体原因去养生了，0.5h 后才回来

T3 又是什么玩意？

冷静分析一下，感觉像贪心

思考了一下，有一种每次保证能多一对公共下标的贪心，于是试着写了一波

然后就写了 1.5h

写完就秒过了第一组样例……

然后测第二组样例，发现错了 $3$ 个左右的答案

然后发现需要记一个 $del$ 数组

改完还是错

然后发现还需要动态往堆里加数

这次改完后，只剩最后一个答案错了

你让我调 $n=7$ 的数据就算了，还让我调 $n=18$ 的数据啊，$a_i$ 和 $b_i$ 还是 $9$ 位数，当我按计算器不要时间的？

于是放弃了，转去写个暴力

然后因为写代码图省事，导致暴力调了 1h

心态爆炸，我当我复习如何 $dp$ 了

最后想到了 t2 的 dp，然而没时间写了，只好赶紧 rush 一发暴力，最后十秒钟交上去了

交上去后发现 check 函数有一行写错了……然而网站强制结束了比赛

分数 $-$ inf

算了，反正我是养生选手，不计较了

考后找 $zyf$ 等人聊天，发现 $zyf$ $t3$ 的 $64$ 分没调完，暴力也没调完，为他默哀

初三巨佬 $scb$ 打了 $70+35+28=133$，可以了

然后大众分大概 $100+35+28=163$ 左右吧？

您们是怎么把 t3 卡常卡到 $40$ 分的

后来突然意识到我的 T1 做法改成 $vector$ 写法后就是 $O(m\log{m})$ 的正解……可是我没(lan)去(de)写，我蔡爆了

T3 的网络流模型很裸……$64$ 分是优化网络流，$100$ 分时贪心模拟网络流……我说怎么觉得这题就是贪心，只不过肯定要支持撤销

出题人把 d1t1 的 $q$ 放得那么小，原来是为了放叉积判斜率大小的人过……没想到把 $O(mq)$ 的做法放过了……

这……出题人的智商……

7.18

有些烦躁，这天的情况就写短些

T1 是啥啊，无向图最短路？数据范围很 kdt 啊？

可是我不会 kdt 上跑最短路，凉了凉了

然而前 88 分是送的，两个暴力 subtask，一个一维线段树优化建图 dij，一个二维线段树优化建图 dij

此处省略一万字过程

T2 一开始看错题了，以为两个概率是分开算的，也就是一轮可以不拿任何一张牌……

然后发现这根本没法做，于是纠正了题意

花了几十分钟推了个 $30$ 分 dp，然后发现转移是固定的，数据范围也很合适，$40$ 分矩阵快速幂即可

您们咋天天让老年选手写这种 dp 啊，我头发快掉光了

T3 夭寿了，NOI 真出交互题了

我到现在都不会做 I 君的商店

题意还是比较好理解的

然后写了几页的交互题格式说明，一眼带过

然后看了下数据范围，不难发现前 20 分就是 $\frac{n^2}{2}$ 次的暴力

然后 A 的亮点就是保证每个点的度数恰好为 $1$，共 $\frac{n}{2}$ 条边

对于一个点，你可以二分它所在边的右端点在哪

然后把所有的点集体二分的话，不就是分治嘛

woc，这暴力分也太裸了，估计在现场赛没啥区分度

但还是硬着头皮写吧

B 有亮点么？没有？不会滚

考后发现 t1 就是 kdt+玄学卡常

好神仙，慢慢学吧

t2 出具体数学上的原题是几个意思，难怪不少人切了

t3 有人讨论么

大众分 $100+40+36=176$ ？不敢保证大家都是这个水平，但不到这个成绩好像就会被吊打

无脑猜测两天大众分 $163+176+100=439$

晚上出榜，哇 rqy rk4，哇 myh rk7，哇 zsy rk30，哇 lbt rk45，哇 hzk rk57，哇 oyyp rk138，哇 wjh rk232，哇 xgy rk264

这分差有点小啊，银牌后段的分数特别密集

时中 477 分卡线进集训队了恭喜他鸭

等会队线多少？477？？？

信竞好可怕啊

回想一下，我预估的大众分才 439 分？现在看来这顶多说是签到分……

我原本以为到了这个分就比较保险地有学上吧？

想多了，不存在的

实际情况是，如果您没到队线，您的所有前途都是未知数

详见后记

题解

回家路线

题意

有 $n$ 个点和 $m$ 趟列车，第 $i$ 辆列车于 $p_i$ 时刻从 $x_i$ 号点出发，于 $q_i$ 时刻到达 $y_i$ 号点。

有一只小猫要从 $1$ 号点坐车到 $n$ 号点，中途可能需要在某些站等待一段时间。每次 $t$ 个时刻的等待，都会使小猫的烦躁值加 $Ax^2+Bx+C$（$A,B,C$ 为给定的全局常数）。假设最后它在第 $z$ 个时刻到达终点，它的烦躁值会再加 $z$。

求小猫到达终点所需的最小烦躁值。

题解

为什么说我脑抽呢？

这题的 $O(mt)$ 做法是个裸 $dp$（空间上只需要开一个 $O(nt)$ 的 $dp$ 数组）。设 $f(i,j)$ 表示第 $j$ 秒小猫在 $i$ 号点时，最少需要积累的烦躁值。实际上只需要保留每趟列车出发和到站两个状态，其它的状态忽略掉就行了……所以转移时只会是

如果用斜优的话，就是给每个点动态建凸包。只保留每趟列车出发和到站两个状态，这样斜优状态总数不会超过 $n$，所以总转移次数不会超过 $n$，时间复杂度是 $O(m\log{n})$ 的。空间是 $O(m)$ 的……我之前没改所以是乱说的，不要在意

另外直接用一个单调指针扫每个凸包的最优点就行了，不用二分（当然我写的代码里加了二分的注释），如果一个凸包加入的新点取代了凸包后面的过多点，导致指针指的下标超过了凸包大小，就把这个指针设为凸包的最后一个点。这个原因很简单，不明白的可以思考一下。

细节请看这篇博客，他撞过的车我写的时候基本都撞过了（考虑一下在凸包上二分一个 $\le p$ 的区间是蠢到什么份上了）

O(mt) 代码

O(mlogm) 代码

（我没删调试，也没去掉 #define int long long，不要在意）

另外 $O(m\log{n})$ 的这份代码交到 loj 不知道为什么全 RE 了，求知道原因的人在评论区通知我，谢谢了！

upd：我tm通过若干发提交终于二分出了 RE 的根源……

简直出乎我所料，vector 的 size 函数返回的是 unsigned int，然后我是把它减 $1$ 再跟其它数比较的，然而当 size 为 $0$ 时，它减 $1$ 就变成了 $2^{32}-1$……然后导致比较大小出错，而这个比较大小的地方还是判断需不需要把 $vector$ 往后新开下标，一比较错就会使程序误认为后面的下标已经开了，于是直接给后面没开的下标赋值，直接 RE……

可我不知道为什么 luogu 能过啊？？？

问了一下 scb 大佬，他说他也遇到过 2 次这个问题，而且因为 stl 库不是你写的，这些问题你通常查不出来……最好的解决办法就是把所有能给你显示 warning 的编译命令都加上，如"-Wall -Wextra -Wconversion"。一定要重视程序的 warning，warning 里警告了你程序里所有不同类型之间做了运算的地方，这些运算一旦崩了，如果你不看 warning，很可能调到你怀疑人生（没错，这个 RE 问题已经调得我怀疑人生了）

机器人

题意

不想简述，或者说原文说的都有用……

题解

35pts

序列

题意

给你两个长度均为 $n$ 的正整数序列 $A$ 和 $B$，要求从两个序列中各选 $K$ 个下标，且至少有 $L$ 个下标在两个序列中都被选。

你需要最小化两个序列所有被选的下标对应的数的和。

题解

总结

1. 个人认为 d1t1 出的数据范围不好且评测数据太水，被简单爆搜乱过，错误爆搜都骗了一堆分，这题放应该考虑放到普及组

2. day1 的区分度不会就是信仰吧

3. ckw 被卡在 rk51（表上写的是 rk53，但好像跟 rk52 同分，且 rk3 的 zzq 应该会退队），没能进国集，签了北邮……为他默哀，我认为他有水平进前 50 的。

4. （有点长）

我通过交流得知，现在竞赛政策改革造成了很不好的影响。以前是清北保送前 50 名，差一点的还可以保降一本线。而如今，清北只保送前 50 名，第 51-100 是给面试机会，然后给口头一本约（就是不做保证）。这就是为什么很多人宁可签人大、北邮、上海交大的一本，也不要清北的口头一本。你可以当场录音，但他们依然可能会鸽掉，即便是纸面签约人家都能撕呢，更何况一句口述的一本（清北招生部：你这口音模仿得挺像啊，哪学的？）

举个撕约的例子，这次 SD 队有个同学在 thuwc2019 拿了二等约，然后清华承诺只要他进了省队就换成一等约。他进了省队了，然后这次 NOI 打铁了，导致清华收回了一等约，他直接没学上了……

在此我就是想告诫大家，学这个竞赛真的不容易。总有人觉得这个竞赛人少啊，知识简单啊，各大高校又重视这个竞赛的人才啊，就以为这是个通往清北等高校的捷径。我干脆直接说了，这门竞赛根本就不是捷径，走不好甚至是死路。别看大家都学得挺好，这里面有真学好和假学好之分；别看这个竞赛的招生比例挺高，自己看看周围的实际情况，十个信竞生里平均有九个是到了高三疯补文化课的。我也不敢说到底怎么学才是真学好，毕竟我也只是茫茫人海中的一粒尘埃。但我可以肯定的是，没有废寝忘食地切题的决心，或是有赛过大佬的学习方法，你不可能在这个竞赛出成绩。现在的事实是，只有进前 50 才能拿到清北的纸面约，进前 100 才能保送 211/985，Ag 才能拿 211/985 的一本约（我也不太确定，大概是这样吧），Cu 你就一无所获地滚回去高考了。而全国学得比你勤奋的 OIer 远远不止 50 个，也远远不止 100 个，如果你不甘心付出些什么，你还做什么白嫖清北签约的梦呢？

路遥知马力，日久见人心。希望 OIer 们心中有数，不要盲目于一时的欢乐。