
壁纸链接
题目链接:https://atcoder.jp/contests/abc477/tasks
A - Traffic Light
颜色按照构成长度为的循环。根据当前字符直接输出其唯一后继即可。
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
按照定义枚举每个人,再遍历所有。若存在,则不满足条件;只有与其余所有人的距离都不小于时,才将编号加入答案。外层按编号递增枚举,因此收集到的编号自然有序。
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
先预处理在中的所有完整出现区间。枚举起点,若,就记录区间。这些区间按起点递增保存,且由于长度相同,终点也随起点递增。
对于询问,二分找到第一个起点不小于的出现区间。若该区间的终点不超过,则完整包含在询问范围内;否则不存在合法区间,因为后续出现位置的终点只会更大。代码统一转为从开始的下标进行判断。
设。使用substr直接比较时,预处理时间复杂度为;每个询问为,总时间复杂度为,题目中,直接比较即可。
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
类型操作可能同时修改个位置,不能逐格执行。用保存最近一次全局染色的颜色,用保存其版本号,将所有未被遮挡位置的修改延迟到必须确定其颜色时处理。
对每个位置维护当前保存的颜色、是否被遮挡,以及该位置最近一次变为未遮挡时的版本。当给一个未遮挡位置加上遮挡时,如果,说明它在暴露期间经历过全局染色,需要先把同步为,再将其设为遮挡状态。移除遮挡时只记录当前,表示从这个版本之后的新染色才会作用于它。
全部询问结束后,遮挡中的位置直接使用已经固定的;未遮挡位置若版本落后于全局版本,则最终颜色为,否则仍为。每个询问和每个位置都只进行常数次操作,时间复杂度为。
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
图由外圈的个顶点和中心顶点组成。任意两点之间的最短路可以分成两类:完全不经过中心,只沿外圈移动;或者经过中心顶点。
先在完整图上以中心顶点为源点执行一次Dijkstra,得到,即中心到每个外圈顶点的最短距离。对于两个外圈顶点,用外圈边权前缀和计算顺时针距离 , 另一方向距离为,所以不经过中心的最短距离为。若路径经过中心,则最短距离为。两者取最小值即可。若,答案直接是。
图中有个顶点和条无向边。Dijkstra的时间复杂度为。
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 998244353typedef 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;}