467 字
1 分钟
Atcoder_Beginner_Contest_482(A~D题)
2026-11-06
浏览量 18 · 访客 1

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

A - Nigiri#

遍历字符串,判断′o′'o'个数是奇数还是偶数即可。

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#

一开始的思路是前缀和,但是这里的H,WH, W太大了,会导致数组超限,所以改用二分查询的方法。
我们先用两个数组记录下所有加入的棋子对应的行和列的位置,再分别从小到大排序。对于每次查询的区间,通过二分法找到能满足这个区间的最小左端点,再通过二分法找到满足这个区间的最大右端点,两个端点位置相减就是本次查询的答案了。时间复杂度为O(QlogN)O(QlogN)。

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#

由于所有人都在同一条数轴上,且只能左右移动,僵尸感染过程可以看作“感染区间”不断向左、右扩展。速度上限为 11,因此两端的人相向移动时,相对速度为 22,所需时间为距离的一半。

对于初始僵尸为第 ii 个人:

若 i=1i=1 或 i=Ni=N,即从端点开始,最优是所有人与僵尸相向移动,答案为:XN−X12\frac{X_N-X_1}{2}。

若 1<i<N1<i<N,需要决定感染先向左侧扩展还是先向右侧扩展:

  1. 先向右传播:max⁡(Xi+1−X12,XN−Xi2)\max\left(\frac{X_{i+1}-X_1}{2},\frac{X_N-X_i}{2}\right)

  2. 先向左传播:max⁡(Xi−X12,XN−Xi−12)\max\left(\frac{X_i-X_1}{2},\frac{X_N-X_{i-1}}{2}\right)

两种方案取较小值:min⁡(max⁡(Xi+1−X12,XN−Xi2),max⁡(Xi−X12,XN−Xi−12))\min\left( \max\left(\frac{X_{i+1}-X_1}{2},\frac{X_N-X_i}{2}\right), \max\left(\frac{X_i-X_1}{2},\frac{X_N-X_{i-1}}{2}\right) \right)

因为 XjX_j 都是偶数,所以上述距离差均为偶数,答案一定是整数。时间复杂度为 O(N)O(N)。

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 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_482(A~D题)
https://mkrari.cn/posts/abc_482/
作者
Mkrari
发布于
2026-11-06
许可协议
CC BY-NC-SA 4.0