ABC370(A-F)
A - Raise Both Hands¶
题目大意
给你两个数字 \(L\) 和 \(R\)，如果 \(L=R\) 输出 Invalid，否则如果 \(L = 1\) 输出 Yes，否则输出 No。
参考代码
#include <iostream>
using namespace std;
int main()
{
int l, r;
cin >> l >> r;
if(l == r)
cout << "Invalid" << endl;
else
cout << (l ? "Yes" : "No") << endl;
return 0;
}
B - Binary Alchemy¶
题目大意
给你 \(N\) 个数字 \(1, 2, \cdots, N\)。数字 \(i\) 和数字 \(j\) 可以合并，合并时如果 \(i \ge j\) 则合并的结果为 \(A_{i, j}\)，否则为 \(A_{j, i}\)，其中 \(1 \le A_{i, j} \le N\)。初始的时候，给你一个数字 \(1\)，依次和数字 \(1, 2, \cdots,N\) 合并，问：最终得到的数字是？
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> a(n+1, vector<int>(n+1));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
cin >> a[i][j];
int i = 1;
for(int j = 1; j <= n; j++)
i = i >= j ? a[i][j] : a[j][i];
cout << i << endl;
return 0;
}
C - Word Ladder¶
题目大意
给你两个长度相同的字符串 \(S\) 和 \(T\)。设 \(X\) 表示一个字符串数组，初始时为空，然后，你可以执行以下操作直到 \(S\) 等于 \(T\)。
- 每次选取 \(S\) 中的一个字符，将其替换成任意字符，然后将当前的 \(S\) 加入到 \(X\) 的末尾。
所有操作结束时，你首先需要输出最少操作多少次才能将 \(S\) 变成 \(T\)。然后按顺序输出数组 \(X\) 的内容，如果有多个答案符合要求，输出字典序最小的答案。
解题思路
从左到右替换字典序减小的字符，从右到左替换字典序增大的字符。
参考代码
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
int n = s.size();
int cnt = 0;
vector<int> less, greater;
for(int i = 0; i < n; i++)
{
if(s[i] == t[i])
continue;
cnt++;
s[i] < t[i] ? less.push_back(i) : greater.push_back(i);
}
cout << cnt << endl;
for(auto i : greater)
{
s[i] = t[i];
cout << s << endl;
}
reverse(less.begin(), less.end());
for(auto i : less)
{
s[i] = t[i];
cout << s << endl;
}
return 0;
}
D - Cross Explosion¶
题目大意
有一个 \(H \times W(1 \le H \times W \le 4 \times 10 ^ 5)\) 的网格，初始的时候，每个格子上都有一堵墙。有 \(Q(1 \le Q \le 2 \times 10 ^5)\) 个炸弹依次放下，第 \(i\) 个炸弹会放置在 \((R_1, C_i)\) 位置。当炸弹放下时，如果 \((R_i, C_i)\) 是墙，则这枚炸弹仅仅摧毁 \((R_i, C_i)\) 这一堵墙，如果 \((R_i, C_i)\) 是墙，炸弹会沿着上下左右四个方向传播，并炸毁距离 \((R_i, C_i)\) 四个方向最近的各一堵墙。问：在 \(Q\) 个炸弹放置完成后，网格中还剩下多少堵墙？
解题思路
用 \(H\) 个 set 记录每一行有哪些墙的纵坐标，\(W\) 个 set 记录每一列有哪些墙的横坐标。处理炸弹的时候同时更新即可。
参考代码
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
int h, w, q;
cin >> h >> w >> q;
vector<set<int>> row(h + 1), col(w + 1);
for (int r = 1; r <= h; r++)
for (int c = 1; c <= w; c++)
row[r].insert(c);
for (int c = 1; c <= w; c++)
for (int r = 1; r <= h; r++)
col[c].insert(r);
while (q--)
{
int r, c;
cin >> r >> c;
auto it = row[r].lower_bound(c);
if (it != row[r].end() && *it == c)
{
row[r].erase(it);
col[c].erase(r);
}
else
{
if (it != row[r].begin())
{
--it;
col[*it].erase(r);
it = row[r].erase(it);
}
if (it != row[r].end())
{
col[*it].erase(r);
row[r].erase(it);
}
it = col[c].lower_bound(r);
if (it != col[c].begin())
{
--it;
row[*it].erase(c);
it = col[c].erase(it);
}
if (it != col[c].end())
{
row[*it].erase(c);
col[c].erase(it);
}
}
}
int ans = 0;
for(int r = 1; r <= h; r++)
ans += row[r].size();
cout << ans << endl;
return 0;
}
E - Avoid K Partition¶
题目大意
给你一个长度为 \(N(1 \le N \le 2 \times 10^5)\) 的数组 \(A = (A_1, A_2, \cdots, A_N)\) 和一个整数 \(K(-10^{15} \le K \le 10^{15})\)，你可以将 \(A\) 切割成任意段连续的子数组。 问：有多少种切割的方案使得任意一个子数组的数字之和不等于 \(K\) ？答案对 \(998244353\) 取模。
解题思路
设 \(s[i]\) 表示前缀和，\(dp[i]\) 表示前 \(i\) 个数字进行切分所得到的合法方案数。转移时，考虑将 \(A_i\) 和之前的哪些数字合并，即 \(dp[i] = \sum\limits_{0\le j < i \land s[i]-s[j] \neq K}dp[j]\)，这样转移是 \(O(n)\) 的，总的时间复杂度就是 \(O(n^2)\)。
但是我们只需要减去满足 \(s[j] = s[i] - K\) 对应的 \(dp[j]\) 就可以，所以只需要把对应的 \(s[i]\) 放到哈希表里作为 key，\(dp[i]\) 作为值，然后用一个变量存储 \(dp\) 数组的前缀和即可。转移的时候，求出 \(s[i]-K\) 的键值对，用前缀和减去值即可，这样转移是 \(O(1)\) 的，总的时间复杂度就是 \(O(n)\)。
参考代码
#include <iostream>
#include <unordered_map>
using namespace std;
using LL = long long;
const LL MOD = 998244353;
int main()
{
LL n, k;
cin >> n >> k;
unordered_map<LL, LL> g;
g[0] = 1;
LL dp_prefix = 1;
LL s = 0;
LL dp = 1;
for (int r = 1; r <= n; r++)
{
LL a;
cin >> a;
s += a;
auto it = g.find(s - k);
LL sub = it == g.end() ? 0 : it->second;
dp = (dp_prefix - sub + MOD) % MOD;
dp_prefix = (dp_prefix + dp) % MOD;
g[s] = (g[s] + dp) % MOD;
}
cout << dp << endl;
return 0;
}
F - Cake Division¶
题目大意
有 \(N(N \le 2 \times 10 ^ 5)\) 块蛋糕，这 \(N\) 块蛋糕是环形的，按照顺时针的顺序，第 \(i\) 块蛋糕的重量是 \(A_i\)，第 \(N\) 块蛋糕的下一个蛋糕是第 \(1\) 块蛋糕。每两块蛋糕之间都有一条线，第 \(i\) 条线指的是第 \(i\) 块蛋糕和第 \(i+1\) 块蛋糕之间的线。
你有 \(K(2 \le K \le N)\) 个朋友，你打算将 \(N\) 块蛋糕相邻的部分组合成 \(K\) 份，分发给你的朋友们。每个朋友至少应该分到一块蛋糕。设第 \(i\) 个朋友收到的蛋糕为 \(A_xA_{x+1}\cdots A_y\)，这些蛋糕的质量和为 \(w_i = A_x + A_{x+1} + \cdots + A_y\)。设 \(w_{\min} = \min(w_1, w_2, \cdots, w_K)\) ，即 \(K\) 个朋友中蛋糕重量之和的最小值。问：\(w_{\min}\) 的最大值是什么？在所有能让 \(w_{\min}\) 取得最大值的方案中，有多少条相邻蛋糕之间的连线无论如何不会切开（如果蛋糕 \(i\) 和蛋糕 \(i+1\) 分给了两个不同的人，则第 \(i\) 条线会被切开）
解题思路
非常绕的题，题解也很绕。。我可能写的也不太好。。
要最大化最小值，显然是要二分答案。考虑怎么 check。按照环形的处理方法，将 \(A\) 数组扩展成两倍长，然后处理出前缀和。当我们二分到某个值 \(x\) 时，等价于 check 前缀和数组中是否存在 \(K\) 对 \((l_i, r_i)\) 满足 \(s[r_i]-s[l_i] \ge x\)，且 \(l_1 \le r_1 = l_2 \le r_2 = \cdots = l_K \le r_K\) 且 \(r_K - l_1 \le N\)。
在 check 的时候，处理出一个 \(ne\) 数组，\(ne[i]\) 表示大于 \(i\) 且第一个满足 \(s[ne[i]] - s[i] \ge x\) 的位置。这样的话从第一刀开始 dfs ，同时用一个栈记录下 \(l_i\) 的值，当栈的大小达到 \(K\) 时，再判断 \(r_K - l_1 \le N\) 条件是否满足即可，只要满足这个条件，就可以判定 check 成功。下面考虑第二个问题，求出有多少条线永远不会被切开。
我们可以发现，对于一种切分方案（需要切开 \(K\) 条线），实际上有 \(K\) 条线是一定会被切开的。由于我们将原数组扩展成了 \(2\) 倍长度来处理环形，所以在 dfs 的时候，只需要从所有线开始枚举，每当栈的大小大于等于 \(K\) 时，就把之前的 \(K\) 层的 \((l_i, r_i)\) 找出来，如果满足条件，则就把 \(l_i\) 一定会被某个方案切开，所以在最后返回值的时候，只需要用 \(N\) 减去会被切开的线，就是第二问的答案。
这样还有个问题，我们需要用 dfs 的方式遍历所有的路线，也就是点 \(1\) 到点 \(N\) 全部都要执行依次 dfs，这样会重复很多路线。有两个解决办法：
- 扩展成二维的 \(ne\) 数组，第二维利用倍增的方式，这样无需 dfs 遍历，可以在 \(\log K\) 的时间内直接求出一个节点访问 \(K\) 次之后的后继。
- 注意到当我们正序抵达某个点 \(i\) 的时候，其实后继的所有点 \(ne[i]\)、\(ne[ne[ui]]\)、\(......\) 都是确定好的，所以为了避免这种重复的访问，一种解决办法就是倒过来查。这个思路其实和反向建图 dijkstra 算法求出所有点到某个固定终点的最短路是一个原理，反向遍历保证了从后往前的路径都固定下来，这种遍历方式的时间复杂度是 \(O(n+m)\) 的。只需要把 \(ne\) 数组的构建方式替换成 \(last\)，从后往前 dfs 就可以了。题解用的这个方法。
参考代码
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> s(2 * n + 1);
for (int i = 1; i <= n; i++)
{
cin >> s[i];
s[i + n] = s[i];
s[i] += s[i - 1];
}
for (int i = n + 1; i <= 2 * n; i++)
s[i] += s[i - 1];
vector<vector<int>> last(2 * n + 1);
auto check = [&s, &last, n, k](int mid) -> int
{
last.assign(2 * n + 1, {});
for (int i = 0, j = 0; i < 2 * n; i++)
{
while (j < 2 * n && s[j] - s[i] < mid)
j++;
last[j].push_back(i);
}
int ans = 0;
vector<int> st;
auto dfs = [&last, &st, &ans, n, k](auto &self, int j) -> void
{
if (j < n && (int)st.size() >= k && st[st.size() - k] - j <= n)
ans++;
st.push_back(j);
for (auto i : last[j])
self(self, i);
st.pop_back();
};
dfs(dfs, 2 * n);
return ans;
};
int l = 1, r = s[n] / k, line = 0;
while (l < r)
{
int mid = (l + r + 1) / 2;
int ans = check(mid);
if (ans == 0)
r = mid - 1;
else
{
l = mid;
line = n - ans;
}
}
cout << l << ' ' << line << endl;
return 0;
}
创建日期: 2024-12-07