AtCoder Beginner Contest 447 复盘笔记

比赛链接：AtCoder Beginner Contest 447
整理日期：2026-07-18
代码来源：7.17 目录中的赛时代码、改错代码、题解复现代码与 A—F 速刷代码。

总结

题目核心知识点本次情况复杂度
A - Seats 2贪心、上界独立尝试 DFS / 记忆化 / DP，后来化简O(1)O(1)
B - mpp计数、模拟独立完成，可以进一步精简O(O(
C - Insert and Erase A不变量、双指针、分段统计独立双指针，因不变量判错 WA 1 点，后改 ACO(O(
D - Take ABC 2贪心、状态压缩式扫描独立模拟 TLE；看题解后复现线性贪心O(O(
E - Divide Graph逆向贪心、并查集看题解后复现并速刷O((N+M)α(N))O((N+M)\alpha(N))
F - Centipede Graph树形 DP、最长链合并看题解后复现并速刷O(N)O(N) / 组
G - Div. 1 & Div. 2前后缀 Top-K、线段树、离线更新战略性放弃改错O(Nlog⁡N)O(N\log N)

这场最值得保留的三条经验：

  1. 先找操作无法改变的东西。C 题中，删除全部 A 后的字符串就是不变量。
  2. 模拟超时时，不要只优化容器；要思考能否把“已经匹配到哪一步”压缩成少量计数。D 题只需记录未匹配的 A 和 AB。
  3. 权值满足“当前位大于所有低位之和”时，普通的数值最优化会变成按高位优先的字典序贪心。E 题就是这种结构。

A - Seats 2

题意

一排有 NN 个座位，要安排 MM 个人，且任意两个相邻座位不能同时坐人。判断是否可行。

约束：1≤N,M≤1001\le N,M\le 100。

核心性质

为了放下尽量多的人，应当隔一个座位坐一个人，例如：

坐 空 坐 空 坐 ...

因此最多能坐的人数为

⌈N2⌉=⌊N+12⌋.\left\lceil\frac N2\right\rceil=\left\lfloor\frac{N+1}{2}\right\rfloor.

所以答案只有一个判断：

M≤N+12.M\le \frac{N+1}{2}.

我的过程与问题

赛时从 DFS、记忆化和三维 DP 入手，其实把一道上界判断题做重了。

  • 朴素 DFS 的状态树最多有指数级分支，会重复计算。
  • map<pair<vector<int>,int>,bool> 把整段落座历史放进状态，状态过大；实际只需知道“上一位是否有人”。
  • 逆推 DP 中曾把转移固定写成 dp[n+1][...]，而正确来源应为 dp[pos+1][...]。
  • 还曾无条件写 dp[pos][cnt][last]=1，等于抹掉刚计算出的 ret。

如果练 DP，合理状态是：

dp[i][j][k]=前 i 个座位坐了 j 人，且第 i 位状态为 k 时是否可达.dp[i][j][k]=\text{前 }i\text{ 个座位坐了 }j\text{ 人，且第 }i\text{ 位状态为 }k\text{ 时是否可达}.

但本题最终应优先选择 O(1)O(1) 贪心。

参考代码（保留我的风格）

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

int main()
{
    int n,m;
    cin>>n>>m;
    int maxPeople=(n+1)/2;
    if(maxPeople>=m) cout<<"Yes"<<"\n";
    else cout<<"No"<<"\n";

    return 0;
}

易错点

  • 奇数个座位时不能写成 n/2，应写 (n+1)/2。
  • 题目只问是否存在方案，不需要真的构造座位安排。

B - mpp

题意

给定只含小写英文字母的字符串 SS。删除所有出现次数达到最大值的字符；若多个字符并列最多，则全部删除。其余字符保持原顺序输出。

约束：1≤∣S∣≤1001\le |S|\le 100。

思路

先用 cnt[26] 统计每个字母的出现次数，再求最大频率

mx=max⁡0≤i<26cnt[i].mx=\max_{0\le i<26}cnt[i].

最后重新遍历原字符串。字符 it 只有在

cnt[it−′a′]≠mxcnt[it-'a']\ne mx

时才输出。重新遍历原串天然保证相对顺序不变。

我的过程与优化

独立代码先找出所有待删除字符，再用 vis 标记每个位置。逻辑正确，但有两层不必要的处理：

  1. 不必构造 del；频率数组已经能直接判断一个字符是否应删除。
  2. 不必构造 vis；第二次扫描时直接输出即可。

参考代码（保留我的风格）

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

int main()
{
    string s;
    cin>>s;
    int cnt[26]={0};
    for(auto it:s) cnt[it-'a']++;

    int maxVal=*max_element(cnt,cnt+26);
    for(auto it:s)
    {
        if(cnt[it-'a']!=maxVal) cout<<it;
    }
    cout<<"\n";
    return 0;
}

易错点

  • 并列最大频率的字符要全部删除，不能只删一个。
  • 输出必须保持原顺序，不能按字母表顺序输出。
  • 答案可以是空串，此时仍输出换行。

C - Insert and Erase A

题意

给定大写字符串 S,TS,T。每次只能在 SS 中插入一个 A，或删除一个 A。问能否把 SS 变成 TT；若能，求最少操作数，否则输出 -1。

约束：1≤∣S∣,∣T∣≤3×1051\le |S|,|T|\le 3\times 10^5。

第一关键点：操作不变量

操作只能增删 A，所以所有非 A 字符本身及其相对顺序都无法改变。

定义 f(X)f(X) 表示从字符串 XX 中删除全部 A 后得到的字符串，则可行的充要条件为

f(S)=f(T).f(S)=f(T).

这里必须比较字符串，而不能只比较每种非 A 字符的数量。

例如：

S = BAC
T = CAB

二者各字符计数相同，但非 A 序列分别为 BC 和 CB，无论怎样增删 A 都不能互相转化。

这正是最初双指针 WA 一个点的根因：只比较了非 A 字符数量，没有检查相对顺序。

此外，字符均为大写字母。若用数组计数，下标必须写 S[i]-'A'，不能写 S[i]-'a'，否则会出现负下标越界。

第二关键点：答案为何是每段 A 数量差

设两串共同的非 A 骨架为

c1c2⋯ck.c_1c_2\cdots c_k.

每个非 A 字符之间，包括字符串首尾，都对应一段 A。若 S,TS,T 在第 ii 段分别有 xi,yix_i,y_i 个 A，那么这一段至少需要

∣xi−yi∣|x_i-y_i|

次增删，并且这样操作一定能做到。因此最少操作数是

∑i=0k∣xi−yi∣.\boxed{\sum_{i=0}^{k}|x_i-y_i|}.

分段双指针

两个指针分别扫描 S,TS,T：

  1. 统计当前位置开始的连续 A 数量 cntAS、cntAT。
  2. 将差值的绝对值加入答案。
  3. 若两串都结束，则处理完成。
  4. 若只有一串结束，说明非 A 骨架长度不同，输出 -1。
  5. 若下一对非 A 字符不同，说明骨架顺序不同，输出 -1。
  6. 跳过这一对相同的非 A 字符，继续处理下一段。

参考代码（保留我的风格）

#include <iostream>
using namespace std;

int main()
{
    string S,T;
    cin>>S>>T;
    int n=S.size(),m=T.size();
    int p1=0,p2=0;
    int ans=0;

    while(p1<n||p2<m)
    {
        int cntAS=0,cntAT=0;
        while(p1<n&&S[p1]=='A')
        {
            cntAS++;
            p1++;
        }
        while(p2<m&&T[p2]=='A')
        {
            cntAT++;
            p2++;
        }

        if(p1==n&&p2==m)
        {
            ans+=abs(cntAS-cntAT);
            break;
        }

        if(p1==n||p2==m)
        {
            cout<<"-1"<<"\n";
            return 0;
        }

        if(S[p1]!=T[p2])
        {
            cout<<"-1"<<"\n";
            return 0;
        }

        ans+=abs(cntAS-cntAT);
        p1++,p2++;
    }
    cout<<ans<<"\n";

    return 0;
}

复杂度

两个指针都只向右移动：

T=O(∣S∣+∣T∣),S=O(1).T=O(|S|+|T|),\qquad S=O(1).

易错点

  • “各非 A 字符数量相同”不是充分条件，必须比较非 A 序列。
  • while(p1<n||p2<m) 内每次访问字符前都要判断边界。
  • 别忘了在匹配一对非 A 字符后执行 p1++,p2++。

D - Take ABC 2

题意

字符串只含 A、B、C。一次操作选择下标 i<j<ki<j<k，满足字符依次为 A、B、C，然后删除它们。求最多能操作多少次。

约束：1≤∣S∣≤1061\le |S|\le 10^6。

赛时思路为什么 TLE

最初做法枚举 A，再向后找未使用的 B，再找未使用的 C。即使使用 vis 或预存三类字符下标，本质仍在反复向后搜索，最坏复杂度接近

O(∣S∣3),O(|S|^3),

而 ∣S∣|S| 可达 10610^6，必然超时。20 AC / 15 TLE 和 22 AC / 13 TLE 说明优化了常数或部分数据，却没有改变复杂度量级。

正解：扫描时维护匹配进度

从左到右扫描，只需要两个计数：

  • cntA：已经出现、但尚未与 B 匹配的 A 数量；
  • cntAB：已经匹配成 AB、但尚未等待到 C 的数量。

遇到不同字符时：

  • A：加入候选，cntA++；
  • B：若有可用 A，消耗一个 A，形成一个 AB；
  • C：若有可用 AB，消耗一个 AB，完成一次操作。

为什么局部贪心正确

遇到 B 时，只要左边有未匹配的 A，立刻配对不会让未来更差：所有未来的 C 都在这个 B 右侧，而保留某个更早的 A 没有额外价值。

同理，遇到 C 时立刻消耗一个已有 AB 也不会损失后续方案。每次匹配都只取当前字符左侧已经合法形成的前缀，因此始终满足下标顺序 i<j<ki<j<k。

参考代码（保留我的风格）

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

int main()
{
    string s;cin>>s;
    int cntA=0,cntAB=0,ans=0;
    for(auto it:s)
    {
        if(it=='A') cntA++;
        else if(it=='B')
        {
            if(cntA>=1)
            {
                cntAB++;
                cntA--;
            }
        }
        else
        {
            if(cntAB>=1)
            {
                ans++;
                cntAB--;
            }
        }
    }

    cout<<ans<<"\n";
    return 0;
}

复杂度

T=O(∣S∣),S=O(1).T=O(|S|),\qquad S=O(1).

可迁移经验

当题目要求按顺序选出一个短模式（如 ABC），并且每个字符只能使用一次时，可以尝试维护各匹配阶段的数量，而不是枚举具体下标。

E - Divide Graph

本题赛时不会，以下为看题解后复现与速刷所得。

题意

给定一个连通无向简单图，边按输入顺序编号为 1∼M1\sim M，第 ii 条边的删除代价为 2i2^i。删除若干边，使图恰好变成两个连通块，求最小删除总代价。最终只对答案取模 998244353998244353。

约束：2≤N,M≤2×1052\le N,M\le 2\times 10^5（并满足题目中的图边数约束）。

权值的特殊性质

对任意 ii，有

2i>∑j=1i−12j=2i−2.2^i>\sum_{j=1}^{i-1}2^j=2^i-2.

因此一条编号更大的边，比所有编号更小的边代价之和还大。最小化删除总代价时，决策优先级是：

  1. 尽量不删除编号最大的边；
  2. 再尽量不删除次大的边；
  3. 依此类推。

注意：题目最小化的是真实整数代价，不能拿取模后的数比较大小。取模只用于输出答案。

从“删边”改看成“留边”

从空图开始，按边编号从大到小考虑是否保留。

  • 当前边两端已连通：保留它只会成环，不改变连通块数量，当然无需删除。
  • 两端不连通，且当前连通块数 components>2：保留它并合并两个连通块。
  • 两端不连通，且 components==2：再保留就会使整张图连通，违反“恰好两个连通块”，所以必须删除，并把 2i2^i 加入答案。

这个过程就是逆向 Kruskal 风格的贪心，并查集负责判断两端是否已经连通。

正确性要点

按编号从大到小处理时，当前边的删除代价大于所有尚未处理边的总代价。只要保留当前边仍有可能最终得到两个连通块，就一定应保留；任何为了删除它而保留若干低编号边的方案都会更贵。

当只剩两个连通块时，连接二者的边必须删掉；同一连通块内部的边无需删除，因为它不会减少连通块数量。

参考代码（保留我的风格）

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int mod=998244353;

class UnionSet{
public:
    vector<int> fa,size;
    UnionSet(int n):fa(n+1),size(n+1)
    {
        for(int i=0;i<=n;i++)
        {
            fa[i]=i;
            size[i]=1;
        }
    }

    int get(int x)
    {
        return fa[x]=(x==fa[x]?x:get(fa[x]));
    }

    void merge(int a,int b)
    {
        int aa=get(a),bb=get(b);
        if(aa==bb) return;
        fa[aa]=bb;
        size[bb]+=size[aa];
    }
};

signed main()
{
    int n,m;
    cin>>n>>m;
    vector<PII> edges(m+1);
    vector<int> pow2(m+1);
    pow2[0]=1;

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        edges[i]={u,v};
        pow2[i]=(pow2[i-1]*2)%mod;
    }

    UnionSet uf(n);
    int components=n;
    int ans=0;

    for(int i=m;i>=1;i--)
    {
        int u=edges[i].first;
        int v=edges[i].second;
        int uu=uf.get(u),vv=uf.get(v);
		
        //if(u!=v)
        //是uu!=vv,不是u!=v!!!!!!!!!!!!!!!
        if(uu!=vv)
        {
            if(components>2)
            {
                uf.merge(uu,vv);
                components--;
            }
            else ans=(ans+pow2[i])%mod;
        }
    }
    cout<<ans<<"\n";

    return 0;
}

复杂度

并查集使用路径压缩：

T=O((N+M)α(N)),S=O(N+M).T=O((N+M)\alpha(N)),\qquad S=O(N+M).

易错点

  • 必须从 m 到 1 逆序枚举边。
  • 初始连通块数量是 n；只有真正合并两个不同集合时才减一。
  • components==2 时只删除连接两个不同连通块的边；块内成环边不用删。
  • 预处理的是 2i mod 9982443532^i\bmod 998244353，其中 pow2[0]=1。

F - Centipede Graph

本题赛时不会，以下为看题解后复现与速刷所得。

题意

长度为 kk 的蜈蚣图有一条包含 kk 个点的主链，主链上的每个点各连接两个只属于它的叶子，因此总点数为 3k3k。给定一棵树，求其中作为子图出现的最大蜈蚣长度。共有 QQ 组测试，所有测试的 NN 之和不超过 2×1052\times 10^5。

结构观察

蜈蚣主链上的点需要：

  • 两条边连接自己的两个叶子；
  • 若是主链内部点，还需要两条主链边，总度数至少为 44；
  • 若是主链端点，只需要一条主链边，总度数至少为 33；
  • 当 k=1k=1 时，唯一主链点只需连接两个叶子，总度数至少为 22。

由于只要求“子图”而不是“诱导子图”，原树上多余的边可以不选。

DP 定义

把树任意定根。定义

dp[u]=从 u 向其子树方向延伸的一条最长蜈蚣主链长度.dp[u]=\text{从 }u\text{ 向其子树方向延伸的一条最长蜈蚣主链长度}.

这里默认主链还可以通过 uu 的父边继续向上，因此：

  • son>=3：除父边外，uu 至少有三个孩子；可拿两个孩子当叶子，再选一个孩子方向延伸主链，故 dp[u]=mx+1。
  • son==2：两个孩子只能当叶子，uu 可以作为这条向下链的端点，故 dp[u]=1。
  • son<=1：连两个叶子都凑不齐，故 dp[u]=0。

其中 mx 是所有子节点 dp[v] 的最大值。

用每个点作为拼接中心更新答案

设 mx,sx 为子节点中最大、次大的 dp：

  • deg[u]==2：可以单独构成长度 11 的蜈蚣。
  • deg[u]==3：uu 作为主链端点，向一个孩子方向延伸，答案候选为 mx+1。
  • deg[u]>=4：uu 可作为主链内部点，拼接两个孩子方向，答案候选为 mx+sx+1。

“向父亲方向延伸”的答案不会漏掉，因为整条主链总有一个相对当前根深度最小的点；在这个点处，主链的其余部分都落在它的孩子方向中。

参考代码（保留我的风格）

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> g[N];//邻接表
int deg[N];
int ans;
int dp[N];

void dfs(int u,int fa)
{
    int mx=-1,sx=-1;
    int son=0;

    for(auto v:g[u])
    {
        if(v==fa) continue;
        son++;
        dfs(v,u);
        int val=dp[v];
        if(val>mx) sx=mx,mx=val;
        else if(val>sx) sx=val;
    }

    if(son>=3) dp[u]=mx+1;
    else if(son==2) dp[u]=1;
    else dp[u]=0;

    int total_deg=deg[u];

    if(total_deg==2) ans=max(ans,1);
    else if(total_deg==3)
    {
        if(mx!=-1) ans=max(ans,mx+1);
    }
    else if(total_deg>=4)
    {
        if(mx!=-1&&sx!=-1) ans=max(ans,mx+sx+1);
    }
}

void solve()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++) g[i].clear();
    fill(deg,deg+1+n,0);

    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++,deg[v]++;
    }
    ans=0;

    dfs(1,0);
    cout<<ans<<"\n";
}

int main()
{
    int q;cin>>q;
    while(q--) solve();
    return 0;
}

复杂度

每条树边只访问常数次：

T=O(N),S=O(N)T=O(N),\qquad S=O(N)

每组如此；所有测试总复杂度为 O(∑N)O(\sum N)。

易错点

  • 树有 N−1N-1 条边，读边循环不能写成 NN 次。
  • 多组测试必须清空邻接表和 deg；ans 也要重新置零。
  • son 不包含父节点，而 deg[u] 包含父节点，两者不能混用。
  • son==2 时是 dp[u]=1，不是 dp[u]=mx：两个孩子都必须留给叶子。
  • 代码注释中的 mx,sx 应称为“最大、次大”，不是“最小、次小”。
  • 递归深度最坏可达 2×1052\times10^5；若平台栈空间严格，可改为迭代 DFS 加逆序处理。

G - Div. 1 & Div. 2

本题按当前学习进度战略性放弃改错：DP 尚未完全学完，线段树为零基础。这里不强行背代码，只记录题目结构和未来回看入口。

题意

有 NN 道候选题，第 ii 道题难度为 ii、类型为 KiK_i、兴趣值为 AiA_i。按难度递增选择六题

i1<i2<i3<i4<i5<i6.i_1<i_2<i_3<i_4<i_5<i_6.

其中：

  • Div. 2 使用 i1,i2,i3,i4i_1,i_2,i_3,i_4，四题类型两两不同；
  • Div. 1 使用 i3,i4,i5,i6i_3,i_4,i_5,i_6，四题类型两两不同。

求六题兴趣值之和的最大值；不存在合法选择则输出 -1。

难点拆解

两场比赛共享中间两题 i3,i4i_3,i_4。固定它们后，需要：

  • 在 i3i_3 左侧选两个题，类型彼此不同，且都不能等于 Ki3,Ki4K_{i_3},K_{i_4}；
  • 在 i4i_4 右侧选两个题，类型彼此不同，且都不能等于 Ki3,Ki4K_{i_3},K_{i_4}。

暴力枚举六个下标显然不可行。即便只枚举 i3,i4i_3,i_4，仍有 O(N2)O(N^2) 对，需要进一步把“某个区间内排除少量类型后的最大两项和”压缩成可快速查询的信息。

题解代码的主线（只建立地图）

本地题解采用以下结构：

  1. L[i]：前缀中按兴趣值保存类型互异的 Top 4。
  2. R[i]：后缀中按兴趣值保存类型互异的 Top 4。
  3. 固定 i3i_3 时，把 Ai3A_{i_3} 与左侧可选的最佳两题合并为 M(i3)M(i_3)。
  4. 枚举 i4i_4 的类型，临时排除该类型对各个 M(i3)M(i_3) 的影响。
  5. 用线段树在区间 [0,i4)[0,i_4) 中查询类型互异的 Top 4 候选。
  6. 再结合 i4i_4 右侧的 Top 候选完成答案更新，之后回滚临时修改。

为什么只保留很小的 Top-K：每次查询至多排除共享题的少数几个类型。若前几名冲突，继续往后看有限个候选就足够；不需要保存整个区间的所有题。

当前阶段的学习顺序

不建议现在直接背 248 行题解。更合理的顺序是：

  1. 学会线段树的单点修改与区间查询。
  2. 理解幺半群：节点保存什么信息、两个节点如何 op 合并、单位元 e 是什么。
  3. 单独练习“区间内不同颜色 / 类型的 Top-K”问题。
  4. 再看前后缀 Top-K 与离线按类型修改。
  5. 最后回到本题，逐段验证 L/R、change、SegTree 和答案拼接。

暂不改错的理由

本题同时要求线段树、Top-K 状态合并、按类型离线修改与回滚。基础尚未补齐时，逐行改错很容易变成记实现而不理解状态。当前把 A—F 的贪心、并查集和树形 DP 吃透，收益更高。

本场错因清单

复杂度

  • A：没有先推最大容量，过早使用 DFS / DP。
  • D：用三层搜索模拟选下标，没有根据 10610^6 的数据范围反推必须接近 O(N)O(N)。

不变量

  • C：只检查了非 A 字符计数，漏掉“非 A 字符相对顺序不变”。

数组下标

  • C：大写字母应减 'A'；减 'a' 会产生负下标。

DP 状态和转移

  • A：把 pos+1 错写成固定的 n+1，并且没有把 ret 写回状态。
  • F：要区分孩子数量 son 与无根树中的总度数 deg[u]。

多组测试

  • F：邻接表、度数与全局答案都必须清空。

后续复习建议

  1. 短期重写：不看代码重写 C、D，重点口述不变量和贪心正确性。
  2. 并查集巩固：找两道“逆序加边”题，熟悉把删边问题转成加边问题。
  3. 树形 DP 巩固：练习树上最长链、树的直径、选最大与次大子树贡献。
  4. 线段树前置：先掌握单点修改、区间和 / 最大值，再学习自定义节点合并。
  5. 最后回看 G：能独立写通用线段树后，再拆解 Top-K 幺半群和离线回滚。

复习时最好能独立回答：

  • A 为什么是 (N+1)/2(N+1)/2？
  • C 为什么删除所有 A 后的字符串必须完全相同？
  • D 的 cntA、cntAB 分别代表什么？
  • E 为什么必须逆序处理边？
  • F 为什么 son==2 时 dp[u]=1？

能不看代码说明这五点，才算真正把本场核心内容消化下来。