ABC364(A-F)
A - Glutton Takahashi¶
题目大意
有 \(N\) 道菜，第 \(i\) 道菜可能是 sweet 或者 salty。你将按顺序品尝这些菜，如果你吃了连续 \(2\) 道 sweet 的菜，后面的菜就不会再吃了。问：能否按顺序吃完所有菜？
参考代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
string s, t;
bool ans = true;
for(int i = 0; i < n - 1; i++)
{
cin >> t;
if(s == "sweet" && t == "sweet")
ans = false;
s = t;
}
cin >> s;
cout << (ans ? "Yes" : "No");
return 0;
}
B - Grid Walk¶
题目大意
有一个 \(H \times W\) 的二维矩阵，矩阵中每个位置可能是 . 代表空地，也可能是 # 代表障碍物。有一个机器人初始时站在 \((S_i, S_j)\) 上，随后，机器人会接到一个串指令，指令是一个由 L， R，U，D （分别代表上、下、左、右）组成的一个字符串。机器人会依次读取指令中的字符。例如，如果接收到 L 指令，机器人会“尝试”往左移动一步，如果左侧是障碍物，或者往左移动会超出矩阵的边界，则机器人不会跳过这条指令。
问：当机器人执行所有指令之后，机器人的最终位置是？
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m, r, c;
cin >> n >> m >> r >> c;
r--, c--;
vector<string> g(n);
for(int i = 0; i < n; i++)
cin >> g[i];
string ord;
cin >> ord;
auto inlim = [&](int r, int c) -> bool
{
return r >= 0 && r < n && c >= 0 && c < m;
};
for(auto ch : ord)
{
if(ch == 'L')
{
if(inlim(r, c-1) && g[r][c-1] == '.')
c--;
}
else if(ch == 'R')
{
if(inlim(r, c+1) && g[r][c+1] == '.')
c++;
}
else if(ch == 'U')
{
if(inlim(r-1, c) && g[r-1][c] == '.')
r--;
}
else
{
if(inlim(r+1, c) && g[r+1][c] == '.')
r++;
}
}
cout << ++r << ' ' << ++c;
return 0;
}
C - Minimum Glutton¶
题目大意
有 \(N(1 \le N \le 2 \times 10 ^5)\) 道菜，第 \(i\) 道菜的甜度是 \(A_i\)，咸度是 \(B_i\)。这 \(N\) 道菜有可能以任意上菜顺序端上来，你将按照上菜顺序依次品尝这些菜。当你品尝的菜的总甜度超过 \(X\)，或者总咸度超过 \(Y\) 时，后面的菜就不会再吃了。问：在所有可能的上菜顺序中，最少 能吃多少道菜？
解题思路
只有两种可能：要么甜度超标，要么咸度超标。对所有的 \(A_i\) 排序统计一个答案，然后对 \(B_i\) 排序统计一个答案，两个答案取最小值即可。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;
int main()
{
int n;
LL x, y;
cin >> n >> x >> y;
vector<LL> a(n);
auto solve = [](vector<LL> &a, LL x) -> int {
sort(a.begin(), a.end(), greater<int>());
LL sum = 0;
int ans = 0;
for(auto d : a)
{
ans++;
sum += d;
if(sum > x)
break;
}
return ans;
};
for(int i = 0; i < n; i++)
cin >> a[i];
int ans = solve(a, x);
for(int i = 0; i < n; i++)
cin >> a[i];
ans = min(ans, solve(a, y));
cout << ans << endl;
return 0;
}
D - K-th Nearest¶
题目大意
在数轴上有 \(N(1 \le N \le 10 ^ 5)\) 个点，第 \(i\) 个点的位置是 \(a_i\)。给你 \(Q(1 \le Q \le 10 ^ 5)\) 个询问，每个询问给你两个数字 \(b_i\) 和 \(k_i\)，你需要回答出在数轴的 \(N\) 个点中，和 \(b_i\) 距离第 \(k_i\) 近的点是哪个？
解题思路
对 \(a_i\) 排序，然后对于每一个询问，直接二分距离 \(x\)，查询 \(b_i - x\) 和 \(b_i + x\) 在所有 \(a_i\) 中的排名，判断是否大于等于 \(k_i\) 即可。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
while (q--)
{
int b, k;
cin >> b >> k;
int p = lower_bound(a.begin(), a.end(), b) - a.begin();
if(p == n)
cout << b - a[n-k] << '\n';
else
{
int l = 0, r = max(abs(b-a[0]), abs(b-a[n-1]));
while(l < r)
{
int mid = (l + r) / 2;
int lcnt = p - (lower_bound(a.begin(), a.begin() + p, b - mid) - a.begin());
int rcnt = (lower_bound(a.begin() + p, a.end(), b + mid + 1) - a.begin()) - p;
if(lcnt + rcnt >= k)
r = mid;
else
l = mid + 1;
}
cout << l << '\n';
}
}
return 0;
}
E - Maximum Glutton¶
题目大意
有 \(N(1 \le N \le 80)\) 道菜，第 \(i\) 道菜的甜度是 \(A_i(1 \le A_i \le 10000)\)，咸度是 \(B_i(1 \le B_i \le 10000)\)。这 \(N\) 道菜有可能以任意上菜顺序端上来，你将按照上菜顺序依次品尝这些菜。当你品尝的菜的总甜度超过 \(X(1 \le X \le 10000)\)，或者总咸度超过 \(Y(1 \le Y \le 10000)\) 时，后面的菜就不会再吃了。问：在所有可能的上菜顺序中，最多 能吃多少道菜？
解题思路
可以很容易想到背包 dp，定义 \(dp[i][j][k]\) 表示前 \(i\) 道菜中选出甜度不超过 \(j\) 且咸度不超过 \(k\) 的所有方案中，最多能选多少道菜。这样的话 dp 的时间复杂度是 \(O(NXY)\)，是会超时的。
考虑类似超大背包问题中的做法，转换 dp 表达式的顺序，定义 \(dp[i][j][k]\) 表示从前 \(i\) 到菜中选出 \(j\) 到菜，且这 \(j\) 道菜的甜度之和是 \(k\) 的所有方案中，咸度的最小值。如果 \(dp[i][j][k] \le Y\)，表示这就是一个合法的方案，这样的话，dp 的时间复杂度就是 \(O(N^2X)\)。
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int N, X, Y;
cin >> N >> X >> Y;
vector dp(N + 1, vector<int>(X+1, Y+1));
dp[0][0] = 0;
for(int i = 1; i <= N; i++)
{
int x, y;
cin >> x >> y;
for(int j = i; j; j--)
for(int k = X; k >= x; k--)
dp[j][k] = min(dp[j][k], dp[j-1][k-x] + y);
}
int ans = 0;
for(int j = 1; j <= N; j++)
for(int k = 0; k <= X; k++)
if(dp[j][k] <= Y)
ans = max(j, ans);
if(ans < N)
ans++;
cout << ans << endl;
return 0;
}
F - Range Connect MST¶
题目大意
给你一个 \(N+Q\) 个点的无向图，其中 \(1 \le N, Q \le 2 \times 10 ^ 5\)，图中点的编号为 \(1, 2, \cdots, N+Q\)。 图中有 \(Q\) 种类型的边，每种类型可用 \(L_i\)，\(R_i\) 和 \(C_i\) 三个参数来描述，其中 \(1 \le L_i \le R_i \le N\)，表示：
- 对于所有的 \(j = L_i, L_i+1, \cdots, R_i\)，点 \(j\) 到点 \(N+i\) 有一条边权为 \(C_i\) 的连边。
问：这个图是否是一个连通图？如果是，求出这个图的最小生成树。否则输出 -1。
解题思路
可以发现，这个图是一个二分图，左侧的点集为 \([1, N]\)，右侧点集为 \([N+1, N+Q]\)，接下来考虑如何构造最小生成树。如果暴力的用 Kruskal 算法一个个加边，那么每一种类型的边 \((L_i, R_i, C_i)\)，都要遍历其中的 \(N\) 个点判断能否加边，时间复杂度达到 \(O(NQ)\)，这是不行的，必须优化这个加边的过程。
进一步我们会发现，如果对于 \([L_i, R_i]\)，中间有一段 \([L, R]\) 已经连通了，对于这一段只需要有一个点和 \(N + i\) 连接即可。于是我们可以把相邻的点都用并查集维护起来，遍历 \([L_i, R_i]\) 的时候按照连通块的最大值进入下一跳就可以了。
参考代码
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
class DSU
{
public:
explicit DSU(int n) : parent_or_size(n, -1) {}
int merge(int a, int b)
{
int x = leader(a), y = leader(b);
if (x == y)
return x;
if (y > x)
std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) { return leader(a) == leader(b); }
int leader(int a) { return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]); }
int size(int a) { return -parent_or_size[leader(a)]; }
private:
// 如果 parent_or_size[u] >= 0，表示指向的父节点
// 如果 parent_or_size[u] < 0，表示自己就是父节点，同时-parent_or_size[u]表示集合大小
std::vector<int> parent_or_size;
};
struct Node
{
int l, r, c;
bool operator<(const Node &other) const { return c < other.c; }
};
int main()
{
int n, q;
cin >> n >> q;
vector<Node> edge(q);
for (int i = 0; i < q; i++)
{
int l, r, c;
cin >> l >> r >> c;
edge[i] = {l, r, c};
}
sort(edge.begin(), edge.end());
DSU dsu(n + 1);
LL ans = 0;
for (const auto &e : edge)
{
int now = dsu.leader(e.l);
while (true)
{
ans += e.c;
if (now + 1 > e.r)
break;
now = dsu.merge(e.l, now + 1);
}
}
cout << (dsu.size(1) == n ? ans : -1);
return 0;
}
创建日期: 2024-11-01