濒临退役

Shunpower · 2025-03-03 22:34:54 · 生活·游记

day0

乘坐轻轨前往 xdfz 附近的酒店住下。

酒店环境很一般……没有洗发水，甚至一开始连热水都没有。等了很久才等到热水，结果水质更是难评。

还是勉强睡了个好觉。

day1

早餐也一般。

进考场了。居然是所在考场的 1 号！

开 T1。一眼枚举中位数，一眼 l_{i,1}\le x\le r_{i,1} 全选尽量多 x。我猜 x<l_{i,1} 和 x>r_{i,1} 的部分全部选 l_{i,2}？于是开始写 \mathcal O(n^2)。

写完了啪过不了样例三。想了一下显然需要调整，如果一边多一边少是可以把中位数 \frac{1}{2} 地一点点挪过去的，显然坏的那边不用调整，于是解不等式就完了。（伏笔）

剩下的就是离散化和扫描线了！很快就写完了，中途还去上了个厕所。

啪！为什么我过不了大样例啊？完蛋了？？？？

于是开始崩溃地写暴力和对拍。写了三档暴力全部过不了大样例，但是 n=6 又根本拍不出来。

拍的时候开始看 T2。

这不是显然要操作分块吗？这我太会了！然后肯定是拓扑排序，内部是简单的在拓扑的时候合并 \mathcal O(B)，外部也是简单的在拓扑的时候线段树合并就可以了！

于是开始写写写。因为还有时间维所以还写了主席树，码长达到了 6KB。写完就过了样例一，我赢了哇？

啪！为什么样例二不但没过还跑了 2.2s 啊？

啊？为什么线段树合并了 8\times 10^6 次啊？

此时已经 11:03 了我的得分仍然是 0。以为自己线段树合并写错了于是开始 fix 线段树合并，怀疑自己写错了又改成启发式合并。代码越写越长，最后发现根本就没办法在拓扑排序的时候复杂度正确地启发式合并啊？

？？？

【此处】【有至少】【四句】【问候自己的话】，拓扑排序的时候根本就不能维护数据结构，复杂度是错的！

一直到这个时候才反应过来这个题怎么可能没有 bitset，怎么可能第一步不是跑一个 \mathcal O(\frac{nm}{w}) 的可达性。写了一发发现可达性确实只需要跑 1.3s。。。

然后就爆了。此时已经接近 12:00 我的得分还是 0，“假了”两个题。回去看 T1，发现自己把解不等式的判定注释掉可以通过大样例？

【此处】【有至少】【四句】【问候自己的话】，我解不等式忘记开 long long 了！

所有多项式暴力共用一个没开 long long 的函数于是全部跑不动大样例。

改完了就过大样例了。

然后现在十二点出头尝试来救 T2。随便想了一会发现 10\sim 12 是只需操作分块，6 是对 a 分块。正解肯定搞不完了，于是再想了想别的部分分根本想不出来于是开始狂写。

然而只需把这俩玩意套起来就有 \mathcal O(n^{\frac{5}{3}})，而且我感觉我写得完。。。

成功在 12:53 救出 32 分。T3 根本没时间写暴力了。

于是写了 24K 代码获得了 100+32+0=132 分！其中 T2 提交了 15K 代码！！非常厉害！！111

感觉自己变尸体了直接。

晚上陪 SA 看音综吸吸，心情放松了一些。

day2

精神良好进入考场。

这个 T1 不是一眼题？一眼按 t 排序，随便写写就好了，写完通过了 a_i\le b_i 的样例。哦怎么还有 a_i>b_i？

随便画了一下发现两部分是独立的，那分别做就好了。又写了一会就用 \mathcal O(n^2) 跑过了所有样例。

好吧，开始数据结构优化！要写一个二分一个区间覆盖等差数列一个区间求和！线段树即可！

于是开始写。首先发现 1log 的二分非常难写，于是下定决心写 2log，然后发现还是要写 1log 的线段树上前后缀二分？？？

这玩意我从来没写过，但是想了想就会了。于是开始写。

写完码长来到了 8KB，然后开始调。遭遇了共轭样例，硬调 n=198 之后成功【仅通过】了所有大样例。

此时已经来到 11:30。懒得拍了。大样例跑了 500ms 要被卡常吧，但是已经没精力卡常了。。。

中途看了一眼 T2 发现是图上状压 dp。前段时间刚好训过，直接启动！

感觉特别难啊？然后开始想 C 性质，判定外向树就行。我觉得一个有向图有外向树当且仅当【有小于等于一个点入度为 0 啊】！

然后这个条件完全做不了 DAG 容斥。想破脑袋了都不会。事实上转成强连通分量的条件就好做很多，但是我想不到。

去写了 T3 暴力，发现 n=18 暴力跑得很快，于是开始卡常，尝试把它卡进四秒。我几乎找出了最优美的暴力写法：

il void dfs(){
    if(q.empty()) return;
    if(memo.count(q)) return;
    memo[q]=1;
    int premax=0;
    deque <int> tmp=q;
    while(!q.empty()){
        if(q[0]>premax){
            int x=q[0];
            q.pop_front();
            if(x>1) q.pb(x-1);
            dfs();
            if(x>1) q.pop_back();
            premax=max(premax,x);
        }
        else q.pop_front();
    }
    q=tmp;
}

然后卡了半天忘了换成哈希表了。

哎哎哎好像反正都只有 8 分。

回到 T2，尝试推 B 性质。我感觉这是个 \mathcal O(1) 的式子啊？？

推了半天也过不了唯一的那个样例。最后对着那个数的质因子蒙了一个式子：

cout<<1ll*(n+1)*qpow(2,n-2)%mod*qpow(4,m-(n-1))%mod*inv(qpow(4,m))%mod<<'\n';//<<'\n';

获得了 12 分。

这是我人生中第一次乱写一个式子得到分数 ^^。

但是【】，怎么回事呢？

day ?