11.3

E - Diameter Endpoint Colors

我感觉相当雷霆啊

(一开始想到子集树去了QAQ)

这里先考虑统计一个树不同直径的数量有多少，可以利用中心来分类讨论

#include 
#include 
#include 
#include 
using namespace std;
using ll = long long;
using pll = pair;
const ll INF = 1e18;void solve()
{int n;cin >> n;vector>g(n + 1);vectored;ed.reserve(n + 1);for(int i = 0 ;i < n - 1 ; i ++ ){int u, v;cin >> u >> v;g[u].emplace_back(v);g[v].emplace_back(u);ed.emplace_back(u, v);}vectorC(n + 1);for(int i = 1; i <= n; i ++ )cin >> C[i];vector>fa(n + 1, vector(35, 0));vectordpth(n + 1, 0);{vectorvis(n + 1, false);vis[1] = true;auto dfs = [&](auto&& dfs, int u)->void{for(int v : g[u]){if(vis[v]) continue;vis[v] = true;fa[v][0] = u;dpth[v] = dpth[u] + 1;dfs(dfs, v);}};dfs(dfs, 1);// for(int i = 1; i <= n ;i ++ ) cout << "TEST :" << i << " " << fa[i][0]  << '\n';for(int i = 1;i <= 32; i ++ )  {for(int j = 1; j <= n ;j ++ ) {fa[j][i] = fa[fa[j][i - 1]][i - 1];}}}auto GetDis = [&](int u, int v)->ll{if(dpth[u] > dpth[v]) swap(u, v);int dif = dpth[v] - dpth[u];ll res{};for(int i = 31 ;i >= 0 ;i -- ){if(dif >> i & 1){res += 1 << i;v = fa[v][i];}}if(u == v) return res;for(int i = 31 ; i >= 0 ;i -- ){if(fa[u][i] != fa[v][i]){u = fa[u][i];v = fa[v][i];res += 1 << i << 1;}}return res + 2;};ll a = 1, b = 1, d{};for(int i = 1; i <= n ;i ++ ){ll da = GetDis(i, a);ll db = GetDis(i, b);if(max(da, db) < d) continue;if(da > db) {d = da; b = i;}else {d = db; a = i;} }// cout << "TEST : " << GetDis(1, 5) <<" " << d << "\n";vectorpath;{vectorvis(n + 1, false);bool fl = false;auto dfs = [&](auto&dfs, int u)->void{for(int v : g[u]){if(vis[v]) continue;vis[v] = true;if(v == b) fl = true;path.emplace_back(v);if(fl) return;dfs(dfs, v);if(fl) return;path.pop_back();}};vis[a] = true;path.emplace_back(a);dfs(dfs, a);}   auto dfs = [&](auto&&dfs, vector&res,vector&vis,  int u, int tar)->void{for(int v : g[u]){if(vis[v]) continue;vis[v] = true;dfs(dfs, res, vis, v, tar - 1);}if(!tar) res.emplace_back(u);};vectorcnt(n + 1, 0);ll res{};if(d & 1){pll rts = {path[path.size() / 2 - 1], path[path.size() / 2]};vectorvis(n + 1);vectorends;vis[rts.first] = vis[rts.second] = true;dfs(dfs, ends, vis, rts.first, d / 2);for(int end : ends) cnt[C[end]] ++ ;ends.clear();dfs(dfs, ends, vis, rts.second, d / 2);for(int end : ends) res += cnt[C[end]];}else{int rt = path[(path.size() + 2 - 1 >> 1) - 1];vectorvis(n + 1);for(int v : g[rt]) vis[v] = true;vis[rt] = true;for(int v : g[rt]){vectorends;dfs(dfs, ends, vis, v, d / 2 - 1);for(int end : ends) res += cnt[C[end]];for(int end : ends) cnt[C[end]] ++ ;}}cout << res << "\n";
}
int main() 
{cin.tie(0)->ios::sync_with_stdio(false);int _ = 1;while( _ -- ) solve();return 0;
}

F - Shift and Inversions

权值主席树，写过几遍了，这次相当轻松,一遍过QWQ

#include 
using namespace std;
using ll = long long;
using pll = pair;
const ll INF = 1e18;
struct PSeg
{struct Node{int ls, rs;int cnt;Node() : ls{},rs{},cnt{} {}};vectorSeg;int n;PSeg(int _n, int _q) {Seg.reserve((_n << 2) + _q * (__lg(_n) + 1));n = _n;}void push_up(int p){int ls = Seg[p].ls;int rs = Seg[p].rs;Seg[p].cnt = Seg[ls].cnt + Seg[rs].cnt;}int build(int s = 1, int t = -1){if(t == -1) t = n;Seg.emplace_back();int p = Seg.size() - 1;if(s == t){Seg[p].cnt = 0;return p;}int mid = s + t >> 1;Seg[p].ls = build(s, mid);Seg[p].rs = build(mid + 1, t);push_up(p);return p;}int clone(int p){Seg.emplace_back(Seg[p]);return Seg.size() - 1;}int add(int x, ll c, int p, int s = 1, int t = -1){if(t == -1) t = n;p = clone(p);if(s == t){Seg[p].cnt += c;return p;}int mid = s + t >> 1;if(mid >= x) Seg[p].ls = add(x, c, Seg[p].ls, s, mid);else Seg[p].rs = add(x, c, Seg[p].rs, mid + 1, t);push_up(p);return p;}ll query(int l, int r, int p ,int s = 1, int t = -1){if(t == - 1) t = n;if(l <= s && t <= r) return Seg[p].cnt;ll L{},R{};int mid = s+ t >> 1;if(mid >= l) L = query(l, r, Seg[p].ls, s, mid);if(mid + 1 <= r) R = query(l, r, Seg[p].rs, mid +1 , t);push_up(p);return L + R;}
};
void solve()
{int n;cin >> n;vectorA(2 * n + 1);for(int i = 1; i <= n ;i ++ ){cin >> A[i];A[i] ++ ;A[i + n] = A[i];}PSeg Seg(n, n << 1);vectorrts;rts.emplace_back(Seg.build());for(int i = 1; i <= 2 * n ;i ++ ) rts.emplace_back(Seg.add(A[i], 1, rts.back()));ll res{};for(int i = 1; i <= n ;i ++ ) res += Seg.query(1, A[i], rts[n]) - Seg.query(1, A[i], rts[i]);for(int i = 1; i <= n ; i ++ ){cout << res << '\n';res -= Seg.query(1, A[i], rts[i + n - 1]) - Seg.query(1, A[i], rts[i]);res += Seg.query(A[i], n, rts[i + n - 1]) - Seg.query(A[i], n, rts[i]);}}
int main() 
{cin.tie(0)->ios::sync_with_stdio(false);int _ = 1;while( _ -- ) solve();return 0;
}

D - Maze Master

不要忘记跳过原本为#的点QWQ

#include 
using namespace std;
using ll = long long;
using pll = pair;
constexpr ll INF = 1e18;
constexpr ll POS = INF / 2;void solve()
{int n ,m ;cin >> n >> m;vectorg(n);for(int i = 0 ;i < n ;i ++ ) cin >> g[i];constexpr int nxs[] = {-1, 0, 1, 0};constexpr int nys[] = {0, 1, 0, -1};vector>dp(n * m, vector(n * m, POS));for(int p = 0 ; p < n * m ; p ++ ){if(g[p / m][p % m] == '#') continue;dp[p][p] = 0;for(int i =0 ; i < 4; i ++ ){int x = p / m + nxs[i], y = p % m + nys[i];if(x < 0 || y < 0 || x >= n || y >= m || g[x][y] == '#' ) continue;int nep = x * m + y;dp[p][nep] = dp[nep][p] = 1;}}ll res{};for(int t = 0; t < n * m ; t ++ ){for(int i = 0 ; i < n * m ;i ++ ) for(int j = 0 ;j < n * m ;j ++ ){dp[i][j] = min(dp[i][j], dp[i][t] + dp[t][j]);}}for(int i = 0 ;i < n * m; i ++ ) for(int j = 0; j < n * m ;j ++ ) if(dp[i][j] < POS) res = max(res, dp[i][j]);cout << res << '\n';
}
int main() 
{cin.tie(0)->ios::sync_with_stdio(false);int _ = 1;while( _ -- ) solve();return 0;
}