A
算一下每个格子的水能流到哪，前缀和，。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q, k;
cin >> n >> q >> k;
vector<int> a(n + 1), b(n + 1);
vector<i64> sum(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
vector<i64> ans(n + 1);
int pre = 1;
for (int i = 1; i <= n; i++) {
if (i - k + 1 >= 0 && b[i] == b[i - k + 1]) {
pre = i - k + 1;
}
ans[i] = sum[i] - sum[pre - 1];
}
for (int i = 0; i < q; i++) {
int x;
cin >> x;
cout << ans[x] << '\n';
}
return 0;
}
B
异或大于 的数量。
支持插入删除 ，
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int N = 100000 * 31;
int tot = 1;
int trie[N][2];
int tag[N];
void clear() {
for (int i = 0; i <= tot; i++) {
memset(trie[i], 0, sizeof trie[i]);
tag[i] = 0;
}
tot = 1;
}
void modify(int x, int v) {
int u = 1;
for (int i = 30; i >= 0; i--) {
int c = x >> i & 1;
if (!trie[u][c]) {
trie[u][c] = ++tot;
}
u = trie[u][c];
tag[u] += v;
}
}
int get(int x, int h) {
int u = 1;
int res = 0;
for (int i = 30; i >= 0; i--) {
int c = x >> i & 1;
if (h >> i & 1) {
u = trie[u][!c];
} else {
res += tag[trie[u][!c]];
u = trie[u][c];
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, hp;
cin >> n >> hp;
for (int i = 0; i < n; i++) {
int o;
cin >> o;
if (o == 0) {
int x;
cin >> x;
modify(x, +1);
} else if (o == 1) {
int x;
cin >> x;
modify(x, -1);
} else {
int x, h;
cin >> x >> h;
int res = get(x, h);
if (res == 0) {
hp--;
}
cout << res << '\n';
}
}
cout << hp << '\n';
return 0;
}
C
。
这里用 表维护区间最小值，
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
template <class T>
struct SparseTable {
int n;
vector<vector<T>> a;
SparseTable(const vector<T> &init) : n(init.size()) {
int lg = __lg(n);
a.assign(lg + 1, vector<T>(n));
a[0] = init;
for (int i = 1; i <= lg; i++) {
for (int j = 0; j <= n - (1 << i); j++) {
a[i][j] = min(a[i - 1][j], a[i - 1][(1 << (i - 1)) + j]);
}
}
}
T get(int l, int r) {// [l, r)
int lg = __lg(r - l);
return min(a[lg][l], a[lg][r - (1 << lg)]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, c;
cin >> n >> c;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
SparseTable<int> mn(a);
vector<i64> f(n + 1);
for (int i = c; i <= n; i++) {
f[i] = max(f[i - 1], f[i - c] + mn.get(i - c, i));
}
cout << f[n] << '\n';
return 0;
}
D
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
i64 sum = 0;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
}
cout << (sum >= m ? "YES" : "NO") << '\n';
return 0;
}
E
前缀和，。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> sum(n + 1);
for (int i = 0; i < n; i++) {
int x = a[i];
sum[max(i - x, 0)]++;
sum[i]--;
sum[i + 1]++;
sum[min(i + x + 1, n)]--;
}
for (int i = 1; i < n; i++) {
sum[i] += sum[i - 1];
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += (sum[i] > 0);
}
cout << ans << '\n';
return 0;
}
G
二分答案，。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, p;
cin >> n >> p;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
auto check = [&](int x) {
i64 res = 0;
for (int i = 0; i < n; i++) {
if (a[i] > x) {
res += 2LL * (a[i] - x);
}
}
return res >= p;
};
int ans = -1;
int l = 0, r = 1E9;
while (l <= r) {
int m = (l + r) >> 1;
if (check(m)) {
l = m + 1;
ans = m;
} else {
r = m - 1;
}
}
cout << ans << '\n';
return 0;
}
H
最小生成树，树的直径，
。
题面重制
《欢乐颂》是一篇科幻小说，由中国著名科幻作家刘慈欣发表于 $2005$ 年 $8$ 月份的《九州幻想》上，是刘慈欣“大艺术系列”的小说之一（同为“大艺术系列”的小说之还有《诗云》、《梦之海》），全文约三万字。在文章中一位宇宙音乐家来到了地球，他在地球举办了一场美妙且震撼的音乐会。音乐家有一面神奇琴，琴面上有 个琴柱（琴柱从
进行编号），每个琴柱都可以发射一种能量这里命名为“弦值”，只有拥有相同“弦值”的不同琴柱之间才可以连接一条琴弦，每个琴柱可以发射多个“弦值”当然也可以不发射。琴弦的产生需要大量的能量，假设两个琴柱各自发射的“弦值”之和分别为
，则产生琴弦的能量为
。
现在音乐家需要演奏一段音乐并且他只有 次连接琴柱的机会，音乐演奏完成的条件是：所有的琴柱必须都直接或间接相连并且音乐家希望使用的能量尽可能的少。音乐家为了保证只有一种琴柱连接方式，所以在满足音乐演奏完成的情况下他会优先选择连接消耗能量较少的琴弦，如果消耗能量相同则选择
较小的（
是琴弦上编号较小的琴柱，
是琴弦上编号较大的琴柱，
为琴柱数量）。音乐家希望回收所有琴弦的能量，但是如果有琴柱连接不完整那么所有的琴弦都会奔溃，因此音乐家最多只有一次回收的机会，回收能量的方式为：选择两个琴柱（可能直接或间接相连），连接这两个琴柱的琴弦所拥有的的能量都会被回收。
音乐家想知道最后他最多可以回收多少能量。
保证最后可以选择连接的琴柱对数 不超过
，每种弦值出现次数不超过
）。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
struct UnionFind {
int n;
vector<int> f;
UnionFind(const int &n = 0) : n(n), f(n) {
iota(f.begin(), f.end(), 0);
}
int get(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x != y) {
f[y] = x;
return 1;
}
return 0;
}
bool united(int x, int y) {
return get(x) == get(y);
}
};
constexpr int N = 1E6;
int vis[N + 1];
vector<int> p[N + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
vector<int> b;
for (int i = 0; i < n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
p[x].push_back(i);
a[i] += x;
if (!vis[x]) {
b.push_back(x);
vis[x] = 1;
}
}
}
vector<array<int, 3>> e;
for (auto &x : b) {
int k = p[x].size();
for (int i = 0; i < k; i++) {
for (int j = i + 1; j < k; j++) {
int u = p[x][i], v = p[x][j];
if (v > u) {
swap(u, v);
}
e.push_back({(a[u] ^ a[v]) + 1, u, v});
}
}
}
sort(e.begin(), e.end());
UnionFind f(n);
int cnt = 0;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < (int) e.size(); i++) {
auto &[w, u, v] = e[i];
if (f.unite(u, v)) {
g[u].push_back({v, w});
g[v].push_back({u, w});
cnt++;
}
if (cnt == n - 1) {
break;
}
}
if (cnt != n - 1) {
cout << "0\n";
return 0;
}
auto bfs = [&](int s) {
vector<i64> dis(n, -1);
queue<int> q;
q.push(s);
dis[s] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto &[nex, w] : g[cur]) {
if (dis[nex] == -1) {
dis[nex] = dis[cur] + w;
q.push(nex);
}
}
}
return dis;
};
auto dis1 = bfs(0);
int l = max_element(dis1.begin(), dis1.end()) - dis1.begin();
auto dis2 = bfs(l);
cout << *max_element(dis2.begin(), dis2.end()) << '\n';
return 0;
}
I
贪心，。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 30; i >= 0; i--) {
if (n >> i & 1) {
n -= (1 << i);
break;
}
}
cout << n - (1 << __builtin_popcount(n)) + 1;
return 0;
}
K
统计 的数量，
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int h[] = {0, 0};
i64 c[] = {0, 0};
for (int i = 1; i <= n; i++) {
int f1 = 4 * i - 2, f2 = i + 1;
while (f1 % 2 == 0) {
h[0]++;
f1 /= 2;
}
while (f1 % 5 == 0) {
h[1]++;
f1 /= 5;
}
while (f2 % 2 == 0) {
h[0]--;
f2 /= 2;
}
while (f2 % 5 == 0) {
h[1]--;
f2 /= 5;
}
c[0] += h[0];
c[1] += h[1];
}
cout << min(c[0], c[1]) << '\n';
return 0;
}
L
线段树。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
template<class Info,
class Merge = plus<Info>>
struct SegmentTree {
const int n;
const Merge merge;
vector<Info> info;
SegmentTree(int n) : n(n), merge(Merge()), info(4 << __lg(n)) {}
SegmentTree(vector<Info> init) : SegmentTree(init.size()) {
function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = merge(info[2 * p], info[2 * p + 1]);
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y));
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
};
struct Seg {
int l, r, mx;
char c;
Seg(const int &x = 0, const char &c = ' ',
const int &mx = 0) : l(x), r(x), c(c), mx(mx) {}
};
struct Info {
int l, r, mx;
char c;
Seg ls, rs;
Info(const int &x = 0, const char &c = ' ', const int &mx = 0,
const Seg &s = Seg()) : l(x), r(x), c(c), mx(mx), ls(s), rs(s) {}
};
Info operator+(const Info &a, const Info &b) {
Info res;
if (b.l - a.r == 1 && b.c == a.c) {
res.mx = a.mx + b.mx;
res.l = a.l;
res.r = b.r;
res.c = a.c;
} else if (a.mx >= b.mx) {
res.mx = a.mx;
res.l = a.l;
res.r = a.r;
res.c = a.c;
} else {
res.mx = b.mx;
res.l = b.l;
res.r = b.r;
res.c = b.c;
}
if (b.ls.l - a.ls.r == 1 && b.ls.c == a.ls.c) {
res.ls.mx = a.ls.mx + b.ls.mx;
res.ls.l = a.ls.l;
res.ls.r = b.ls.r;
res.ls.c = a.ls.c;
} else {
res.ls = a.ls;
}
if (b.rs.l - a.rs.r == 1 && b.rs.c == a.rs.c) {
res.rs.mx = a.rs.mx + b.rs.mx;
res.rs.l = a.rs.l;
res.rs.r = b.rs.r;
res.rs.c = b.rs.c;
} else {
res.rs = b.rs;
}
if ((a.rs.mx + b.ls.mx > res.mx || (a.rs.mx + b.ls.mx == res.mx && a.rs.l < res.l)) && a.rs.c == b.ls.c) {
res.mx = a.rs.mx + b.ls.mx;
res.c = a.rs.c;
res.l = a.rs.l;
res.r = b.ls.r;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
string s;
cin >> s;
SegmentTree<Info> seg(n);
for (int i = 0; i < n; i++) {
Info v(i, s[i], 1, Seg(i, s[i], 1));
seg.modify(i, v);
}
for (int i = 0; i < q; i++) {
int o;
cin >> o;
if (o == 1) {
int l, r;
cin >> l >> r;
l--;
Info res = seg.rangeQuery(l, r);
cout << res.l + 1 << ' ' << res.r + 1 << '\n';
} else {
int x;
char c;
cin >> x >> c;
x--;
Info v(x, c, 1, Seg(x, c, 1));
seg.modify(x, v);
}
}
return 0;
}
京公网安备 11010502036488号