JSOI2020 游记

· · 个人记录

Day 1

开场看题:

T1 挺可做的样子。
T2 数学题？
T3 不大可做。

然后试图切 T1，结果先想了线段树分治，然后发现不必要又去掉了
想了个二分+树状数组，2log 60pts。
样例死活过不去，结果竟然不会 STL/kk
然后过了大样例，丢一边不管了

T2 推 20min 式子，立刻 O(m^2) 爆切一题。

T3 思考 30min 无果，转头写大暴力。
感觉不大好写，又回去优化 T1。
仍然无果，就把离散化去掉以免出锅。
又写 T3 暴力。 然后随手扔给他一组小数据，T 了。
于是对它剪枝，预处理全部集合+迭代加深才算把它过去。
由于没什么分又不管了。

然后发现 T2 p=1 时可能出锅，赶紧加上特判。

预计 60+100+(0-15)=160-175?
似乎能活，出去一问发现高一人均 200+，翻不了盘了
顺便 % 一发 D1T3 会退火的 pcf
我好菜啊，D1T1 线段树上二分都想不到
还好没 FST

Day 2

开场看题：

T1 显然状压 DP（可我不会）
T2 怎么又求和又异或又求和？不会，不管了
T3 按常理是不可做题（这次竟然是生成树权值套数论?）

T1 以为过了，写一发，样例竟然输出负数，行，假了
然后口胡了一个空间 O(2^m)，时间 O(m^22^m) 的做法，码出来过了样例。
又口胡了一个时间空间均为 O(m2^m) 的做法，卡空间，丢一边不管了

T2 看似很不可做的样子，不管了

T3 反演一波，然后大概是

\sum_{x=1}^{152501}\varphi(x)\sum_{T,x|w_i}\sum{w_i}

然后枚举 x，枚举边考虑贡献，复杂度 O(144n^3m+152501n^2)，以为能过，然后把极限数据丢给它，T 了。
看部分分，1,2,4 三档挺稳，第 3 档加个特判，70 分。

又看 T2，忽然想到之前训练的时候做到过 01Trie 上加 1 和 01Trie 合并（当然在两个不同的题里），于是就是个 sb 题，切了。

T1 仍然不会过题，就写时间空间均为 O(m2^m) 的做法，写完之后强行测大样例，T 飞了。不得不开 O2，5s 后又 RE 了。然后发现数组越界，改过来 10s 后 WA 了。
然后心态没了，好不容易调出来，数组开到 22，sizeof 算一波空间，413MB。又测一发 22 的数据，1.8s。
于是只会 80。

测一发 T2 的极限数据，很稳

自闭中……

突然怀疑 T2 的复杂度，过了 3min 才想起来线段树合并复杂度的证明是合并一个点后总点数减一。
照搬一下证明 T2 的复杂度，然后复杂度就很对。

预计 80+100+70=250?
我都这个成绩不是要人均 AK 吗
出去一问，T1 卡常题，T2T3 都是原题，心态没了

说好的字符串呢？说好的 160-180 能活呢? 又翻不了盘了

Day ...

Day 1: 60+100+15=175
Day 2: 80+100+60=240
我 D2T3 民间跑出来居然是 WA? 那不是会被卡没了……

CSP 380 都能踩校线进队，退役失败
然后我就是省队最菜的选手了