链接：https://codeforces.com/gym/104366
A. Cask Effect
#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<i64> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << fixed << setprecision(1);
if (n == 1) {
cout << a[0] << '\n';
return 0;
}
if (n == 2) {
cout << (a[0] + a[1]) / 2.0 << '\n';
return 0;
}
sort(a.begin(), a.end());
cout << min((a[0] + a[n - 1]) / 2.0, double(a[1])) << '\n';
return 0;
}
D. Concrete Painting
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 998244353;
constexpr int N = 2E5;
int pw[N + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
pw[0] = 1;
for (int i = 1; i <= N; i++) {
pw[i] = 2LL * pw[i - 1] % P;
}
int n;
cin >> n;
vector<int> a;
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
a.push_back(x[i]);
a.push_back(y[i]);
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int m = a.size();
vector<int> sum(m);
for (int i = 0; i < n; i++) {
sum[lower_bound(a.begin(), a.end(), x[i]) - a.begin()]++;
sum[lower_bound(a.begin(), a.end(), y[i]) - a.begin()]--;
}
i64 ans = 0;
partial_sum(sum.begin(), sum.end(), sum.begin());
for (int i = 1; i < m; i++) {
ans = (ans + i64(a[i] - a[i - 1]) * (pw[sum[i - 1]] - 1) % P * pw[n - sum[i - 1]] % P) % P;
}
cout << ans << '\n';
return 0;
}
E. Triangle Pick
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using Real = double;
constexpr Real eps = 1E-8;
struct Point {
Real x, y, z;
Point(const Real &x = 0, const Real &y = 0, const Real &z = 0) : x(x), y(y), z(z) {}
Point &operator+=(Point p) & {
x += p.x;
y += p.y;
z += p.z;
return *this;
}
Point &operator-=(Point p) & {
x -= p.x;
y -= p.y;
z -= p.z;
return *this;
}
Point &operator*=(Real v) & {
x *= v;
y *= v;
z *= v;
return *this;
}
Point operator-() const {
return Point(-x, -y, -z);
}
friend Point operator+(Point a, Point b) {
return a += b;
}
friend Point operator-(Point a, Point b) {
return a -= b;
}
friend Point operator*(Point a, Real b) {
return a *= b;
}
friend Point operator*(Real a, Point b) {
return b *= a;
}
};
int sign(const Real &x) {
return x < -eps ? -1 : x > eps ? 1 : 0;
}
const Real norm(const Point &a) {
return a.x * a.x + a.y * a.y + a.z * a.z;
}
const Real dot(const Point &a, const Point &b) {
return a.x * b.x + a.y * b.y + a.z * b.z;
}
Point cross(const Point &a, const Point &b) {
return Point(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
}
struct Line {
Point a, b;
Line() = default;
Line(const Point &a, const Point &b) : a(a), b(b) {}
};
struct Ray : Line {
Ray() = default;
using Line::Line;
};
const Point o(0, 0, 0);
using Triangle = array<Point, 3>;
vector<Point> cpoint(const Ray &r, const Triangle &g) {
Point v = cross(g[1] - g[0], g[2] - g[0]);
if (dot(v, r.b - r.a) == 0) {
return {};
}
Real k = dot(v, g[0] - r.a) / dot(v, r.b - r.a);
if (sign(k) < 0) {
return {};
}
Point p = r.a + (r.b - r.a) * k;
if (dot(v, cross(p - g[0], p - g[1])) < 0 || dot(v, cross(p - g[1], p - g[2])) < 0 || dot(v, cross(p - g[2], p - g[0])) < 0) {
return {};
}
return {p};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<Point, 3>> a(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
int x, y, z;
cin >> x >> y >> z;
a[i][j] = Point(x, y, z);
}
}
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
Point p(x, y, z);
Ray r = Ray(o, p);
int ans = -1;
double mn = 1E100;
for (int j = 0; j < n; j++) {
auto c = cpoint(r, a[j]);
if (!c.empty()) {
double d = norm(c[0]);
if (d < mn) {
mn = d;
ans = j;
}
}
}
cout << ans + 1 << '\n';
}
return 0;
}
G. Expected Sum
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 998244353;
vector<i64> fac, ifac;
i64 power(i64 a, i64 b, int p = P) {
i64 res = 1;
for (; b; b >>= 1, a = a * a % p) {
if (b & 1) {
res = res * a % p;
}
}
return res;
}
i64 inv(i64 x) {
return power(x, P - 2);
}
void init(int N) {
fac.assign(N + 1, 0);
ifac.assign(N + 1, 0);
fac[0] = 1;
for (int i = 1; i <= N; i++) {
fac[i] = fac[i - 1] * i % P;
}
ifac[N] = inv(fac[N]);
for (int i = N - 1; i >= 0; i--) {
ifac[i] = ifac[i + 1] * (i + 1) % P;
}
}
i64 C(int n, int m) {
if (m < 0 || m > n) {
return 0;
}
return fac[n] * ifac[m] % P * ifac[n - m] % P;
}
const i64 inv100 = inv(100);
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
vector<i64> p(n);
for (int i = 1; i < n; i++) {
int x;
cin >> x;
p[i] = x * inv100 % P;
}
i64 k = 1;
i64 ans = 0;
for (int i = n - 1; i >= 0; i--) {
ans = (ans + k * (s[i] - '0') % P) % P;
k = k * (1 - p[i] + P) % P * 10 % P;
k = (k + p[i]) % P;
}
cout << ans << '\n';
return 0;
}
H. Light the Street
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, k, d;
cin >> n >> k >> d;
double l = 1E-10, r = 1E10;
auto check = [&](double x) {
return 2 * sqrt(1.0 * d / x) + 2 * (k - 1) * sqrt(2.0 * d / x) >= n;
};
double ans = 0;
for (int times = 0; times < 50; times++) {
double mid = (l + r) / 2.0;
if (check(mid)) {
l = mid;
ans = l;
} else {
r = mid;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
I. Subsetting and Summing
#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<array<int, 3>> a(n);
for (int i = 0; i < n; i++) {
auto &[x, y, z] = a[i];
cin >> x >> y >> z;
}
i64 ans = 0;
for (auto xi : {-1, +1}) {
for (auto yi : {-1, +1}) {
for (auto zi : {-1, +1}) {
i64 res = 0;
for (int i = 0; i < n; i++) {
auto &[x, y, z] = a[i];
i64 resx = xi * x;
i64 resy = yi * y;
i64 resz = zi * z;
if (resx + resy + resz >= 0) {
res += resx + resy + resz;
}
}
ans = max(ans, res);
}
}
}
cout << ans << '\n';
return 0;
}
K. The Secret Comparison
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t, o;
cin >> t >> o;
if (o == t) {
cout << "even even seven EIeven.\n";
} else if (t > o) {
cout << "orz teralem is the king!\n";
} else {
cout << "orz overflowker is the king!\n";
}
return 0;
}
M. Easy Problem of Prime
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
vector<int> minp, primes;
vector<i64> f;
void sieve(int n) {
minp.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (minp[i] == 0) {
minp[i] = i;
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) {
break;
}
minp[i * p] = p;
if (p == minp[i]) {
break;
}
}
}
}
void solve() {
int n;
cin >> n;
cout << f[n] << '\n';
}
constexpr int N = 1E7;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
sieve(N);
f.assign(N + 1, 0);
for (int i = 2; i <= N; i++) {
if (i % 2 == 0) {
if (i >= 4) {
f[i] = 2;
} else {
f[i] = 1;
}
} else {
if (minp[i] == i) {
f[i] = 1;
} else if (i - 2 >= 2 && minp[i - 2] == i - 2) {
f[i] = 2;
} else {
f[i] = 3;
}
}
}
for (int i = 1; i <= N; i++) {
f[i] += f[i - 1];
}
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
- Programming Collegiate Northeast Chinese Contestprogramming collegiate northeast chinese programming collegiate northeast contest programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shanghai contest programming collegiate shenzhen contest programming collegiate contest harbin