AtCoder Beginner Contest 454 复盘

比赛目录：8.3--454
题目列表：AtCoder Beginner Contest 454 讨论记录：D 题 · E 题 · F 题 · G 题
排版与复盘结构参考：笔记/AtCoder Beginner Contest 452/ABC452.md

完成情况

题目学习归属核心知识点复杂度
A - Closed interval独立 AC闭区间计数O(1)O(1)
B - Mapping独立 AC频次数组、单射与满射O(N+M)O(N+M)
C - Straw Millionaire独立 AC；先 TLE，后改成栈遍历有向图可达性、DFS/BFSO(N+M)O(N+M)
D - (xx)赛时想到规范化，但未写完；看题解后独立默写规范形、栈式字符串消除$O(
E - LRUD Moving赛时 DFS 导致 MLE/TLE；看题解、抄写后独立默写棋盘染色、构造、前后缀拼接O(N2)O(N^2)
F - Make it Palindrome 2AI 题解、抄写后独立默写对称差、差分、配对操作、排序贪心O(Nlog⁡N)O(N\log N)
G - Mode in the Subtree因未学习树上 DSU，战略性放弃改错DSU on Tree、轻重儿子、欧拉序官方为 O(Nlog⁡N)O(N\log N)

本场最值得保留的结论

  1. C 题不是反复应用规则，而是从物品 11 出发求有向图可达点。 一旦某个点第一次可达，就把它压入栈继续扩展；每个点和每条边只需处理常数次。
  2. D 题的“标准统一化”方向是对的。 当双向操作互为逆操作时，可以寻找唯一规范形，把可达性问题转化成规范形相等。
  3. E 题先判存在性，再做构造。 染色给出 N 为偶数且空格为白格的充要条件；s1 从起点正向剥离，s2 从终点反向剥离。
  4. F 题最难的不是代码，而是连续三次等价转化： 原数组 AA 到对称差 BB，区间操作到差分 CC 的两点操作，再到固定选取数量后的排序贪心。
  5. G 题当前不应强行改代码。 在没有系统学习树上 DSU 前，只保留问题转化、数据维护目标和学习路线，避免把 AI 代码误当成已经掌握的模板。

A - Closed interval

题意与思路

求闭区间 [L,R][L,R] 中整数的数量。两端都包含，因此答案为

R−L+1.R-L+1.

代码

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int L,R;
    cin>>L>>R;
    cout<<R-L+1<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

时间复杂度为 O(1)O(1)，空间复杂度为 O(1)O(1)。

B - Mapping

题意

NN 个人各自穿着编号为 FiF_i 的衣服，衣服种类编号为 11 到 MM。分别判断：

  1. 是否所有人的衣服种类两两不同；
  2. 是否每种衣服都至少有一个人穿。

思路

令 cnt[x]cnt[x] 表示衣服 xx 出现的次数。

  • 所有人穿不同衣服，当且仅当所有 cnt[x]≤1cnt[x]\le 1，即最大频次不超过 11；
  • 每种衣服都有人穿，当且仅当所有 cnt[x]≥1cnt[x]\ge 1，即最小频次不小于 11。

从映射角度看，第一问在判断是否为单射，第二问在判断是否为满射。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int cnt[N];

void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int f;cin>>f;
        cnt[f]++;
    }
    int max_cnt=0,min_cnt=INT_MAX;
    for(int i=1;i<=m;i++)
    {
        if(cnt[i]>max_cnt) max_cnt=cnt[i];
        if(cnt[i]<min_cnt) min_cnt=cnt[i];
    }
    cout<<(max_cnt>1?"No":"Yes")<<"\n";
    cout<<(min_cnt==0?"No":"Yes")<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

时间复杂度为 O(N+M)O(N+M)，空间复杂度为 O(M)O(M)。

C - Straw Millionaire

题意

初始只有物品 11。若已经拥有物品 AiA_i，就可以把它交给第 ii 个朋友并得到物品 BiB_i。求最终可能获得多少种物品。

赛时失败路径：反复扫描所有规则

最初把已经拥有的物品放进 set，然后不断扫描全部 MM 条规则；只要本轮得到新物品，就再扫描一轮。

问题在于，一轮可能只新增一个物品，最坏要进行 O(N)O(N) 轮，每轮检查 O(M)O(M) 条边，总复杂度可达

O(NM),O(NM),

在 N,M≤3×105N,M\le 3\times 10^5 时必然 TLE。

正确转化：有向图可达性

把每条规则 Ai→BiA_i\to B_i 看成一条有向边。初始拥有物品 11，问题就是：从节点 11 出发能够到达多少个节点？

维护已经到达的集合 s 和待扩展的栈 st：

  1. 节点第一次被发现时加入 s 和 st；
  2. 从栈顶取出节点 uu，枚举所有 u→vu\to v；
  3. 若 vv 尚未访问，就标记并继续扩展。

这就是迭代版 DFS。这里“栈优化”不是对原反复扫描的小修小补，而是识别出了图遍历模型。

代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
vector<set<int>> v(N);

void solve()
{
    int n, m;
    cin >> n >> m;
    set<int> s;
    s.insert(1);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].insert(b);
    }

    for(auto p:v[1]) s.insert(p);
    if(s.size()==1)
    {
        cout<<"1"<<"\n";
        return;
    }

    stack<int> st;
    for(auto p:s) st.push(p);

    while(!st.empty())
    {
        int b=st.top();
        st.pop();

        for(auto p:v[b])
        {
            if(s.count(p)) continue;
            s.insert(p);
            st.push(p);
        }
    }

    cout<<s.size()<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

若邻接表和访问标记都用普通 vector/布尔数组，可以严格做到 O(N+M)O(N+M)；当前代码中的 set 会带来对数因子，但仍能通过。

易错点

  • 不要因为题面以“不断交换物品”叙述，就真的按轮模拟规则。
  • 可重复使用已经得到的物品，所以无需考虑物品被“交出去后消失”；这里只关心某种物品是否曾经可获得。
  • 邻接边重复不影响可达性。使用 set 去重不是必需条件。

D - (xx)

题意

字符串只包含 (、x、)，可以任意次进行互逆操作：

(xx) -> xx
xx   -> (xx)

判断能否把 AA 变成 BB。所有测试中字符串总长度不超过 2×1062\times 10^6。

赛时思路

赛时已经想到“把 A,BA,B 全部统一成标准形式”，方向正确，但在识别栈尾模式和删除区间的实现上没有完成。

规范形

定义 f(S)f(S)：不断执行 (xx) -> xx，直到不存在 (xx)，所得字符串称为 SS 的规范形。

规范形与消除顺序无关。原因是任意两个当前存在的 (xx) 互不重叠，先消除其中一个不会破坏另一个；结合字符串长度严格下降，可以归纳得到最终结果唯一。

于是有

A 能变成 B  ⟺  f(A)=f(B).A\text{ 能变成 }B\iff f(A)=f(B).
  • 若 f(A)=f(B)f(A)=f(B)，先把 AA 化简到公共规范形，再逆向执行 B→f(B)B\to f(B) 的步骤即可到达 BB；
  • 每次正向或逆向操作都不改变规范形，因此可达的两个字符串规范形必然相等。

线性计算规范形

从左到右扫描字符，把当前字符追加到 ret。若最后四个字符恰好是 (xx)，就删去这四个字符，再追加 xx。

这里官方代码使用一次 if 就够：替换后字符串以 x 结尾，而 (xx) 必须以 ) 结尾，因此替换不可能立刻在栈尾再次产生新的 (xx)。下一次读入字符后再检查即可。

substr 与迭代器

ret.substr(ret.size()-4,4)

中的 ret.size()-4 是下标；而 ret.end()-4 是迭代器。二者指向逻辑上的同一位置，但不能混用：

ret.substr(ret.size()-4,4);       // substr 接收下标和长度
ret.erase(ret.end()-4,ret.end()); // erase 的区间重载接收迭代器

必须先判断 ret.size()>=4，否则无符号的 size_t 执行 size()-4 会下溢。

代码（看题解后独立默写）

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    string A,B;
    cin>>A>>B;
    auto simplify=[&](string s)
    {
        string ret;
        for(auto& ch:s)
        {
            ret+=ch;
            if(ret.size()>=4&&ret.substr(ret.size()-4,4)=="(xx)")
            {
                ret.erase(ret.end()-4,ret.end());
                ret+="xx";
            }
        }
        return ret;
    };
    cout<<(simplify(A)==simplify(B)?"Yes":"No")<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}

每个字符入栈一次，每次消除使长度减少 22，总时间复杂度为 O(∣A∣+∣B∣)O(|A|+|B|)，空间复杂度为 O(∣A∣+∣B∣)O(|A|+|B|)。

E - LRUD Moving

题意

在 N×NN\times N 棋盘上，从 (1,1)(1,1) 出发，恰好移动 N2−2N^2-2 步到达 (N,N)(N,N)，期间不重复访问格子，并访问除 (A,B)(A,B) 外的所有格子。判断是否可行，并构造一条路径。

赛时失败路径：DFS 搜索哈密顿路径

赛时代码枚举每一步的四个方向，并把整条字符串按值传入递归。这个搜索空间是指数级的；同时最大递归深度接近 N2N^2，每层还可能复制长度为 O(N2)O(N^2) 的字符串，因此 TLE、MLE 都不可避免。

这题不是搜索题，而是“存在性判定 + 直接构造”。

第一步：棋盘染色判定存在性

按 i+ji+j 的奇偶性染色：偶数为黑格，奇数为白格。每移动一步颜色必然改变。

路径共访问

(N2−2)+1=N2−1(N^2-2)+1=N^2-1

个格子，起点和终点都是黑格。

  • 若 NN 为奇数，则 N2−1N^2-1 为偶数。黑白交替且首格为黑时，第偶数个格子应为白，与终点为黑矛盾；
  • 若 NN 为偶数，原棋盘黑白格各有 N2/2N^2/2 个。合法路径首尾为黑，路径上的黑格比白格多一个，因此唯一不访问的格子必须是白格，即 A+BA+B 为奇数。

所以答案为 Yes 的充要条件是

N≡0(mod2),A+B≡1(mod2).N\equiv 0\pmod 2, \qquad A+B\equiv 1\pmod 2.

第二步：从两端缩减

满足条件后，把问题不断缩成更小的矩形。

行缩减

一段

R...(N-1 次)...R D L...(N-1 次)...L D

会蛇形走完当前最上方两行，并停到下一行的左端。

  • 若禁入点不在最上方两行，即 1-based 下 a>2，可以从起点端执行该段，加入 s1，并令 a-=2；
  • 否则从终点端反向剥掉底部两行，把反转后的片段存进 s2。

列缩减

行缩减结束后只剩两行。片段 DRUR 走完左侧两列并进入下一列。

  • 若禁入点不在最左两列，即 b>2，加入 s1 并令 b-=2；
  • 否则从终点端处理右侧两列，把反转片段加入 s2。

为什么 s2 要反转存储、逆序拼接

s1 记录从起点出发的正向片段。s2 记录从终点往回剥离时对应的后缀片段，因此有两层顺序关系：

  1. 单个片段要反转后存入，使其成为最终答案方向上的字符序列；
  2. 从终点依次剥离的片段，在正向路径中出现顺序相反，所以最后要倒序拼接整个 s2。

最终答案为

ans⁡=s11+s12+⋯+s1p+s2q+s2q−1+⋯+s21.\operatorname{ans} =s1_1+s1_2+\cdots+s1_p +s2_q+s2_{q-1}+\cdots+s2_1.

第三步：处理最后的 2×22\times 2

缩减结束后，禁入点只能是当前 2×22\times2 中的一个白格：

  • 若为 (1,2)(1,2)，走 DR；
  • 若为 (2,1)(2,1)，走 RD。

最关键的边界错误

1-based 代码必须写

if(a>2)
if(b>2)

不能写成 >=2。当 a==2 时禁入点就在要扫过的第二行；当 b==2 时禁入点就在要扫过的第二列。这里正是最终 WA 的原因，也是源码中 ////base-1必须为严格大于 的重点。

另一个注释笔误是“N2−1N^2-1 必须为偶数”。实际上路径访问 N2−1N^2-1 个格子且首尾同为黑格，因此它必须为奇数，所以 NN 必须为偶数。

代码（注释最完整的 copy1.cpp）

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n,a,b;
    cin>>n>>a>>b;
    //染色思想,我们令i+j为偶数时为黑色,i+j为奇数时为白色
    //N^2-1必须为奇数,则N必须为偶数
    //路线为黑 白黑 白黑 白黑.......
    //经过画图,我们会经过N^2-1个格子,只有一个格子我们不会经过
    //所以,这个a+b必须为奇数(白格子)
    if(n&1||(a+b)%2==0)
    {
        cout<<"No"<<"\n";
        return;
    }
    ////s1记录从起点顺着来的路线
    ////s2为从终点逆着来的路线
    ///两者逐渐往(a,b)所在的那两行两列逼近缩减
    ////最终只留下一个2x2的方格,用if特判即可
    vector<string> s1,s2;
    int half=n/2;//我们以两行为一次操作
    //行的缩减,执行half-1次
    //把(a,b)那两行单独空出来处理
    for(int i=1;i<half;i++)
    {
        string s=string(n-1,'R')+'D'+string(n-1,'L')+'D';
        ////if(a>=2)base-1必须为严格大于!!!!!!!!
        if(a>2)
        {
            s1.push_back(s);
            a-=2;
        }
        else
        {
            reverse(s.begin(),s.end());
            s2.push_back(s);
        }
    }
    //列的缩减
    //把(a,b)所处的那两列单独拎出来处理
    for(int i=1;i<half;i++)
    {
        string s="DRUR";
        ////if(b>=2)
        if(b>2)
        {
            s1.push_back(s);
            b-=2;
        }
        else
        {
            reverse(s.begin(),s.end());
            s2.push_back(s);
        }
    }

    //最后只剩下2×2的方格了
    if(a==1&&b==2) s1.push_back("DR");
    else s1.push_back("RD");

    string ans;
    for(auto& str:s1) ans+=str;
    for(int i=(int)s2.size()-1;i>=0;i--) ans+=s2[i];

    cout<<"Yes\n"<<ans<<"\n";

}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}

代码保持了原注释；其中关于 N2−1N^2-1 奇偶性的注释应按上文修正理解。构造输出本身长度为 N2−2N^2-2，所以时间、空间复杂度均为 O(N2)O(N^2)。

F - Make it Palindrome 2

题意

每次选择区间 [l,r][l,r]，把其中所有元素加 11 后对 MM 取模。求把数组变成回文数组所需的最少操作次数。

这题代码不长，但思路要经过多层严格等价转化。

第一步：只保留左右配对差

令

H=⌊N2⌋,Bi=(Ai−AN+1−i) mod M,1≤i≤H.H=\left\lfloor\frac N2\right\rfloor, \qquad B_i=(A_i-A_{N+1-i})\bmod M,\qquad 1\le i\le H.

数组为回文，当且仅当所有 Bi=0B_i=0。当 NN 为奇数时，中间元素只与自己对应，完全不用处理，所以必须使用 half=n/2，不能向上取整。

跨越数组中点的操作可以消去对称重叠部分，等价改写为不跨中点的操作。因此：

  • 在左半边进行一次区间加，对应 BB 的某段区间加 11；
  • 在右半边进行一次区间加，对应 BB 的镜像区间减 11。

于是原问题等价为：对 BB 的任意区间进行 +1+1 或 −1-1，使其全部归零。

第二步：双哨兵差分

补两个零边界：

B0=BH+1=0.B_0=B_{H+1}=0.

定义长度 L=H+1L=H+1 的差分数组

Ci=(Bi−Bi−1) mod M,1≤i≤H+1.C_i=(B_i-B_{i-1})\bmod M,\qquad 1\le i\le H+1.

这两个边界不能省略。例如 BB 全为常数 xx 时，内部差分虽然为零，但完整的 CC 是

(x,0,0,…,0,M−x),(x,0,0,\ldots,0,M-x),

并不是全零。首尾差分保存了“对整段 BB 操作”的信息。

对 BB 的区间 [l,r][l,r] 加 11，等价于

Cl+=1,Cr+1−=1.C_l\mathrel{+}=1, \qquad C_{r+1}\mathrel{-}=1.

区间减 11 时符号相反。因此问题变为：每次选择两个不同位置，使其中一个加 11、另一个减 11，最终让 CC 全部归零。

任意一对位置都能映射回合法区间：若加法位置在左，就对应 BB 的区间加；若加法位置在右，就对应 BB 的区间减。位置顺序不是额外限制。

第三步：每个 CiC_i 选择一种归零方向

设 0≤Ci<M0\le C_i<M。要把 CiC_i 变成零，有两种有效方式：

  • 对它做 CiC_i 次减法；
  • 对它做 M−CiM-C_i 次加法，使它到达 M≡0(modM)M\equiv0\pmod M。

设集合 XX 中的位置选择减法，其余位置选择加法。记

S=∑i=1LCi,SX=∑i∈XCi.S=\sum_{i=1}^{L}C_i, \qquad S_X=\sum_{i\in X}C_i.

所需减法数为

D=SX,D=S_X,

所需加法数为

U=∑i∉X(M−Ci)=(L−∣X∣)M−(S−SX).U=\sum_{i\notin X}(M-C_i) =(L-|X|)M-(S-S_X).

由于一次操作同时贡献一次加法和一次减法，官方推导得到操作数

max⁡(U,D)=SX+Mmax⁡(L−∣X∣−SM,0).\max(U,D) =S_X+M\max\left(L-|X|-\frac SM,0\right).

由首尾哨兵差分的定义，SS 一定是 MM 的倍数。

第四步：为什么排序取前 kk 个

固定 k=∣X∣k=|X| 时，公式只与 SXS_X 有关，因此应选 CC 中最小的 kk 个数。

当

k<L−SMk<L-\frac SM

时，多选一个元素会使 SXS_X 增加至多 M−1M-1，但惩罚项会减少 MM，总答案严格下降；越过该位置后惩罚项不再下降，而 SXS_X 只会不减。

因此最优选择数量为

k=L−SM,k=L-\frac SM,

答案就是排序后最小的 kk 个 CiC_i 之和。

这里不是“均值不等式”，更准确地说是一个离散平衡点与边际变化：平衡点之前每多选一个都变优，之后再选不会变优。

下标错误链

  1. half 必须是 n/2。奇数长度的中间元素无需配对；
  2. B[0] 和 B[half+1] 都是零哨兵；
  3. C 必须计算到 half+1，否则漏掉右边界差分；
  4. 有效长度是 len=half+1；
  5. 排序区间是 sort(C.begin()+1,C.end())，不能误写成两个相同的迭代器；
  6. sumC 和答案可能达到 O(NM)O(NM)，需要 long long。

代码（注释最完整的 copy1.cpp）

//思路:转为为Bi数组,求Bi全为0时的最小操作次数,再把Bi转化为差分数组
////对区间加减常数k-->秒想差分数组
//然后求令整个差分数组Ci为0的最小操作次数即可
//将操作次数分类为加和减
//由均值不等式可以知道,当加法的操作次数等于减法的操作次数时,总的操作次数最少
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    ////int half=(n+1)/2;奇数的话中间那个数完全不用管,靠!!!!!!,我sb了
    int half=n/2;//只看左右配对数即可
    ////vector<int> B(half+1);
    vector<int> B(half+2);
    for(int i=1;i<=half;i++)
    {
        //B[0]和B[half+1]为哨兵位
        B[i]=(a[i]-a[n+1-i]+m)%m;
    }

    //创建差分数组
    vector<int> C(half+2);
    ////for(int i=1;i<=half;i++)
    for(int i=1;i<=half+1;i++)
    {
        C[i]=(B[i]-B[i-1]+m)%m;
    }

    int sumC=0;
    int len=half+1;////C数组的有效长度
    for(int i=1;i<=len;i++) sumC+=C[i];
    int k=len-sumC/m;
    sort(C.begin()+1,C.end());

    int ans=0;
    for(int i=1;i<=k;i++) ans+=C[i];
    cout<<ans<<"\n";
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}

时间复杂度为 O(Nlog⁡N)O(N\log N)，空间复杂度为 O(N)O(N)。

G - Mode in the Subtree

当前学习归属

这题的 AC 代码来自 AI。由于树上 DSU 尚未学习，本场战略性放弃改错是合理的；下面只记录已经核验的问题模型和知识地图，不把代码当成已掌握内容。

题目要求维护什么

对每个节点 vv，统计其子树内每种颜色的出现次数 fif_i，求

mv=max⁡ifim_v=\max_i f_i

以及达到最大频次的颜色数量

kv=∣{i∣fi=mv}∣.k_v=\left|\{i\mid f_i=m_v\}\right|.

最后计算

∑v=1N(mv⊕v)(kv⊕v)pmod998244353.\sum_{v=1}^{N}(m_v\mathbin{\oplus}v)(k_v\mathbin{\oplus}v)pmod{998244353}.

真正困难之处是 N≤2.5×106N\le2.5\times10^6：普通 unordered_map 小并大虽然复杂度看似可以，但常数和内存都过重，递归 DFS 也可能爆栈。

官方 DSU on Tree 框架

对每个节点选择子树最大的儿子作为重儿子，其余为轻儿子：

  1. 先递归处理轻儿子，得到答案后清空其统计表；
  2. 再处理重儿子，并保留其统计表；
  3. 用欧拉序区间把所有轻子树重新加入重儿子的表；
  4. 加入当前节点，此时表中恰好是当前整棵子树；
  5. 读取当前最大频次和达到该频次的颜色数。

需要维护三个数组/变量：

cnt[color]  当前表中该颜色的出现次数
freq[t]     当前恰好出现 t 次的颜色数量
mx          当前最大出现次数

由于颜色编号不超过 NN，可以用连续数组代替哈希表。每个节点只会在根到它的路径经过轻边时被重复加入，而轻边数量为 O(log⁡N)O(\log N)，因此总复杂度为 O(Nlog⁡N)O(N\log N)，空间复杂度为 O(N)O(N)。

后续学习路线

  1. 先学习子树大小、重儿子与“经过一条轻边后子树大小至少减半”的证明；
  2. 用递归版 DSU on Tree 完成一题普通规模的子树颜色众数；
  3. 再学习欧拉序把子树压成连续区间；
  4. 最后回到本题，理解为什么要用数组邻接表、显式事件栈和按需清空来控制常数与递归深度。

在完成以上专题前，不建议背本题五千余字节的 AI 实现。

错因分类

1. 模型识别

  • C：把图可达性写成多轮规则模拟；
  • E：把有规律的棋盘构造写成指数级 DFS。

2. 下标与边界

  • D：size()-4 是下标，end()-4 是迭代器，且必须先检查长度；
  • E：1-based 下必须用 a>2、b>2；
  • F：奇数中点不配对，双哨兵和最后一项差分都不能漏。

3. 证明与实现脱节

  • D：想到了规范化，但没有把“检查栈尾四字符并替换”写出来；
  • F：大致理解公式后，仍在数组长度、有效区间和排序端点上连续出错。

4. 前置知识不足

  • G：树上 DSU 尚未学习，不适合直接对超大规模优化代码做改错。

可执行训练项

  1. 图遍历辨识： 找三道“获得物品/技能/权限”的题，强制画成有向图后再写 BFS 或 DFS。
  2. 字符串栈消除： 独立实现三种固定模式消除，分别练习 substr、迭代器区间和手动尾部比较。
  3. 构造题验证器： 对 E 的答案检查长度、边界、是否撞禁入点、是否重复访问、终点是否正确；构造题必须形成自动验证习惯。
  4. 差分完整性： 每次写差分先明确原数组有效区间和两侧哨兵，再写出差分有效区间，不凭感觉分配数组长度。
  5. F 题重推： 不看笔记，从 A→B→C→XA\to B\to C\to X 四步重新推导一次，并解释为什么 k=L−S/Mk=L-S/M。
  6. G 题暂缓： 完成一题基础 DSU on Tree 后，再回来逐段解释 AC 代码；在此之前不做机械默写。

核验记录

  • 已核对官方 A-G 题面与约束；
  • 已按消息顺序读完 D、E、F、G 四段 DeepSeek 分享对话；
  • 已完整读取 ABC452 复盘作为排版与质量基准；
  • 已读取比赛目录内全部 C++ 版本、需求文件、//// 上下文，以及 E 题构造图和相关动画/验证材料；
  • A-G 本笔记所依据的代码均使用 GCC 14.2、C++17 编译通过；
  • A-G 官方样例均通过，G 题额外核对了全部三个官方样例；
  • E 题两套本地验证器各检查 108 个构造用例，均为 108/108 通过。