睡觉了，某些人可能根本不会写线段树。
Link：Educational Codeforces Round 138
Problem E Cactus Wall
做法：考虑到答案这就是建图的最小割。一般来讲，这种题都可以转换成求某种最短路。事实上这个题就是在第0列建和第m+1列建立两个虚点，然后有\#的转移边权为0，否则为1的图的最短路。注意到这张图边权为0或1，因此直接做01BFS即可。
时间复杂度：\mathcal{O}(nm)
顺带一提，这个题和F. Not Splitting有一点类似，但是那个题显然困难很多。
Code
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<char>> mp(n + 1);
for (int i = 1; i <= n; i++) {
string x;
cin >> x;
x = " " + x;
mp[i] = {x.begin(), x.end()};
}
deque<pair<int, int>> Q;
static vector<pair<int, int>> d = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
auto check = [&](int x, int y) {
if (x < 1 || x > n || y < 1 || y > m) return false;
if (x >= 2 && mp[x - 1][y] == '#') return false;
if (x <= n - 1 && mp[x + 1][y] == '#') return false;
if (y >= 2 && mp[x][y - 1] == '#') return false;
if (y <= m - 1 && mp[x][y + 1] == '#') return false;
return true;
};
vector<vector<int>> dis(n + 1, vector<int>(m + 1, n * m + 1));
vector<vector<int>> vis(n + 1, vector<int>(m + 1, 0));
vector<vector<pair<int, int>>> last(n + 1, vector<pair<int, int>>(m + 1));
for (int i = 1; i <= n; i++) {
if (!check(i, 1)) continue;
if (mp[i][1] == '#') {
Q.emplace_front(i, 1);
dis[i][1] = 0;
} else {
Q.emplace_back(i, 1);
dis[i][1] = 1;
}
vis[i][1] = 1;
last[i][1] = {-1, -1};
}
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop_front();
for (auto [dx, dy] : d) {
if (!check(x + dx, y + dy) || vis[x + dx][y + dy]) continue;
if (mp[x + dx][y + dy] == '#') {
dis[x + dx][y + dy] = dis[x][y];
Q.emplace_front(x + dx, y + dy);
} else {
dis[x + dx][y + dy] = dis[x][y] + 1;
Q.emplace_back(x + dx, y + dy);
}
last[x + dx][y + dy] = {x, y};
vis[x + dx][y + dy] = 1;
}
}
int BestEnd = 1;
for (int i = 1; i <= n; i++) {
if (dis[i][m] < dis[BestEnd][m]) BestEnd = i;
}
if (dis[BestEnd][m] == n * m + 1) {
cout << "No\n";
return;
}
int nowx = BestEnd, nowy = m;
while (pair<int, int>(nowx, nowy) != pair<int, int>{-1, -1}) {
mp[nowx][nowy] = '#';
auto [x, y] = last[nowx][nowy];
swap(x, nowx), swap(y, nowy);
}
cout << "Yes\n";
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cout << mp[i][j];
cout << '\n';
}
return;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Problem F Distance to the Path
做法：如果将操作分解，每个点维护一个向量\{x_i\},i\in[0,20]，表示这个点距离恰好为i的儿子都加上x_i，则查询时只需要检查其20个父亲的贡献即可。每次修改中，影响的点为u\rightarrow v的路径上的点和其LCA的至多20个父亲，显然对于路径上的点，只需要修改x_d即可，但是对于LCA及其父亲，影响为等差数列，也就是需要修改的为x_{d-t},x_{d-t-1}（t为LCA的第t个父亲）。
然后就是做HLD后用21个线段树/树状数组取维护这些向量，查询时暴力向上跳同时累计贡献即可。
时间复杂度：\mathcal{O}(md\log n+m\log^2 n)
事实上，树状数组会快很多，笔者一开始写了线段树，不仅写错了，而且险些获得TLE的好结果。
Code
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <class T>
struct BIT {
int N;
vector<T> data;
BIT() = default;
BIT(int size) { init(size); }
void init(int size) {
N = size + 2;
data.assign(N + 1, {});
}
// get sum of [0,k]
T sum(int k) const {
if (k < 0) return T{}; // return 0 if k < 0
T ret{};
for (++k; k > 0; k -= k & -k) ret += data[k];
return ret;
}
// getsum of [l,r]
inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }
// get value of k
inline T operator[](int k) const { return sum(k) - sum(k - 1); }
// data[k] += x
void add(int k, T x) {
for (++k; k < N; k += k & -k) data[k] += x;
}
// range add x to [l,r]
void imos(int l, int r, T x) {
add(l, x);
add(r + 1, -x);
}
};
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> t(n + 1);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
t[u].push_back(v);
t[v].push_back(u);
}
vector<int> siz(n + 1), son(n + 1), f(n + 1), dep(n + 1);
auto dfs1 = [&](auto self, int u, int fa) -> void {
siz[u] = 1;
f[u] = fa;
dep[u] = dep[fa] + 1;
for (auto v : t[u]) {
if (v == fa) continue;
self(self, v, u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
};
dfs1(dfs1, 1, 0);
vector<int> dfn(n + 1), top(n + 1);
int cnt = 0;
auto dfs2 = [&](auto self, int u, int tp) -> void {
dfn[u] = cnt++;
top[u] = tp;
if (!son[u]) return;
self(self, son[u], tp);
for (auto v : t[u]) {
if (v == f[u] || v == son[u]) continue;
self(self, v, v);
}
};
dfs2(dfs2, 1, 0);
int m;
cin >> m;
vector<BIT<i64>> bit(21, BIT<i64>(cnt));
while (m--) {
int op;
cin >> op;
if (op == 1) {
int x;
cin >> x;
int step = 0;
i64 ans = 0;
while (step <= 20 && x) {
ans += bit[step].sum(dfn[x]);
x = f[x];
step++;
}
cout << ans << '\n';
}
if (op == 2) {
int u, v, k, d;
cin >> u >> v >> k >> d;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
bit[d].imos(dfn[top[u]], dfn[u], k);
u = f[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
if (u != v) bit[d].imos(dfn[u] + 1, dfn[v], k);
int step = d;
while (step >= 0) {
if (u == 1) {
for (int i = 0; i <= step; i++)
bit[i].imos(dfn[u], dfn[u], k);
break;
}
bit[step].imos(dfn[u], dfn[u], k);
if (step == 0) break;
step--;
bit[step].imos(dfn[u], dfn[u], k);
u = f[u];
}
}
}
return 0;
}
近期评论