AtCoder Beginner Contest 311
A - First ABC (abc311 A)
题目大意
给定一个字符串，问最短的一个前缀，包含A B C这三个字符。
解题思路
注意到这个前缀的末尾字母一定是这三个字母中的一个，因此答案就是这三个字母出现位置最早的最大值。
神奇的代码
#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;
string s;
cin >> n >> s;
cout << max({s.find('A'), s.find('B'), s.find('C')}) + 1 << '\n';
return 0;
}
B - Vacation Together (abc311 B)
题目大意
给定\(n\)个人的\(d\)天的空闲与否的情况，问最长的连续天，这\(n\)个人都空闲。
解题思路
我们找到第一个大家都空闲的，以此为左端点，找满足条件的最远的右端点，这作为一个候选答案。
接下来的左端点就不要\(+1\)，而是改成从右端点右边继续找，因为\(+1\)开始的情况不会比刚才最优。
最终答案就是这些候选答案的最大值，双指针法，复杂度是\(O(n^2)\)。
因为数据规模不大，判断某天是否所有人都空闲时，直接遍历即可。
神奇的代码
#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, d;
cin >> n >> d;
vector<string> s(n);
for (auto& i : s)
cin >> i;
int ans = 0;
auto ok = [&](int day) {
int free = true;
for (auto& i : s)
free &= (i[day] == 'o');
return free;
};
for (int i = 0; i < d; ++i) {
int j = i;
while (j < d && ok(j))
++j;
ans = max(ans, j - i);
if (j != i)
--j;
i = j;
}
cout << ans << '\n';
return 0;
}
C - Find it! (abc311 C)
题目大意
给定多个基环内向树，找一个环。
解题思路
题意的构图方式实际上是一棵或多棵基环内向树，其特点是从任意一个点出发，必定会跑到环内。
因此随便从一个点进行\(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);
int n;
cin >> n;
vector<int> to(n);
for (int i = 0; i < n; ++i) {
int v;
cin >> v;
--v;
to[i] = v;
}
int u = 0;
vector<int> visit(n);
for (u = 0; !visit[u]; u = to[u]) {
visit[u] = 1;
}
vector<int> ans{u};
for (int i = to[u]; i != u; i = to[i]) {
ans.push_back(i);
}
cout << ans.size() << '\n';
for (auto& i : ans)
cout << i + 1 << ' ';
cout << '\n';
return 0;
}
D - Grid Ice Floor (abc311 D)
题目大意
给定一张二维网格，外围是石头，里面有若干个石头，其余都是冰面，从左上出发，选一个方向前进，会一直前进直到碰到石头。停下来，然后可以继续选一个方向前进。
问能访问到的格子数。
解题思路
考虑能访问到的格子\((i,j)\)的状态，我们发现只有五种，即当我们在格子\((i, j)\)时，此时的运动状态为：
- 方向往上
- 方向往下
- 方向往左
- 方向往右
- 停下来
因此我们就设\(dp[i][j][0/1/2/3/4/5]\)表示到达格子\((i,j)\)，此时状态是上述\(5\)种中的一个，这个情况是否发生（即bool型）
转移就根据当前状态，枚举后继状态转移即可。
因为这里的DP顺序不是常规的循环，而是依赖于当前的运动状态的，所以转移类似于\(BFS\)式的转移。
每个格子最终只会访问到\(5\)次，因此复杂度是\(O(n^2)\)。
对于格子\((i, j)\), \(dp[i][j]\)的\(5\)个状态中有任意一个状态访问过（为真），则这个格子就访问过了。
答案就是上述这些格子的总和。
神奇的代码
#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, m;
cin >> n >> m;
vector<string> tu(n);
for (auto& i : tu)
cin >> i;
vector<vector<array<int, 5>>> ok(n,
vector<array<int, 5>>(m, array<int, 5>{}));
queue<array<int, 3>> team;
array<int, 4> dx{1, -1, 0, 0};
array<int, 4> dy{0, 0, 1, -1};
team.push({1, 1, 2});
team.push({1, 1, 0});
ok[1][1][0] = ok[1][1][2] = ok[1][1][4] = 1;
auto stop = [&](int x, int y) { return tu[x][y] == '#'; };
while (!team.empty()) {
auto [x, y, d] = team.front();
team.pop();
if (d == 4) { // stop
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (!stop(nx, ny) && !ok[nx][ny][i]) {
team.push({nx, ny, i});
ok[nx][ny][i] = 1;
}
}
continue;
}
int nx = x + dx[d], ny = y + dy[d];
if (stop(nx, ny)) {
if (!ok[x][y][4]) {
team.push({x, y, 4});
ok[x][y][4] = 1;
}
} else {
team.push({nx, ny, d});
ok[nx][ny][d] = 1;
}
};
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
bool access = false;
for (auto& k : ok[i][j])
access |= k;
ans += access;
}
cout << ans << '\n';
return 0;
}
E - Defect-free Squares (abc311 E)
题目大意
给定一个二维网格，有一些格子上有洞。
问有多少个正方形大小的网格，其里面都没洞。
解题思路
考虑一维的情况，我们可以枚举右端点\(r\)，然后考虑有多少个左端点\(l\)，满足\([l,r]\)都没洞。
容易发现，如果位置\(i\)有洞，那么所有左端点\(l \leq i\)都不满足上述要求。
我们对洞的数量求一个前缀和\(sum\)，那么\([l,r]\)没洞等价于\(sum[r] - sum[l - 1] = 0\)。
注意到\(sum\)是个单调数组，那么右边的等价式其实是一个关于\(l\)的单调函数，我们可以二分枚举\(l\)，找到最小的满足\(sum[r] - sum[l - 1] = 0\)的位置，那么右端点为\(r\)，满足条件的左端点数量就是\(r - l + 1\)。枚举所有右端点累计求和即为答案。
回到这个二维，我们枚举这个网格的右下角，因为是正方形，我们只需枚举其边长，就能知道左上角的位置，然后题意的条件就相当于一个二维前缀和的相减，同样是一个单调函数，因此问题就解决了，只是一维变二维了。
神奇的代码
#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, n;
cin >> h >> w >> n;
vector<vector<int>> presum(h + 1, vector<int>(w + 1, 0));
for (int i = 0; i < n; ++i) {
int u, v;
cin >> u >> v;
presum[u][v]++;
}
for (int i = 1; i <= h; ++i)
for (int j = 1; j <= w; ++j) {
presum[i][j] +=
presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1];
}
LL ans = 0;
auto calc = [&](int x, int y) {
int l = 0, r = min(x, y) + 1;
while (l + 1 < r) {
int mid = (l + r) >> 1;
int lx = x - mid + 1, ly = y - mid + 1;
int hold = presum[x][y] - presum[lx - 1][y] - presum[x][ly - 1] +
presum[lx - 1][ly - 1];
if (hold == 0) {
l = mid;
} else {
r = mid;
}
}
return l;
};
for (int i = 1; i <= h; ++i)
for (int j = 1; j <= w; ++j) {
ans += calc(i, j);
}
cout << ans << '\n';
return 0;
}
F - Yet Another Grid Task (abc311 F)
题目大意
给定一个初始二维网格，格子有黑有白。
如果一个格子\((i, j)\)是黑的，那么\((i+1, j),(i + 1, j + 1)\)也必须是黑的。
初始不一定满足上述条件，现在你可以对格子涂成黑色，问满足上述条件的局面数。
解题思路
涂一个点，等价于这个点往下的一个直角三角形都被涂，隐隐约约感觉状态就拆成了这个点涂和下面以及旁边的点要不要涂的状态，但总感觉还要一些额外的状态，比如旁边的点涂不涂貌似会影响到当前决策，但想不出来，寄
神奇的代码
G - One More Grid Task (abc311 G)
题目大意
给定一个二维网格，问一个价值最大的矩形区域。
一个矩形区域的价值为，该区域的数字和$\times $该区域的最小值。
解题思路
考虑一维怎么做。
价值有两项，一个是和一个是区域最小值，如果我们枚举左端点，那么右端点变动时，数字和与最小值都可能变化，最坏情况下每移动一个位置，最小值都变一次，感觉避免不了\(O(n^2)\)。
我们还可以枚举区域的最小值\(a_i\)，那么以该值为最小值的区域的左右端点\(l,r\)，可以假想是从\(i\)左右扩张，一直扩张到要小于\(a_i\)位置。这是以它为最小值的最大的区间，因为值都是正的，因此这是一个以该值作为最小值的价值最大的区间。
对每个\(a_i\)都求一遍这个价值取最大就是答案。
而对于一个\(a_i\)，如何找到\(l,r\)，其实这是一个经典问题，即找左边第一个比它小的数，右边第一个比它小的数，可以运用单调栈在\(O(n)\)内找出来。
于是我们事先预处理出每个数的左右边界\(l_i, r_i\)，我们枚举\(a_i\)作为最小值，其一个候选答案就是\(a_i \times (sum[r_i] - sum[l_i - 1])\)，其中\(sum\)数组也是需要预处理的前缀和数组，用于\(O(1)\)求区间和。答案就是所有候选答案的最大值。此时时间复杂度是\(O(n)\)。
回到这个二维，注意规模只有\(300\)，如果我们先花\(O(n^2)\)枚举一个上下边界，此时要考虑的就是左右边界了，问题其实就变成了上述的一维情况，一个位置的最小值就是这上下边界中这一列的最小值，而值（用于算前缀和的）就是这一列的数字之和。问题其实解决了。
考虑实现细节，当我们枚举上下边界后，需要求出变成一维情况的数组，其中算左右边界的最小值是该列的最小值，可以预先花\(O(n^2)\)预处理出每一列的两两行的最小值，也可以用ST表。然后算前缀和的是该列的数字之和，因此还得预处理出每一列的前缀和。
总的时间复杂度就是\(O(n^3)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
// usage:
// auto fun = [&](int i, int j) { return min(i, j); };
// SparseTable<int, decltype(fun)> st(a, fun);
// or:
// SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
public:
int n;
vector<vector<T>> mat;
F func;
SparseTable(const vector<T>& a, const F& f) : func(f) {
n = static_cast<int>(a.size());
int max_log = 32 - __builtin_clz(n);
mat.resize(max_log);
mat[0] = a;
for (int j = 1; j < max_log; j++) {
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int from, int to) const { // [from, to]
assert(0 <= from && from <= to && to <= n - 1);
int lg = 32 - __builtin_clz(to - from + 1) - 1;
return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m, 0));
vector<SparseTable<int>> st;
vector<vector<int>> presum(n, vector<int>(m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
cin >> a[i][j];
partial_sum(a[i].begin(), a[i].end(), presum[i].begin());
st.push_back(
SparseTable<int>(a[i], [](int x, int y) { return min(x, y); }));
}
LL ans = 0;
auto solve = [&](int L, int R) {
vector<int> num(n), sum(n);
for (int i = 0; i < n; ++i) {
num[i] = st[i].get(L, R);
sum[i] = presum[i][R];
if (L)
sum[i] -= presum[i][L - 1];
}
partial_sum(sum.begin(), sum.end(), sum.begin());
vector<int> l(n), r(n);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && num[st.top()] >= num[i]) {
r[st.top()] = i - 1;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
r[st.top()] = n - 1;
st.pop();
}
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && num[st.top()] > num[i]) {
l[st.top()] = i + 1;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
l[st.top()] = 0;
st.pop();
}
for (int i = 0; i < n; ++i) {
int cur = sum[r[i]];
if (l[i])
cur -= sum[l[i] - 1];
ans = max(ans, 1ll * cur * num[i]);
}
};
for (int i = 0; i < m; ++i)
for (int j = i; j < m; ++j) {
solve(i, j);
}
cout << ans << '\n';
return 0;
}
Ex - Many Illumination Plans (abc311 Ex)
题目大意
<++>
解题思路
<++>
神奇的代码