416 字
1 分钟
Atcoder_Beginner_Contest_481(A~E题)

壁纸链接
题目链接:https://atcoder.jp/contests/abc481/tasks
A - Digits of A+B
最终结果只可能是位数或位数,直接相加判断一下即可。
void solve(){ int a, b; cin >> a >> b; if(a + b >= 10){ cout << 2 << '\n'; } else cout << 1 << '\n';}B - Polyline
对于刚好等于的我们提前计数,剩下的只需要判断连续的两个和的值是否发生突变(一边大于,一边小于),然后计数即可。
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
直接用映射名字,和(整数),模拟个事件的操作即可。
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
因为这里有向图的边权可以为或,所以不能直接用,而是用双端队列实现 ,将边权为的边(编号最小的)放在队头,提前遍历,边权为的放队尾延后遍历。这样找的最短路便是总代价最少的了。
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
将每个点看作从原点出发的向量。问题等价于:找一个半圆(极角跨度),使其包含最多的向量。
先按象限分两组:上半平面(含正 轴)为 ,下半平面(含负 轴)为 ,先按组排序。同组内,利用叉积 判断极角大小。 说明 的角度小于 。全程使用 防止溢出,避免浮点误差。
然后将数组首尾相连(破环成链),用 模拟环形访问。固定左端点 ,右端点 单调向右扩展。条件是 ,这保证了 到 的角度跨度严格小于度()。每次用 更新答案即可。
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 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_481(A~E题)
https://mkrari.cn/posts/abc_481/