A. The bottom of the ninth
答案为 \(\sum a_i - \sum b_i + 1\)
B. Spot the Difference
模拟
C. Merge the balls
直接按题意模拟就是 \(O(n)\) 的，那么这题的瓶颈就在于两个球做合并，注意到 \(2^a + 2^a = 2^{a+1}\)，那么我们就可以不考虑底数 \(2\)，而直接处理指数即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> st;
rep(i, n) {
int a;
cin >> a;
while (st.size() >= 1 and st.back() == a) {
st.pop_back();
a++;
}
st.push_back(a);
}
cout << st.size() << '\n';
return 0;
}
D. Grid and Magnet
不妨将磁铁周围的格子标记为 X，可以发现由剩下可通行的格子构成的同一个连通块里的格子的自由度一定是相同的，也就是这个连通块的大小再加上这个连通块四周的 X 的个数
可以用 \(\operatorname{bfs}\) 来处理
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};
int main() {
int h, w;
cin >> h >> w;
vector<string> s(h);
rep(i, h) cin >> s[i];
vector x(h, vector<bool>(w));
rep(i, h)rep(j, w) {
if (s[i][j] != '#') continue;
x[i][j] = true;
rep(v, 4) {
int ni = i+di[v], nj = j+dj[v];
if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
x[ni][nj] = true;
}
}
int ans = 1;
vector used(h, vector<bool>(w));
vector last(h, vector<int>(w)); int tm = 0;
rep(si, h)rep(sj, w) {
if (x[si][sj]) continue;
if (used[si][sj]) continue;
++tm;
int cnt = 0;
queue<P> q;
q.emplace(si, sj); used[si][sj] = true;
while (q.size()) {
auto [i, j] = q.front(); q.pop();
cnt++;
rep(v, 4) {
int ni = i+di[v], nj = j+dj[v];
if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
if (used[ni][nj]) continue;
if (x[ni][nj]) {
if (last[ni][nj] != tm) cnt++, last[ni][nj] = tm;
continue;
}
q.emplace(ni, nj);
used[ni][nj] = true;
}
}
ans = max(ans, cnt);
}
cout << ans << '\n';
return 0;
}