[problem:305369A]
Сделаем то, что от нас требуют в условии — просто посчитаем количество таких индексов, что $$$a_i \neq b_i$$$
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;
string a, b;
getchar();
getline(cin, a);
getline(cin, b);
int ans = 0;
for(int i = 0; i < n; i++)
if (a[i] != b[i])
ans++;
cout << ans << '\n';
}
}
[problem:305369B]
Заметим, что в точках пересечения $$$y$$$ обоих графиков будет совпадать. Тогда приравняем $$$y$$$. Приравняв левые части, можем приравнять и правые части, тогда получим квадратное уравнение $$$a*x^2 +b*x + c = d*x +e$$$. Выразим из него $$$x$$$, Теперь подставим его в любое из изначальных уравнений, получим $$$y$$$.
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
int32_t main() {
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
b -= d;
c -= e;
int D = b * b - 4 * a * c;
cout.precision(6);
if (D < 0)
cout << 0;
else if (D == 0){
cout << 1 << '\n';
int x = ((double)(-b) + sqrt(D)) / 2.0 / a;
cout << fixed << x << ' ' << d * x + e << '\n';
}
else{
cout << 2 << '\n';
double x1 = (-b + sqrt(D)) / 2.0 / a;
cout << fixed << x1 << ' ' << d * x1 + e << '\n';
double x2 = (-b - sqrt(D)) / 2.0 / a;
cout << fixed << x2 << ' ' << d * x2 + e << '\n';
}
}
[problem:305369C]
Если бы ограничения не были бы слишком большими, то мы бы могли просто посчитать префиксные произведения и перебирать индекс раздела. Чтобы решить эту проблему с большими числами, воспользуемся интересным свойством: логарифм произведения равен сумме логарифмов. Теперь мы уменьшили числа и можем решать простую версию задачи.
Автор реализации: Maksim1744
/*
author: Maksim1744
created: 13.01.2021 17:52:19
*/
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T>& v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T>& v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T>& v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define TAG_LENGTH 25
#define LR_LEFT left
#define LR_RIGHT right
#define LR_VALUE value
#define LR_SECOND_VALUE mn
#include "C:/C++ libs/print.cpp"
#else
#define showl 42;
#define shows 42;
#define show(...) 42;
#define showm(...) 42;
#define showt(...) 42;
#define printTree(...) 42;
#define printGraph(...) 42;
#define printLRTree(...) 42;
#define printMatrix(...) 42;
#define printWGraph(...) 42;
#define debug if (false)
#endif
template<auto P>
struct Modular {
using value_type = decltype(P);
value_type value;
Modular(ll k = 0) : value(norm(k)) {}
Modular<P>& operator += (const Modular<P>& m) { value += m.value; if (value >= P) value -= P; return *this; }
Modular<P> operator + (const Modular<P>& m) const { Modular<P> r = *this; return r += m; }
Modular<P>& operator -= (const Modular<P>& m) { value -= m.value; if (value < 0) value += P; return *this; }
Modular<P> operator - (const Modular<P>& m) const { Modular<P> r = *this; return r -= m; }
Modular<P> operator - () const { return Modular<P>(-value); }
Modular<P>& operator *= (const Modular<P> &m) { value = value * 1ll * m.value % P; return *this; }
Modular<P> operator * (const Modular<P>& m) const { Modular<P> r = *this; return r *= m; }
Modular<P>& operator /= (const Modular<P> &m) { return *this *= m.inv(); }
Modular<P> operator / (const Modular<P>& m) const { Modular<P> r = *this; return r /= m; }
Modular<P>& operator ++ () { return *this += 1; }
Modular<P>& operator -- () { return *this -= 1; }
Modular<P> operator ++ (int) { Modular<P> r = *this; *this += 1; return r; }
Modular<P> operator -- (int) { Modular<P> r = *this; *this -= 1; return r; }
bool operator == (const Modular<P>& m) const { return value == m.value; }
bool operator != (const Modular<P>& m) const { return value != m.value; }
value_type norm(ll k) {
if (!(-P <= k && k < P)) k %= P;
if (k < 0) k += P;
return k;
}
Modular<P> inv() const {
value_type a = value, b = P, x = 0, y = 1;
while (a != 0) { value_type k = b / a; b -= k * a; x -= k * y; swap(a, b); swap(x, y); }
return Modular<P>(x);
}
};
template<auto P> Modular<P> pow(Modular<P> m, ll p) {
Modular<P> r(1);
while (p) {
if (p & 1) r *= m;
m *= m;
p >>= 1;
}
return r;
}
template<auto P> ostream& operator << (ostream& o, const Modular<P> &m) { return o << m.value; }
template<auto P> istream& operator >> (istream& i, Modular<P> &m) { ll k; i >> k; m.value = m.norm(k); return i; }
template<auto P> string to_string(const Modular<P>& m) { return to_string(m.value); }
using Mint = Modular<1000000007>;
// using Mint = Modular<998244353>;
// using Mint = long double;
const ll mod = 1000000007;
vector<Mint> f, fi;
void init_C(int n) {
f.assign(n, 1); fi.assign(n, 1);
for (int i = 2; i < n; ++i) f[i] = f[i - 1] * i;
fi.back() = Mint(1) / f.back();
for (int i = n - 2; i >= 0; --i) fi[i] = fi[i + 1] * (i + 1);
}
Mint C(int n, int k) {
if (k < 0 || k > n) return 0;
else return f[n] * fi[k] * fi[n - k];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
vector<ll> a(n);
cin >> a;
if (n == 1) {
cout << Mint(a[0]) << '\n';
return 0;
}
int cnt_neg = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < 0)
++cnt_neg;
}
if (cnt_neg % 2 == 0) {
Mint ans = 1;
for (auto k : a) {
ans *= k;
}
if (a[0] == 1 || a.back() == 1) ans += 1;
cout << ans << '\n';
return 0;
}
ld pref1 = 0, pref2 = 0;
int ind = 0;
while (a[ind] > 0) {
pref1 += log((ld)a[ind]);
++ind;
}
pref1 += log((ld)abs(a[ind]));
ind = n - 1;
while (a[ind] > 0) {
pref2 += log((ld)a[ind]);
--ind;
}
pref2 += log((ld)abs(a[ind]));
if (pref1 > pref2) reverse(a.begin(), a.end());
Mint a1 = 1, a2 = 1;
ind = 0;
while (a[ind] > 0) {
a1 *= a[ind];
++ind;
}
a1 *= a[ind];
++ind;
if (ind == n) a2 = 0;
while (ind < n) {
a2 *= a[ind];
++ind;
}
cout << a1 + a2 << '\n';
return 0;
}
[problem:305369D]
Заметим, что под кандидаты чисел подходят только квадраты простых чисел. Тогда переберём все простые числа до $$$\sqrt{n}$$$ и проверим, подходят ли они под неравенство $$$l \le cur^2 \le r$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6;
bool sieve[N + 1];
void compute_primes() {
for (int i = 2; i <= N; i++)
sieve[i] = true;
for (long long i = 2; i <= N; i++) {
if (sieve[i]) {
for (long long j = i * i; j <= N; j += i)
sieve[j] = false;
}
}
}
int32_t main()
{
compute_primes();
long long l, r, ans = 0;
cin >> l >> r;
for(int i = ceil(sqrt(l)); i <= floor(sqrt(r)); i++){
if (sieve[i])
ans++;
}
cout << ans << '\n';
}
[problem:305369E]
Нам нужна структура данных, которая умеет выполнять операции из условия за $$$O(log_2n)$$$. Примером такой структуры является дерево отрезков. Так как ограничения достаточно маленькие, то обычное дерево отрезков на сумму здесь будет сложно заслать. Поэтому просто напишем его нерекурсивную реализацию или дерево Фенвика.
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
int n, q;
int a[1000000];
int f[1000000];
int sum(int x) {
int result = 0;
for (; x >= 0; x = (x & (x + 1)) - 1) {
result += f[x];
}
return result;
}
int sum(int l, int r) {
if (l) {
return sum(r) - sum(l - 1);
} else {
return sum(r);
}
}
void increase(int idx, int delta) {
a[idx] += delta;
for (; idx < n; idx |= idx + 1) {
f[idx] += delta;
}
}
int32_t main() {
cin >> n >> q;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
increase(i, t);
}
int ans = LLONG_MIN;
while(q--){
int tp, l, r;
cin >> tp >> l >> r;
if(tp == 1)
ans = max(ans, sum(l - 1, r - 1));
else
increase(l - 1, r - a[l - 1]);
}
if(ans == LLONG_MIN)
cout << "0\n";
else
cout << ans << '\n';
}
[problem:305369F]
Фактически нам нужно посчитать математическое ожидание на отрезке. Просто сначала предпросчитаем массив, в котором будем хранить произведение $$$a_i * p_i$$$. Затем сделаем по нему префиксные суммы и просто будет отвечать на запрос суммы на отрезке.
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int n, q;
cin >> n >> q;
double m[n];
for(int i = 0; i < n; i++){
double a, p;
cin >> a >> p;
p /= 100;
m[i] = a * p;
}
for(int i = 1; i < n; i++)
m[i] += m[i - 1];
while(q--){
int l, r;
cin >> l >> r;
l--, r--;
cout.precision(6);
if (l > 0)
cout << fixed << m [r] - m [l - 1] << '\n';
else
cout << fixed << m [r] << '\n';
}
}