AtCoder Beginner Contest 477

点击查看题面

A - Traffic Light

题目大意

交通信号灯的颜色按照蓝色（$\text{B}$）、黄色（$\text{Y}$）、红色（$\text{R}$）的固定周期依次循环切换：

$$\text{B}⟶\text{Y}⟶\text{R}⟶\text{B}⟶\dots$$

给定当前信号灯显示的颜色字符 $c$，求其下一个变换的颜色并输出。

数据范围：

• 保证输入的字符 $c\in \{\text{’B’},\text{’Y’},\text{’R’}\}$。

---

思路

本题本质上是有限离散状态转移的模拟。系统的状态空间大小仅为 $|\mathrm{\Sigma }|=3$，构成一个极小的单向有向环。

对于固定状态转移关系的建模，常见有以下几种方案：

1. 关联容器映射（原解法思路）： 将当前状态视为键（Key），下一状态视为值（Value），构建映射表：

$$\{(\text{’B’},\text{’Y’}),(\text{’Y’},\text{’R’}),(\text{’R’},\text{’B’})\}$$

通过键查询后继值，实现逻辑简单清晰。 2. 分支判断（条件分流）： 使用 if-else 或 switch-case 语句直接对输入字符进行硬编码匹配并返回对应字符。 3. 环形序列索引： 将状态序列表达为字符串 $S=\text{"BYRB"}$。通过查找字符 $c$ 在 $S$ 中的首次出现下标 $idx$，直接访问其相邻后继元素 $S[idx+1]$。

---

复杂度分析

针对原代码使用 std::map<char, char> 的实现方案：

• 时间复杂度：$\mathcal{O}(1)$。 虽然 std::map 底层采用红黑树实现，查找与插入的理论时间复杂度为 $\mathcal{O}(\log k)$（$k$ 为节点数量），但此处节点规模固定为常数 $k=3$，树高最大仅为 $2$，因而实际操作代价为绝对的常数时间 $\mathcal{O}(1)$。
• 空间复杂度：$\mathcal{O}(1)$。 红黑树仅存储 $3$ 个节点及若干辅助指针，占用的堆内存与栈内存均为微小的常数空间 $\mathcal{O}(1)$。

---

参考代码

参考代码

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

void fc() { 
    unordered_map<char,char>m;
    m['B']='Y';
    m['Y']='R';
    m['R']='B';
    char c;
    std::cin>>c; 
    std::cout<<m[c];
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}

---

B - Standing Outliers

题目大意

数轴上分布着 $N$ 个人，编号为 $1\sim N$，其中第 $i$ 个人的坐标为 $X_i$（允许多人位于相同坐标）。

若一个人与其余所有人的欧几里得距离均不小于 $D$，即对所有满足 $1\le j\le N$ 且 $j\ne i$ 的 $j$ 均满足：

$$|X_i-X_j|\ge D$$

则称该人“独处”（Stand Apart）。

请按编号升序输出所有“独处”人员的个数 $K$ 以及对应的具体编号。若不存在任何人满足条件，则第二行输出留空。

数据范围：

• $2\le N\le 100$
• $1\le D\le {10}^9$
• $1\le X_i\le {10}^9$
• 所有输入数值均为整数。

---

思路

本题要求找出在全局范围内与其他所有点间距均不小于 $D$ 的点。

1. 一维偏序下的邻域判定性质： 在一维数轴上，若将所有点按照坐标升序排序，则对于排在下标 $i$ 处的点，其在整个数轴上的最近邻点必然是其紧邻的前驱点 $i-1$ 或紧邻的后继点 $i+1$。 因此，无需对每一个点都进行全局 $\mathcal{O}(N)$ 的逐一对比，仅需验证其相邻的两端：

• 左边界约束：若存在前驱（$i>0$），校验 $X_i-X_{i-1}\ge D$；
• 右边界约束：若存在后继（$i<N-1$），校验 $X_{i+1}-X_i\ge D$。 边界端点（第 $0$ 个点与第 $N-1$ 个点）只需分别进行单侧校验。

2. 原始编号绑定与排序： 由于排序操作会打乱初始输入的顺序，因此使用 std::pair<int, int> 将坐标与原始下标 $(X_i,i)$ 绑定存储。排序后利用 Lambda 表达式抽象边界检查逻辑，筛选出符合条件的点的原始编号。
3. 结果有序化： 筛选出的原始编号在答案序列中不一定呈现升序排列，最终对答案序列执行一次升序排序即可满足输出规范。

---

复杂度分析

• 时间复杂度：$\mathcal{O}(N\log N)$。

• 对 $N$ 个二元组进行坐标升序排序，耗时为 $\mathcal{O}(N\log N)$；

• 遍历有序序列并执行局部前驱/后继常数级判定的耗时为 $\mathcal{O}(N)$；

• 对至多 $N$ 个合法编号执行升序排序，耗时为 $\mathcal{O}(K\log K)$（其中 $K\le N$）。 主导时间复杂度为排序阶段的 $\mathcal{O}(N\log N)$。即使数据规模扩展至 $N=2\times {10}^5$，亦能在时限内高效通过。

• 空间复杂度：$\mathcal{O}(N)$。 算法需要开辟动态数组 std::vector<std::pair<int, int>> 存储坐标与原始编号的绑定关系，以及存储答案编号的容器，额外空间开销线性依赖于输入规模 $N$。

---

参考代码

参考代码

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

void fc() {
    int n,d;
    std::cin>>n>>d;
    std::vector<std::pair<int,int>>a(n);
    for(int i=0;i<n;i++)std::cin>>a[i].first,a[i].second=i;
    std::sort(a.begin(),a.end());

    auto f=[&](int x){
        if(x){
            return a[x].first-a[x-1].first>=d;
        }
        return true;
    };
    auto g=[&](int x){
        if(x<n-1){
            return a[x+1].first-a[x].first>=d;
        }
        return true;
    };

    std::vector<int>ans;
    for(int i=0;i<n;i++){
        if(f(i)&&g(i))ans.push_back(a[i].second);
    }

    std::sort(ans.begin(),ans.end());

    std::cout<<ans.size()<<"\n";
    for(auto x:ans)std::cout<<x+1<<" ";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}

---

C - Range Search Query

题目大意

给定一个长度为 $|S|$ 的字符串 $S$ 和一个长度为 $|T|$ 的模式串 $T$。

现需要处理 $Q$ 次相互独立的询问。每次询问给出两个整数 $L$ 和 $R$（采用 $1$-based 标号），要求判断子串 $S[L\dots R]$ 是否包含 $T$ 作为其子串。若包含输出 Yes，否则输出 No。

数据范围：

• $1\le |S|\le 4\times {10}^5$
• $1\le |T|\le 10$
• $1\le Q\le 2\times {10}^5$
• $1\le L\le R\le |S|$
• 字符串 $S,T$ 仅由小写英文字母构成。

---

思路

本题的核心是判断区间 $[L,R]$ 内部是否存在模式串 $T$ 的完整匹配。

1. 匹配条件的数学转化 设 $T$ 在主串 $S$ 中的某一次出现起始于下标 $p$（$0$-based），则该次匹配占用的区间为 $[p,p+|T|-1]$。 该匹配完全落在询问区间 $[l,r]$（$0$-based，即 $l=L-1,r=R-1$）内，当且仅当同时满足：

$$p\ge l\text{且}p+|T|-1\le r$$

2. 单调性与贪心性质 由于模式串 $T$ 的长度是固定的，对于所有满足 $p\ge l$ 的匹配起点，对应的区间右端点 $p+|T|-1$ 随起点 $p$ 严格单调递增。 因此，我们只需要考察 大于等于 $l$ 的最小起点 $p_{min}$：

• 若 $p_{min}+|T|-1\le r$，则已经找到合法匹配，答案为 Yes。
• 若 $p_{min}+|T|-1>r$（或根本不存在 $\ge l$ 的匹配），则后续任何更大的起点 $p>p_{min}$ 其右端点必然也严格大于 $r$，绝不可能被区间 $[l,r]$ 包含，答案必然为 No。

3. 算法流程

• 预处理匹配起点：利用 KMP 算法在线性时间内扫描主串 $S$，找出所有与 $T$ 匹配的起始下标，按顺序存入动态数组 $A$ 中。
• 二分查找回答询问：对于每个询问 $[l,r]$，在单调递增数组 $A$ 中利用 std::lower_bound 查找第一个满足 $x\ge l$ 的起始下标。若存在且 $x+|T|-1\le r$，则输出 Yes；否则输出 No。

---

复杂度分析

• 时间复杂度：

• 预处理阶段：KMP 构建 Next 数组复杂度为 $O(|T|)$，在主串 $S$ 中匹配的复杂度为 $O(|S|)$。提取的所有匹配起始下标总数 $K\le |S|$。

• 询问阶段：共 $Q$ 次询问，每次询问使用 std::lower_bound 在长度最多为 $|S|$ 的有序数组中进行二分查找，单次复杂度为 $O(\log |S|)$。

• 总时间复杂度：$O(|S|+|T|+Q\log |S|)$。代入数据规模 $|S|=4\times {10}^5,Q=2\times {10}^5$，总基本操作次数约为 $4\times {10}^6$，远在 2.0 秒限制之内。

• 空间复杂度：

• KMP 的 Next 数组需要 $O(|T|)$ 空间；

• 存储匹配起点的数组 $A$ 最多包含 $|S|$ 个元素，占用 $O(|S|)$ 空间。

• 总空间复杂度：$O(|S|+|T|)$，消耗内存数兆字节，远低于 1024 MiB 的空间上限。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> getNext(const string &p) {
    int n = p.size();
    vector<int> nxt(n, 0);
    for (int i = 1, j = 0; i < n; ++i) {
        while (j > 0 && p[i] != p[j]) j = nxt[j - 1];
        if (p[i] == p[j]) j++;
        nxt[i] = j;
    }
    return nxt;
}
vector<int> kmp(const string &s, const string &p) {
    vector<int> res;
    vector<int> nxt = getNext(p);
    int n = s.size(), m = p.size();
    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) j = nxt[j - 1];
        if (s[i] == p[j]) j++;
        if (j == m) {
            res.push_back(i - m + 1);
            j = nxt[j - 1];
        }
    }
    return res;
}
void fc() {
    int q;std::cin>>q;
    std::string s,t;
    std::cin>>s>>t;

    auto a=kmp(s,t);
    std::sort(a.begin(),a.end());
    // for(auto x:a)std::cout<<x<<" ";std::cout<<"\n";
    while(q--){
        int l,r;std::cin>>l>>r;
        --l,--r;
        
        auto it=std::lower_bound(a.begin(),a.end(),l);
        if(it==a.end()){
            std::cout<<"No\n";continue;
        }

        int x=*it;
        int y=x+t.size()-1;

        if(x>=l&&y<=r){
            std::cout<<"Yes\n";
        }else{
            std::cout<<"No\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}

---

D Masking Tape

题目大意

水平方向排列着编号为 $1$ 到 $N$ 的 $N$ 个格子。每个格子的初始颜色均为字符 'a'，且初始时所有格子上均未覆盖胶带。

现有 $Q$ 次操作，需按顺序依次处理：

1. 1 X：若格子 $X$ 上未贴胶带，则贴上一张胶带；若已贴有胶带，则揭下胶带（状态翻转）。
2. 2 C：将所有当前未被胶带覆盖的格子颜色修改为小写字符 $C$。

请在全部 $Q$ 次操作执行完毕后，输出每个格子最终的颜色序列。

数据范围：

• $1\le N,Q\le 3\times {10}^5$
• 操作 1 保证：$1\le X\le N$
• 操作 2 保证：$C$ 为单个英文小写字母

---

思路

如果每次遇到操作 2 都直接遍历所有无胶带的格子进行暴力染色，最坏情况下时间复杂度将达到 $\mathcal{O}(N\cdot Q)$，显然会超时。因此需要通过时间戳记录与状态切换结算（懒标记/惰性求值）的思想，将染色开销均摊到每个状态改变的瞬间。

观察操作性质可得：

1. 操作 2 是一种全局染色。若在某个时间区间内连续发生多次操作 2，前序染色的效果会被后续染色完全覆盖，因此对于任意暴露在外的格子，只有最后一次生效的操作 2 的颜色才具有决定意义。
2. 维护两个全局变量：idx 表示最后一次执行操作 2 的时间戳（操作序号），col 表示该次操作所指定的颜色。

针对每个格子 $x$ 的状态机转移与颜色结算时机：

• 初始状态： 所有格子均为暴露状态，记录暴露起始时间戳 $a[x]=-1$，覆盖标记 $\text{vis}[x]=0$。

• 从未覆盖到覆盖（贴上胶带）： 格子一旦贴上胶带，后续的操作 2 将无法影响它。此时格子在被“封存”前所获得的颜色，取决于在其暴露区间 $[a[x],i]$ 内是否发生过全局染色：

• 若最近一次全局染色时间戳 $\text{idx}>a[x]$，说明在它暴露期间有新的颜色覆盖，立即将其颜色固化为 $s[x]=\text{col}$。

• 将标记更新为 $\text{vis}[x]=1$。

• 从覆盖到未覆盖（揭下胶带）： 揭下胶带后，格子此前固化的颜色保持不变，但重新进入了可被染色的暴露状态。此时只需更新其重新暴露的起始时间戳 $a[x]=i$，并设 $\text{vis}[x]=0$。

• 最终统一结算： 处理完全部 $Q$ 次操作后，遍历所有仍处于暴露状态（$\text{vis}[x]=0$）的格子。若最后一次全局染色发生在其最后一次暴露之后（即 $\text{idx}>a[x]$），则说明它受到了最终全局染色的影响，将其颜色更新为 $\text{col}$。

---

复杂度分析

• 时间复杂度：

• 遍历 $Q$ 次操作，每次单点修改和状态判定均为 $\mathcal{O}(1)$。

• 最后对 $N$ 个格子做一次线性扫描结算，耗时 $\mathcal{O}(N)$。

• 整体时间复杂度为 $\mathcal{O}(N+Q)$。

• 空间复杂度：

• 维护长为 $N$ 的颜色序列 $s$、暴露时间戳数组 $a$ 以及胶带标记数组 $\text{vis}$，空间复杂度为 $\mathcal{O}(N)$。

---

参考代码

参考代码

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

void fc() {
    int n, q;
    std::cin >> n >> q;

    // a[i] 记录格子 i 最近一次变为暴露状态的操作时刻，初始为 -1
    // vis[i] 记录格子 i 当前是否覆盖有胶带（1 表示有，0 表示无）
    std::vector<int> a(n, -1), vis(n);
    std::string s(n, 'a');
    char col = 'a';
    int idx = -1; // 记录最近一次操作 2 的时间戳

    for (int i = 0; i < q; i++) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int x;
            std::cin >> x;
            --x;

            if (vis[x]) {
                // 原先有胶带 -> 揭下胶带：更新重新暴露的时间戳
                vis[x] = 0;
                a[x] = i;
            } else {
                // 原先无胶带 -> 贴上胶带：结算暴露期间的最新全局染色
                if (idx > a[x]) {
                    s[x] = col;
                }
                vis[x] = 1;
            }
        } else {
            // 全局染色：记录最新染色目标字符与对应的时间戳
            std::cin >> col;
            idx = i;
        }
    }

    // 处理完所有操作后，为依然处于暴露状态且被染色覆盖的格子更新最终颜色
    for (int i = 0; i < n; i++) {
        if (!vis[i] && idx > a[i]) {
            s[i] = col;
        }
    }
    std::cout << s << '\n';
}

int main() {
    // 提高 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) fc();
    return 0;
}

---

E Wheel Distance

题目大意

给定一个包含 $N+1$ 个顶点的带权无向图，顶点编号为 $1$ 到 $N+1$。图由两组边构成：

1. 环边（外圈轮缘）： 对每个整数 $i$（$1\le i\le N$），顶点 $i$ 与顶点 $(imodN)+1$ 之间存在一条权值为 $A_i$ 的无向边。
2. 辐条边（连接中心）： 对每个整数 $i$（$1\le i\le N$），顶点 $i$ 与顶点 $N+1$ 之间存在一条权值为 $B_i$ 的无向边。

现有 $Q$ 次独立询问，每次给定起点 $S$ 与终点 $T$（保证 $1\le S<T\le N+1$），求顶点 $S$ 到顶点 $T$ 的最短路径长度。

数据范围：

• $3\le N\le 2\times {10}^5$
• $1\le Q\le 2\times {10}^5$
• $1\le A_i,B_i\le {10}^9$
• $1\le S<T\le N+1$
• 所有输入数值均为整数

---

思路

该图的拓扑结构为典型的轮图（Wheel Graph）：前 $N$ 个顶点组成一个长度为 $N$ 的简单环，第 $N+1$ 个顶点作为中心枢纽，与环上的每一个顶点均有一条直连边相通。

对于每次询问的最短路径 $(S,T)$，根据图的连通特征，可按终点是否为中心点进行分类讨论：

1. 若 $T=N+1$

询问即为求外圈顶点 $S$ 到中心点 $N+1$ 的最短距离 $\text{dist}(S,N+1)$。

• 从中心点 $N+1$ 到外圈各点的路径，不仅可以直接通过单条辐条边到达（距离为 $B_i$），还可以先通过辐条边到达某一外圈顶点 $k$，再沿外圈环边走到 $S$。
• 这是一个单源最短路径问题。以 $N+1$ 为起点，在包含外圈所有边和全部辐条边的子图上运行单源最短路算法（如 Dijkstra 算法），即可预处理出所有外圈点到中心点的真实最短距离 $\text{dis}[i]=\text{dist}(i,N+1)$。

2. 若 $1\le S<T\le N$

两点均位于外圈环上。根据路径是否经过中心点 $N+1$，任意可行路径必然属于以下两类之一：

• 不经过中心点 $N+1$： 路径被完全限制在外圈简单环上。从 $S$ 到 $T$ 仅有两个行走方向：
• 顺时针（沿下标递增方向）： 跨越的边集为 $\{S,S+1,\dots ,T-1\}$，其距离为：

$$s_1=\sum _{k=S}^{T-1}{A}_k$$

• 逆时针（跨越首尾交界处）： 其距离为整环边权总和减去顺时针距离：

$$s_2=\sum _{k=1}^N{A}_k-s_1$$

利用前缀和数组预处理数组 $A$，可在 $\mathcal{O}(1)$ 时间内求得 $s_1$ 与 $s_2$。

• 经过中心点 $N+1$： 由于所有边权非负，由最短路径的最优子结构性质可知，若路径途经中心点 $N+1$，则 $S\to N+1$ 与 $N+1\to T$ 两段必须各自取各自的最短路。因此途经中心点的最短可能长度为：

$$s_3=\text{dist}(S,N+1)+\text{dist}(N+1,T)=\text{dis}[S]+\text{dis}[T]$$

综上所述，当 $1\le S<T\le N$ 时，两点间最短路径长度为：

$$min(s_1,s_2,s_3)$$

---

复杂度分析

• 时间复杂度：

• Dijkstra 最短路预处理： 图中有 $N+1$ 个顶点、$2N$ 条边。优先队列优化的 Dijkstra 算法复杂度为 $\mathcal{O}(N\log N)$。

• 环上前缀和预处理： 线性扫描数组 $A$，耗时 $\mathcal{O}(N)$。

• 单次询问回答： 前缀和作差与三者取极小值操作均为 $\mathcal{O}(1)$，处理 $Q$ 次询问总耗时 $\mathcal{O}(Q)$。

• 总时间复杂度： $\mathcal{O}(N\log N+Q)$，可在 $2.0\text{ s}$ 时限内轻松通过。

• 空间复杂度：

• 存储前缀和数组、辐条边权数组、最短距离数组以及优先队列，占用空间均为线性阶，整体空间复杂度为 $\mathcal{O}(N)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = std::pair<ll, int>;
const ll inf = LLONG_MAX;

int n, q;
std::vector<ll> a, b, dis;

void d() {
    std::priority_queue<P, std::vector<P>, std::greater<P>> q;
    dis[n + 1] = 0;
    for (int i = 1; i <= n; i++) {
        dis[i] = b[i];
        q.push({dis[i], i});
    }

    while (q.size()) {
        auto [d, u] = q.top();
        q.pop();
        if (dis[u] < d) continue;

        int s[2] = {u % n + 1, (u == 1 ? n : u - 1)};
        int w[2] = {a[u], a[(u == 1 ? n : u - 1)]};
        for (int i = 0; i < 2; i++) {
            ll dn = d + w[i];
            if (dn < dis[s[i]]) {
                dis[s[i]] = dn;
                q.push({dn, s[i]});
            }
        }
    }

    // for (int i = 1; i <= n; i++) std::cout << dis[i] << " ";
}
void fc() {
    std::cin >> n >> q;
    a.resize(n + 1);
    b.resize(n + 1);
    dis.assign(n + 2, inf);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= n; i++) std::cin >> b[i];

    d();

    for (int i = 1; i <= n; i++) a[i] += a[i - 1];

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        if(r==n+1){
            std::cout<<dis[l]<<"\n";continue;
        }
        ll s1 = a[r - 1] - a[l - 1];
        ll s2 = a[n] - s1;
        ll s3 = dis[l] + dis[r];

        std::cout << std::min({s1, s2, s3}) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // std::cin>>t;
    while (t--) fc();
    return 0;
}

---