ABC386(A-F)
A - Full House 2¶
题目大意
有四张卡片，卡片上的数字分别是 \(A\)，\(B\)，\(C\) 和 \(D\)。能否再添加一张任意数字的卡片，使得这五张卡片的牌型为斗地主中的“三带二”（即一种数字出现了 \(3\) 次，另一种数字出现了 \(2\) 次）
解题思路
四张卡片的数字次数分布有：
1 1 1 11 1 21 32 24
只有第三和第四种情况可以加一张牌成为 2 3，也就是有两种次数的情况，用哈希表统计即可。
参考代码
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<int, int> cnt;
for(int i = 0; i < 4; i++)
{
int x;
cin >> x;
cnt[x]++;
}
cout << (cnt.size() == 2 ? "Yes" : "No") << endl;
return 0;
}
B - Calculator¶
题目大意
有一个计算器，计算器上只有 00，0，1，2，3，4，5，6，7，8，9 这些按键。
如果想在计算器上显示数字 \(X\)，至少要按多少次按键？
参考代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
int n = s.size();
int ans = 0;
for(int i = 0; i < n; i++)
{
if(s[i] == '0')
{
if(i + 1 < n && s[i+1] == '0')
i++;
}
ans++;
}
cout << ans << endl;
return 0;
}
C - Operate 1¶
题目大意
C 题描述和 F 题一致，但 C 题中 \(K=1\)
给你两个字符串 \(S\) 和 \(T\)，其中 \(1 \le |S|, |T| \le 5 \times 10 ^ 5\)，你可以对 \(S\) 执行至多 \(K(K = 1)\) 次操作，每次操作时，从下列三种类型中选择一种：
- 在 \(S\) 的任意位置插入一个任意的字符。
- 删除 \(S\) 的任意位置的一个字符。
- 将 \(S\) 的任意一个位置的字符替换成任意的字符。
问：能否在至多执行 \(K(K=1)\) 次操作的前提下将 \(S\) 变成 \(T\)？
解题思路
设 \(n=|S|\)，\(m = |T|\)，因为 \(K=1\)，所以有四种情况：
- 如果 \(|n-m| > 1\)，因为一次操作最多让 \(S\) 的长度变化 \(1\)，所以这种情况无解。
- 如果 \(n+1=m\)，则一定是执行一次插入字符操作，找出 \(S\) 和 \(T\) 第一个不相等的位置 \(i\)，则必须插入 \(T_i\) 字符才能解决不等，然后再判断 \(S[i:n]\) 和 \(T[i+1:m]\) 是否完全相等。
- 如果 \(n=m\)，则最多是执行一次替换字符操作，找出 \(S\) 和 \(T\) 第一个不相等的位置 \(i\)，则必须将 \(S_i\) 替换成 \(T_i\) 字符才能解决不等，然后再判断 \(S[i+1:n]\) 和 \(T[i+1:m]\) 是否完全相等。
- 如果 \(n-1=m\)，则一定是执行一次删除字符操作，找出 \(S\) 和 \(T\) 第一个不相等的位置 \(i\)，则必须删除 \(S_i\) 字符才能解决不等，然后再判断 \(S[i+1:n]\) 和 \(T[i:m]\) 是否完全相等。
参考代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
int k;
string s, t;
cin >> k >> s >> t;
int n = s.size(), m = t.size();
bool equal = true;
if (n == m)
{
for (int i = 0; i < n; i++)
if (s[i] != t[i])
{
equal = s.substr(i + 1, string::npos) == t.substr(i + 1, string::npos);
break;
}
}
else if (n + 1 == m)
{
for (int i = 0; i < n; i++)
if (s[i] != t[i])
{
equal = s.substr(i, string::npos) == t.substr(i + 1, string::npos);
break;
}
}
else if (m + 1 == n)
{
for (int i = 0; i < m; i++)
if (s[i] != t[i])
{
equal = s.substr(i + 1, string::npos) == t.substr(i, string::npos);
break;
}
}
else
equal = false;
cout << (equal ? "Yes" : "No") << endl;
return 0;
}
D - Diagonal Separation¶
题目大意
有一个 \(N \times N(1 \le N \le 10 ^ 9)\) 的网格，每个格子都可以染成黑色或者白色。初始的时候，已经有 \(M(1 \le M \le \min(N^2, 2 \times 10 ^ 5))\) 个格子已经染好色了，第 \(i\) 个染好色的格子的位置是 \((X_i, Y_i)\)，颜色用字符 \(C_i\) 表示，如果 \(C_i\) 是 B 表示黑色，W 则表示白色。
现在，你需要对剩余的 \(N^2-M\) 个格子染色，问：是否存在一种染色方案，能够满足以下所有条件？
- 对于网格中的每一行，都存在一个整数 \(i(0 \le i \le N)\)，使得该行的最靠左的 \(i\) 格格子都是黑色，剩下的格子都是白色。
- 对于网格中的每一列，都存在一个整数 \(i(0 \le i \le N)\)，使得该列的最靠上的 \(i\) 格格子都是黑色，剩下的格子都是白色。
样例如下
4 3
4 1 B
3 2 W
1 3 B
上图中标红的格子表示初始就染了色的格子，一种合法的染色方案如上图所示。
解题思路
可以推导出一个性质，假设有一个格子 \(X_i, Y_i\) 初始被染成了黑色，则以 \((1, 1)\) 为左上角，\((X_i, Y_i)\) 为右下角的矩形中所有的格子都必须染成黑色，这样才能满足条件。
于是考虑一种做法，先处理 \(M\) 个格子中的黑色格子，处理可以得到每一行最右边的黑色格子，以及每一列最下边的黑色格子。然后再处理白色格子是否冲突就好了。但是由于 \(N \le 10^9\)，每一行、每一列都存下来是不行的。进一步可以发现，最后一个黑色格子的位置是有单调性的，以行为例，每一行的 \(i\)（也就是最靠右的黑色格子的位置） 从是越来越小（越来越靠左）的，可以压缩存储，如下图所示：
这种染色方法尽量压缩了黑色格子的空间，因为单调递减，所以只需要存储黑色格子发生变化的位置，例如上图，只需要存储 \((1, 3)\) 和 \((4, 1)\) 的黑色格子。把这些黑色节点存到 map 里（至多存 \(M\) 个），然后对于每一个白色格子通过二分的方式可以求得对应的行列的黑色格子，判断是否冲突就好。
参考代码
#include <functional>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
map<int, int, greater<int>> br, bc;
br[n+1] = 0;
bc[n+1] = 0;
vector<pair<int, int>> white;
while (m--)
{
int r, c;
char col;
cin >> r >> c >> col;
if (col == 'B')
{
br[r] = max(br[r], c);
bc[c] = max(bc[c], r);
}
else
white.push_back({r, c});
}
auto process = [](map<int, int, greater<int>> &mp) -> void
{
int last = -1;
for (auto it = mp.begin(); it != mp.end();)
{
if (it->second <= last)
it = mp.erase(it);
else
{
last = it->second;
it++;
}
}
};
auto check = [](map<int, int, greater<int>> &mp, int x, int y) -> bool
{
auto it = --mp.upper_bound(x);
return it->second < y;
};
process(br);
process(bc);
for (auto [r, c] : white)
{
if(!check(br, r, c) || !check(bc, c, r))
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
E - Maximize XOR¶
题目大意
给你一个长度为 \(N(1 \le N \le 2 \times 10 ^ 5)\) 的序列 \(A = (A_1, A_2, ..., A_N)\)。给你一个正整数 \(K\)，其中 \(C_N^K \le 10 ^ 6\)。
你需要从 \(A\) 中挑选出 \(K\) 个数字，使得这些数字的异或和最大。
解题思路
\(C_N^K \le 10 ^ 6\)，直接枚举所有的组合就好。
参考代码
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n, k;
cin >> n >> k;
vector<LL> a(n);
for(auto &x : a)
cin >> x;
vector<LL> suf(n+1);
for(int i = n-1; i >= 0; i--)
suf[i] = suf[i+1] ^ a[i];
LL ans = 0;
auto dfs = [n, &a, &suf, &ans](auto &self, int i, int k, LL x) -> void
{
if(k == 0)
{
ans = max(ans, x);
return;
}
if(n - i == k)
{
ans = max(ans, x ^ suf[i]);
return;
}
self(self, i+1, k-1, x ^ a[i]);
self(self, i+1, k, x);
};
dfs(dfs, 0, k, 0);
cout << ans << endl;
return 0;
}
F - Operate K¶
题目大意
F 题描述和 C 题一致，但 F 题中 \(1 \le K \le 20\)
给你两个字符串 \(S\) 和 \(T\)，其中 \(1 \le |S|, |T| \le 5 \times 10 ^ 5\)，你可以对 \(S\) 执行至多 \(K(1 \le K \le 20)\) 次操作，每次操作时，从下列三种类型中选择一种：
- 在 \(S\) 的任意位置插入一个任意的字符。
- 删除 \(S\) 的任意位置的一个字符。
- 将 \(S\) 的任意一个位置的字符替换成任意的字符。
问：能否在至多执行 \(K(1 \le K \le 20)\) 次操作的前提下将 \(S\) 变成 \(T\)？
解题思路
这道题实际是来自经典的 P2758 编辑距离 - 洛谷，编辑距离问题询问的是将 \(S\) 变成 \(T\) 至少需要几次操作，做法如下：
定义 \(dp[i][j]\) 表示将 \(S\) 的前 \(i\) 个字符变成 \(T\) 的前 \(j\) 个字符需要操作的次数的最小值。初始值为有 \(dp[0][j] = j\) 以及 \(dp[i][0] = i\) 转移的时候有四种情况：
- \(S_i = T_j\)，无需使用替换操作就有 \(dp[i][j] = dp[i-1][j-1]\)
- \(S_i \neq T_j\)，需要使用替换操作才能让 \(S_i\) 和 \(T_j\) 相等， \(dp[i][j] = dp[i-1][j-1] + 1\)
- 使用添加字符操作，添加一个 \(T_j\) 在 \(S\) 的末尾，有 \(dp[i][j] = dp[i][j-1] + 1\)
- 使用删除字符操作，删除 \(S_i\)，有 \(dp[i][j] = dp[i-1][j] + 1\)
在上述情况中取最小值就好。设 \(n = |S|\)，\(m = |T|\)，时间复杂度是 \(O(nm)\)，最终的答案就是 \(dp[n][m]\)。
因此本题相当于询问是否有 \(dp[n][m] \le K\)，但是考虑到 \(1 \le n, m \le 5 \times 10 ^ 5\)，\(O(nm)\) 必定超时。
考虑到 \(K \le 20\)，而每一次操作至多让 \(S\) 的长度变化 \(1\)，因此实际上我们至多能得到 \([n-K, n+K]\) 长度的字符串，这样我们可以压缩状态，定义 \(dp[i][d]\)，其中第二个维度的大小为 \(2K+1\)，表示将 \(S\) 的前 \(i\) 个字符变成 \(T\) 的前 \(i + d - K\) 个字符需要操作次数的最小值，这里相当于 \(j=i+d-K\)，计算的时候参照原始的编辑距离算就好了，注意处理好边界条件即可。
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
string s, t;
cin >> k >> s >> t;
int n = s.size(), m = t.size(), len = 2 * k + 1;
s = " " + s;
t = " " + t;
if (abs(n - m) > k)
{
cout << "No" << endl;
return 0;
}
vector<vector<int>> dp(n + 1, vector<int>(len, k + 1));
for (int j = k; j < len; j++)
dp[0][j] = j - k;
for (int i = 1; i <= n; i++)
{
for (int d = 0, j = i + d - k; d < len && j <= m; d++, j++)
{
if(j < 0)
continue;
if (j == 0)
{
dp[i][d] = i;
continue;
}
dp[i][d] = (s[i] == t[j] ? 0 : 1) + dp[i - 1][d];
if (d >= 1)
dp[i][d] = min(dp[i][d], dp[i][d - 1] + 1);
if (d + 1 < len)
dp[i][d] = min(dp[i][d], dp[i - 1][d + 1] + 1);
}
}
cout << (dp[n][m-n+k] <= k ? "Yes" : "No") << endl;
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
string s, t;
cin >> k >> s >> t;
int n = s.size(), m = t.size(), len = 2 * k + 1;
s = " " + s;
t = " " + t;
if (abs(n - m) > k)
{
cout << "No" << endl;
return 0;
}
vector<int> dp(len, k + 1);
for (int j = k; j < len; j++)
dp[j] = j - k;
for (int i = 1; i <= n; i++)
{
for (int d = 0, j = i + d - k; d < len; d++, j++)
{
if (j <= 0 || j > m)
{
dp[d] = j == 0 ? i : k + 1;
continue;
}
dp[d] = (s[i] == t[j] ? 0 : 1) + dp[d];
if (d + 1 < len)
dp[d] = min(dp[d], dp[d + 1] + 1);
}
for (int d = 1, j = i + d - k; d < len; d++, j++)
{
if (j <= 0 || j > m)
continue;
dp[d] = min(dp[d], dp[d - 1] + 1);
}
}
cout << (dp[m - n + k] <= k ? "Yes" : "No") << endl;
return 0;
}
创建日期: 2025-01-08