824 字
2 分钟
Atcoder_Beginner_Contest_476(A~E题)
2026-10-07
浏览量 26 · 访客 6

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

A - Appender#

只需判断字符串末尾字符。若末尾为e,追加r;否则追加er,随后输出结果。

void solve(){
string s; cin >> s;
if(s[static_cast<int>(s.size()) - 1] == 'e'){
s += 'r';
}
else s += "er";
cout << s << '\n';
}

B - Wild Card#

逐位比较两个等长字符串。若TiT_i为*,该位置可以替换成任意小写字母,不产生限制;否则必须满足Si=TiS_i=T_i。只要存在一个既不是通配符又与SiS_i不同的位置,就无法匹配。

void solve(){
int n; cin >> n;
string s, t; cin >> s >> t;
bool f = true;
for(int i = 0; i < n;i++){
if(t[i] != '*' && s[i] != t[i]){
f = false;
}
}
if(f) cout << "Yes" << '\n';
else cout << "No" << '\n';
}

C - Third Largest Number#

使用大根堆维护当前前缀中的全部元素。读入AiA_i并加入堆后,当i≥3i\geq3时,堆顶是当前最大值;暂时弹出最大的两个元素,此时新的堆顶就是按降序排列后的第三个值。记录答案后再将前两个元素放回,堆的内容便恢复为完整前缀,可以继续处理下一个元素。

相同的数值会以不同堆元素保留,因此重复值也会正常计入名次。每轮进行常数次堆操作,时间复杂度为O(Nlog⁡N)O(N\log N)。

int n; cin >> n;
vector<int> a(n + 1);
vector<int> ans;
priority_queue<int> pq;
for(int i = 1; i <= n;i++){
cin >> a[i];
pq.push(a[i]);
if(i >= 3){
int first = pq.top();
pq.pop();
int second = pq.top();
pq.pop();
ans.push_back(pq.top());
pq.push(first);
pq.push(second);
}
}
for(auto it : ans) cout << it << '\n';

D - Automat#

先分别对两类商品的价格升序排序,并计算前缀和。若决定购买ii个饮料,为了同时最小化总价格和所需的KK元纸币数,应选择价格最小的ii个。购买价格为BjB_j的饮料至少需要⌈BjK⌉\lceil\frac{B_j}{K}\rceil张KK元纸币,多付出的部分会以11元纸币找回。因此前缀数组needKineedK_i记录购买前ii个饮料所需的KK元纸币总数,只有needKi≤YneedK_i\leq Y时方案才可行。

初始货币总价值为X+KYX+KY。买完这ii个饮料后,剩余总价值为 remain=X+KY−∑j=1iBjremain=X+KY-\sum_{j=1}^{i}B_j。 甜点机接受两种纸币并以11元纸币找零,所以购买甜点时只需考虑剩余总价值,不再受纸币种类限制。为了最大化甜点数量,同样选择价格最小的若干个;在甜点价格前缀和中二分查找不超过remainremain的最大下标即可。

枚举i=0,1,…,Mi=0,1,\ldots,M并更新饮料数与甜点数之和。排序和前缀和预处理的时间复杂度为O(Nlog⁡N+Mlog⁡M)O(N\log N+M\log M)。

void solve(){
ll n, m, k; cin >> n >> m >> k;
ll x, y; cin >> x >> y;
vector<ll> a(n + 1), b(m + 1);
for(int i = 1; i <= n;i++) cin >> a[i];
for(int i = 1; i <= m;i++) cin >> b[i];
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
vector<ll> preA(n + 1);
for(int i = 1; i <= n;i++)
preA[i] = preA[i - 1] + a[i];
vector<ll> preB(m + 1);
vector<ll> needK(m + 1);
for(int i = 1; i <= m;i++){
preB[i] = preB[i - 1] + b[i];
needK[i] = needK[i - 1] + (b[i] + k - 1) / k;
}
ll total = x + k * y;
ll ans = 0;
for(int i = 0;i <= m;i++){
if(needK[i] > y) break;
ll remain = total - preB[i];
if(remain < 0) continue;
int A = upper_bound(preA.begin() + 1, preA.end(), remain) - preA.begin() - 1;
ans = max(ans, (ll)i + A);
}
cout << ans << '\n';
}

E - Min-Max Swap#

线段树模板详见下方的个人模板。
每次操作需要查询区间内最小值、最大值及它们所在的位置,交换后还要修改两个单点。若逐次遍历整个区间,最坏时间复杂度会达到O(NM)O(NM),因此使用线段树维护区间信息。

线段树的每个节点保存四个量:区间最小值mnmn及其位置mnPosmnPos、区间最大值mxmx及其位置mxPosmxPos。合并两个子节点时分别选择更小值和更大值,并继承相应位置。由于PP是一个排列,所有元素互不相同,不需要处理最值位置的并列问题。

对于一次[l,r][l,r]操作,区间查询得到最小值位置xx和最大值位置yy。交换Px,PyP_x,P_y后,对x,yx,y执行两次单点修改,使线段树与数组保持一致。建树复杂度为O(N)O(N),每次查询及两次更新均为O(log⁡N)O(\log N),总时间复杂度为O(N+Mlog⁡N)O(N+M\log N)。

void solve(){
int n, m;
cin >> n >> m;
vector<int> p(n + 1);
for(int i = 1; i <= n; i++){
cin >> p[i];
}
SegTree seg(n);
seg.build(p);
while(m--){
int l, r;
cin >> l >> r;
auto res = seg.query(l, r);
int x = res.mnPos;
int y = res.mxPos;
swap(p[x], p[y]);
seg.update(x, p[x]);
seg.update(y, p[y]);
}
for(int i = 1; i <= n; i++){
cout << p[i] << " \n"[i == n];
}
}

个人模板;

#include <bits/stdc++.h>
#include <exception>
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;
struct SegTree{
struct Node{
int mn, mx;
int mnPos, mxPos;
};
int n;
vector<Node> tr;
SegTree(int n){
this -> n = n;
tr.resize(4 * n + 5);
}
Node merge(Node a, Node b){
Node res;
if(a.mn < b.mn){
res.mn = a.mn;
res.mnPos = a.mnPos;
}
else{
res.mn = b.mn;
res.mnPos = b.mnPos;
}
if(a.mx > b.mx){
res.mx = a.mx;
res.mxPos = a.mxPos;
}
else{
res.mx = b.mx;
res.mxPos = b.mxPos;
}
return res;
}
void build(int u, int l, int r, vector<int>& p){
if(l == r){
tr[u] = {p[l], p[l], l, l};
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid, p);
build(u << 1 | 1, mid + 1, r, p);
tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
}
void build(vector<int>& p){
build(1, 1, n, p);
}
void update(int u, int l, int r, int pos, int val){
if(l == r){
tr[u] = {val, val, pos, pos};
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
update(u << 1, l, mid, pos, val);
else
update(u << 1 | 1, mid + 1, r, pos, val);
tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
}
void update(int pos, int val){
update(1, 1, n, pos, val);
}
Node query(int u, int l, int r, int ql, int qr){
if(ql <= l && r <= qr){
return tr[u];
}
int mid = (l + r) >> 1;
if(qr <= mid)
return query(u << 1, l, mid, ql, qr);
if(ql > mid)
return query(u << 1 | 1, mid + 1, r, ql, qr);
Node left = query(u << 1, l, mid, ql, qr);
Node right = query(u << 1 | 1, mid + 1, r, ql, qr);
return merge(left, right);
}
Node query(int l, int r){
return query(1, 1, n, l, r);
}
};
void solve(){
}
signed main(){
ios::sync_with_stdio(false),
cin.tie(nullptr), cout.tie(nullptr);
signed _ = 1;
//cin >> _;
while(_--){
solve();
}
return 0;
}
分享

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

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