Daiwa Securities Co. Ltd. Programming Contest 2023(AtCoder Beginner Contest 331)
A - Tomorrow
int main() {
IOS;
for (_ = 1; _; --_) {
int M, D, y, m, d; cin >> M >> D >> y >> m >> d;
++d;
if (d > D) ++m, d -= D;
if (m > M) ++y, m -= M;
cout << y << ' ' << m << ' ' << d;
}
return 0;
}
B - Buy One Carton of Milk
int main() {
IOS;
for (_ = 1; _; --_) {
int n, m, s, l; cin >> n >> s >> m >> l;
memset(d, 0x3f, sizeof d); d[0] = 0;
rep (i, 1, n + 11) {
if (i - 6 >= 0) umin(d[i], d[i - 6] + s);
if (i - 8 >= 0) umin(d[i], d[i - 8] + m);
if (i - 12 >= 0) umin(d[i], d[i - 12] + l);
}
int mi = 1e9;
rep (i, n, n + 11) umin(mi, d[i]);
cout << mi;
}
return 0;
}
C - Sum of Numbers Greater Than Me
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n;
rep (i, 1, n) cin >> a[i], b[i] = c[i] = i;
sort(b + 1, b + 1 + n, [&](int x, int y) { return a[x] < a[y]; });
rep (i, 1, n) s[i] = s[i - 1] + a[b[i]];
c[b[n]] = n;
per (i, n - 1, 1) {
if (a[b[i]] == a[b[i + 1]]) c[b[i]] = c[b[i + 1]];
else c[b[i]] = i;
}
rep (i, 1, n) cout << s[n] - s[c[i]] << ' ';
}
return 0;
}
D - Tile Pattern
没有修改操作,脑抽用二维树状算面积和了, 就不放板子了,用二维前缀和维护面积和就好了。
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n >> k;
int t = n, s = 0; n <<= 1; m = n;
rep (i, 1, t) rep (j, 1, t) {
char c; cin >> c;
if (c ^ 'W') {
add(i, j, i, j, 1);
add(i + t, j, i + t, j, 1);
add(i, j + t, i, j + t, 1);
add(i + t, j + t, i + t, j + t, 1);
++s;
}
}
rep (i, 1, k) {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
int xx1 = x1 % t, yy1 = y1 % t, xx2 = x2 % t, yy2 = y2 % t;
if (xx2 < xx1) xx2 += t;
if (yy2 < yy1) yy2 += t;
int x = (x2 - x1 - (xx2 - xx1)) / t, y = (y2 - y1 - (yy2 - yy1)) / t;
ll res = ask(xx1 + 1, yy1 + 1, xx2 + 1, yy2 + 1);
res += 1ll * x * y * s;
res += ask(xx1 + 1, 1, xx2 + 1, t) * y + ask(1, yy1 + 1, t, yy2 + 1) * x;
cout << res << '\n';
}
}
return 0;
}
E - Set Meal
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n >> m >> k;
rep (i, 1, n) cin >> a[i], c[i] = i;
rep (i, 1, m) cin >> b[i], d[i] = i;
sort(c + 1, c + 1 + n, [&](int x, int y) { return a[x] > a[y]; });
sort(d + 1, d + 1 + m, [&](int x, int y) { return b[x] > b[y]; });
unordered_map<int, unordered_set<int>> st;
rep (i, 1, k) {
int x, y; cin >> x >> y;
st[x].insert(y);
}
int mx = -1;
for (int i = 1, mj = n + 1, j = 1; i <= n && j < mj; ++i, j = 1) {
for (; j < mj; ++j) if (!st[c[i]].count(d[j])) {
mj = j;
umax(mx, a[c[i]] + b[d[j]]);
break;
}
}
cout << mx;
}
return 0;
}
F - Palindrome Query
线段树,哈希维护回文判断
const int N = 1e6 + 5, P = 13331;
int n, m, _, k, cas;
unsigned int p[N];
char s[N];
struct BitTree {
struct node {
int l, r, len;
unsigned int val1, val2;
} tr[N << 2];
void push_up(int rt) {
tr[rt].val1 = tr[rt << 1].val1 * p[tr[rt << 1 | 1].len] + tr[rt << 1 | 1].val1;
tr[rt].val2 = tr[rt << 1 | 1].val2 * p[tr[rt << 1].len] + tr[rt << 1].val2;
}
void build(int rt, int l, int r, char* a) {
tr[rt].l = l, tr[rt].r = r, tr[rt].len = r - l + 1, tr[rt].val1 = tr[rt].val2 = 0;
if (l == r) { tr[rt].val1 = tr[rt].val2 = a[l]; return; }
int mid = l + r >> 1;
build(rt << 1, l, mid, a); build(rt << 1 | 1, mid + 1, r, a);
push_up(rt);
}
void change(int rt, int k, char c) {
if (tr[rt].l == k && tr[rt].r == k) {
tr[rt].val1 = tr[rt].val2 = c;
return;
}
int mid = tr[rt].l + tr[rt].r >> 1;
if (k <= mid) change(rt << 1, k, c);
else if (k > mid) change(rt << 1 | 1, k, c);
push_up(rt);
}
unsigned int ask(int rt, int l, int r, bool f) {
if (r < l) return 0;
if (tr[rt].l >= l && tr[rt].r <= r) return f ? tr[rt].val2 : tr[rt].val1;
int mid = tr[rt].l + tr[rt].r >> 1;
unsigned int ansl = l <= mid ? ask(rt << 1, l, r, f) : 0;
unsigned int ansr = r > mid ? ask(rt << 1 | 1, l, r, f) : 0;
unsigned int ans = 0;
if (!f) ans = r > mid ? ansl * p[min(r, tr[rt << 1 | 1].r) - mid] + ansr : ansl;
else ans = l <= mid ? ansr * p[mid - max(l, tr[rt << 1].l) + 1] + ansl : ansr;
return ans;
}
} bit;
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n >> m >> s + 1; p[0] = 1;
rep (i, 1, n) p[i] = p[i - 1] * P;
bit.build(1, 1, n, s);
rep (i, 1, m) {
int op; cin >> op;
if (op == 2) {
int l, r; cin >> l >> r;
int len = r - l + 1 >> 1;
unsigned int x = bit.ask(1, l, l + len - 1, 0), y = bit.ask(1, r - len + 1, r, 1);
cout << (x == y ? "Yes\n" : "No\n");
} else {
int k; char c; cin >> k >> c;
bit.change(1, k, c);
}
}
}
return 0;
}
- Contest Programming Securities Beginner AtCodercontest programming securities beginner contest programming beginner atcoder contest programming beginner registry contest programming beginner keyence contest programming beginner systems beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334