A
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[57];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
sort(a + 1, a + n + 1);
int sum = 0;
for (int i = 1;i <= n / 2;i++) sum += a[n - i + 1] - a[i];
cout << sum << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int n;
cin >> n;
int cnt = 0, last = 1;
ll sum = 0;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
sum += abs(x);
if (x < 0) cnt += last == 1, last = -1;
if (x > 0) last = 1;
}
cout << sum << ' ' << cnt << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
ll n;
cin >> n;
ll ans = 0, sum = 0;
for (int i = 62;i >= 0;i--) {
(sum <<= 1) |= (n >> i) & 1;
ans += sum;
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> g[200007];
int f[200007];
void dfs(int u, int fa) {
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u);
f[u] += f[v];
}
if (!f[u]) f[u] = 1;
}
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) g[i].clear(), f[i] = 0;
for (int i = 1;i <= n - 1;i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
cout << 1LL * f[u] * f[v] << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
E
题意
有一个长为 \(n\) 的数组 \(a\) ，初始时 \(a_i = 0\) 。
对于一个区间 \([l,r]\) ，若 \(a_i(l \leq i \leq r)\) 为 \(1\) 的数量严格大于 \(0\) 的数量，则称这个区间是美丽的。
现在给出 \(m\) 个区间，以及 \(q\) 个操作，每个操作都是：给定一个位置 \(x\) ，将 \(a_x\) 变为 \(1\) 。
操作按顺序执行，最少执行几个操作，使得 \(m\) 个区间中至少有一个区间是美丽的。
题解
知识点：前缀和，二分。
考虑二分答案，每次检验暴力执行所有需要的操作，再算一遍前缀和，最后对每个区间查询即可。
时间复杂度 \(O((n+m+q) \log q)\)
空间复杂度 \(O(n+m+q)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, q;
int Q[100007], l[100007], r[100007];
bool check(int x) {
vector<int> sum(n + 1);
for (int i = 1;i <= x;i++) sum[Q[i]] = 1;
for (int i = 1;i <= n;i++) sum[i] += sum[i - 1];
for (int i = 1;i <= m;i++)
if (2 * (sum[r[i]] - sum[l[i] - 1]) > r[i] - l[i] + 1) return true;
return false;
}
bool solve() {
cin >> n >> m;
for (int i = 1;i <= m;i++) cin >> l[i] >> r[i];
cin >> q;
for (int i = 1;i <= q;i++) cin >> Q[i];
int l = 1, r = q;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << (l > q ? -1 : l) << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
F
题意
地铁系统是一棵树且根节点为 \(1\) ，每个节点都有一个权值 \(x \in \{-1,1\}\) 。
初始时只有根节点，现在给出 \(n\) 个操作，有两种：
- 为指定节点 \(v\) 增加一个儿子，编号为当前最大编号加 \(1\) ，权值为 \(x\) 。
- 查询路径 \((u,v)\) 上，是否存在一个子段的和为 \(k\) 。
题解
知识点：倍增，LCA。
由于权值都是 \(\pm 1\) 的，考虑将子段和为 \(k\) 转化为 \(k\) 在最小子段和与最大子段和之间即可。
同时操作是尾加不带修的，因此树上倍增就可以在线解决了（否则要离线+树剖+线段树）。
现在只需要维护子链的最小子段和以及最大子段和即可，注意这里子链性质不具有交换律，因此要注意严格区分合并的左右。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n \log n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {
int sum = 0;
int lmn = 0;
int rmn = 0;
int mn = 0;
int lmx = 0;
int rmx = 0;
int mx = 0;
T(int x = 0) {
sum = x;
lmn = min(x, 0);
rmn = min(x, 0);
mn = min(x, 0);
lmx = max(x, 0);
rmx = max(x, 0);
mx = max(x, 0);
};
void rev() {
swap(lmn, rmn);
swap(lmx, rmx);
}
friend T operator+(const T &a, const T &b) {
T ans;
ans.sum = a.sum + b.sum;
ans.lmn = min(a.lmn, a.sum + b.lmn);
ans.rmn = min(b.rmn, a.rmn + b.sum);
ans.mn = min({ a.mn,b.mn,a.rmn + b.lmn });
ans.lmx = max(a.lmx, a.sum + b.lmx);
ans.rmx = max(b.rmx, a.rmx + b.sum);
ans.mx = max({ a.mx,b.mx,a.rmx + b.lmx });
return ans;
}
};
int cnt;
int x[200007];
int dep[200007], p[20][200007];
T f[20][200007];
void update(int u, int fa) {
p[0][u] = fa;
dep[u] = dep[fa] + 1;
f[0][u] = T(x[fa]);
for (int i = 1;i <= 19;i++) {
p[i][u] = p[i - 1][p[i - 1][u]];
f[i][u] = f[i - 1][u] + f[i - 1][p[i - 1][u]];
}
}
T query(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
T l = T(x[u]), r = T(x[v]);
for (int i = 19;i >= 0;i--) {
if (dep[p[i][u]] >= dep[v]) {
l = l + f[i][u];
u = p[i][u];
}
if (u == v) return l;
}
for (int i = 19;i >= 0;i--) {
if (p[i][u] != p[i][v]) {
l = l + f[i][u];
r = r + f[i][v];
u = p[i][u];
v = p[i][v];
}
}
r.rev();
return l + f[0][u] + r;
}
bool solve() {
int n;
cin >> n;
cnt = 1;
x[1] = 1;
update(1, 0);
while (n--) {
char op;
cin >> op;
if (op == '+') {
int fa, w;
cin >> fa >> w;
x[++cnt] = w;
update(cnt, fa);
}
else {
int u, v, k;
cin >> u >> v >> k;
T ans = query(u, v);
if (ans.mn <= k && k <= ans.mx) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}