[Educational Codeforces Round 141 (Rated for Div. 2)题解

Educational Codeforces Round 141 (Rated for Div. 2)

A. Make it Beautiful

题意
重排数组判断是否能够不存在任何元素等于其前面的数之和
题解
全部相同则不行，否则排序后最小最大次小次大即可构造出

#include<bits/stdc++.h>
#define io ios::sync_with_stdio(false);cin.tie(0);
using namespace std;int main() {int t, n;cin >> t;while (t--) {cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i)cin >> a[i];sort(a.begin(), a.end());if (a.front() == a.back()) {cout << "NO\n";} else {cout << "YES\n";int i = 0, j = a.size() - 1;int op = 0;while (i <= j) {if (!op)cout << a[i++] << " ";elsecout << a[j--] << " ";op ^= 1;}cout << "\n";}}return 0;
}

B. Matrix of Differences

题意
排列填进一个数组，使得两两绝对值种类最多
题解
显然每一行仍是最小最大次小次大，每一行翻转一次即可

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int maxn = 4e6+10;
const int mod = 1e9+7;void solve() {int n;cin >> n;vector<vector<int>> a(n, std::vector<int>(n));int l = 1, r = n * n;int ok = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = ok ? l++ : r--;ok ^= 1;}if (i & 1) reverse(a[i].begin(), a[i].end());}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cout << a[i][j] << " \n"[j == n - 1];}}
}int main() {ios::sync_with_stdio(false),cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}
}

C. Yet Another Tournament

题意
你和 $n$ 个人比赛，第i个人一开始能赢前面 $i - 1$ 个人，即赢 $i - 1$ 场，你有 $m$ 的初始值， $\geq a[i]$ 即可赢第 $i$ 个人，按胜场排 $r k$ ，问你的最优 $r k$ 是什么。
题解
显然贪心的选最小的 $k$ 个人，考虑第 $k + 1$ 个人能否替换第 $k$ 个人，能替换的话等价于原本你, $k$ , $k + 1$ 的排名由3, 2, 1变成1, 1, 1则排名上升，每个都更新答案即可。

#include<bits/stdc++.h>using namespace std;
const int maxn = 5e5 + 5;
int a[maxn], b[maxn], s[maxn];
int main() {int t;cin >> t;while(t -- ){int n , m;cin >> n >> m;for(int i = 1 ; i <= n ; i ++ ){cin >> a[i];b[i] = a[i];}sort(b + 1 , b + 1 + n);for(int i = 1 ; i <= n ; i ++ ){s[i] = s[i - 1] + b[i];}int res = n + 1; //有 n + 1 个人for(int i = 1 ; i <= n ; i ++ ){if(m >= s[i]){res = min(res , n - i + 1);}if(i < n && m >= s[i] + max(a[i + 1] - b[i] , (int)0)){res = min(res , n - i);}}cout << res << "\n";}return 0;
}

D. Different Arrays

题意
你有 $n - 1$ 次操作，顺序将 $a_i$ 从 $a_{i-1}$ 流向 $a_{i + 1}$ 或者反过来。问最后 $n$ 个数的不同方案数。
题解
考虑将操作看成都是从 $a_{i - 1}$ 流向 $a_{i + 1}$ 值 $a_i$ 或者 $a_i$ , 每次其实相当于从添加一个新的数 $b _{i + 1}$ 同时对 $a_{i - 1}$ 修改产生新序列，所以 $a_{i-1}$ 具备无后效性， $d p [i] [j]$ 表示前 $i$ 个数字结尾为 $j$ 的方案数，枚举值域转移即可。时间复杂度 $O(n^3)$

#include<bits/stdc++.h>using namespace std;
using ll = long long;
const int maxn = 303;
const int del = 300 * 300;ll dp[maxn][maxn * maxn * 2];
int a[maxn];
const int mod = 998244353;int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}dp[1][a[1] + del] = 1;dp[2][a[2] + del] = 1;for (int i = 2; i <= n - 1; ++i) {for (int j = -del; j <= del; ++j) {dp[i + 1][a[i + 1] - j + del] = (dp[i + 1][a[i + 1] - j + del] + dp[i][j + del]) % mod;dp[i + 1][a[i + 1] + j + del] = (dp[i + 1][a[i + 1] + j + del] + dp[i][j + del]) % mod;if (!j) {dp[i + 1][a[i + 1] + del] = (dp[i + 1][a[i + 1] + del] - dp[i][j + del] + mod) % mod;}}}ll ans = 0;for (int i = -del; i <= del; ++i) {ans = (ans + dp[n][i + del]) % mod;}cout << ans;return 0;
}

E. Game of the Yea

题意
A和B轮流 $k$ 次尝试击杀boss, A在第 $a_i$ 次击杀boss, $B$ 在 $b_i$ 次，问对于所有 $i$ 从 $1$ 到 $n$ , 都是 $A$ 先击杀 $b oss$ 的有哪些
题解
不难转化为 $\lceil \frac{a_i}{k} \rceil \leq \lceil \frac{b_i}{k} \rceil$ , 显然有个枚举 $i$ 做数论分块并求前缀和的方案，复杂度 $O(n\sqrt{n}$ 无法通过本题，考虑对于 $a_i \leq b_i$ , 该式子显然成立，则讨论 $a_i > b_i$ 的情况，其实就是在询问是否存在 $x$ ，使得 $b_i \leq kx < a_i$ , 对这种情况做差分前缀和，枚举 $k$ 及其倍数为调和级数，可以在 $n l nn$ 复杂度通过此题

#include<bits/stdc++.h>using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], b[maxn], d[maxn];
int main() {ios::sync_with_stdio(false);cin.tie(0);int n, t;cin >> t;while(t--) {vector<int> ans;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i], d[i] = 0;}for (int i = 1; i <= n; ++i) {cin >> b[i];}for (int i = 1; i <= n; ++i) {if (a[i] > b[i]) {d[b[i]]++;d[a[i]]--;}}for (int i = 1; i <= n; ++i) {d[i] += d[i - 1];}for (int k = 1; k <= n; ++k) {bool f = 1;for (int j = k; j <= n; j += k) {if (d[j]) {f = 0;break;}}if (f)ans.emplace_back(k);}cout << ans.size() << "\n";for (auto u : ans) {cout << u << " ";}cout << '\n';}return 0;
}

F. Double Sort II

题意
题解
首先是个非常套路的 $t r i c k$ , 我们把 $i -> p_i$ 转换成一张图，则发现图由多个环组成，每个操作相当于环上断开一个点成自环，并将剩余的链再次成环。考虑假如只有一张图，每个环只有一个点是不用拆的，答案等于 $n - 环数$ 。现在有多个环，我们希望两边不操作的点数尽量多。由于每个环只能选一个点不操作，所以只有某个点最后同时成为环 $a$ 和另一张图的环 $b$ 的代表时，才能不操作，考虑把环看成点，a相当于左部点，b为右部点，有相同元素的两个点相连，使用 $d ini c$ 或者匈牙利求出二分图最大匹配即可，答案即为$n - $最大匹配数。输出方案的话，对于最大匹配的两个环任选一个代表点即可。时间复杂度$ O(n ^ 2 ) or O(n\sqrt{n})$

#include<bits/stdc++.h>using namespace std;
const int maxn = 3005;
int a[maxn], b[maxn], match[maxn << 1], tota, totb, bela[maxn], nxta[maxn], belb[maxn], nxtb[maxn];
bool vis[maxn << 1], va[maxn], vb[maxn];
int mp[maxn][maxn];vector<int> G[maxn];bool dfs(int x) {for (auto v : G[x]) {if (!vis[v]) {vis[v] = 1;if (!match[v] || dfs(match[v])) {match[v] = x;return 1;}}}return 0;
}void getcir(bool* v, int tot, int* bel, int i, int *nxt) {int x = i;while (!v[x]) {v[x] = 1;bel[x] = tot;x = nxt[x];}
}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];nxta[i] = a[i];}for (int i = 1; i <= n; ++i) {cin >> b[i];nxtb[i] = b[i];}for (int i = 1; i <= n; ++i) {if (!va[i]) {getcir(va, ++tota, bela, i, nxta);}   if (!vb[i]) {getcir(vb, ++totb, belb, i, nxtb);}}for (int i = 1; i <= n; ++i) {if (mp[bela[i]][belb[i]])continue;mp[bela[i]][belb[i]] = i;G[bela[i]].emplace_back(belb[i]);}int ans = 0;for (int i = 1; i <= tota; ++i) {memset(vis, 0, sizeof(vis));if (dfs(i))ans++;}cout << n - ans << "\n";vector<int> p (n + 1, 0);for (int i = 1; i <= totb; ++i) {if (match[i]) {p[mp[match[i]][i]] = 1;}}for (int i = 1; i <= n; ++i) {if (!p[i]) {cout << i << ' ';}}return 0;
}

G. Weighed Tree Radius

题意
给定一颗 $n$ 个点，点权为 $a_i$ 的树，定义 $w_v(u) = dis(v, u) + a_u$ , $max_{1\leq u \leq n}w_v(u)$ , 定义半径为 $r = min (e (u))$
题解
这种问题也可以看成是 $t r i c k$ 吧, 我们考虑往每个点挂个虚点，定义 $w'(u,v) = dis(u,v) + a(u) + a(v), w'(u, u) = 2 * a_u$ 。在这种树的直径上我们有很多优美的性质可以解决问题，显然对于原问题我们考虑其应该是与中点相关，所以我们考虑对于新树的直径的中点，容易证得在原树上必定存在一个点为直径的中点，使得 $\lceil\frac{d}{2}\rceil$ , 下证，首先

假如中点在原树上，由于 $d i s$ 是连续的，所以显然满足。否则假如中点不在原树上，设 $mi d$ 在 $u$ 所在链上，我们考虑此时 $e (u) = a (u)$ 且 $e (u) > d i s (u, v) + a (v)$ , 而这时中点取 $u$ 则满足 $d = e (u) = a (u)$ , 这也是为什么我们要挂上2个虚点的原因。
其次对于任意顶点 $z$ 来说 $e(z) = max(w_z(x), w_z(y))$ , 由于直径的性质，这很显然。所以显然直径上的中点所得的 $e$ 为最小值, $e(v)_{min} = \lceil\frac{d}{2}\rceil$

现在问题就是怎么维护树的直径及修改，对于同一颗树上的多个联通块的合并，其树的直径的端点仍然等于这两个连通块的直径端点4选2。所以现在这是一个naive的问题，树上随便定义一个顺序，直接用线段树暴力合并修改即可。使用 $RMQ$ 求 $L C A$ 时间复杂度为 $O (n l o g n)$

#include<bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
#define lson p << 1, l, mid
#define rson p << 1 | 1, mid + 1, r 
using namespace std;
using ll = long long;
const int maxn = 2e5 + 5;
int n, a[maxn], dfn[maxn], d[maxn], st[maxn << 1][21], lg[maxn << 1], ti, m;
vector<int> G[maxn];
void dfs(int x, int f) {dfn[x] = ++ti;d[x] = d[f] + 1;st[ti][0] = x;for (auto v : G[x]) {if (v == f)continue;dfs(v, x);st[++ti][0] = x;}
}
void RMQ() {for (int i = 2; i <= ti; ++i)lg[i] = lg[i >> 1] + 1;for (int j = 1; j <= lg[ti]; ++j) {for (int i = 1; (i + (1 << j) - 1) <= ti; ++i) {int r = i + (1 << (j - 1));st[i][j] = d[st[i][j - 1]] < d[st[r][j - 1]] ? st[i][j - 1] : st[r][j - 1]; }}
}
int query(int l, int r) {if (l > r)swap(l, r);int k = lg[r - l + 1];return d[st[l][k]] < d[st[r - (1 << k) + 1][k]] ? st[l][k] : st[r - (1 << k) + 1][k];
}int LCA(int x, int y) {return query(dfn[x], dfn[y]);
}ll dis(int x, int y) {return d[x] + d[y] - 2 * d[LCA(x, y)];
}struct TreeDIA {int x, y;ll len;TreeDIA() { //默认构造x = y = len = 0;}TreeDIA(int _x, int _y) : x(_x), y(_y) {len = dis(x, y) + a[x] + a[y];}bool operator<(TreeDIA b) {return len < b.len;}};
TreeDIA merge(TreeDIA A, TreeDIA B) {TreeDIA p[] = {A, B, TreeDIA(A.x, B.x), TreeDIA(A.x, B.y), TreeDIA(A.y, B.x), TreeDIA(A.y, B.y)};return *max_element(p, p + 6);
}struct SegmentTree {TreeDIA dia[maxn << 2];void pushUp(int p) {dia[p] = merge(dia[ls], dia[rs]);}void update(int p, int l, int r, int x) {if (l == r) {dia[p] = TreeDIA(x, x);return;}int mid = l + r >> 1;if (x <= mid)update(lson, x);elseupdate(rson, x);pushUp(p);}void build(int p, int l, int r) {if (l == r) {dia[p] = TreeDIA(l, l);return;}int mid = l + r >> 1;build(lson);build(rson);pushUp(p);}
}tr;int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];for (int i = 1; i < n; ++i) {int u, v;cin >> u >> v;G[u].emplace_back(v);G[v].emplace_back(u);}dfs(1, 0);RMQ();tr.build(1, 1, n);cin >> m;for (int i = 1; i <= m; ++i) {int v, x;cin >> v >> x;a[v] = x;tr.update(1, 1, n, v);ll ans = max({(tr.dia[1].len + 1) / 2, (ll)a[tr.dia[1].x], (ll)a[tr.dia[1].y]});cout << ans << '\n';}return 0;
}