链接：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;
}