啊?

aaron0919 · 2026-03-09 22:02:59 · 生活·游记

反正乱打的应该不会查 latex 滥用和标点符号吧。

脑子太乱了将就看看把。

2026省选 Day0 - 3.6

:scroll:

呃呃呃, 争取复习全部搞定.

[x] 李超线段树
[x] 虚树
[x] lca
[x] rmq
[ ] 线段树 3
[x] 网络流以及经典建模
[x] SAM 和 SAM 的 100 种用法
[ ] 数数题
[ ] 拉插的 100 种姿势
[x] ~~可持久化块状链表~~ 可持久化平衡树
[x] SPS ~~全家桶~~ 基础
[x] 各式各样的莫队
[x] Pollard-\rho 和 Miller-Rabin

P4097 【模板】李超线段树 / [HEOI2013] Segment - 洛谷

你敢相信这垃圾玩意儿卡了我一个小时.

学到了一亿个小错误.

首先看错了题, x,y 强制在线取模还 :tm: 不一样.

其次是竖线, 这题可以把竖线改为水平的一个点.

还有罪泥马啥币的浮点数锅, 在这里警告一遍.

\Huge\boxed{\color{red}所有浮点数比较都要\pm\epsilon}

还有一个最尼玛糖糖糖的错误.

\Huge\boxed{\color{red}\epsilon不要设成10^{12}}

P3835 【模板】可持久化平衡树 - 洛谷

呃呃呃, 不要打错左右儿子, rnk 和 kth 打的时候还是要细心一点, 养成打 newnode 的习惯.

记得多开大点, 第一次遇见 32 倍解决不了的问题.

P3379 【模板】最近公共祖先（LCA） - 洛谷

也是终于学会了 \mathcal O(n\log n)-\mathcal O(1) 的 \operatorname{lca}.

发现自己的 dfn+倍增 \operatorname{lca} 不如正版倍增 \operatorname{lca} 快, 自闭了.

具体的, dfs 序求 \operatorname{lca} 就是设要求 \operatorname{lca}(u,v), 设为 w.

假设 dfn_u<dfn_v (特判等于), 那么 w\to v 中除了 w 的点的 dfn\in(dfn_u,dfn_v], 然后找这一段 (dfn_u,dfn_v] 中深度最小的点的父亲就是 w.

顺便复习 RMQ.

P2495 【模板】虚树 / [SDOI2011] 消耗战 - 洛谷

还是调了好久, 复习了一下虚树建法, 先相邻两点连 \operatorname{lca}, 排序去重后再对每一对相邻的 a_{i-1},a_i 连 \operatorname{lca}(a_{i-1},a_i)\to a_i, 做到不重不漏.

总之有很多地方数组访问的下表要带 dfn.

P6097 【模板】子集卷积 - 洛谷

震惊, 我的暴力高位前缀和跑的比~~我的废物~~ FWT 变换还快.

或卷积就是高维前缀和嘛, 逆就是差分.

这个咚咚要记录 siz 分别卷, 记住就好了喵.

P4718 【模板】Pollard-Rho - 洛谷

尝试背诵, ~~16:03~~, 被拉去听讲了.

回忆了一下 MR 应该是 Fermat:\forall0<x,x^{n-1}\bmod n=1\\Second:\not\exist1<x<p-1,x^2\bmod n=1, PR 应该是 f(x)=x^2+c\bmod n, 欸我忘了.

学习一下, 算了不看算法, 手模一下.

对于 n=114,c=5,x_0=14, 有 \{x_i\}=\{0,14,87,50,111,14,87,50,111,14,87\}, 环长为 4, 其中 \gcd(4,114)=2 就是非平凡因数, 我不会会了吧, 然后倍增判环, 我记得 c\not=\pm2,0 似乎.

好吧失败了, 1271 我的 PR 分解不出来, 开始认真学习.

原来求的不是 \gcd(环长,n) 而是 \gcd(|x-y|,n), 其中一个一次跳一步另一个两步.

终于卡过去了, 总结一下一些问题:

MR 要结合线性探测和费马才行, 就是设 n-1=u\times2^t 先判掉 x^u=\pm 1, 然后做 t-1 次平方, 如果没有出现 n-1 就是合数.
如果 MR 枚举的质数已经比 \ge n 了返回 1.
PR 中 f(x) 不要取两次模.
PR 循环的终止条件是 \gcd(|x-y|,n)\not=1, 如果结果不是 n 就返回, 否则 n 是死循环.

P1903 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列 - 洛谷

带修莫队, 新手搓的, 就是多记一个修改, 然后块长调成 n^{2/3}.

记得开始莫队时当前修改时间戳应该是最后一个.

P3804 【模板】后缀自动机（SAM） - 洛谷

依旧重学.

flowchart TD

A[新字符] --> B[创建 cur]

B --> C[向 suffix link 向上补转移]

C --> D{是否到 root}

D -->|是| E[link 指向 root]

D -->|否| F{长度是否刚好}

F -->|是| G[link 指向 q]

F -->|否| H[创建 clone]

H --> I[修改转移]

I --> J[修改 link]

E --> K[last 更新]
G --> K
J --> K

在放个代码加深记忆.

void push_back(char ch)
{
    int cur = st.size(), c = ch - 'a', p = lst;
    st.emplace_back();
    st[cur].len = st[lst].len + 1, lst = cur;
    while (~p && !~st[p].nxt[c])
    {
        st[p].nxt[c] = cur, p = st[p].link;
    }
    if (!~p)
    {
        st[cur].link = 0;
        return;
    }
    int q = st[p].nxt[c];
    if (st[q].len == st[p].len + 1)
    {
        st[cur].link = q;
    }
    else
    {
        int clone = st.size();
        st.emplace_back(st[q]);
        st[clone].len = st[p].len + 1;
        while (~p && st[p].nxt[c] == q)
        {
            st[p].nxt[c] = clone, p = st[p].link;
        }
        st[q].link = st[cur].link = clone;
    }
}

具体槽点:

记得更新 lst
clone 后记得更新 q 的 link.

明天再来默一遍.

ok, 似乎莫队了, 祝自己 ++RP.

2026省选 Day1 - 3.7

先赛前复习一下.

P3376 【模板】网络最大流 - 洛谷

发现自己斜挂了好多地方, 例如所有边都要判 cap>0...

然后每一轮 dfs 前都要清当前弧优化标记, 还有 dfs 到了汇点就要返回.

P3381 【模板】最小费用最大流 - 洛谷

就是把 bfs 改为 SPFA, 但是我不会 SPFA.

哦, SPFA 要判在不在队列里面哦, 还有不能提前 return 要跑玩最短路.

然后 dfs 时候只能走最短路边, 不能有当前弧优化, 同时回溯的时候计算 cost.

哭了, T1 离 AC 只差一个变量, 还白背了一个 ntt, T2 一上来先默个 SAM, 结果是 KMP...

先打了两小时 T1 的前后缀背包做法, 然后花了 1h 背 ntt, 结果跑的比暴力还慢.

然后去打 T2 的全 0, 打完去看 T3 的暴力, 最后留一小时卡 T1.

结果没有想到子树做时没有想到把 n 改为 siz_u, 改了就过了.

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

只能鼓励一下自己, 今年我还是来体验的, 现在发现自己的脑残, 总比明年好.

~~太棒了, 我已经领悟到阿Q精神了,可以构造 hack 把加了 siz 优化的 T1 也卡掉, 祝大家都被 hack 哈哈哈.~~

然后 T2 竟然是 bitset, 什么东西, 什么叫 YYZ 切 T2 了? 不管了, 打好明天更重要.

2026省选 Day2 - 3.8

??? 开题后一看什么鬼交互型 ??? 什么垃圾预言家.

以前我都要在 cmd 里狂敲 UpArrow 和 Enter, 这次直接手打 CPH 赢麻了, 改成对拍都只用几步还是爽啊.

然后 T1 很容易想到不包含 0 的区间答案是 0, 然后可以先二分出 0 的位置.

因为要大概 n 次询问, 玩了一会儿想到是不是求包含 0 的前后缀都问一遍, 然后对相邻两个不同 mex 的可以定位一个数.

然后寻思是不是剩下的乱填, 然后试着打了打, 过了第一个小样例, 大样例乱 WA, 果断魔改 grader 自动生成数据对拍.

然后想着对于每一个区间的 mex, 里面出现过的数一定要在这个区间里面, 因此维护每个数可能出现区间的 l 和 r.

然后 n 个区间就要对若干个值域连续段的 l checkmax, r checkmin, 然后对着限制从紧到松填, 填完后删一个位置.

因此先打并查集删点, 调对后打两颗吉司机, 终于在开考 2:20 分左右打出来了, 现在只有 90 分.

想着怎么去掉询问次数中的 log, 然后发现可以求后缀的时候顺带求出, 然后就只用 n+1 次也就是 99 分了.

非常遗憾没有想到哪里还能抠一次, 去看 T2, 手玩 + 打随机化暴力花了 1h, 应该能拿 8 分吧.

接着是 T3, 题目的对着一坨空集比较字典序是认真的吗, 那一段我反复读了三次才确认是 \{\empty\} 和 \empty 比较, 那哪个大呢?

手玩了样例一, 没有对我的想法提供卵用, 然后模样例二, 死活模不出来.

不管了, 假设 \{>\empty>\} 打了个暴力, 结果一直过不了样例二, 中途爆搜炸了还重启了一次, 好在文件都没丢失.

然后接着模样例二, 刚刚重启时抬头看到样例二的修正了, 代码里输出一下发现还是挂了样例二.

接着仔细对比, 发现是 rt=5 错了, 手模后发现怎么会有 2 个等号, 明明 siz 都不同怎么字典序相同.

然后就爆炸了, 只好回去看 T2, 没什么心思, 躺了, 无聊想想 T1 grader 怎么打, 样例 grader 这么垃圾.

赛后发现 T1 全局的 mex 是确定的, 吉司机可以改为离线做, 自己纯汤.

最后 64+30+12+99+8?+0=213, 被 YYZ 拉爆 140 多分.

:+1:

这次正赛心态比较好, 尽管还是被破样例搞炸了, 至少前 3 个小时脑子都是清醒的在想题.

:-1:

两天的 T1 都因为小细节没签到, day1 被 ntt 凭空吃掉 1h, day2 被 segment beats 凭空吃掉 0.8h, 不过 day2 的 segment beats 没有白打.

然后 D1T2 这种串串 + dp题直接阵亡, 甚至没有根据题目位置联想到 bitset, D1T3 这种 Ad-Hoc 没仔细读性质(还是太抽象了), 没有拿到高档暴力.

结果 D2T2 也没有想到:

如果一道题怎么想也想不到, 那一定是欧拉回路!!!

谁说的啊我都不记得这句话.

总结来说就是简单拿不满, 面对高难非常吃力.

:scroll:

长期规划.

[ ] 学好吃的算法
[ ] 吃好吃的 ds
[ ] 刷题练手感
[ ] 玩玩交互题

还是好想啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊几声.