AtCoder Beginner Contest 370
A - Raise Both Hands (abc370 A)
题目大意
给出Snuke举的左右手情况，如果只举左手，输出Yes，如果只举右手，输出No，否则输出Invalid。
解题思路
逐一判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int l, r;
cin >> l >> r;
if (l == 1 && r == 0)
cout << "Yes" << '\n';
else if (l == 0 && r == 1)
cout << "No" << '\n';
else
cout << "Invalid" << '\n';
return 0;
}
B - Binary Alchemy (abc370 B)
题目大意
给定物品合成成分表\(a_{ij}\)表示物品 \(i\)和物品 \(j\)合成物品 \(a_{ij}\)。
问物品 \(1\)，依次与 \(1,2,3,..N\)物品合成，问最后的物品。
解题思路
按照题意查表，模拟合成即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<int>> a(n);
for (int i = 0; i < n; i++) {
a[i].resize(i + 1);
for (auto& x : a[i]) {
cin >> x;
--x;
}
}
int cur = 0;
for (int i = 0; i < n; ++i) {
int x = cur, y = i;
if (x < y)
swap(x, y);
cur = a[x][y];
}
cout << cur + 1 << '\n';
return 0;
}
C - Word Ladder (abc370 C)
题目大意
给定两个字符串\(s,t\)。
用最小的次数，使得 \(s=t\)，并且字符串\(x\)的字典序最小。
操作为，选择 \(s_i = c\)，并且将修改后的 \(s\)放入 \(x\)的末尾。
解题思路
如何次数最小呢？
依次考虑\(s\)从左到右的每一位 \(i\)，如果 \(s_i \neq t_i\)，那我肯定要 \(s_i = t_i\)，但这是我们此时要进行的操作吗？还是先放一放，改后面的字母后，再改当前位？
由于每次会将修改后的\(s\)放入 \(x\)的末尾，因此我们要优先考虑首先进行的操作，应该是：即刻进行，还是缓一缓在进行。
如果\(s_i > t_i\)，那就优先更改当前位，这样改后的 \(s\)的字典序更小。
如果 \(s_i < t_i\)，那就先更改后面位的，最后再改当前位，这样得到的 \(x\)的字典序最小。
这种回溯的感觉，可以用\(DFS\)实现上述操作。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s, t;
cin >> s >> t;
vector<string> ans;
auto dfs = [&](auto dfs, int pos) {
if (pos == s.size()) {
return;
}
if (s[pos] == t[pos]) {
dfs(dfs, pos + 1);
} else if (s[pos] < t[pos]) {
dfs(dfs, pos + 1);
s[pos] = t[pos];
ans.push_back(s);
} else {
s[pos] = t[pos];
ans.push_back(s);
dfs(dfs, pos + 1);
}
};
dfs(dfs, 0);
cout << ans.size() << '\n';
for (auto& i : ans)
cout << i << '\n';
return 0;
}
D - Cross Explosion (abc370 D)
题目大意
二维网格，初始每个格子有墙。
依次进行\(q\)次放炸弹的操作，给定每次放炸弹的位置 \((i,j)\)，如果该位置有墙，则该墙消失。
否则，炸弹会爆炸，会产生十字冲击波，该位置上下左右的各第一个墙都会消失。
问最后还存在的墙的数量。
解题思路
对于第一种情况，直接移除该位置的墙即可。
对于第二种情况，需要找到该列上下、该行左右最近的墙。
墙的数量\(hw \leq 4e5\)，可以储存每个墙的坐标。
然后对于每行和每列，分别维护\(hset[i]\)表示第\(i\)行还有墙的列坐标，是个\(set\)，\(wset[i]\)表示第 \(i\)列还有墙的行坐标 ，也是个\(set\)。
这样，对于一个炸弹 \((i,j)\)，如果该位置没有墙\((hset[i].find(j) == hset[i].end())\)，则需要找到 \(< j\)的最大和 \(> j\) 的最小的数字。同理对于\(wset\)也要找对应的数字，然后 \(erase\)。这样每次操作的复杂度都是 \(O(\log)\)，总的时间复杂度就是 \(O(q\log (h + w))\)。
代码对于没有墙的逻辑是：
- \(it = hset[i].lower\_bound(j)\)， 由于没有墙，此时一定 \(*it > y\)（否则是 \(*it == y\)），如果 \(it != hset[i].end()\)，那么它就是下面的第一个墙（这里认为左上是原点），要毁掉，于是\(it = hset[i].erase(it)\)， \(erase\)返回值是移除了该 \(*it\)后的下一个元素。
- 然后要找上面的第一个墙，此时 \(it\)是 \(>y\)的第一个位置（无论刚刚是否\(erase\)了），因此如果 \(it != hset[i].begin()\)，那么 \(prev(it)\)就是上面的第一个墙，要毁掉，于是 \(hset[i].erase(prev(it))\)。
同理的思路处理 \(wset\)即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w, q;
cin >> h >> w >> q;
vector<int> hh(h), ww(w);
iota(hh.begin(), hh.end(), 0);
iota(ww.begin(), ww.end(), 0);
vector<set<int>> hset(h), wset(w);
for (int i = 0; i < h; i++) {
hset[i].insert(ww.begin(), ww.end());
}
for (int i = 0; i < w; i++) {
wset[i].insert(hh.begin(), hh.end());
}
while (q--) {
int x, y;
cin >> x >> y;
--x, --y;
auto it = hset[x].lower_bound(y);
if (it != hset[x].end() && *it == y) {
hset[x].erase(y);
wset[y].erase(x);
} else {
if (it != hset[x].end()) {
wset[*it].erase(x);
it = hset[x].erase(it);
}
if (it != hset[x].begin()) {
it = prev(it);
wset[*it].erase(x);
hset[x].erase(it);
}
it = wset[y].lower_bound(x);
if (it != wset[y].end()) {
hset[*it].erase(y);
it = wset[y].erase(it);
}
if (it != wset[y].begin()) {
it = prev(it);
hset[*it].erase(y);
wset[y].erase(it);
}
}
}
int cnt = 0;
for (int i = 0; i < h; i++) {
cnt += hset[i].size();
}
cout << cnt << '\n';
return 0;
}
E - Avoid K Partition (abc370 E)
题目大意
给定一个数组\(a\)，划分成若干个子区间，使得没有子区间的和为 \(k\)。
求划分方案数。
解题思路
朴素\(dp\)就是设 \(dp[i]\)表示前 \(i\)段划分满足条件的方案数。
转移则枚举最后一次的区间，然后 \(dp[i] = \sum_{1 \leq j \leq n, sum[j+1..i] \neq k} dp[j]\)。
复杂度显然是 \(O(n^2)\)的。
棘手在条件 \(sum[j+1..i] \neq k\)上，如果没有这个条件，这个转移其实就是一个前缀和，用前缀和优化即为 \(O(n)\)。
我们用前缀和相减代替区间和，即 \(sum[j+1..i] = sum[i] - sum[j]\)，转移式即为\(dp[i] = \sum_{1 \leq j \leq n, sum[i] - sum[j] = k} dp[j]\)。
换句话说，我们要对\(sum[j] \neq sum[i] - k\)的 \(dp[j]\)求和，这是个非常稀疏的条件，即如果设 \(cnt[i] = \sum_{sum[j] = i} dp[j]\)，即前缀和为 \(i\)的 \(dp\)值，那上述转移式可改写成\(dp[i] = \sum_{1 \leq j < i} dp[j] - cnt[sum[i] - k]\)。
即一个前缀和与一个数的差值，这样转移就是\(O(1)\)了，因此维护一个\(dp\)前缀和 \(\sum_{1 \leq j < i} dp[j]\)以及前缀和的\(dp\)和\(cnt[i] = \sum_{sum[j] = i} dp[j]\)即可。
时间复杂度就是\(O(n \log n)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
LL k;
cin >> n >> k;
vector<int> a(n);
for (auto& x : a)
cin >> x;
map<LL, int> cnt;
cnt[0] = 1;
LL presum = 0;
int precnt = 1;
int ans = 0;
for (auto& i : a) {
presum += i;
ans = (precnt - cnt[presum - k] + mo) % mo;
cnt[presum] = (cnt[presum] + ans) % mo;
precnt = (precnt + ans) % mo;
};
cout << ans << '\n';
return 0;
}
F - Cake Division (abc370 F)
题目大意
给定一个环形数组，划分为\(k\)段，使得每段和的最小值最大。
在该最大值的各种划分方案中，求有多少位置，在所有划分方案中都不被分开。
解题思路
<++>
神奇的代码
G - Divisible by 3 (abc370 G)
题目大意
如果一个数是好的，说明它的因子和能被\(3\)整除。
给定 \(n,m\)，问一个长度为 \(m\)的数组 \(a\)的数量，满足其各数的乘积不超过 \(n\)，且是好数。
解题思路
<++>
神奇的代码