AtCoder Beginner Contest 332
A - Online Shopping
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n >> m >> k;
ll ans = 0;
rep (i, 1, n) {
ll a, b; cin >> a >> b;
ans += a * b;
}
ans += (ans >= m ? 0 : k);
cout << ans;
}
return 0;
}
B - Glass and Mug
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> k >> n >> m;
int a = 0, b = 0;
rep (i, 1, k) {
if (a == n) a = 0;
else if (b == 0) b = m;
else if (n - a > b) a += b, b = 0;
else b -= n - a, a = n;
}
cout << a << ' ' << b;
}
return 0;
}
C - T-shirts
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n >> m >> s;
int ans = 0, a = m, b = 0;
rep (c, 0, n) {
bool f = 1;
b = c; a = m;
rep (i, 0, n - 1) {
if (s[i] == '0') a = m, b = c;
else if (s[i] == '1') {
if (a > 0) --a;
else if (b > 0) --b;
else { f = 0; break; }
} else {
if (b > 0) --b;
else { f = 0; break; }
}
}
if (f) { ans = c; break; }
}
cout << ans;
}
return 0;
}
D - Swapping Puzzle
int a[N][N], b[N][N];
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n >> m;
rep (i, 0, n - 1) rep (j, 0, m - 1) cin >> a[i][j];
rep (i, 0, n - 1) rep (j, 0, m - 1) cin >> b[i][j];
vector<int> x(n), z(m);
rep (i, 0, n - 1) x[i] = i;
rep (i, 0, m - 1) z[i] = i;
int ans = 1e9;
do {
vector<int> y = z;
do {
bool f = 1;
rep (i, 0, n - 1) rep (j, 0, m - 1) {
if (b[i][j] != a[x[i]][y[j]]) f = 0;
}
if (!f) continue;
vector<int> z = x;
int cnt = 0;
rep (i, 0, n - 1) rep (j, i + 1, n - 1) if (z[i] > z[j]) ++cnt;
z = y;
rep (i, 0, m - 1) rep (j, i + 1, m - 1) if (z[i] > z[j]) ++cnt;
ans = min(ans, cnt);
} while (next_permutation(y.begin(), y.end()));
} while (next_permutation(x.begin(), x.end()));
cout << (ans == 1e9 ? -1 : ans);
}
return 0;
}
E - Lucky bag
看 t 神代码会的,这里需要一个证明,枚举子集的 dp 复杂度只有 \(3^n\)
一般模板长这样
for (int t = 0; t < 1 << n; ++t)
for (int u = t; ; u = u - 1 & t) {
// dp logic
if (!u) break;
}
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n >> m;
ll s = 0;
rep (i, 0, n - 1) cin >> a[i], s += a[i];
double avg = 1.0 * s / m;
vector<double> cost(1 << n);
for (int t = 0; t < 1 << n; ++t) {
int cur = 0;
rep (i, 0, n - 1) if (t >> i & 1) cur += a[i];
cost[t] = (cur - avg) * (cur - avg);
}
const double inf = 1e30;
vector<double> d(1 << n, inf); d[0] = 0;
rep (_, 1, m) {
vector<double> tmp(1 << n, inf);
for (int t = 0; t < 1 << n; ++t)
for (int u = t; ; u = u - 1 & t) {
umin(tmp[t], d[u] + cost[u ^ t]);
if (!u) break;
}
swap(tmp, d);
}
cout << precision(12) << d.back() / m;
}
return 0;
}
F - Random Update Query
推个式子,用线段树维护就好了,没有区间查询,我就没有写 push up 的逻辑
const int N = 2e5 + 5, mod = 998244353;
int n, m, _, k, cas;
int a[N];
int qpow(int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ans = 1ll * ans * a % mod;
return ans;
}
struct BitTree {
struct node { int l, r, val, tag_k, tag_x; } tr[N << 2];
void push_down(int rt) {
if (tr[rt << 1].l == tr[rt << 1].r) {
tr[rt << 1].val = (1ll * tr[rt << 1].val * tr[rt].tag_k % mod + tr[rt].tag_x) % mod;
} else {
tr[rt << 1].tag_x = (1ll * tr[rt << 1].tag_x * tr[rt].tag_k % mod + tr[rt].tag_x) % mod;
tr[rt << 1].tag_k = 1ll * tr[rt << 1].tag_k * tr[rt].tag_k % mod;
}
if (tr[rt << 1 | 1].l == tr[rt << 1 | 1].r) {
tr[rt << 1 | 1].val = (1ll * tr[rt << 1 | 1].val * tr[rt].tag_k % mod + tr[rt].tag_x) % mod;
} else {
tr[rt << 1 | 1].tag_x = (1ll * tr[rt << 1 | 1].tag_x * tr[rt].tag_k % mod + tr[rt].tag_x) % mod;
tr[rt << 1 | 1].tag_k = 1ll * tr[rt << 1 | 1].tag_k * tr[rt].tag_k % mod;
}
tr[rt].tag_x = 0, tr[rt].tag_k = 1;
}
void build(int rt, int l, int r, int* a) {
tr[rt] = {l, r, 0, 1, 0};
if (l == r) { tr[rt].val = a[l]; return; }
int mid = l + r >> 1;
build(rt << 1, l, mid, a); build(rt << 1 | 1, mid + 1, r, a);
}
void change(int rt, int l, int r, int k, int x) {
if (r < l) return;
if (tr[rt].l >= l && tr[rt].r <= r) {
if (tr[rt].l == tr[rt].r) {
tr[rt].val = (1ll * tr[rt].val * k % mod + x) % mod;
} else {
tr[rt].tag_x = (1ll * tr[rt].tag_x * k % mod + x) % mod;
tr[rt].tag_k = 1ll * tr[rt].tag_k * k % mod;
}
return;
}
push_down(rt);
int mid = tr[rt].l + tr[rt].r >> 1;
if (l <= mid) change(rt << 1, l, r, k, x);
if (r > mid) change(rt << 1 | 1, l, r, k, x);
}
ll ask(int rt, int x) {
if (tr[rt].l == x && tr[rt].r == x) return tr[rt].val;
push_down(rt);
int mid = tr[rt].l + tr[rt].r >> 1;
if (x <= mid) return ask(rt << 1, x);
return ask(rt << 1 | 1, x);
}
} bit;
int main() {
IOS;
for (_ = 1; _; --_) {
cin >> n >> m;
ll s = 0;
rep (i, 1, n) cin >> a[i];
bit.build(1, 1, n, a);
rep (i, 1, m) {
int l, r, t; cin >> l >> r >> t;
int mm = qpow(r - l + 1, mod - 2);
int x = 1ll * t * mm % mod, k = 1ll * (r - l) * mm % mod;
bit.change(1, l, r, k, x);
}
rep (i, 1, n) cout << bit.ask(1, i) << ' ';
}
return 0;
}
- Beginner AtCoder Contest 332beginner atcoder contest 332 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 328 beginner atcoder contest 310 beginner atcoder contest 315