ABC361(A-G)
A - Insert¶
题目大意
给你 \(N\) 个数 \(A_1, A_2, \cdots, A_N\)，将 \(X\) 插入到 \(A_K\) 和 \(A_{K+1}\) 之间，输出插入后的 \(N+1\) 个数。
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, k, x, a;
cin >> n >> k >> x;
for(int i = 0; i < k; i++)
{
cin >> a;
cout << a << ' ';
}
cout << x << ' ';
for(int i = k; i < n; i++)
{
cin >> a;
cout << a << ' ';
}
return 0;
}
B - Intersection of Cuboids¶
题目大意
在三维空间中，可以用一个六元组 \((a, b, c, d, e, f)\) 表示长方体，其中 \((a, b, c)\) 和 \((d, e, f)\) 分别代表对角线两个点的坐标，且 \(a < d\)，\(b < e\)，\(c < f\)。
给你两个长方体的六元组，判断这两个长方体是否相交（仅当相交的部分的体积是正数，这两个长方体才相交）
解题思路
将长方体三条边投影进行相交即可，则长方体相交体积大于 \(0\) 的条件等价于三条边的投影相交的长度都大于 \(0\)
参考代码
#include <iostream>
using namespace std;
int main()
{
int x[2][2], y[2][2], z[2][2];
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
cin >> x[i][j] >> y[i][j] >> z[i][j];
auto check = [](int x[2][2]) -> bool {
int lx = max(x[0][0], x[1][0]), rx = min(x[0][1], x[1][1]);
return lx < rx;
};
if(check(x) && check(y) && check(z)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
C - Make Them Narrow¶
题目大意
给你 \(N\) 个数 \(A_1, A_2, \cdots, A_N\)，你需要删除其中 \(K(1 < k < N \le 2 \times 10 ^5)\) 个数，使得剩下的数字的最大值减去最小值 最小
解题思路
首先将 \(N\) 个数排序。
假设当前最小的数是 \(A_l\)，最大的数是 \(A_r\) 。如果直观的做，考虑每一次删除应该删掉 \(A_l\) 还是 \(A_r\)，需要比较 \(A_r - A_{r-1}\) 和 \(A_{l+1} - A_l\) 的值，哪个大删哪个。一开始我就是这么做的，但是 WA 了两发之后发现情况不太对，因为如果 \(A_r - A_{r-1} = A_{l+1} - A_l\) 的话，我们需要比较下一个值，这中间边界条件不太好想。。
正确的做法是，由于数列已经排过序，最终的结果一定是左边删了若干个，右边删了若干个，相当于中间长度为 \(N-K\) 的序列是最终保留的数字，直接滑动窗口来枚举所有的 \(N-K\) 序列的答案就可以了。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
k = n - k;
int ans = a[k-1] - a[0];
for(int r = k; r < n; r++)
ans = min(ans, a[r]-a[r-k+1]);
cout << ans << endl;
return 0;
}
D - Go Stone Puzzle¶
题目大意
有 \(N(2 \le N \le 14)\) 个石头排成一行，第 \(i\) 个石头可能是黑色的（用字符 B 表示）或白色的（用字符 W 表示），初始的时候在第 \(N\) 个石头后面还有两个空位，你可以借助这两个空位变换石头的排列，变换的规则如下：
- 首先，选择两个相邻的且都有石头的位置 \(x\) 和 \(x+1\)。
- 假设当前的空位置 \(k\) 和 \(k+1\) 没有石头，将位置 \(x\) 的石头放到位置 \(k\)，位置 \(x+1\) 的石头放到 \(K+1\)
- 然后，位置 \(x\) 和位置 \(x+1\) 成为新的空位。
给你初始的石头排列 \(S\)，问，能不能将其变成 \(T\)，如果能，输出最少的变换次数，如果不能，输出 -1。
解题思路
\(N+2\) 个位置，每个位置三种状态（黑、白、空），但由于空位置始终只有 \(2\) 个，状态数远远低于 \(3^{N+2}\)，直接 bfs 即可。
参考代码
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
int n;
string start, target;
int bfs()
{
if(start == target) {
return 0;
}
unordered_map<string, int> dis;
dis[start] = 0;
queue<pair<string, int>> q;
q.push({start, n});
while (!q.empty())
{
string s = q.front().first;
int e = q.front().second;
q.pop();
int d = dis[s];
for (int i = 0; i < n + 1; i++)
{
if (s[i] == '.' || s[i+1] == '.')
continue;
swap(s[i], s[e]);
swap(s[i + 1], s[e + 1]);
if (s == target)
return d + 1;
if (!dis.count(s))
{
dis[s] = d + 1;
q.push({s, i});
}
swap(s[i], s[e]);
swap(s[i + 1], s[e + 1]);
}
}
return -1;
}
int main()
{
cin >> n >> start >> target;
start += "..";
target += "..";
cout << bfs() << endl;
return 0;
}
E - Tree and Hamilton Path 2¶
题目大意
给你一棵 \(N(2 \le N \le 2 \times 10^5)\) 个点的树，树中每一条边都有边权（边权为正），你可以从任意一个点出发，每走过一条边就要计入一次边权的花费，问：访问所有点的总花费的最小值是多少？
解题思路
假设从某个点出发，访问所有点 然后回到起点，那么花费就是所有边权 \(2\) 倍的和，这是因为每一条边都会被走过 \(2\) 次。
现在考虑不需要回到起点怎么做，这代表着我们从某个起点出发，访问到最后一个点就结束了，于是从终点回到起点的路径中所有的边权只需要记入 \(1\) 次权值。所以我们要最大化起点到终点的路径权值之和，这就是 树的直径。用所有边权的 \(2\) 倍和减去 树的直径 即可。
参考代码
#include <iostream>
using namespace std;
using LL = long long;
const int maxn = 2E5 + 10;
const int maxm = maxn * 2;
int n;
int head[maxn], edge[maxm], ne[maxm], cost[maxm], idx = 1;
void add(int u, int v, int w)
{
edge[idx] = v;
ne[idx] = head[u];
cost[idx] = w;
head[u] = idx++;
}
LL dis[maxn];
int z = 0;
void dfs(int u, int fa)
{
for(int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if(v == fa)
continue;
dis[v] = dis[u] + cost[i];
if(dis[v] > dis[z])
z = v;
dfs(v, u);
}
}
int main()
{
cin >> n;
LL ans = 0;
for(int i = 1, u, v, w; i < n; i++)
{
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
ans += 2 * w;
}
dfs(1, 0);
dis[z] = 0;
dfs(z, 0);
ans -= dis[z];
cout << ans << endl;
return 0;
}
F - x = a^b¶
题目大意
给你一个整数 \(N(1 \le N \le 10^{18})\)，求出 \([1, N]\) 中有多少个数字 \(x\) 可以被表示为 \(x = a^b\) 且 \(b \ge 2\) 的形式。
解题思路
由于 \(N\) 是 \(10^{18}\) ，首先考虑 \(b \ge 3\) 的数字，我们可以在枚举所有的 \(2 \le a \le 10^6\)，得到所有 \(b \ge 3\) 的答案。
接下来考虑 \(b = 2\) 的答案，直接枚举 \(a\) 需要枚举到 \(10^9\)，这是不行的。但是， \([1, N]\) 里面完全平方数的个数是等于 \(\sqrt{N}\) 的，因此 \(b = 2\) 的答案就是 \(\sqrt{N}\)。
这样会有一个问题，\(b \ge 3\) 的时候也统计了一些完全平方数，还需要将这一部分的值排除掉。进一步我们会发现：
- 当 \(b \ge 3\) 且 \(b\) 是偶数时，\(a^b = a^{2k} = (a^2)^k\) 一定是完全平方数。
- 当 \(b \ge 3\) 且 \(b\) 是奇数时，\(a^b = a^{2k+1} = (a^2)^ka\)，此时如果 \(a\) 是完全平方数，则 \(a^b\) 就是完全平方数。
根据第一个推论，枚举 \(b \ge 3\) 时只需要枚举奇数的 \(b\)。
根据第二个推论，枚举 \(b \ge 3\) 的所有 \(a\) 时需要跳过 \(a\) 是完全平方数的情况。
这样，我们就能不重不漏的枚举出所有答案。
参考代码
#include <iostream>
#include <cmath>
#include <unordered_set>
using namespace std;
int main()
{
using LL = long long;
LL n;
cin >> n;
unordered_set<LL> nums;
for(LL i = 2; i * i * i <= n; i++)
{
if((LL)sqrt(i) * (LL)sqrt(i) == i)
continue;
LL x = i;
while(x <= n / i / i)
{
x *= i * i;
nums.insert(x);
}
}
cout << (LL)sqrtl(n) + nums.size() << endl;
return 0;
}
G - Go Territory¶
题目大意
在二维平面上有 \(N(1 \le N \le 2 \times 10^5)\) 个点，这 \(N\) 个点都在第一象限（或第一象限的坐标轴上），第 \(i\) 个点的坐标是 \((X_i, Y_i)\)，其中 \(0 \le X_i, Y_i \le 2 \times 10^5\) 。
假设这 \(N\) 个点是黑色的点，其他点是白色的。对于一个白色点来说，将黑色点视为障碍，如果可以经过若干次上下左右的移动到达 \((-1, -1)\)，那么这个白色的点没有被围住。如果无论如何也无法移动到 \((-1, -1)\)，那么这个白色点就是被黑色点围住的点。
问：这 \(N\) 个黑色点围住了多少个白色点？
解题思路
由于 \(0 \le X_i, Y_i \le 2 \times 10^5\)，如果将格点视为图的点跑一遍 dfs 求联通块会超时。考虑到 \(N \le 2 \times 10^5\)，可以按照 \(N\) 个黑色点，将每一行相邻的白色点合并起来，例如这个样例：
合并后我们可以得到：
-
当 \(y = 0\) 时，有 \([0, 0],[4, 5], [8, +\infty]\) 三个区间是白色点。
-
当 \(y = 1\) 时，有 \([1, 2],[4, 4], [6, 7], [9, +\infty]\) 四个个区间是白色点。
- \(\cdots\cdots\)
这样，我们只需要在每个区间上求连通块即可。估算一下，最多有 \(2 \times 10^5\) 行，每新增一个黑色点最多新增一个区间，所以最多有 \(2 \times 10^5 + N\) 个区间，dfs 是可以通过的。
接下来考虑压缩区间的数量。许多行实际是没有黑点的，这些行只有一个区间 \([0, +\infty]\)，这些行其实没有必要存储，用一个哈希表存储至少有一个黑点的行即可（见代码实现）。此外，可以再将平面扩展的左端扩展成 \(x = -1\)，以及右端扩展成所有 \(X\) 坐标的最大值 \(m\)，这样会方便后续的处理。
初始的时候，最下、最上、最左、最右的所有区间一定是没有被围住的，从这些区间开始 dfs 即可。但由于我扩展了左右边界，所以最左和最右是不用枚举的（会自动遍历过去）。此外，由于我只存储了有黑点的行，所以对于 \(y = k\) 行，如果 \(y = k + 1\) 或者 \(y = k - 1\) 行没有黑点，那么 \(y = k\) 行的所有区间就不会被围住，从这些点开始 dfs 就可以了。
对于一个区间，dfs 在转移时，枚举出上方和下方坐标范围内相邻区间即可。dfs 遍历结束后，没有被访问到的区间长度之和就是被围住的白点数量。
具体还是看代码吧。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
using LL = long long;
struct Line
{
int y, l, r;
bool vis{false};
bool operator<(const Line &other) const { return l < other.l; }
int Length() const { return r - l + 1; }
};
unordered_map<int, vector<int>> black;
unordered_map<int, vector<Line>> lines;
void dfs(const Line &now)
{
if (auto it = lines.find(now.y - 1); it != lines.end())
{
vector<Line> &down_line = it->second;
auto down_line_it = lower_bound(down_line.begin(), down_line.end(), now);
if (down_line_it != down_line.begin())
{
--down_line_it;
if (down_line_it->r >= now.l && !down_line_it->vis)
{
down_line_it->vis = true;
dfs(*down_line_it);
}
++down_line_it;
}
for (; down_line_it != down_line.end() && down_line_it->l <= now.r; down_line_it++)
if (!down_line_it->vis)
{
down_line_it->vis = true;
dfs(*down_line_it);
}
}
if (auto it = lines.find(now.y + 1); it != lines.end())
{
vector<Line> &up_line = it->second;
auto up_line_it = lower_bound(up_line.begin(), up_line.end(), now);
if (up_line_it != up_line.begin())
{
--up_line_it;
if (up_line_it->r >= now.l && !up_line_it->vis)
{
up_line_it->vis = true;
dfs(*up_line_it);
}
++up_line_it;
}
for (; up_line_it != up_line.end() && up_line_it->l <= now.r; up_line_it++)
if (!up_line_it->vis)
{
up_line_it->vis = true;
dfs(*up_line_it);
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m = -1;
cin >> n;
if (n == 0)
{
cout << 0 << endl;
return 0;
}
for (int i = 0, x, y; i < n; i++)
{
cin >> x >> y;
black[y].push_back(x);
m = max(m, x);
}
m++;
for (auto &[y, v] : black)
{
vector<Line> row;
sort(v.begin(), v.end());
Line now{y, -1, -1};
for (auto x : v)
{
now.r = x - 1;
if (now.Length() > 0)
row.emplace_back(now);
now.l = x + 1;
}
now.r = m;
row.emplace_back(now);
lines[y] = move(row);
}
for (auto &[y, row] : lines)
if (!lines.count(y - 1) || !lines.count(y + 1))
for (auto &line : row)
if (!line.vis)
{
line.vis = true;
dfs(line);
}
LL ans = 0;
for (auto &[y, row] : lines)
for (auto &line : row)
if (!line.vis)
ans += line.Length();
cout << ans << endl;
return 0;
}
创建日期: 2024-07-24