303 字
1 分钟
Atcoder_Beginner_Contest_479(A~D题)
2026-10-18
浏览量 42 · 访客 10

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

A - Odd Index Sum#

按要求遍历累加即可。

void solve(){
int n; cin >> n;
int ans = 0;
for(int i = 1; i <= n;i++){
int x; cin >> x;
if(i & 1) ans += x;
}
cout << ans << '\n';
}

B - Longest Rainy Streak#

在遍历的时候用cntcnt记录′R′'R'字符连续的天数,当不连续时清零cntcnt,然后每次遍历时更新能达到的最长天数即可。

void solve(){
int n; cin >> n;
string s; cin >> s;
int cnt = 0, mx = 0;
for(auto it : s){
if(it == 'R'){cnt++; mx = max(mx, cnt);}
else {mx = max(mx, cnt); cnt = 0;}
}
cout << mx << '\n';
}

C - Bento Packing#

nn很小,写个dfsdfs枚举一下即可。

void solve(){
int n; ll w;
cin >> n >> w;
vector<ll> a(n + 1), b(n + 1);
for(int i = 1; i <= n;i++){
cin >> a[i] >> b[i];
}
ll ans = 0;
auto dfs = [&](auto&& self, ll x, ll y, ll sum) -> void {
if(x == n + 1){
if(y <= w) ans = max(ans, sum);
return;
}
self(self, x + 1, y, sum);
self(self, x + 1, y + b[x], sum + a[x]);
};
dfs(dfs, 0, 0, 0);
cout << ans << '\n';
}

D - Back and Forth Distance#

关键观察:当s<ts < t时,那么最优的情况只可能是:1.一步到位,s→ts \rightarrow t,代价是RsR_s的值。
2.先左后右,s→m→ts \rightarrow m \rightarrow t,其中mm表示在ss左边,且RmR_{m}代价最小的位置。(1≤m<s)(1 \leq m < s)这时的代价是Ls+RmL_s + R_{m}的值。
并且显然,最优解只在这两种情况里出现。
同理,当s>ts > t时,有两种最优可能:1.一步到位,s→ts \rightarrow t,代价是LsL_s的值。
2.先右后左,s→m→ts \rightarrow m \rightarrow t,其中mm表示在ss右边,且LmL_{m}代价最小的位置。(s<m≤n)(s < m \leq n)这时的代价是Rs+LmR_s + L_{m}的值。
对于ss前后的RmR_m和LmL_m的最小值,我们可以用前后缀数组来预处理记录最小值。由此对于给定的ss和tt,我们都可以在O(1)O(1)里给出答案。复杂度仅为O(n)O(n)。

void solve(){
int n, q; cin >> n >> q;
vector<ll> L(n + 1), R(n + 1);
vector<ll> premiR(n + 1, (ll)1e9 + 2LL), sufmiL(n + 1, (ll)1e9 + 2LL);
for(int i = 2; i <= n;i++) cin >> L[i];
for(int i = 1; i < n;i++) cin >> R[i];
sufmiL[n] = L[n];
for(int i = n - 1; i >= 2;i--){
sufmiL[i] = min(sufmiL[i + 1], L[i]);
}
premiR[1] = R[1];
for(int i = 2; i < n;i++){
premiR[i] = min(premiR[i - 1], R[i]);
}
while(q--){
ll ans = 0;
int s, t; cin >> s >> t;
if(t < s){
if(s + 1 <= n){
ans = min(L[s], R[s] + sufmiL[s + 1]);
}
else ans = L[s];
}
else if(s < t){
if(s - 1 >= 1){
ans = min(R[s], L[s] + premiR[s - 1]);
}
else ans = R[s];
}
cout << ans << '\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<ll> 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(){
}
signed main(){
ios::sync_with_stdio(false),
cin.tie(nullptr), cout.tie(nullptr);
signed _ = 1;
//cin >> _;
while(_--){
solve();
}
return 0;
}
分享

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

Atcoder_Beginner_Contest_479(A~D题)
https://mkrari.cn/posts/abc_479/
作者
Mkrari
发布于
2026-10-18
许可协议
CC BY-NC-SA 4.0