
壁纸链接
题目链接: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
逐位比较两个等长字符串。若为*,该位置可以替换成任意小写字母,不产生限制;否则必须满足。只要存在一个既不是通配符又与不同的位置,就无法匹配。
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
使用大根堆维护当前前缀中的全部元素。读入并加入堆后,当时,堆顶是当前最大值;暂时弹出最大的两个元素,此时新的堆顶就是按降序排列后的第三个值。记录答案后再将前两个元素放回,堆的内容便恢复为完整前缀,可以继续处理下一个元素。
相同的数值会以不同堆元素保留,因此重复值也会正常计入名次。每轮进行常数次堆操作,时间复杂度为。
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
先分别对两类商品的价格升序排序,并计算前缀和。若决定购买个饮料,为了同时最小化总价格和所需的元纸币数,应选择价格最小的个。购买价格为的饮料至少需要张元纸币,多付出的部分会以元纸币找回。因此前缀数组记录购买前个饮料所需的元纸币总数,只有时方案才可行。
初始货币总价值为。买完这个饮料后,剩余总价值为 。 甜点机接受两种纸币并以元纸币找零,所以购买甜点时只需考虑剩余总价值,不再受纸币种类限制。为了最大化甜点数量,同样选择价格最小的若干个;在甜点价格前缀和中二分查找不超过的最大下标即可。
枚举并更新饮料数与甜点数之和。排序和前缀和预处理的时间复杂度为。
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
线段树模板详见下方的个人模板。
每次操作需要查询区间内最小值、最大值及它们所在的位置,交换后还要修改两个单点。若逐次遍历整个区间,最坏时间复杂度会达到,因此使用线段树维护区间信息。
线段树的每个节点保存四个量:区间最小值及其位置、区间最大值及其位置。合并两个子节点时分别选择更小值和更大值,并继承相应位置。由于是一个排列,所有元素互不相同,不需要处理最值位置的并列问题。
对于一次操作,区间查询得到最小值位置和最大值位置。交换后,对执行两次单点修改,使线段树与数组保持一致。建树复杂度为,每次查询及两次更新均为,总时间复杂度为。
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 998244353typedef 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;}