Codeforces Round 914 (Div. 2) A~E

本文主要是介绍Codeforces Round 914 (Div. 2) A~E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.Forked!（思维）

题意：

给出骑士的跳跃能力 $(x, y)$ 以及国王和皇后的位置，问有多少个位置可以让骑士可以直接攻击到国王和皇后。

分析：

棋盘非常大 $(10^{8} \times 10^{8})$ ，因此无法枚举所有位置，所以需要转换思想，把国王的位置看作骑士所在的位置，那么此时骑士能攻击到的位置就是实际上骑士可能被放置的位置，然后再检查这些位置能否同时攻击到皇后即可。

Tips:当 $x = y$ 时，骑士只能攻击四方向。

代码：

#include <bits/stdc++.h>typedef long long LL;
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 5e4;int n, m, x_k, y_k, x_q, y_q;void solve() {int ans = 0;cin >> n >> m >> x_k >> y_k >> x_q >> y_q;int dir[8][2] = {n, m, n, -m, -n, m, -n, -m, m, n, m, -n, -m, n, -m, -n};//8方向int len = 8;if (n == m) len = 4;//两个跳跃能力相同时，只能4方向跳跃for (int i = 0; i < len; i++) {int x = x_k + dir[i][0];//此时(x, y)为枚举的骑士位置int y = y_k + dir[i][1];for (int j = 0; j < len; j++) {int xx = x + dir[j][0];int yy = y + dir[j][1];if (xx == x_q && yy == y_q) {//检查能否攻击到皇后ans++;break;}}}cout << ans << endl;
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

B.Collecting Game(思维)

题意：

给出一个包含 $n$ 个元素的数组 $a$ ，开始时你可以选择一个数字 $a_i$ 并将这个数字从数组中取出，然后可以进行若干次以下操作：

如果当前数字 $a_i > a_j$ ( $a_j$ 为数组中剩余的一个数字)，那么可以从数组中将这个元素删除，并将这个元素的值加到 $a_i$ 中。

问，选择 $a_1, a_2, ..., a_n$ 作为开始的数字，最多可以删除多少个数字。

分析：

贪心的删除数字，在选择完数字后，可以先删除所有比自己小的数字，让自己尽可能大，然后从小到大依次去删除剩余的数字，直到无法删除，此时这一段维护的区间（起点到所有比起点大的被删除的元素），能删除的数字个数是相同的，记录能被删除的数字个数（所有前面数字均可），然后以不能被删除的点作为区间新的起点，继续去删除后面的数字，直到所有元素均被删除。

可以使用结构体存储数组，记录每个元素的值以及在原数组中的下标，并对元素的值按从小到大排序。

然后模拟上述过程即可。

代码：

#include <bits/stdc++.h>typedef long long LL;
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 5e4;struct Node{int num, id;bool operator < (const Node &o) const {if (num != o.num) return num < o.num;return id < o.id;}
}a[N];int n, ans[N];void solve() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i].num;a[i].id = i;}int l = 0;//区间起点sort(a, a + n);LL sum = a[0].num;for (int i = 1; i < n; i++) {if (sum < a[i].num) {//无法删除当前点了for (int j = l; j < i; j++) {//此时区间内能删除的点的数量均相同ans[a[j].id] = i - 1;}l = i;//更新区间起点sum += a[i].num;//记录前缀和} else {sum += a[i].num;}}for (int i = l; i < n; i++) {ans[a[i].id] = n - 1;//最后部分的数字作为起点可以删除其他所有元素}for (int i = 0; i < n; i++) { if (i) cout << ' ';cout << ans[i];}cout << endl;
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

C.Array Game(思维)

题意：

有个包含 $n$ 个正整数的数组 $a$ ，你可以进行以下操作 $k$ 次：

选择 $a$ 数组中的两个元素 $a_i, a_j(i \ne j)$ ，将 $a_j - a_i|$ 的结果放在 $a$ 数组最后。

问经过操作后，数组中最小的 $a_i$ 是多少。

分析：

分以下三种情况讨论：

$\ge 3$ : 前两次操作选择同一对 $(i, j)$ ，那么产生的两次减法的结果是相同的，那么再使用一次操作将这两个结果相减，得到的一定为0，因此只要 $\le k$ ，就必有 $min(a_1, a_2, ..., a_{n + k}) = 0$
$k = 1$ : 将数组排序，使用所有相邻的后一个数字减去建一个数字，记录最小的结果，然后取这个结果与原数组中的最小值比较，哪个小就是答案。
$k = 2$ : 取以下三种情况中的最小值
- $a$ 数组中的最小值
- $k = 1$ 时获得的最小值
- 枚举所有 $k = 1$ 时的情况，将这些点作为新的点，再通过枚举的+二分的方式找到原数组 $a$ 中与这个点最接近的数字（分两种情况，比查找的数字大和小），记录减法的最小结果。

代码：

#include <bits/stdc++.h>typedef long long LL;
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 5e4;int n, m;
LL a[N];void solve() {cin >> n >> m;for (int i = 0; i < n; i++) cin >> a[i];if (m >= 3) {cout << 0 << endl;return;}sort(a, a + n);if (m == 1) {LL ans = a[0];for (int i = 1; i < n; i++) {ans = min(ans, a[i] - a[i - 1]);}cout << ans << endl;} else {LL ans = a[0];for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {ans = min(ans, a[j] - a[i]);int pos = lower_bound(a, a + n, a[j] - a[i]) - a;
//找到第一个大于等于的数字位置，此时下标为第一个大于等于，前一个下标为最后一个小于的，判断哪个更接近if (pos != n) ans = min(ans, a[pos] - (a[j] - a[i]));if (pos > 0) ans = min(ans, (a[j] - a[i]) - a[pos - 1]);}}cout << ans << endl;}
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

D.Set To Max

题意：

给出包含 $n$ 个元素的数组 $a$ 和 $b$ ，你可以执行若干次以下操作：

选择一个区间 $\sim r$ ，让区间上所有的数字均修改为 $max(a_l, a_{l + 1}, ..., a_r)$

问，能否将数组 $a$ 变为数组 $b$

分析：

由于操作只能将数字变大，那么当 $a_i > b_i$ 时必然无解。

然后考虑 $a_i < b_i$ 的情况，此时只能选择左右两边最接近且 $a_j = b_i$ 的点，同时，如果在 $\sim j$ 之间出现了 $a_k > b_i$ 或 $b_k < b_i$ ，那么也无法将 $a_i$ 修改为 $b_i$ 。

对于D1(Easy Version)，由于数据较小，可以使用for循环对左右两边查找距离最近且值与 $b_i$ 相同的点，只要找到的元素与 $a_i$ 之间不存在更大的元素，且这段区间内的 $b_j$ 均大于等于 $b_i$ ，那么就可以完成修改（只需检查能否修改，不需要修改到数组中，两边只要有一边能找到就可以完成修改）。

对于D2(Hard Version)，可以使用vector存储数字对应的下标，使用二分对最近的值相同的点，并使用RMQ,线段树等算法对区间内 $a$ 数组的最大值， $b$ 数组的最小值进行查找，检查是否存在合法方案即可。

代码：

#include <bits/stdc++.h>typedef long long LL;
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 5e4;int n, m, TA[N << 2], TB[N << 2], a[N], b[N];void pushup(int x) {TA[x] = max(TA[x << 1], TA[x << 1 | 1]);TB[x] = min(TB[x << 1], TB[x << 1 | 1]);
}void build(int l, int r, int x) {if (l == r) {TA[x] = a[l];TB[x] = b[l];return;}int mid = l + r >> 1;build (l, mid, x << 1);build (mid + 1, r , x << 1 | 1);pushup(x);
}int queryMax(int l, int r, int x, int ql, int qr) {if (l >= ql && r <= qr) {return TA[x];}int mid = l + r >> 1;int ans = 0;if (ql <= mid) ans = max(ans, queryMax(l, mid, x << 1, ql, qr));if (qr > mid) ans = max(ans, queryMax(mid + 1, r , x << 1 | 1, ql, qr));return ans;
}int queryMin(int l, int r, int x, int ql, int qr) {if (l >= ql && r <= qr) {return TB[x];}int mid = l + r >> 1;int ans = 1e9;if (ql <= mid) ans = min(ans, queryMin(l, mid, x << 1, ql, qr));if (qr > mid) ans = min(ans, queryMin(mid + 1, r , x << 1 | 1, ql, qr));return ans;
}vector<int> V[N];void easy_version() {for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {cin >> b[i];}for (int i = 1; i <= n; i++) {if (a[i] > b[i]) {cout << "NO" << endl;return;} else if (a[i] < b[i]) {bool flag = false;for (int j = i - 1; j >= 1; j--) {if (b[j] < b[i] || a[j] > b[i]) {break;}if (a[j] == b[i]) {flag = true;break;}}for (int k = i + 1; k <= n; k++) {if (b[k] < b[i] || a[k] > b[i]) {break;}if (a[k] == b[i]) {flag = true;break;}}if (!flag) {cout << "NO" << endl;return;}}}cout << "YES" << endl;
}void hard_version() {for (int i = 1; i <= n; i++) V[i].clear();for (int i = 1; i <= n; i++) {cin >> a[i];V[a[i]].push_back(i);}for (int i = 1; i <= n; i++) {cin >> b[i];}build(1, n, 1);for (int i = 1; i <= n; i++) {if (a[i] != b[i]) {if (V[b[i]].empty()) {cout << "NO" << endl;return;}int right = lower_bound(V[b[i]].begin(), V[b[i]].end(), i) - V[b[i]].begin();int left = right - 1;if (left >= 0 && queryMax(1, n, 1, V[b[i]][left], i) == b[i] && queryMin(1, n, 1, V[b[i]][left], i) == b[i] || queryMax(1, n, 1, i, V[b[i]][right]) == b[i] && queryMin(1, n, 1, i, V[b[i]][right]) == b[i]) {}else {cout << "NO" << endl;return;}}}cout << "YES" << endl;
}int main() {int Case;cin >> Case;while (Case--) {cin >> n;if (n <= 1e3) {easy_version();} else {hard_version();}}return 0;
}

E.Tree Queries

题意：

给你一棵 $n$ 个点的树， $q$ 次询问，每次询问会给出一个点 $x$ 和 $k$ 个要删掉的点，在树上删掉这 $k$ 个点和 $k$ 个点相连的边后，询问在剩下的若干个连通块中， $x$ 能到的最远的点的距离。

分析：

首先考虑树的直径的性质：

当合并两个区间（即合并两棵树）时，新的树的直径的两个端点，一定是在原来两棵树直径的四个点里选两个点。
$x$ 所在的连通块能到的最远点，一定是 $x$ 这个连通块的直径的两个端点中的一个。

其次考虑 $df s$ 序的性质： $a$ 的 $df s$ 序对应 $[in [a], o u t [a]]$ ， $b$ 的 $df s$ 序区间对应 $[in [b], o u t [b]]$ 。

若 $ in[a]<in[b]<out[a] $，说明$ b $在$ a $的子树里，一定有$ in[a]<in[b] \le out[b] \le out[a]$

首先算出 $df s$ 序，删掉 $k$ 个点后，把 $df s$ 序切成若干个区间，区间数是大致是 $k - 2 k$ 级别的，剩下的区间都是 $x$ 的可达区间，每个区间对应一个连续的 $df s$ 序当删掉 $u$ 时，根据 $u$ 和 $x$ 的关系，有两种情况：

$l c a (u, x) = u$ ，即 $u$ 是 $x$ 的祖先，那么由于 $u$ 不可达了，记 $x$ 到 $u$ 的路径上 $u$ 的直连儿子是 $v$ ，那么相当于只保留下来 $v$ 这棵子树内可以到达，也就是 $ban$ 掉 $[0, in [v]) 、 [o u t [v], n)$ 。
$u$ 和 $x$ 没有祖先关系，那么由于 $u$ 不可达，所以 u 的这棵子树不可达了， $ban$ 掉 $[in [u], o u t [u]]$

根据 $k$ 个点，获取到 $k$ 个 $ban$ 掉的区间时，根据上面提到的 $df s$ 序的性质， $df s$ 序只会存在区间嵌套 $l_i< l_j< r_j< r_i）$ 的情况，不会存在两个 $df s$ 区间相交一部分 $l_i< l_j< r_i< r_j）$ 的情况。按左端点增序，左端点相同右端点降序排序遍历，手动去除掉被套在内层的区间，只保留外层的区间。这样得到的若干个区间，就是互不相交的若干个要 $ban$ 掉的 $df s$ 序区间，其补集，就是合法的区间，均与 $x$ 连通，利用上文提到的树的直径的性质，统一 $m er g e$ 合法区间的直径，用线段树上每一个区间维护这个 $df s$ 序区间的直径的两个点，求合法区间 $[l, r]$ 的直径时，先在线段树上做一个 $m er g e$ ，再对若干个合法区间做一个 $m er g e$ ，再和询问点 $x$ 做一个 $m er g e$ ，这样得到了 $x$ 连通块的直径的两个端点 $x$ 能到的最远点一定是直径两个点中的一个，分别询问距离取 $ma x$ 即可。

代码：

#include <bits/stdc++.h>const int N = 2e5 + 10, int_max = 0x3f3f3f3f;
using namespace std;
vector<int> dep, sz, par, head, tin, tout, tour;
vector<vector<int>> adj;
int n, ind, q;void dfs(int x, int p) {sz[x] = 1;dep[x] = dep[p] + 1;par[x] = p;for (auto &i: adj[x]) {if (i == p)continue;dfs(i, x);sz[x] += sz[i];if (adj[x][0] == p || sz[i] > sz[adj[x][0]])swap(adj[x][0], i);}if (p != 0)adj[x].erase(find(adj[x].begin(), adj[x].end(), p));
}void dfs2(int x, int p) {tour[ind] = x;tin[x] = ind++;for (auto &i: adj[x]) {if (i == p)continue;head[i] = (i == adj[x][0] ? head[x] : i);dfs2(i, x);}tout[x] = ind;
}int k_up(int u, int k) {if (dep[u] <= k)return -1;while (k > dep[u] - dep[head[u]]) {k -= dep[u] - dep[head[u]] + 1;u = par[head[u]];}return tour[tin[u] - k];
}int lca(int a, int b) {while (head[a] != head[b]) {if (dep[head[a]] > dep[head[b]])swap(a, b);b = par[head[b]];}if (dep[a] > dep[b])swap(a, b);return a;
}int dist(int a, int b) {return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}#define ff first
#define ss secondint dist(pair<int, int> a) {return dist(a.ff, a.ss);
}pair<int, int> merge(pair<int, int> a, pair<int, int> b) {auto p = max(make_pair(dist(a), a), make_pair(dist(b), b));for (auto x: {a.ff, a.ss}) {for (auto y: {b.ff, b.ss}) {if (x == 0 || y == 0)continue;p = max(p, make_pair(dist(make_pair(x, y)), make_pair(x, y)));}}return p.ss;
}pair<int, int> mx[N * 4];
#define LC(k) (2 * k)
#define RC(k) (2 * k + 1)void update(int p, int k, int L, int R) {if (L + 1 == R) {mx[k] = {tour[p], tour[p]};return;}int mid = (L + R) / 2;if (p < mid)update(p, LC(k), L, mid);elseupdate(p, RC(k), mid, R);mx[k] = merge(mx[LC(k)], mx[RC(k)]);
}void query(int qL, int qR, vector<pair<int, int>> &ret, int k, int L, int R) {if (qR <= L || R <= qL)return;if (qL <= L && R <= qR) {ret.push_back(mx[k]);return;}int mid = (L + R) / 2;query(qL, qR, ret, LC(k), L, mid);query(qL, qR, ret, RC(k), mid, R);
}// segtree template end
bool cmp(pair<int, int> a, pair<int, int> b) {return (a.ff < b.ff) || (a.ff == b.ff && a.ss > b.ss);
}int query(vector<int> arr, int x) {vector<pair<int, int>> banned, ret;for (int u: arr) {if (lca(u, x) == u) {u = k_up(x, dep[x] - dep[u] - 1);banned.push_back({0, tin[u]});banned.push_back({tout[u], n});} else {banned.push_back({tin[u], tout[u]});}}sort(banned.begin(), banned.end(), cmp);vector<pair<int, int>> tbanned; // remove nested intervalsint N = 0;for (auto [a, b]: banned) {if (b <= N)continue;else if (a != b) {tbanned.push_back({a, b});N = b;}}banned = tbanned;int tim = 0;for (auto [a, b]: banned) {if (tim < a)query(tim, a, ret, 1, 0, n);tim = b;}if (tim < n)query(tim, n, ret, 1, 0, n);pair<int, int> dia = make_pair(x, x);for (auto p: ret)dia = merge(dia, p);int ans = max(dist(x, dia.ff), dist(x, dia.ss));return ans;
}int main() {cin >> n >> q;dep = sz = par = head = tin = tout = tour = vector<int>(n + 1, 0);adj = vector<vector<int>>(n + 1);for (int i = 1; i < n; i++) {int a, b;cin >> a >> b;adj[a].push_back(b);adj[b].push_back(a);}dfs(1, 0);head[1] = 1;dfs2(1, 0);for (int i = 1; i <= n; i++) {update(tin[i], 1, 0, n);}for (int i = 1; i <= q; i++) {int x, k;cin >> x >> k;vector<int> arr(k);for (int &y: arr)cin >> y;cout << query(arr, x) << endl;}return 0;
}