303 字
1 分钟
Atcoder_Beginner_Contest_479(A~D题)

壁纸链接
题目链接: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
在遍历的时候用记录字符连续的天数,当不连续时清零,然后每次遍历时更新能达到的最长天数即可。
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
很小,写个枚举一下即可。
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
关键观察:当时,那么最优的情况只可能是:1.一步到位,,代价是的值。
2.先左后右,,其中表示在左边,且代价最小的位置。这时的代价是的值。
并且显然,最优解只在这两种情况里出现。
同理,当时,有两种最优可能:1.一步到位,,代价是的值。
2.先右后左,,其中表示在右边,且代价最小的位置。这时的代价是的值。
对于前后的和的最小值,我们可以用前后缀数组来预处理记录最小值。由此对于给定的和,我们都可以在里给出答案。复杂度仅为。
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 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<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/