SCOI 2018 游记

Day1

首先拿到题先看了一下,大致看出 T1 动态点分,T2 二次剩余+数据结构维护,T3 不知道。

理了思路以后尝试写 T1,写着写着发现空间越开越大,题却恶意卡空间卡到了 64M。压了半天也压不下去,只好分三个部分去写 50 分暴力。

再看 T2,推了一个式子发现只需要做若干次二次剩余即可。然后又正准备写,发现模数是 long long,一乘就爆了。鼓捣了半天 __int128 发现没法编译。然后试图高精,算复杂度又无故乘 10 爆掉了。于是无奈打暴力。

最后在 T3 写了个骗不到分的随机化走人。

出来以为大家把 T1 和 T2 都秒掉了,非常气,一问才发现都被空间和 long long 卡住了。

分数是 30+20+0=50,不知道为什么 T1 爆了一种暴力 20 分。

听佬说 T3 是线性基,搞不懂。

Day2

兴致冲冲地背好了后缀数组,一进场发现没字符串?

通看,T1T3 又是修改+询问式的数据结构,T2 是一个计算几何。

没办法,先推 T1,推着推着发现拆开分类讨论可以,于是弄了 4 棵线段树各维护 8 个值。测了一下过了大样例,发现才 9:50,就先去看后面的题了。

T2 简单画了画准备写 30 分,30 分就一个中垂线求交点就行了。但是写起来十分令人崩溃,写到 11:30 才过了样例。如果要拿接下来 30 分还要加一个圆的切线,觉得很不稳就没写,赶紧去看 T3。

T3 想了半天没有想出来策略,打暴力又差点把题看错,弄了半天才写出 10 分来。

最后 T1 也没拍成。

出来讨论了一下发现大家 T1 都写的是线段树维护凸函数,就只有我实际上是把凸函数的四条线给拆成了四棵树,不过正确性是有的。

T3 Joker 说是线段树维护凸包,所以他就没搞。

分数是 100+0+10=110,果然 T2 还是没稳住。

赛后

总共 160 分,两天加起来还没有佬一天得的多。

SCOI 一年比一年难了,然后不知道这次抽什么风出了三个数据结构,两个数学和一个算几,没有图论DP字符串怎么活。

全省排第 22 吧,反正没上线。这次那沙比政策还是卡下来一个人。。。然后我非高二选手里面第一。

发表评论

电子邮件地址不会被公开。 必填项已用*标注