AtCoder Beginner Contest 452 复盘

整理来源：7.29 目录
题目列表：AtCoder Beginner Contest 452

完成情况

题目	状态	核心知识点
A - Gothec	独立 AC	模拟、条件判断
B - Draw Frame	独立 AC	二维网格、边界判断
C - Fishbones	尝试 TLE，学习题解后掌握	存在性预处理、状态压缩
D - No-Subsequence Substring	学习题解后掌握	DP、子序列自动机思想、逆序更新
E - You WILL Like Sigma Problem	学习题解后掌握	按商分块、前缀和、调和级数
F - Interval Inversion Count	学习题解后掌握	恰好转为至多、双指针、树状数组
G - 221 Substring	战略性放弃改错	RLE、后缀数组、LCP

---

A - Gothec

题意

给定公历中的月 $M$ 和日 $D$，判断它是否为五节句之一：

$$(1,7),(3,3),(5,5),(7,7),(9,9).$$

若是则输出 Yes，否则输出 No。

思路

数据范围极小，直接依次判断五个日期即可。

代码

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

void solve()
{
    int m,d;
    cin>>m>>d;
    if(m==1&&d==7)
    {
        cout<<"Yes"<<"\n";
        return;
    }
    if(m==3&&d==3)
    {
        cout<<"Yes"<<"\n";
        return;
    }
    if(m==5&&d==5)
    {
        cout<<"Yes"<<"\n";
        return;
    }
    if(m==7&&d==7)
    {
        cout<<"Yes"<<"\n";
        return;
    }
    if(m==9&&d==9)
    {
        cout<<"Yes"<<"\n";
        return;
    }
    cout<<"No"<<"\n";
}

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

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

---

B - Draw Frame

题意

给定一个 $H\times W$ 的网格，将边框上的格子涂成 #，其余格子涂成 .，输出最终网格。

思路

枚举每个格子 $(i,j)$。它位于边框上的充要条件为：

$$i=1\quad\text{或}\quad i=H\quad\text{或}\quad j=1\quad\text{或}\quad j=W.$$

代码

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

void solve()
{
    int h,w;
    cin>>h>>w;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(i==1||i==h||j==1||j==w)
            {
                cout<<"#";
            }
            else cout<<".";
        }
        cout<<"\n";
    }
}

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

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

---

C - Fishbones

题意

鱼骨由一根脊柱和 $N$ 根肋骨组成。脊柱上写一个长度为 $N$ 的字符串。第 $i$ 根肋骨上写一个长度为 $A_i$ 的字符串，并要求它的第 $B_i$ 个字符等于脊柱的第 $i$ 个字符。

所有字符串都必须从给定的 $M$ 个字符串中选择，同一个字符串可以重复使用。对每个给定字符串 $S_j$，判断它能否作为脊柱。

最初尝试与 TLE 原因

最初将字符串按长度分组。对每个候选脊柱的每个位置，再遍历长度为 $A_i$ 的整组字符串寻找匹配项。

即使按长度分组，最坏情况下 $M$ 个字符串的长度全部相同，复杂度仍然为：

$$O(NM^2),$$

其中 $M\le 2\times 10^5$，一定会超时。

按长度分组只缩小了搜索范围，却没有消除对相同问题的重复搜索。

核心转化：只记录“是否存在”

一根肋骨是否可选，只由以下三个信息决定：

1. 字符串长度；
2. 要检查的位置；
3. 该位置所需的字符。

而 $A_i,B_i\le 10$，字符只有 26 种，所以预处理：

$$\operatorname{exists}[\ell][p][c] = \begin{cases} \mathrm{true},&\text{存在长度为 }\ell\text{ 且第 }p\text{ 位为 }c\text{ 的字符串},\\ \mathrm{false},&\text{否则}. \end{cases}$$

这样，每根肋骨的查询从遍历一组字符串变成 $O(1)$ 查表。

各根肋骨可以独立选择字符串，因此候选脊柱 $s$ 合法的充要条件是：

$$|s|=N \quad\text{且}\quad \forall i\in[1,N], \operatorname{exists}[A_i][B_i-1][s_{i-1}]=\mathrm{true}.$$

代码

#include <bits/stdc++.h>
using namespace std;
const int N=20;
int n,m;
int A[N],B[N];
vector<string> S;

bool exists[N][N][26];//预处理数组

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>A[i]>>B[i];
    cin>>m;
    S.resize(m);
    for(int i=0;i<m;i++)
    {
        cin>>S[i];

        //预处理
        int len=S[i].size();
        for(int pos=0;pos<len;pos++)
        {
            exists[len][pos][S[i][pos]-'a']=true;
        }
    }

    for(const auto& s:S)
    {
        if((int)s.size()!=n)
        {
            cout<<"No"<<"\n";
            continue;
        }

        int flag=1;
        for(int i=1;i<=n;i++)
        {
            //这里s的下标也是base-0!!!!!!!!!!
            if(!exists[A[i]][B[i]-1][s[i-1]-'a'])
            {
                flag=0;
                break;
            }
        }

        cout<<(flag?"Yes":"No")<<"\n";
    }
}

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

预处理和查询都只需扫描每个字符串至多 10 个字符，因此时间复杂度为 $O(MN)$，空间复杂度为 $O(10\times10\times26+M)$。

易错点

• $B_i$ 是 1-based，字符串下标是 0-based，所以使用 B[i]-1。
• 第 $i$ 根肋骨对应脊柱的第 $i$ 个字符；代码中 i 为 1-based，所以使用 s[i-1]。
• 找到一个满足条件的肋骨字符串就足够，因为题目允许重复使用字符串，各根肋骨之间没有冲突。
• 当状态空间很小而询问很多时，要考虑将重复的“搜索”压缩为“存在性查表”。

---

D - No-Subsequence Substring

题意

统计 $S$ 的非空连续子串中，有多少个不包含 $T$ 作为子序列。相同字符串若来自不同位置，仍分别计数。

约束为：

$$|S|\le 2\times 10^5,\qquad |T|\le 50.$$

不能枚举所有 $O(|S|^2)$ 个子串，但 $T$ 很短，可以把“与 $T$ 的匹配进度”作为 DP 状态。

DP 状态

扫描 $S$，处理当前字符后，定义：

$$\begin{aligned} dp[j]=\#\{\, &\text{以当前位置结尾、能匹配 }T\text{ 的前 }j\text{ 个字符，}\\ &\text{但不能匹配前 }j+1\text{ 个字符的子串}\,\}. \end{aligned}$$

这里的匹配是子序列匹配。因此 $j$ 是该子串能匹配的 $T$ 的最长前缀长度。

• $dp[0]$：连 $T_1$ 都不能匹配；
• $dp[|T|]$：已经包含完整的 $T$，不合法；
• $\sum_{j=0}^{|T|-1}dp[j]$：以当前位置结尾的合法子串数。

状态转移

每处理一个字符 ch：

1. dp[0]++：加入只包含当前字符的新子串，先假设它匹配 0 个字符；
2. 若 ch==T[i]，则原来匹配长度为 $i$ 的所有子串都能推进到 $i+1$：

$$dp[i+1]\mathrel{+}=dp[i],\qquad dp[i]=0;$$

3. 累加 $dp[0],\ldots,dp[|T|-1]$。

若 ch==T[0]，刚刚加入 dp[0] 的单字符子串会在处理 $i=0$ 时转入 dp[1]；否则它自然留在 dp[0]。

为什么必须逆序更新

i 必须从 $|T|-1$ 递减到 0，确保转移使用的是上一轮的旧状态。同一个 ch 不能在一轮中连续匹配 $T$ 的多个位置。

这与 0/1 背包逆序更新的原因相同：避免本轮刚产生的 dp[i] 又被本轮重复使用。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string S,T;
ll dp[60];//dp[len]:以当前字符结尾,并且与T匹配长度为len的子串个数
ll ans;

void solve()
{
    cin>>S>>T;
    int lenT=T.size();
    for(auto ch:S)
    {
        //新增只由当前字符组成的子串
        dp[0]++;

        //逆序更新,保证使用的是上一轮的旧值
        for(int i=lenT-1;i>=0;i--)
        {
            if(T[i]==ch)
            {
                //dp的下标表示匹配长度,所以i+1可以取到lenT
                dp[i+1]+=dp[i];
                dp[i]=0;
            }
        }

        //dp[lenT]已经包含完整的T,不能计入答案
        for(int i=0;i<lenT;i++) ans+=dp[i];
    }

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

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

时间复杂度为 $O(|S||T|)$，空间复杂度为 $O(|T|)$。答案最大为 $\frac{|S|(|S|+1)}{2}$，必须使用 long long。

易错点

• dp[j] 不是“匹配方案数”，而是按最长可匹配前缀长度分类后的子串个数。
• 这里统计的是连续子串，但判定条件中的 $T$ 是不要求连续的子序列。
• dp[0]++ 对应每个右端点新产生的单字符子串。
• 更新必须逆序，否则一个当前字符可能被重复使用。
• dp[lenT] 是不合法状态，可以继续维护，但不能加入答案。

---

E - You WILL Like Sigma Problem

题意

计算：

$$\sum_{i=1}^{N}\sum_{j=1}^{M}A_iB_j(i\bmod j)\pmod{998244353}.$$

其中 $N,M\le 5\times10^5$。直接枚举 $(i,j)$ 的复杂度为 $O(NM)$，无法通过。

第一步：交换求和顺序

固定 $j$：

$$\mathrm{Ans} =\sum_{j=1}^{M}B_j\left(\sum_{i=1}^{N}A_i(i\bmod j)\right).$$

第二步：按商分组

令：

$$k=\left\lfloor\frac{i}{j}\right\rfloor.$$

对于固定的 $j,k$，满足该商的 $i$ 构成闭区间：

$$L=\max(1,kj),\qquad R=\min(N,(k+1)j-1).$$

区间内有：

$$i\bmod j=i-kj.$$

所以该段贡献为：

$$\begin{aligned} \sum_{i=L}^{R}A_i(i-kj) &=\sum_{i=L}^{R}A_i\cdot i-\sum_{i=L}^{R}A_i(kj)\\ &=\sum_{i=L}^{R}A_i\cdot i-kj\sum_{i=L}^{R}A_i. \end{aligned}$$

这里没有丢掉 $-kj$，它被作为常数提出求和号，形成第二项。本题只使用加、减、乘，不需要逆元。

第三步：两个 1-based 前缀和

按照自己的习惯，数组和前缀和都使用 1-based：

$$\mathrm{sum1}[i]=\sum_{x=1}^{i}A_x, \qquad \mathrm{sum2}[i]=\sum_{x=1}^{i}A_x\cdot x.$$

闭区间 $[L,R]$ 的两种和为：

$$\sum_{i=L}^{R}A_i=\mathrm{sum1}[R]-\mathrm{sum1}[L-1],$$ $$\sum_{i=L}^{R}A_i\cdot i=\mathrm{sum2}[R]-\mathrm{sum2}[L-1].$$

因此每个分块能在 $O(1)$ 内求出。

复杂度

对每个 $j$，枚举约 $\left\lfloor N/j\right\rfloor+1$ 个商。总次数为：

$$O\left(M+\sum_{j=1}^{M}\left\lfloor\frac{N}{j}\right\rfloor\right) =O(M+N\log N).$$

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
const int MOD=998244353;
int n,m;
int A[N],B[N];
int sum1[N];//A_i求和
int sum2[N];//A_i*i求和

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=1;i<=m;i++) cin>>B[i];

    //base-1前缀和
    for(int i=1;i<=n;i++)
    {
        sum1[i]=(sum1[i-1]+A[i])%MOD;
        sum2[i]=(sum2[i-1]+(A[i]*i)%MOD)%MOD;
    }

    auto range_sum1=[&](int l,int r)
    {
        if(l>r) return 0LL;
        return (sum1[r]-sum1[l-1]+MOD)%MOD;
    };

    auto range_sum2=[&](int l,int r)
    {
        if(l>r) return 0LL;
        return (sum2[r]-sum2[l-1]+MOD)%MOD;
    };

    int ans=0;
    for(int j=1;j<=m;j++)
    {
        int total=0;
        //按k划分区间,k=floor(i/j)
        for(int k=0;k*j<=n;k++)
        {
            int L=max(1LL,k*j);//防止L为0
            int R=min((k+1)*j-1,n);//防止R超过n

            if(L>R) continue;
            int sum_Aii=range_sum2(L,R);
            int sum_Ai=range_sum1(L,R);
            int contribute=(sum_Aii-(k*j)%MOD*sum_Ai%MOD+MOD)%MOD;
            total=(total+contribute)%MOD;
        }
        ans=(ans+total*B[j]%MOD)%MOD;
    }

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

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

易错点

• N 是数组容量常量，n 才是实际输入规模；循环边界和 R 必须使用 n。
• 明确使用 1-based 闭区间前缀和，不要与“sum[i] 表示前 $i$ 个数”的 0-based 写法混用。
• $k=0$ 时数学区间从 0 开始，但有效下标从 1 开始，所以 L=max(1LL,k*j)。
• 模意义下做前缀和差必须加 MOD 再取模，避免 C++ 的负余数。
• 复杂度中的内层循环次数是调和级数，不是 $O(NM)$。

---

F - Interval Inversion Count

题意

给定 $1\sim N$ 的排列 $P$ 和整数 $K$，求有多少个连续子区间 $[l,r]$，其内部逆序对数恰好为 $K$。

一个逆序对是满足以下条件的下标对：

$$l\le i<j\le r,\qquad P_i>P_j.$$

例如 $(6,3,2)$ 中有 $(6,3),(6,2),(3,2)$ 三个逆序对。

第一步：将“恰好”转成“至多”

定义：

$$f(x)=\#\{[l,r]\mid \operatorname{inv}(P_l,\ldots,P_r)\le x\}.$$

那么：

$$\#\{\operatorname{inv}=K\}=f(K)-f(K-1).$$

“逆序对数至多 $x$”具有单调性，适合使用双指针；“恰好 $K$”本身不方便直接维护。

第二步：双指针维护窗口

维护左闭右开窗口 $[l,r)$，r 表示下一个准备加入的位置。

固定 $l$ 时不断扩展 $r$，直到再加入 $P_r$ 就会使逆序对数超过 $x$。此时右端点可以取：

$$l,l+1,\ldots,r-1,$$

共有 $r-l$ 个合法区间。

删除元素只会减少逆序对，所以当 $l$ 右移时，r 不需要回退。左右指针都只移动 $O(N)$ 次。

第三步：Fenwick 树维护窗口中的值域计数

树状数组的下标不是排列位置，而是元素值：

$$\text{bit}[v]=\text{当前窗口中值 }v\text{ 的出现次数}.$$

因此 bit.sum(v) 表示窗口内值不超过 $v$ 的元素个数。

加入右端点

加入 val=P[r] 前，当前窗口为 $[l,r)$，大小为 $r-l$，且窗口内所有元素都位于 val 左侧。新增逆序对数为窗口内大于 val 的元素数：

$$\begin{aligned} \mathrm{add} &=(r-l)-\operatorname{count}(\le \mathrm{val})\\ &=(r-l)-\operatorname{bit.sum}(\mathrm{val}). \end{aligned}$$

这里不能写 $r-l+1$，因为 P[r] 还没有进入窗口和树状数组。

删除左端点

删除 val=P[l] 前，窗口内其余元素都位于它右侧。它参与的逆序对数就是右侧小于它的元素数：

$$\operatorname{count}(<\mathrm{val})=\operatorname{bit.sum}(\mathrm{val}-1).$$

所以先从 now 中减去该值，再从树状数组删除 val。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int n,k;
int P[N];

class Fenwick
{
    int n;
    vector<int> b;
    inline int lowbit(int x)
    {
        return x&(-x);
    }
public:
    Fenwick(int _n):n(_n),b(_n+1){}

    void add(int pos,int val)
    {
        while(pos<=n)
        {
            b[pos]+=val;
            pos+=lowbit(pos);
        }
    }

    int sum(int pos)
    {
        int ret=0;
        while(pos>0)
        {
            ret+=b[pos];
            pos-=lowbit(pos);
        }
        return ret;
    }
};

void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>P[i];

    auto calc=[&](int k)
    {
        if(k<0) return 0LL;

        Fenwick bit(n);
        int now=0;//统计当前窗口中的逆序对个数
        int ans=0;
        int r=1;////右指针不能回退!!!!!!!

        for(int l=1;l<=n;l++)
        {
            if(r<l) r=l;
            while(r<=n)
            {
                int val=P[r];
                //因为r为右端点,所以当前窗口内的元素都在r的左边
                //大于val的元素个数=窗口大小-小于等于val的个数
                int add=(r-l)-bit.sum(val);//增加的逆序对个数

                if(now+add>k) break;

                now+=add;
                bit.add(val,1);
                r++;
            }

            //以l为左端点,右端点可以取l到r-1,一共r-l个
            ans+=r-l;

            //左端点出窗口
            int val=P[l];
            //窗口中所有小于左端点的数都在它右侧
            now-=bit.sum(val-1);
            bit.add(val,-1);
        }
        return ans;
    };

    //逆序对恰好为k = 逆序对<=k - 逆序对<=k-1
    int fk=calc(k);
    int minus=calc(k-1);

    cout<<fk-minus<<"\n";
}

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

时间复杂度为 $O(N\log N)$：双指针总共移动 $O(N)$ 次，每次树状数组操作为 $O(\log N)$，calc 调用两次不改变量级。空间复杂度为 $O(N)$。

易错点

• 题目求的是连续子区间的逆序对数，不是整个排列的逆序对数。
• r 必须在枚举 l 的循环外定义且不能回退；若每轮写 int r=l，会退化为 $O(N^2\log N)$，并破坏窗口状态。
• 树状数组按“值”存出现次数，不是按原数组下标存值。
• 窗口是 $[l,r)$，P[r] 尚未加入，所以当前窗口大小为 r-l。
• 删除 P[l] 时，它仍在树状数组中；查询 sum(val-1) 不会把它自己计入。
• 区间个数和逆序对数都可能超过 int，需要 long long。

---

G - 221 Substring

当前策略

本题涉及后缀数组（SA）和最长公共前缀数组（LCP）。目前尚未系统学习这两个算法，因此战略性放弃代码改错，不把一份不理解的模板当作已经掌握。

建议学习顺序：

1. 游程编码（RLE）；
2. 后缀数组的含义与构造；
3. Kasai 算法求 LCP；
4. 利用 SA 与 LCP 统计本质不同子串；
5. 再回到本题处理“不含分隔符 0”的限制。

题意

若序列的每个极长相同值段中，“连续长度”等于“元素值”，则称其为 221 序列。

例如：

$$(2,2,3,3,3,1,2,2)$$

的游程编码为 $(2,2),(3,3),(1,1),(2,2)$，每段的值与长度相等，所以合法。

题目要求统计原序列 $A$ 的连续子数组中，本质不同的非空 221 序列个数。相同内容即使出现在不同位置，也只计算一次。

官方转化概要

先对 $A$ 做游程编码，得到若干对 $(v_i,m_i)$，其中 $v_i$ 是值，$m_i$ 是该段长度。

一个 221 子数组横跨第 $l\sim r$ 个游程时：

• 首尾游程可以只截取一部分，因此要求 $v_l\le m_l,\ v_r\le m_r$；
• 中间游程必须完整包含，因此要求 $v_i=m_i\quad(l<i<r)$。

将每个游程替换为：

$$(v_i,m_i)\longrightarrow \begin{cases} (0),&v_i>m_i,\\ (v_i),&v_i=m_i,\\ (v_i,0,v_i),&v_i<m_i. \end{cases}$$

其中 0 是不可跨越的分隔符。这样，原序列中本质不同的 221 子数组，与新序列 $T$ 中本质不同且不含 0 的非空子数组一一对应。

SA + LCP 的计数式

定义 zerofree[p] 为从 $T_p$ 开始向右连续非 0 元素的数量。按字典序枚举后缀，当前后缀起点为 $sa[i]$，它最多产生长度为 zerofree[sa[i]] 的合法前缀。

与前一个后缀重复的前缀长度为 lcp[i-1]，所以当前后缀新增的本质不同合法子数组数为：

$$\max\left(0,\ \text{zerofree}[sa[i]]-\text{lcp}[i-1]\right).$$

对所有后缀求和即可。

暂不纳入代码

本题的主要难点不是照抄 SA 模板，而是理解以下两层一一对应：

1. 221 子数组与 $T$ 中不含 0 的子数组；
2. 每个本质不同子数组由后缀数组中的某个后缀首次贡献。

等掌握 SA 和 LCP 后，再独立实现并验证本题。当前不把 AI 生成的倍增 SA 代码作为已掌握代码记录。

---

本场总结

值得沉淀的模式

1. 小状态空间 + 大量存在性查询：像 C 一样预处理为布尔状态，避免反复遍历候选集合。
2. 固定一个短模式串：像 D 一样，把与短串的匹配进度作为 DP 状态。
3. 整除、取模表达式：像 E 一样按商相同的区间分块，再用前缀和求段贡献。
4. 求“恰好为 $K$”困难：尝试转化为“至多 $K$”减“至多 $K-1$”，后者往往具有单调性。
5. 窗口内的顺序统计：Fenwick 树可按值维护出现次数，快速查询小于、至多、大于某值的元素数量。
6. 不会的高级模板不要硬抄：G 先记转化，等学完 SA/LCP 后再补，学习收益更高。

下标习惯

本场多次出错都与下标语义有关。写代码前先明确：

• 原数组是 0-based 还是 1-based；
• 前缀和表示 $[1,i]$ 还是 $[0,i)$；
• 双指针窗口是 $[l,r]$ 还是 $[l,r)$；
• 状态下标表示“字符位置”还是“已匹配长度”。

不要只看变量名，要把区间与状态定义直接写在注释里。