NOIP2018 差点退役记

时间:2023-03-08 21:25:00

Day 1 不想说了,反正就是三个水题,直接来讲Day 2。

Day 2 一上来,T1做法写的丑了点,折腾了一会,大概50min的样子写完了。

T3一眼DDP……这玩意儿我就写过一个模板,还只写过一次。考场上直接来莽风险有点大,又看到这玩意儿部分分还挺多的?就先扔了。

然后就开了这个坑爹的T2。

T2第一眼以为是只要斜行单调就行了,但是仔细分析了一波,发现这样的话,\(3 \ 3\) 的样例就会是 \(2 \times 3 \times 4 \times 3 \times 2 = 144\) ,会错。

仔细想了想,这东西不仅是要斜行单调,有可能两条不同的路径到同一个点的时候,会跑出相同的字典序,然后后面的部分只要能够跑出不同的字典序,就会出问题。

稍微修了一下锅,条件变为

  1. 满足每一个斜行的数字从左下到右上是单调递减的。
  2. 如果对于某个数字,其左边的数和上面的数相同,那么以这个点为左上角,终点为右下角的这个矩形,每个斜行所填的数字强制相同。

直接基于这个东西,强上状压DP的话,复杂度是 \(2^mm^2n = 1.63 \times 10^{10}\) ,不太能跑,不过状态数相对较少,说不定可以试一试。不过这个东西两头的时候细节相当恶心,又只能拿到 \(80pts\) ,不大甘心。

想到这里的时候,T2大概开了 \(40min\) ,个人认为还是比较正常的。

后面的过程,就想得有点多了,整个思路也越来越不正常,最后时间不大够了,决定写暴力。如果只写裸暴力的话未免有点太亏了,想来想去写了个复杂度大概是 \(m^{n-m} m!^2 \times nm\) ……的暴力,大概就是暴力枚举每个斜行由 \(1\) 变为 \(0\) 的位置,然后再暴力 check 第二个条件是否合法。这玩意儿剪下枝的话,应该还是能跑个 \(8 \ 8\) 的。

然而……整场比赛我可能就败在这个地方了……

考场上枚举位置的时候,写了个我可能会后悔很久的错误……

inline void dfs(int cur,int tot) {
if(cur > tot) { Calc();return; }
For(i,1,min(cur,n + m - cur) + 1) P[cur] = i,dfs(cur + 1,tot),P[cur] = 0;
}

然而这个枚举的上界……我算错了……

inline void dfs(int cur,int tot) {
if(cur > tot) { Calc();return; }
For(i,1,min(min(cur,n + m - cur),n) + 1) P[cur] = i,dfs(cur + 1,tot),P[cur] = 0;
}

只要改一下就行了……

就是这个玩意儿……它能跑对所有 \(|n-m| \le 1\) 的数据。很不幸,所有样例都是 \(n=m\) 的。

后来拿着这个暴力程序找了 \(min(n,m) = 2\) 的规律,\(min(n,m) = 3\) 的时候发现找不出来了……

又拿这个程序,把 \(8 \ 8\) 以内跑得慢的点打了下表。自认为有 \(65pts\) ,就去 rush T3的暴力了。

T3暴力我直接写的 \(52pts\) 的,调了好一会,才调对。

考场一出来,FakeBeng说T2他找了 \(65pts\) 的规律,\(\min(n,m) = 3\) 也有规律,说什么一直乘 \(3\) 就行了。我当时觉得心头一凉……我还地记得我的程序 \(3 \ 5\) 跑出来是 \(1300\) 左右的一个数字,而他说他裸暴力跑出来是 \(1008\)。

中午吃饭的时候,完全没有心思。一直在想到底哪里有问题……后来猛然间发现,这个枚举上界似乎是有问题的,只有在 \(|n-m| \le 1\) 的时候才是对的。这样,因为所有的东西都是拿这个错误的暴力跑的,自己的 \(65pts\) 就变成了 \(rand(15,35)pts\) 了。

我回头仔细想了想,其实如果这个暴力我只要写对了,所有规律我肯定是能轻松找出来的……我的暴力都能跑 \(8 \ 8\) 了,乘 \(3\) 的规律不可能看不出来。

晚上的时候在知乎上看到了 \(Wearry\) 的 \(O(\log n + \log m)\) 的题解……才意识到,自己考场上想的状压DP状态数真的很少,在 \(n > m + 1\) 的时候就只有一种状态了……也就是说自己再冷静分析一波,也许可以在考场上直接写出非打表的正解……即使不写状压DP,也可以通过小范围的分类讨论,直接得到一个式子,式子有点恶心,但也能做。

最后T3因为 long long 的原因挂了一个点。\(100 + 100 + 100 + 100 + 25 + 48 = 473\)

出来的时候 doe 还告诉了我 Day2T3 的非 DDP 的正解,倍增+DP。听上去会比 DDP 好写很多,相较于树剖版的 DDP 也会少一个 \(\log\) ,大致做法和nyg的NOIP模拟题几乎是一模一样的。不过她自己也很遗憾没写出来。大概一眼看到觉得是 DDP 就不会去想其他做法了吧。

最后这场NOIP以我校全线崩盘而告终。我问了一圈,似乎所有人全都吊死在了这个T2上,也不知道该说什么好。

不管你怎么讨厌这套题,不管你怎么讨厌这个T2,但这就是你的NOIP分数,实实在在,呈现在你眼前,有些刺眼,却又无可奈何。

仔细想起来,上一届NOIP考得似乎也不是太好,但是HNOI的时候,完美翻盘。

所以,HNOI2019?

This will be our story.

UPD after HNOI2019:

现在回头看这篇所谓的游记,感觉自己的戾气挺重的……怎么说也该反思一下翻车的原因吧……

说白了,一部分原因还是自己心态出了问题,给自己的期望太高。当得分达不到自己所谓的期望的时候,就不想动键盘。事实上,Day2T2写一个我最后写的爆搜不需要超过 \(20min\),可最后我在这道题上花费了将近两个小时。当发现自己得分效率不高的时候,应当果断放弃继续深入思考,拿走现在会的分数。Day2T3即使写不出 DDP,最后写一个不错的暴力相信也不算个难事。

另一部分就是这个写挂的问题。现在写题(之前也有)有个不太好的习惯,不喜欢对拍,总是相信自己的准确率。HNOI2019 已经吃了一次亏了,如果不改的话 NOI 恐怕还会重蹈覆辙。