416 字
1 分钟
Atcoder_Beginner_Contest_481(A~E题)
2026-10-26
浏览量 36 · 访客 12

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

A - Digits of A+B#

最终结果只可能是11位数或22位数,直接相加判断一下即可。

void solve(){
int a, b; cin >> a >> b;
if(a + b >= 10){
cout << 2 << '\n';
}
else cout << 1 << '\n';
}

B - Polyline#

对于刚好等于kk的aia_i我们提前计数,剩下的只需要判断连续的两个aia_i和ai+1a_{i + 1}的值是否发生突变(一边大于kk,一边小于kk),然后计数即可。

void solve(){
int n, k; cin >> n >> k;
int ans = 0;
vector<int> a(n + 1);
for(int i = 1; i <= n;i++){
cin >> a[i];
if(a[i] == k) ans++;
}
for(int i = 1; i < n;i++){
if(a[i] > k && a[i + 1] < k) ans++;
if(a[i] < k && a[i + 1] > k) ans++;
}
cout << ans << '\n';
}

C - Bank Accounts#

直接用mapmap映射名字(string)(string),和IDID(整数),模拟QQ个事件的操作即可。

void solve(){
int Q; cin >> Q;
int cnt = 1;
map<string, int> mp;
while(Q--){
string s; cin >> s;
if(!mp[s]) mp[s] = cnt++;
cout << mp[s] << '\n';
}
}

D - Autopilot#

因为这里有向图的边权可以为00或11,所以不能直接用bfsbfs,而是用双端队列实现0−10 - 1 BFSBFS,将边权为00的边(编号最小的)放在队头,提前遍历,边权为11的放队尾延后遍历。这样找的最短路便是总代价最少的了。

void solve(){
int n, m, s, t; cin >> n >> m >> s >> t;
vector<vector<int>> g(n + 1);
for(int i = 1; i <= m;i++){
int u, v; cin >> u >> v;
g[u].push_back(v);
}
vector<ll> dist(n + 1, 1e11);
deque<int> dq;
dist[s] = 0, dq.push_back(s);
while(!dq.empty()){
int u = dq.front();
dq.pop_front();
int mi = 2e5 + 2;
for(int v : g[u]) mi = min(mi, v);
for(int v : g[u]){
ll w = (v == mi ? 0 : 1);
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
if(w == 0) dq.push_front(v);
else dq.push_back(v);
}
}
}
cout << (dist[t] == 1e11 ? -1 : dist[t]) << '\n';
}

E - Most Brilliant Starry Sky#

将每个点看作从原点出发的向量。问题等价于:找一个半圆(极角跨度<π<π),使其包含最多的向量。
先按象限分两组:上半平面(含正 xx 轴)为 00,下半平面(含负 xx 轴)为 11,先按组排序。同组内,利用叉积 cross(a,b)=a.x∗b.y−a.y∗b.xcross(a, b) = a.x*b.y - a.y*b.x 判断极角大小。cross(a,b)>0cross(a,b) > 0 说明 aa 的角度小于 bb。全程使用 __int128_t\_\_int128\_t 防止溢出,避免浮点误差。
然后将数组首尾相连(破环成链),用 j%nj \% n 模拟环形访问。固定左端点 ii,右端点 jj 单调向右扩展。条件是 cross(p[i],p[j%n])>0cross(p[i], p[ j\%n]) > 0,这保证了 ii 到 jj 的角度跨度严格小于180180度(ππ)。每次用 j−ij - i 更新答案即可。

struct Point {ll x, y;};
void solve(){
int n; cin >> n;
vector<Point> p(n);
for(int i = 0; i < n;i++){
cin >> p[i].x >> p[i].y;
}
auto half = [&](const Point& p) -> int {
return (p.y > 0 || (p.y == 0 && p.x > 0)) ? 0 : 1;
};
auto cross = [&](const Point& a, const Point& b) -> __int128_t {
return (__int128_t)a.x * b.y - (__int128_t)a.y * b.x;
};
sort(p.begin(), p.end(), [&](const Point& a, const Point& b){
if(half(a) != half(b)){
return half(a) < half(b);
}
return cross(a, b) > 0;
});
int ans = 1, j = 1;
for(int i = 0; i < n;i++){
if(j < i + 1) j = i + 1;
while(j < i + n && cross(p[i], p[j % n]) > 0) j++;
ans = max(ans, j - i);
}
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_481(A~E题)
https://mkrari.cn/posts/abc_481/
作者
Mkrari
发布于
2026-10-26
许可协议
CC BY-NC-SA 4.0