先简单写一下 A-E 的题解。
A
异或的经典性质：\(x \oplus x=0\)。
B
显然要把字典序最小的那个字母放到最前面。
如果这个字母出现了很多次，那么应该选择最后一次出现的位置。这也很容易证明。
C
联立以后计算一下就行了。
比赛的时候爆了一次 int。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const int maxn = 2e5 + 5;
const ll mod = 998244353;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
const double eps = 1e-6;
void solve() {
int n, m;
cin >> n >> m;
vector<int> K(n);
for (int i = 0; i < n; ++i) {
cin >> K[i];
}
vector<tuple<ll, ll, ll>> parabolas(m);
for (int i = 0, a, b, c; i < m; ++i) {
cin >> a >> b >> c;
parabolas[i] = {a, b, c};
}
sort(K.begin(), K.end());
for (auto [A, B, C] : parabolas) {
if (C <= 0) {
cout << "NO" << endl;
} else {
ll sAC = sqrt(4.0 * A * C);
if (sAC * sAC == A * C * 4) sAC--;
auto it = lower_bound(K.begin(), K.end(), B - sAC);
if (it == K.end()) {
cout << "NO" << endl;
} else if (*it > B + sAC) {
cout << "NO" << endl;
} else {
cout << "YES\n" << (*it) << endl;
}
}
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
D
容易发现，当 \(k\) 从大到小变化时，点会一层一层的加进连通块里。
然后这个 \(k\) 的最大值是树的直径，所以点的层数应该以直径为标准进行统计。
最后模拟这个加点的过程即可。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
vector<int> g[maxn];
int dep[maxn], h[maxn];
int mxdep, root;
void dfs0(int u, int f) {
dep[u] = dep[f] + 1;
for (auto v : g[u]) {
if (v == f) continue;
dfs0(v, u);
}
if (dep[u] >= mxdep) {
mxdep = dep[u];
root = u;
}
}
void dfs(int u, int f) {
dep[u] = dep[f] + 1;
for (auto v : g[u]) {
if (v == f) continue;
dfs(v, u);
}
h[u] = max(h[u], dep[u]);
}
void solve() {
int n;
cin >> n;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
dep[0] = -1;
mxdep = 0;
dfs0(1, 0);
int r = root;
dfs0(root, 0);
dfs(r, 0);
dfs(root, 0);
vector<int> cnt(n + 5, 0);
for (int i = 1; i <= n; ++i) {
cnt[h[i]]++;
}
cnt[mxdep]--;
vector<int> ans(n + 5, n);
for (int k = mxdep; k >= 1; --k) {
ans[k] = ans[k + 1] - cnt[k];
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << " \n"[i == n];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
E
比赛的时候时间不够了，想写个 dsu on tree 试一下，可惜最后还是没写完。
这题的正解其实很简单，考虑整棵树的 MAD，如果这个数出现的次数不是 \(2\)，那么不管断哪条边都不会改变答案。如果出现次数正好是 \(2\)，那么只有这两个点之间的链被断开的时候，答案才会变化。所以先把链提取出来，然后在链上面按顺序算过去就行了。
如果没有观察到这个性质，用 dsu on tree 其实也是能做的。但是会跑的慢一些。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
vector<pii> g[maxn];
int w[maxn];
map<int, int> subtree, total;
set<int> smad, tmad;
int sz[maxn], big[maxn];
int L[maxn], R[maxn], dfn, node[maxn];
int ans[maxn], edge_id[maxn];
void dfs0(int u, int f) {
L[u] = ++dfn;
node[dfn] = u;
sz[u] = 1;
for (auto [v, e] : g[u]) {
if (v == f) continue;
edge_id[v] = e;
dfs0(v, u);
sz[u] += sz[v];
if (!big[u] || sz[big[u]] < sz[v])
big[u] = v;
}
R[u] = dfn;
}
void add(int x) {
subtree[x]++;
if (subtree[x] == 2)
smad.insert(x);
total[x]--;
if (total[x] == 1)
tmad.erase(x);
}
void del(int x) {
total[x]++;
if (total[x] == 2)
tmad.insert(x);
subtree[x]--;
if (subtree[x] == 1)
smad.erase(x);
}
int MAD() {
int mx = 0;
if (!smad.empty()) {
mx = max(mx, *smad.rbegin());
}
if (!tmad.empty()) {
mx = max(mx, *tmad.rbegin());
}
return mx;
}
void dfs1(int u, int f, bool keep) {
for (auto [v, e] : g[u]) {
if (v == f || v == big[u])
continue;
dfs1(v, u, false);
}
if (big[u]) {
dfs1(big[u], u, true);
}
for (auto [v, e] : g[u]) {
if (v == f || v == big[u])
continue;
for (int i = L[v]; i <= R[v]; i++) {
add(w[node[i]]);
}
}
add(w[u]);
ans[edge_id[u]] = MAD();
if (keep == false) {
for (int i = L[u]; i <= R[u]; i++) {
del(w[node[i]]);
}
}
}
void solve() {
int n;
cin >> n;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[v].pb({ u, i });
g[u].pb({ v, i });
}
for (int i = 1; i <= n; ++i) {
cin >> w[i];
total[w[i]]++;
if (total[w[i]] == 2)
tmad.insert(w[i]);
}
dfs0(1, 0);
dfs1(1, 0, false);
for (int i = 1; i < n; ++i) {
cout << ans[i] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
不加任何优化的 dsu on tree 几乎是贴着时限过的。最好还是优化一下，比如先离散化一下，省掉两个 map，就可以跑的和正解一样快了。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
vector<pii> g[maxn];
int w[maxn];
int subtree[maxn], total[maxn];
set<int> smad, tmad;
int sz[maxn], big[maxn];
int L[maxn], R[maxn], dfn, node[maxn];
int ans[maxn], edge_id[maxn];
void dfs0(int u, int f) {
L[u] = ++dfn;
node[dfn] = u;
sz[u] = 1;
for (auto [v, e] : g[u]) {
if (v == f) continue;
edge_id[v] = e;
dfs0(v, u);
sz[u] += sz[v];
if (!big[u] || sz[big[u]] < sz[v])
big[u] = v;
}
R[u] = dfn;
}
void add(int x) {
subtree[x]++;
if (subtree[x] == 2)
smad.insert(x);
total[x]--;
if (total[x] == 1)
tmad.erase(x);
}
void del(int x) {
total[x]++;
if (total[x] == 2)
tmad.insert(x);
subtree[x]--;
if (subtree[x] == 1)
smad.erase(x);
}
int MAD() {
int mx = 0;
if (!smad.empty()) {
mx = max(mx, *smad.rbegin());
}
if (!tmad.empty()) {
mx = max(mx, *tmad.rbegin());
}
return mx;
}
void dfs1(int u, int f, bool keep) {
for (auto [v, e] : g[u]) {
if (v == f || v == big[u])
continue;
dfs1(v, u, false);
}
if (big[u]) {
dfs1(big[u], u, true);
}
for (auto [v, e] : g[u]) {
if (v == f || v == big[u])
continue;
for (int i = L[v]; i <= R[v]; i++) {
add(w[node[i]]);
}
}
add(w[u]);
ans[edge_id[u]] = MAD();
if (keep == false) {
for (int i = L[u]; i <= R[u]; i++) {
del(w[node[i]]);
}
}
}
void solve() {
int n;
cin >> n;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[v].pb({ u, i });
g[u].pb({ v, i });
}
vector<int> all;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
all.pb(w[i]);
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
unordered_map<int, int> wmap;
for (int i = 0; i < all.size(); ++i)
wmap[all[i]] = i + 1;
for (int i = 1; i <= n; ++i) {
w[i] = wmap[w[i]];
total[w[i]]++;
if (total[w[i]] == 2)
tmad.insert(w[i]);
}
dfs0(1, 0);
dfs1(1, 0, false);
for (int i = 1; i < n; ++i) {
if (ans[i]) ans[i] = all[ans[i] - 1];
cout << ans[i] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}