链接：https://codeforces.com/gym/104363
A. Magic Computer
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 998244353;
i64 power(i64 a, i64 b) {
i64 res = 1;
for (; b; b >>= 1, a = a * a % P) {
if (b & 1) {
res = res * a % P;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
cout << power(2, n - 1) << '\n';
return 0;
}
B. Chevonne's Game
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
template<class Info, class Tag>
struct LazySegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << std::__lg(n), Info());
tag.assign(4 << std::__lg(n), Tag());
std::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] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
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;
push(p);
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;
push(p);
return 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);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F pred) {
if (l >= y || r <= x || !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F pred) {
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F pred) {
if (l >= y || r <= x || !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F pred) {
return findLast(1, 0, n, l, r, pred);
}
};
struct Tag {
int x;
Tag(int x = 0) : x(x) {};
void apply(const Tag &t) {
x ^= t.x;
}
};
struct Info {
int c0, c1, l, r;
Info(int c0 = 0, int c1 = 0, int l = -1E9, int r = -1E9) {
this->c0 = c0;
this->c1 = c1;
this->l = l;
this->r = r;
}
void apply(const Tag &t) {
if (t.x) {
swap(c0, c1);
l ^= 1;
r ^= 1;
}
}
};
Info operator+(const Info &a, const Info &b) {
int c0 = a.c0 + b.c0;
int c1 = a.c1 + b.c1;
return Info(c0 + (a.r + b.l == 0), c1 + (a.r + b.l == 2), a.l, b.r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
string s;
cin >> n >> q >> s;
vector<Info> a(n);
for (int i = 0; i < n; i++) {
a[i].l = a[i].r = s[i] - '0';
}
LazySegmentTree<Info, Tag> seg(a);
for (int i = 0; i < q; i++) {
char o;
int l, r;
cin >> o >> l >> r;
l--;
if (o == 'M') {
seg.rangeApply(l, r, 1);
} else {
auto res = seg.rangeQuery(l, r);
cout << max(res.c0, res.c1) + 1 << '\n';
}
}
return 0;
}
E. Ethernet
#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;
cout << fixed << setprecision(12);
if (n != m) {
cout << 1.0 / (m + 1) << '\n';
} else {
cout << 1.0 / n << '\n';
}
return 0;
}
F. Folder
#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;
set<int> s;
for (int i = 0; i < n - 1; i++) {
int x;
cin >> x;
s.insert(x);
}
cout << n - 1 - s.size() << '\n';
return 0;
}
G. Gravity
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using Real = i64;
using Point = complex<Real>;
Real cross(const Point &a, const Point &b) {
return (conj(a) * b).imag();
}
Real dot(const Point &a, const Point &b) {
return (conj(a) * b).real();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Point> a(n);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
a[i] = Point(x, y);
}
Point p(0, 0);
for (int i = 0; i < n; i++) {
p += a[i];
}
vector<double> b(n);
for (int i = 0; i < n; i++) {
b[i] = cross(a[i], p);
}
sort(b.begin(), b.end(), greater());
double ans = 0;
i64 sum = 0;
for (int i = 0; i < n - 1; i++) {
sum += b[i];
ans = max(ans, 1.0 * sum / (1LL * (i + 1) * (n - i - 1)));
}
cout << fixed << setprecision(12) << ans / 2.0 << '\n';
return 0;
}
- Heilongjiang Programming Collegiate Provincial Contestprogramming collegiate provincial contest heilongjiang programming collegiate provincial programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong programming provincial collegiate shandong programming collegiate provincial counting programming provincial collegiate sponsored 2023 programming collegiate provincial 题解programming collegiate provincial