802 字
2 分钟
Atcoder_Beginner_Contest_477(A~E题)
2026-10-08
浏览量 20 · 访客 5

壁纸链接
题目链接:https://atcoder.jp/contests/abc477/tasks

A - Traffic Light#

颜色按照B→Y→R→BB\to Y\to R\to B构成长度为33的循环。根据当前字符直接输出其唯一后继即可。

void solve(){
char c; cin >> c;
if(c == 'B'){
cout << "Y" << '\n';
}
else if(c == 'Y'){
cout << 'R' << '\n';
}
else if(c == 'R'){
cout << 'B' << '\n';
}
}

B - Standing Outliers#

按照定义枚举每个人ii,再遍历所有j≠ij\neq i。若存在∣Xi−Xj∣<D|X_i-X_j|< D,则ii不满足条件;只有与其余所有人的距离都不小于DD时,才将编号ii加入答案。外层按编号递增枚举,因此收集到的编号自然有序。

void solve(){
int n; ll d;
cin >> n >> d;
vector<ll> a(n + 1);
vector<int> pos;
for(int i = 1; i <= n;i++){
cin >> a[i];
}
for(int i = 1; i <= n;i++){
bool f = true;
for(int j = 1; j <= n;j++){
if(i == j) continue;
if(abs(a[j] - a[i]) < d){
f = false;
}
}
if(f) pos.push_back(i);
}
cout << static_cast<int>(pos.size()) << '\n';
for(auto it : pos) cout << it << " ";
cout << '\n';
}

C - Range Search Query#

先预处理TT在SS中的所有完整出现区间。枚举起点ii,若S[i,i+∣T∣−1]=TS[i,i+|T|-1]=T,就记录区间(i,i+∣T∣−1)(i,i+|T|-1)。这些区间按起点递增保存,且由于长度相同,终点也随起点递增。

对于询问[L,R][L,R],二分找到第一个起点不小于LL的出现区间。若该区间的终点不超过RR,则TT完整包含在询问范围内;否则不存在合法区间,因为后续出现位置的终点只会更大。代码统一转为从00开始的下标进行判断。

设∣S∣=n,∣T∣=m|S|=n,|T|=m。使用substr直接比较时,预处理时间复杂度为O(nm)O(nm);每个询问为O(log⁡n)O(\log n),总时间复杂度为O(nm+Qlog⁡n)O(nm+Q\log n),题目中m≤10m\leq10,直接比较即可。

void solve(){
int Q; cin >> Q;
string s, t; cin >> s >> t;
int s_len = static_cast<int>(s.size());
int t_len = static_cast<int>(t.size());
vector<pii> pos;
for (int i = 0; i + t_len <= s_len; i++) {
if (s.substr(i, t_len) == t) {
pos.push_back({i, i + t_len - 1});
}
}
while (Q--) {
int L, R;
cin >> L >> R;
--L, --R;
auto it = lower_bound(pos.begin(), pos.end(), make_pair(L, INT_MIN));
if (it != pos.end() && it->second <= R) {
cout << "Yes" << '\n';
}
else{
cout << "No" << '\n';
}
}
}

D - Masking Tape#

类型22操作可能同时修改O(N)O(N)个位置,不能逐格执行。用global_colorglobal\_color保存最近一次全局染色的颜色,用global_verglobal\_ver保存其版本号,将所有未被遮挡位置的修改延迟到必须确定其颜色时处理。

对每个位置维护当前保存的颜色aia_i、是否被遮挡has_blockihas\_block_i,以及该位置最近一次变为未遮挡时的版本last_verilast\_ver_i。当给一个未遮挡位置加上遮挡时,如果last_veri<global_verlast\_ver_i<global\_ver,说明它在暴露期间经历过全局染色,需要先把aia_i同步为global_colorglobal\_color,再将其设为遮挡状态。移除遮挡时只记录当前global_verglobal\_ver,表示从这个版本之后的新染色才会作用于它。

全部询问结束后,遮挡中的位置直接使用已经固定的aia_i;未遮挡位置若版本落后于全局版本,则最终颜色为global_colorglobal\_color,否则仍为aia_i。每个询问和每个位置都只进行常数次操作,时间复杂度为O(N+Q)O(N+Q)。

void solve(){
int N, Q; cin >> N >> Q;
vector<char> a(N + 1, 'a');
vector<int> last_ver(N + 1, 0);
vector<bool> has_block(N + 1, false);
int global_ver = 0;
char global_color = 'a';
while(Q--){
int op; cin >> op;
if(op == 1){
int num; cin >> num;
if(!has_block[num]){
if(last_ver[num] < global_ver){
a[num] = global_color;
}
has_block[num] = true;
}
else{
last_ver[num] = global_ver;
has_block[num] = false;
}
}
else{
char c; cin >> c;
global_color = c;
global_ver++;
}
}
string s = "";
for(int i = 1; i <= N;i++){
if(has_block[i]) s += a[i];
else{
if(last_ver[i] < global_ver) s += global_color;
else s += a[i];
}
}
cout << s << '\n';
}

E - Wheel Distance#

图由外圈的NN个顶点和中心顶点N+1N+1组成。任意两点之间的最短路可以分成两类:完全不经过中心,只沿外圈移动;或者经过中心顶点。

先在完整图上以中心顶点N+1N+1为源点执行一次Dijkstra,得到distidist_i,即中心到每个外圈顶点的最短距离。对于两个外圈顶点S<TS<T,用外圈边权前缀和计算顺时针距离 d=preT−1−preS−1d=pre_{T-1}-pre_{S-1}, 另一方向距离为total−dtotal-d,所以不经过中心的最短距离为min⁡(d,total−d)\min(d,total-d)。若路径经过中心,则最短距离为distS+distTdist_S+dist_T。两者取最小值即可。若T=N+1T=N+1,答案直接是distSdist_S。

图中有N+1N+1个顶点和2N2N条无向边。Dijkstra的时间复杂度为O(Nlog⁡N)O(N\log N)。

void solve(){
int n, q; cin >> n >> q;
vector<ll> a(n + 1), b(n + 1);
for(int i = 1; i <= n;i++) cin >> a[i];
for(int i = 1; i <= n;i++) cin >> b[i];
vector<vector<pll>> g(n + 2);
for(int i = 1; i <= n;i++){
int j = (i == n ? 1 : i + 1);
g[i].push_back({j, a[i]});
g[j].push_back({i, a[i]});
g[i].push_back({n + 1, b[i]});
g[n + 1].push_back({i, b[i]});
}
vector<ll> dist(n + 2, LLONG_MAX);
priority_queue<pll, vector<pll>, greater<pll>> pq;
dist[n + 1] = 0;
pq.push({0, n + 1});
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(d != dist[u]) continue;
for(auto [v, w] : g[u]){
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
vector<ll> pre(n + 1, 0);
for(int i = 1; i <= n;i++){
pre[i] = pre[i - 1] + a[i];
}
ll total = pre[n];
while(q--){
int s, t;
cin >> s >> t;
if(t == n + 1){
cout << dist[s] << '\n';
continue;
}
ll d1 = pre[t - 1] - pre[s - 1];
ll cycle = min(d1, total - d1);
ll center = dist[s] + dist[t];
cout << min(cycle, center) << '\n';
}
}

个人模板:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define mod 998244353
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll fast_pow(ll a, ll b, ll MOD){
ll ans = 1;
while(b){
if(b & 1) ans = (ans * a) % MOD;
b >>= 1;
a = (a * a) % MOD;
}
return ans;
}
vector<ll> get_inverse(ll n, ll MOD){
vector<ll> inverse(n + 1, 0);
inverse[1] = 1;
for(int i = 2; i <= n;i++){
inverse[i] = MOD - (MOD / i) * inverse[MOD % i] % MOD;
}
return inverse;
}
struct DSU{
vector<int> fa, sz;
DSU(int n){
fa.resize(n + 1);
sz.resize(n + 1, 1);
for(int i = 1; i <= n;i++){
fa[i] = i;
}
}
int find(int x){
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool merge(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
if(sz[x] > sz[y]) swap(x, y);
fa[y] = x;
sz[x] += sz[y];
return true;
}
};
struct BIT{
int n;
vector<int> tr;
BIT(int n) {
this -> n = n;
tr.assign(n + 1, 0);
}
void add(int x, int v){
while(x <= n){
tr[x] += v;
x += x & -x;
}
}
int sum(int x) {
int ans = 0;
while(x > 0){
ans += tr[x];
x -= x & -x;
}
return ans;
}
};
void solve(){
}
int main(){
ios::sync_with_stdio(false),
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
//cin >> _;
while(_--){
solve();
}
return 0;
}
分享

如果这篇文章对你有帮助,欢迎分享给更多人!

Atcoder_Beginner_Contest_477(A~E题)
https://mkrari.cn/posts/abc_477/
作者
Mkrari
发布于
2026-10-08
许可协议
CC BY-NC-SA 4.0