467 字
1 分钟
Atcoder_Beginner_Contest_482(A~D题)

壁纸链接
题目链接:https://atcoder.jp/contests/abc482/tasks
A - Nigiri
遍历字符串,判断个数是奇数还是偶数即可。
void solve(){ string s; cin >> s; int cnt = 0; for(auto it : s){ if(it == 'o') cnt++; } cout << (cnt & 1 ? "odd" : "even") << '\n';}B - Blank Bingo
我的思路是直接判断所有情况,对角斜线2条直线,行5条和列5条直线,最后只记录对应需要最少标记的情况都还需要多少个标记即可。
void solve(){ vector<string> s(6); for(int i = 1; i <= 5;i++){ cin >> s[i]; s[i] = " " + s[i]; } int ans = 5; //row for(int i = 1; i <= 5;i++){ int cnt = 0; for(int j = 1; j <= 5;j++) if(s[i][j] == 'o') cnt++; ans = min(ans, 5 - cnt); } //column for(int i = 1; i <= 5;i++){ int cnt = 0; for(int j = 1; j <= 5;j++) if(s[j][i] == 'o') cnt++; ans = min(ans, 5 - cnt); } //xie int cnt = 0; for(int i = 1; i <= 5;i++) if(s[i][i] == 'o') cnt++; ans = min(ans, 5 - cnt); cnt = 0; for(int i = 1; i >= 5;i++) if(s[i][5 - i + 1] == 'o') cnt++; ans = min(ans, 5 - cnt);
cout << ans << '\n';}C - Band Count
一开始的思路是前缀和,但是这里的太大了,会导致数组超限,所以改用二分查询的方法。
我们先用两个数组记录下所有加入的棋子对应的行和列的位置,再分别从小到大排序。对于每次查询的区间,通过二分法找到能满足这个区间的最小左端点,再通过二分法找到满足这个区间的最大右端点,两个端点位置相减就是本次查询的答案了。时间复杂度为。
void solve(){ ll H, W, N, Q; cin >> H >> W >> N >> Q; vector<ll> column, row; for(int i = 1; i <= N;i++){ int R, C; cin >> R >> C; column.push_back(C), row.push_back(R); } sort(column.begin(), column.end()); sort(row.begin(), row.end()); while(Q--){ int op; cin >> op; if(op == 1){ ll x, y; cin >> x >> y; cout << upper_bound(row.begin(), row.end(), y) - lower_bound(row.begin(), row.end(), x) << '\n'; } else{ ll x, y; cin >> x >> y; cout << upper_bound(column.begin(), column.end(), y) - lower_bound(column.begin(), column.end(), x) << '\n'; } }}D - Wannabe Zombie
由于所有人都在同一条数轴上,且只能左右移动,僵尸感染过程可以看作“感染区间”不断向左、右扩展。速度上限为 ,因此两端的人相向移动时,相对速度为 ,所需时间为距离的一半。
对于初始僵尸为第 个人:
若 或 ,即从端点开始,最优是所有人与僵尸相向移动,答案为:。
若 ,需要决定感染先向左侧扩展还是先向右侧扩展:
-
先向右传播:
-
先向左传播:
两种方案取较小值:
因为 都是偶数,所以上述距离差均为偶数,答案一定是整数。时间复杂度为 。
void solve(){ int n; cin >> n; vector<ll> a(n + 1); for(int i = 1; i <= n;i++) cin >> a[i]; if(n == 1){ cout << 0 << '\n'; return; } for(int i = 1; i <= n;i++){ ll ans; if(i == 1 || i == n) ans = (a[n] - a[1]) / 2; else{ ll ans1 = max((a[i + 1] - a[1]) / 2, (a[n] - a[i]) / 2); ll ans2 = max((a[i] - a[1]) / 2, (a[n] - a[i - 1]) / 2); ans = min(ans1, ans2); } 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_482(A~D题)
https://mkrari.cn/posts/abc_482/