Спасибо за участие! Надеюсь задачи вам понравились.
Один из тестировщиков (redpanda) сделал прекрасный видео разбор задач A-C, очень рекомендую посмотреть.
Разбор
Tutorial is loading...
Решение (74TrAkToR)
t = int(input())
for T in range(t):
la, lb = map(int, input().split())
ra, rb = map(int, input().split())
if la > lb:
la, lb, ra, rb = lb, la, rb, ra
if la < lb and rb < ra:
print("NO")
else:
print("YES")
Разбор
Tutorial is loading...
Решение (FelixArg)
#include <bits/stdc++.h>
using namespace std;
void solve(){
long long x, y, k;
cin >> x >> y >> k;
while (k > 0 && x != 1) {
long long ost = (x / y + 1) * y - x;
ost = max(1ll, ost);
ost = min(ost, k);
x += ost;
while (x % y == 0) {
x /= y;
}
k -= ost;
}
cout << x + k % (y - 1) << '\n';
}
int main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
for (int test = 0; test < tests; test++){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Подсказка 1
Все числа $$$a_{i}$$$ положительные, может ли это как то помочь?
Подсказка 2
Попробуйте воспользоваться динамическим программированием.
Разбор
Tutorial is loading...
Решение 1 (FelixArg)
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000007;
void solve(){
int n, l, r;
cin >> n >> l >> r;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
vector<long long> pref(n + 1);
for (int i = 0; i < n; i++){
pref[i + 1] = pref[i] + a[i];
}
vector<int> dp(n + 1);
int s = 0;
int j = -1;
for (int i = 0; i < n; i++){
dp[i + 1] = max(dp[i + 1], dp[i]);
if (j < i){
j = i;
s = 0;
}
while(j < n && s < l){
s += a[j++];
}
if (s >= l && s <= r){
dp[j] = max(dp[j], dp[i] + 1);
}
s -= a[i];
}
cout << dp[n] << '\n';
}
int main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
for (int test = 0; test < tests; test++){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Решение 2 (74TrAkToR)
t = int(input())
for T in range(t):
n, l, r = map(int, input().split())
a = [int(x) for x in input().split()]
ans = 0
cur = 0
L, R = 0, 0
while L < n:
while R < n and cur < l:
cur += a[R]
R += 1
if l <= cur and cur <= r:
ans += 1
L = R
cur = 0
else:
cur -= a[L]
L += 1
print(ans)
Подсказкa 1
Как изменяется разница между высотами, если мы выберем конкретную подматрицу?
Подсказкa 2
Стоит свести задачу к математической конструкции. Может что-то из теории чисел может помочь?
Разбор
Tutorial is loading...
Решение (FelixArg)
import math
def solve():
n, m, k = map(int, input().split())
a = [[int(x) for x in input().split()] for j in range(n)]
s = [input() for i in range(n)]
pref = [[0 for i in range(m + 1)] for j in range(n + 1)]
diff = 0
for i in range(n):
cur = 0
for j in range(m):
if s[i][j] == '1':
cur += 1
diff += a[i][j]
else:
diff -= a[i][j]
pref[i + 1][j + 1] = pref[i][j + 1] + cur
if diff == 0:
print("YES")
return
g = 0
for i in range(n - k + 1):
for j in range(m - k + 1):
f = pref[i + k][j + k] - pref[i + k][j] - pref[i][j + k] + pref[i][j]
f = abs(k * k - 2 * f)
g = math.gcd(g, f)
if g == 0 or diff % g != 0:
print("NO")
else:
print("YES")
if __name__ == "__main__":
t = int(input())
for _ in range(t):
solve()
1982E - Количество k-хороших подотрезков
Подсказкa
Попробуйте использовать подход "разделяй и властвуй".
Разбор
Tutorial is loading...
Решение (FelixArg)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
map<pair<long long, int>, tuple<int, long long, long long>> mem;
tuple<int, long long, long long> calc(long long n, int k){
if (k < 0){
return tuple{0, 0ll, 0ll};
}
if (n == 1){
return tuple{1, 1ll, 1ll};
}
int bit = 63 - __builtin_clzll(n);
long long mid = (1ll << bit);
if (mid == n){
mid >>= 1;
if (mem.count({n, k})){
return mem[{n, k}];
}
}
auto [f1, s1, e1] = calc(mid, k);
auto [f2, s2, e2] = calc(n - mid, k - 1);
int sub1 = (e1 % MOD) * ((e1 + 1) % MOD) % MOD * 500000004 % MOD;
f1 = (f1 * 1ll - sub1 + MOD) % MOD;
int sub2 = (s2 % MOD) * ((s2 + 1) % MOD) % MOD * 500000004 % MOD;
f2 = (f2 * 1ll - sub2 + MOD) % MOD;
long long p = (e1 + s2) % MOD;
int f_cur = (f1 * 1ll + f2 + (p * 1ll * ((p + 1) % MOD) % MOD * 500000004 % MOD)) % MOD;
long long s_cur = s1;
long long e_cur = e2;
if (s1 == e1 && s1 != 0){
s_cur = (s1 + s2);
}
if (s2 == e2 && s2 != 0){
e_cur = (e1 + e2);
}
if ((mid << 1) == n){
mem[{n, k}] = tuple{f_cur, s_cur, e_cur};
}
return tuple{f_cur, s_cur, e_cur};
};
void solve(){
long long n;
int k;
cin >> n >> k;
cout << get<0>(calc(n, k)) << '\n';
}
int main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
for (int test = 0; test < tests; test++){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
1982F - И снова задача о сортировке
Подсказкa
Если поддерживать множество таких индексов $$$i$$$, что $$$a_{i} < a_{i - 1}$$$, то может ли это как то помочь?
Разбор
Tutorial is loading...
Решение (FelixArg)
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000007;
struct SegTree{
vector<int> mn, mx;
int n;
SegTree(int _n): n(_n){
mx.assign(2 * n, -inf);
mn.resize(2 * n, inf);
}
void upd(int pos, int val){
mx[pos + n] = val;
mn[pos + n] = val;
pos = (pos + n) >> 1;
for (;pos > 0; pos >>= 1){
mx[pos] = max(mx[pos << 1], mx[(pos << 1) | 1]);
mn[pos] = min(mn[pos << 1], mn[(pos << 1) | 1]);
}
}
pair<int,int> get(int l, int r){
pair<int,int> res = {-inf, inf};
l += n;
r += n + 1;
for (;l < r; l >>= 1, r >>= 1){
if (l & 1) {
res.first = max(res.first, mx[l]);
res.second = min(res.second, mn[l++]);
}
if (r & 1) {
res.first = max(res.first, mx[--r]);
res.second = min(res.second, mn[r]);
}
}
return res;
}
};
void solve(){
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
SegTree tree(n);
set<int> st;
for (int i = 0; i < n; i++){
tree.upd(i, a[i]);
if (i > 0 && a[i] < a[i - 1]){
st.insert(i);
}
}
function<int(int, int)> find_pref = [&](int pos, int x){
if (pos < 0){
return 0;
}
int l = 0, r = pos;
while(l <= r){
int m = l + (r - l) / 2;
if (a[m] > x){
r = m - 1;
}
else{
l = m + 1;
}
}
return r + 1;
};
function<int(int, int)> find_suff = [&](int pos, int x){
if (pos >= n){
return n - 1;
}
int l = pos, r = n - 1;
while(l <= r){
int m = l + (r - l) / 2;
if (a[m] >= x){
r = m - 1;
}
else{
l = m + 1;
}
}
return r;
};
function<void()> query = [&](){
if (st.empty()){
cout << -1 << ' ' << -1 << '\n';
return;
}
int l = *st.begin() - 1;
int r = *(--st.end());
auto [mx, mn] = tree.get(l, r);
cout << find_pref(l - 1, mn) + 1 << ' ' << find_suff(r + 1, mx) + 1 << '\n';
};
query();
int q;
cin >> q;
for (int i = 0; i < q; i++){
int pos, val;
cin >> pos >> val;
pos--;
if (pos > 0 && a[pos] < a[pos - 1]){
st.erase(pos);
}
if (pos + 1 < n && a[pos + 1] < a[pos]){
st.erase(pos + 1);
}
a[pos] = val;
tree.upd(pos, val);
if (pos > 0 && a[pos] < a[pos - 1]){
st.insert(pos);
}
if (pos + 1 < n && a[pos + 1] < a[pos]){
st.insert(pos + 1);
}
query();
}
}
int main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
for (int test = 0; test < tests; test++){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
