Educational Codeforces Round 126

Educational Codeforces Round 126

A

根据前面的 a i a_i ai​ 和 b i b_i bi​ 贪心的调整即可。$O(n)$。

int a[maxn], b[maxn];
void solve() {int n;cin >> n;for (int i = 0; i < n; ++i)cin >> a[i];for (int i = 0; i < n; ++i)cin >> b[i];ll ans = 0;for (int i = 1; i < n; ++i) {ll t1 = abs(a[i] - a[i - 1]) + abs(b[i] - b[i - 1]);ll t2 = abs(b[i] - a[i - 1]) + abs(a[i] - b[i - 1]);ans += min(t1, t2);}cout << ans << endl;
}

B

可以先 BFS 一遍预处理出所有数字的最少操作次数。$O(n)$。

也可以枚举加一的次数去算。

int a[maxn], ans[maxn], vis[maxn];
void bfs(int n = 32768) {queue<pii> q;q.push({32768, 0});vis[32768] = 1;vis[0] = 1;while (!q.empty()) {int x = q.front().first, v = q.front().second;q.pop();ans[x] = v;if (x >= 1 && !vis[x - 1]) {q.push({x - 1, v + 1});vis[x - 1] = 1;}if (x % 2 == 0 && !vis[x / 2]) {q.push({x / 2, v + 1});vis[x / 2] = 1;if (!vis[(x + 32768) / 2]) {q.push({(x + 32768) / 2, v + 1});vis[(x + 32768) / 2] = 1;}}}
}
void solve() {int n;cin >> n;bfs(32768);for (int i = 1; i <= n; ++i) {cin >> a[i];cout << ans[a[i]] << ' ';}
}

C

因为一次只会加 $1$ 或者 $2$ 的高度，设原来最高的高度是 $h$，那么最后所有树的高度应该是 $h$ 或者 $h+1$。然后统计每棵树需要新增的高度，计算需要的奇数天和偶数天的数量，如果奇数更多没办法补上，如果偶数更多可以用奇数天去补。每 $4$ 天可以增加 $6$ 个高度，算一下需要几个 $4$ 天就好了。

#include 
using namespace std;
using ll = long long;
const ll inf = 1e15;
const int maxn = 4e5 + 5;
ll a[maxn], f[6] = {0, 1, 2, 2, 3, 4};
void solve() {int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}ll mx = *max_element(a + 1, a + n + 1);ll odd = 0, even = 0, ans = inf;for (int i = 1; i <= n; ++i) {ll dx = mx - a[i];if (dx & 1)odd++;even += dx / 2;}ll res = 0;if (odd >= even) {res = odd * 2 - (odd > even);} else {res = odd * 2;even -= odd;even *= 2;ll a = even / 6, b = even % 6;res += 4 * a + f[b];}ans = min(res, ans);odd = 0, even = 0, mx++;for (int i = 1; i <= n; ++i) {ll dx = mx - a[i];if (dx & 1)odd++;even += dx / 2;}res = 0;if (odd >= even) {res = odd * 2 - (odd > even);} else {res = odd * 2;even -= odd;even *= 2;ll a = even / 6, b = even % 6;res += 4 * a + f[b];}ans = min(res, ans);cout << ans << endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;cin >> T;while (T--) {solve();}
}

D

看到区间加等差数列容易想到线段树维护差分数组，然后贪心的考虑，因为后面加的多所以从后往前修改。

但是因为从后往前每一位要改的都是固定的，可以直接算出来以后用前缀和来处理，这样就是 $O(n)$ 的，实现起来也简单的多。

#include 
using namespace std;
using ll = long long;const int maxn = 3e5 + 5;
int n, k;
ll a[maxn], d[maxn];
namespace sgt {
ll t[maxn << 2], tag[maxn << 2];
#define ls p << 1
#define rs p << 1 | 1
void push_up(int p) { t[p] = t[ls] + t[rs]; }
void build(int p, int l, int r, ll *a) {if (l == r) {t[p] = a[l];tag[p] = 0;return;}int mid = (l + r) >> 1;build(ls, l, mid, a);build(rs, mid + 1, r, a);push_up(p);
}
void push_down(int p, int l, int r) {int mid = (l + r) >> 1;t[ls] += tag[p] * (mid - l + 1);t[rs] += tag[p] * (r - mid);tag[ls] += tag[p];tag[rs] += tag[p];tag[p] = 0;
}
void modify(int p, int x, int y, int l, int r, ll k) {if (x <= l && r <= y) {t[p] += k * (r - l + 1);tag[p] += k;return;}int mid = (l + r) >> 1;push_down(p, l, r);if (x <= mid)modify(ls, x, y, l, mid, k);if (y > mid)modify(rs, x, y, mid + 1, r, k);push_up(p);
}
ll query(int p, int x, int y, int l, int r) {if (x <= l && r <= y) {return t[p];}int mid = (l + r) >> 1;push_down(p, l, r);ll ans = 0;if (x <= mid)ans += query(ls, x, y, l, mid);if (y > mid)ans += query(rs, x, y, mid + 1, r);push_up(p);return ans;
}
}; // namespace sgtvoid solve() {cin >> n >> k;for (int i = 1; i <= n; ++i) {cin >> a[i];d[i] = a[i] - a[i - 1];}sgt::build(1, 1, n, d);ll ans = 0;for (int i = n; i >= 1; --i) {int j = max(1, i - k + 1);ll p = i - j + 1;ll tmp = sgt::query(1, 1, i, 1, n);if (tmp <= 0)continue;tmp = (tmp + p - 1) / p;ans += tmp;sgt::modify(1, j, j + k - 1, 1, n, -tmp);}cout << ans << endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;// cin >> T;while (T--) {solve();}
}

E

区间内连通块数量相当于总的块数减去有效的边数。先用前缀和预处理出块数，然后用并查集维护前缀有效边数和。由于是从整个序列左端点开始计算的，查询的时候可能会把左边的一些不连通的块归到一起。然后注意到只有最左边是一段连续的 101 时才可能出现这种情况，所以找到第一个不是 101 的列，分类讨论：

• 如果所有的列都是 101，答案就是 $2$
• 如果上中下都是 1，说明左边这些都能连到右边去，答案不变
• 如果上下都是 0，说明这两段都是独立的，答案 $+2$
• 其余情况都是有一个可以和右边连着，另一个独立，答案 $+1$

做法来源于官方题解，下面的代码也是照着答案写的。细节稍微有点多。

#include 
using namespace std;
using ll = long long;
#define endl '\n'
const int maxn = 5e5 + 5;
namespace dsu {
int fa[maxn << 2], sz[maxn << 2];
void init(int n) {iota(fa, fa + n + 1, 0);fill(sz, sz + n + 1, 1);
}
int find(int x) { return fa[x] == x ? fa[x] : (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;
}
}; // namespace dsu
char str[maxn];
int a[3][maxn], tot[maxn];
int ph[maxn], pv[maxn], nxt[maxn];
void solve() {int n, q;cin >> n;for (int i = 0; i < 3; ++i) {cin >> (str + 1);for (int j = 1; j <= n; ++j)a[i][j] = (str[j] == '1');}dsu::init(n * 3);for (int i = 1; i <= n + 1; ++i) {tot[i + 1] += tot[i];for (int j = 0; j < 3; ++j)tot[i + 1] += a[j][i];}for (int i = 1; i <= n; ++i) {for (int j = 0; j < 2; ++j) {if (a[j][i] && a[j + 1][i] && dsu::merge(j * n + i, j * n + n + i))pv[i + 1]++;}for (int j = 0; j < 3; ++j) {if (i > 1 && a[j][i] && a[j][i - 1] &&dsu::merge(j * n + i, j * n - 1 + i))ph[i]++;}}for (int i = 1; i <= n + 1; ++i) {pv[i] += pv[i - 1], ph[i] += ph[i - 1];}for (int i = n; i >= 1; --i) {if (a[0][i] && !a[1][i] && a[2][i])nxt[i] = nxt[i + 1] + 1;}cin >> q;while (q--) {int l, r;cin >> l >> r;int pos = l + nxt[l];if (pos > r) {cout << 2 << endl;continue;}int cnt = tot[r + 1] - tot[pos];int edg = pv[r + 1] - pv[pos] + ph[r] - ph[pos];int ans = cnt - edg;if (pos != l) {if (a[0][pos] && a[1][pos] && a[2][pos]);else if (!a[0][pos] && !a[2][pos])ans += 2;elseans++;}cout << ans << endl;}
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;// cin >> T;while (T--) {solve();}
}

F

题目给的这 $n$ 个区间都是固定的，可以一个个分开来考虑。对于一个区间，如果新增 $k-1$ 个传送门将其分为 $k$ 个子区间，显然最优的放法是尽可能平均的放置。

我们的目标是最小化新增的传送门数量，使费用不超过 $m$，所以我们希望每次新放的传送门都能尽可能的多节省一些费用。在一个区间内新增一个传送门所节省的费用可以 $O(1)$ 计算。在一个区间内，随着传送门数量的增加，每次新增所能节省的费用会逐渐减少。那么我们可以二分这个节省的费用 $cost$，只要往一个区间里加传送门节省的费用 $\ge cost$，就继续增加，这可以固定 $cost$ 后二分门的数量来算。如果最后多省下了一些费用，再计算出可以去掉的传送门数量，减一下就是答案了。

#include 
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define endl '\n'
const int maxn = 2e5 + 5;
int n;
ll a[maxn];
ll calc(ll dis, ll seg) {ll x = dis % seg, y = seg - x, v = dis / seg;return y * v * v + x * (v + 1) * (v + 1);
}
pll check(ll save) {ll cost = 0, cnt = 0;for (int i = 1; i <= n; ++i) {ll d = a[i] - a[i - 1];ll l = 0, r = d, res = 1;while (l <= r) {ll mid = (l + r) >> 1;if (calc(d, mid - 1) - calc(d, mid) >= save)res = mid, l = mid + 1;elser = mid - 1;}cost += calc(d, res);cnt += res - 1;}return {cost, cnt};
}
void solve() {cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];ll m;cin >> m;ll l = 0, r = 1e18, save = 0;while (l <= r) {ll mid = (l + r) >> 1;pll tmp = check(mid);if (tmp.first <= m)save = mid, l = mid + 1;elser = mid - 1;}pll ans = check(save);ans.second -= (m - ans.first) / save;cout << ans.second << endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;// cin >> T;while (T--) {solve();}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！