abcdeffa's Blog

当局者迷,旁观者清。

0%

NOIP2020 游记

虽然我也不知道我为什么要在这个时候补游记,但还是补一下。

Day 1

早上依然有去小卖铺的保留环节。

开场看了一下 T1,确定了这不是儒略历。

然后看了一发 T2,哇是个字符串题。

看了一下 T3,想起自己考前前一天所想的:「不会考构造题的」。历史总是惊人的相似。

然后看了一下 T4,哇十维空间里散步。好厉害的样子。

然后确定了一下 T1 应该没内鬼就写了,想到了拓扑,但还是为了迎合一下那个应该是留给 $O(nm)$ 的数据范围写了一个 $O(nm)$ 的屑做法。

当时在想为什么不搞个分数取模,后来想想嗯这个好像是超纲的。

然后看到了题目末尾那个不太确定有什么用的限制,是为了让分子和分母不爆 long long 吧,出题人真严谨呢。

很快地把大样例过了以后就把这题丢掉了。

来,让我们欣赏一下这份在赛后会 WA 60 分的代码的分数相加的这一部分吧:

1
2
3
4
5
6
7
8
void Add (long long A, long long B, long long C, long long D, long long p)
{
long long AA = A * D + B * C;
long long BB = B * D;
long long x = gcd(AA, BB);
AA /= x, BB /= x;
ans[p][0] = AA, ans[p][1] = BB;
}

哈哈哈他没有先除再乘!

然后去看 T2,想了想发现自己有思路了。

但 $O(n \ln n \log n \log \text{mod})$(其中 $\text{mod}$)是 Hash 的模数。

欸好像这个复杂度好像过不太去的样子呢。

不管了,写!

然后这个菜鸡由于太久没写求子串哈希值,用了一种很屑的做法,他甚至还在现场推了一发等比数列的求和公式。

如果你注意看的话,你甚至发现这个复杂度里没有出现 $|\sum|$ 或是 $\log |\sum|$。为什么呢?因为他认为出现次数为奇数次的字符最多有 $n$ 个!

然后这份代码在 CCF(?)的评测机下喜提 56 分。赛后改了一发就 84 分了,再卡一发常就 A 掉了。

如果多给我 5 分钟赛后修改的时间,我将绝杀!

可惜没有如果。

然后就跑去想 T3,发现自己甚至连 $n = 2$ 都不会做。盯着大样例的输出玩了一会儿,但并没有玩出个所以然来。

自闭了很久后去把 T4 的暴力写了。

然后回来 T3 继续自闭。

最后终于用一个连样例都过不去的爆搜和打表,写下了这场比赛的句号。

当时觉得自己拿个 200+ 还是没有问题的吧。

第二天出分,一看:151(60+56+0+35),瞬间感觉人没了。

不过的确是自己菜,又有什么好抱怨的呢?

今天是 GDKOI 2021 的 Day1,想起自己的 CSP 2020 的游记也是 NOIP 2020 前一天补的。

果然我还是懒呢。