TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)
A - Counting Passes
int main() {
IOS;
cin >> n >> m;
int ans = 0;
rep (i, 1, n) cin >> k, ans += k >= m;
cout << ans;
return 0;
}
B - Minimize Abs 1
int main() {
IOS;
int l, r; cin >> n >> l >> r;
rep (i, 1, n) {
cin >> m;
int y = m;
if (r <= m) y = r;
else if (l >= m) y = l;
cout << y << ' ';
}
return 0;
}
C - Minimize Abs 2
考虑枚举 x
,然后通过开根号贪心找 y
int main() {
IOS;
long long x; cin >> x;
ll ans = x;
for (ll i = 0, ii = i * i; ; ++i, ii = i * i) {
ll s = x - ii;
ans = min(ans, abs(s));
if (s <= 0) break;
ll j = ceil(sqrt(s));
ans = min(ans, abs(j * j + ii - x));
ans = min(ans, abs((j - 1) * (j - 1) + ii - x));
if (j <= i) break;
}
cout << ans;
return 0;
}
D - Counting Ls
枚举三角形的中心点 A,然后去枚举同 X 轴的点 B,再枚举同 y 轴的点 C。
然后就是推公式,化简。
int main() {
IOS;
cin >> n;
ll ans = 0, cnt = 0;
vector<vector<int>> a(n);
vector<int> b(n);
rep (i, 0, n - 1) rep (j, 0, n - 1) {
char c; cin >> c;
if (c == 'o') a[i].pb(j), ++b[j];
}
rep (i, 0, n - 1) {
int sz = a[i].size();
int c = 0;
for (auto &x : a[i]) c += b[x] - 1;
ans += 1ll * c * (sz - 1);
}
cout << ans;
return 0;
}
E - Mex and Update
线段树维护 MEX, 只需要维护 [0, 20000] 区间即可。
const int N = 2e5 + 5;
int n, m, _, k, cas;
int a[N];
struct BitTree {
struct node { int l, r, val; } tr[N << 2];
void push_up(int rt) {
tr[rt].val = 0;
if (tr[rt << 1].l == tr[rt << 1].r) tr[rt].val += tr[rt << 1].val > 0;
else tr[rt].val += tr[rt << 1].val;
if (tr[rt << 1 | 1].l == tr[rt << 1 | 1].r) tr[rt].val += tr[rt << 1 | 1].val > 0;
else tr[rt].val += tr[rt << 1 | 1].val;
}
void build(int rt, int l, int r) {
tr[rt] = {l, r, 0};
if (l == r) { tr[rt].val = 0; return; }
int mid = l + r >> 1;
build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r);
}
void change(int rt, int x, int k) {
if (tr[rt].l == x && tr[rt].r == x) {
tr[rt].val += k;
return;
}
int mid = tr[rt].l + tr[rt].r >> 1;
if (x <= mid) change(rt << 1, x, k);
else change(rt << 1 | 1, x, k);
push_up(rt);
}
int ask(int rt) {
if (tr[rt].l == tr[rt].r) return tr[rt].l;
if (tr[rt << 1].val < tr[rt << 1].r - tr[rt << 1].l + 1) return ask(rt << 1);
return ask(rt << 1 | 1);
}
} bit;
int main() {
IOS;
bit.build(1, 0, 200001);
cin >> n >> m;
rep (i, 1, n) {
cin >> a[i];
if (a[i] <= 200000)
bit.change(1, a[i], 1);
}
rep (i, 1, m) {
int x, y; cin >> x >> y;
if (a[x] <= 200000) bit.change(1, a[x], -1);
a[x] = y;
if (a[x] <= 200000) bit.change(1, a[x], 1);
cout << bit.ask(1) << '\n';
}
return 0;
}
F - Minimize Bounding Square
倍增,把 x 轴 y 轴分开处理即可
const int N = 2e5 + 5;
int n, m, _, cas;
ll k, sx[N], sy[N];
int x[N], y[N];
ll check(int d, ll s[], int a[]) {
ll mi = 1ll << 60;
rep (i, 2, n * 2 + 1) {
int c = a[i >> 1] - (i & 1 ? d : 0);
ll res = 0;
int x = lower_bound(a + 1, a + 1 + n, c) - a - 1;
res += 1ll * c * x - s[x];
x = lower_bound(a + 1, a + 1 + n, c + d) - a - 1;
res += s[n] - s[x] - 1ll * (c + d) * (n - x);
umin(mi, res);
}
return mi;
}
int main() {
IOS;
cin >> n >> k;
rep (i, 1, n) cin >> x[i] >> y[i];
sort(x + 1, x + 1 + n); sort(y + 1, y + 1 + n);
rep (i, 1, n) sx[i] = sx[i - 1] + x[i], sy[i] = sy[i - 1] + y[i];
int ans = (1 << 30) - 1;
per (i, 29, 0) if (check(ans - (1 << i), sx, x) + check(ans - (1 << i), sy, y) <= k)
ans -= 1 << i;
cout << ans;
return 0;
}
- Contest Programming Beginner SYSTEMS AtCodercontest programming beginner systems contest programming beginner atcoder contest programming securities beginner contest programming beginner registry contest programming beginner keyence beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328