Masalalar uchun Sarvar Saydullayevdan video editoriallar:
A-E masalalar: https://www.youtube.com/watch?v=bQmuEL5Ax1c
F - masala: https://www.youtube.com/watch?v=zAq-QcTjDIg
Yozma editorial:
Bilamizki ikkita teng sonlarni XOR lari doim 0 ga teng bo'ladi. Demak, agar biz massivni 2 ta XOR lari teng to'plamga ajrata olishimiz uchun massivning barcha elementlarining XOR lari 0 ga teng bo'lishi kerak.
Python
n = int(input())
a = list(map(int, input().split()))
k = a[0]
for i in range(1, n):
k ^= a[i]
if k == 0:
print("yes")
else:
print("no")C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int &i : a)
cin >> i;
int k = a[0];
for (int i = 1; i < n; i++)
k ^= a[i];
cout << (k == 0 ? "yes" : "no");
}Yechimga o'tishdan oldin matematik bir qoidani esga olsak: agar \(\frac{a}{b}\) kasrda \(a\) va \(b\) qisqarmas kasrlar bo'lsa, faqatgina \(b\) sonini tub ko'paytuvchilarga ajratganimizda tub bo'luvchilari \(2\) va(yoki) \(5\) dan iborat bo'lsagina bu kasr chekli o'nli kasr bo'ladi, aks holda cheksiz davriy kasr hosil bo'ladi. Bizning sonimiz \(\frac{1}{x}\) ko'rinishida bo'lgani uchun bu doim qisqarmas kasr bo'ladi. Agar chekli bo'lsa undagi verguldan keyingi raqamlar sonini topish esa \(2\) va(yoki) \(5\) ning darajalariga bog'liqdir. Bizning sonimiz faqat \(2\) ni yoki faqat \(5\) ning dajajasidan tashkil topgan bo'lsa shunisi aniqki undagi verguldan keyingi raqamlar soni shu sonning darajasiga teng bo'ladi(har safar 1 ta xona qo'shilib ketaveradi). Ammo \(2\) ham \(5\) ham ishtirok etgan bolsa, unda javob ikkalasidan darajasi kattasiga teng bo'ladi, chunki sonni \(2\) ga bo'lib song \(5\) ga bo'lsak ham undagi xonalar soni 1 taga ortadi xolos.
Python
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
if n == 1 and (p[0] == 2 or p[0] == 5):
print(q[0])
elif n == 2 and p[0] == 2 and p[1] == 5:
print(max(q[0], q[1]))
else:
print("inf") C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> p(n), q(n);
for (int &i : p)
cin >> i;
for (int &i : q)
cin >> i;
if (n == 1 && (p[0] == 2 || p[0] == 5))
cout << q[0];
else if (n == 2 && p[0] == 2 && p[1] == 5)
cout << max(q[0], q[1]);
else
cout << "inf";
}Azimjon yutishi uchun tanlashi kerak bo'lgan sonlari binary search orqali tanlab chiqamiz, ammo katta butun sonlar bilan ishlashda bazida xato javob chiqishi mumkin. shuning uchun javobni topgandan so'ng uning atrofidagi ba'zi sonlarni yana bir bor tekshirish lozim.
Python
n = int(input())
arr = list(map(int, input().split()))
s = sum(arr)
l, r = 1, int(1e12 + 5)
while r > l:
m = (l + r) // 2
if 0.8 * (s + m) / (n + 1) < m:
r = m
else:
l = m + 1
ans = 0
df = 1e9
for i in range(r - 10, r + 10):
if abs(i - 0.8 * (s + i) / (n + 1)) < df:
df = abs(i - 0.8 * (s + i) / (n + 1))
ans = i
print(ans)
C++
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n;
cin >> n;
vector<int> arr(n);
int s = 0;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
s += arr[i];
}
int l = 1, r = 1e12 + 5, m;
while (r > l)
{
m = (l + r) / 2;
if (0.8 * (s + m) / (n + 1) < m)
r = m;
else
l = m + 1;
}
int ans = 0;
double df = 1e9;
for (int i = r - 10; r + 10 > i; i++)
{
if (abs(i - 0.8 * (s + i) / (n + 1)) < df)
{
df = abs(i - 0.8 * (s + i) / (n + 1));
ans = i;
}
}
cout << ans << '\n';
}Aytilgan shartlarni qanoatlantiruvchi qismsatr uzunligi doim \(26\) dan katta bo'lmasligi aniq chunki hech bir harf takrorlanmasin deyilgan. Shuning uchun har safar ketma-ket qismsatrlarni qarab ketaveramiz va doim optimal yechimni olib ketamiz.
Python
s = input()
n = len(s)
mx = 0
res = ""
m = set()
for i in range(n):
m.clear()
c = 0
for j in range(i, n):
if s[j] in m:
break
m.add(s[j])
c += ord(s[j]) - ord("a") + 1
if c > mx or (c == mx and s[i : j + 1] < res):
mx = c
res = s[i : j + 1]
print(res)
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
int n = s.length(), mx = 0;
string res = "";
set<char> m;
for (int i = 0; i < n; i++)
{
m.clear();
int c = 0;
for (int j = i; j < n; j++)
{
if (m.count(s[j]))
break;
m.insert(s[j]);
c += s[j] - 'a' + 1;
if (c > mx || (c == mx && s.substr(i, j - i + 1) < res))
{
mx = c;
res = s.substr(i, j - i + 1);
}
}
}
cout << res << endl;
}
Bu masalani dp algoritmi yordamida osongina hal etishimiz mumkin. \(N\) ga \(B\)o'lchamli dp massivda, \(dp[i][j]\) uchun \(i-\)elementgacha, bo'lgan qiymatlar uchun \(j\) so'm yordamida maksimal qancha konfet olishimiz mumkinligini saqlab ketsak, oxirida barcha \(j\) lardagi qiymatlarning maksimumi bizning javobimiz bo'ladi.
Python
N, B = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
dp = [[0] * (B + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(B + 1):
dp[i][j] = dp[i - 1][j]
if j >= c[i - 1]:
x = a[i - 1] * b[i - 1]
if i > 1 and j >= c[i - 1]:
dp[i][j] = max(dp[i][j], dp[i - 2][j - c[i - 1]] + x)
elif i == 1 and j >= c[i - 1]:
dp[i][j] = max(dp[i][j], x)
res = 0
for i in range(B + 1):
res = max(res, dp[N][i])
print(res)
C++
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int N, B;
cin >> N >> B;
vector<int> a(N), b(N), c(N);
for (int i = 0; i < N; ++i)
cin >> a[i];
for (int i = 0; i < N; ++i)
cin >> b[i];
for (int i = 0; i < N; ++i)
cin >> c[i];
vector<vector<int>> dp(N + 1, vector<int>(B + 1, 0));
for (int i = 1; i <= N; ++i)
{
for (int j = 0; j <= B; ++j)
{
dp[i][j] = dp[i - 1][j];
if (j >= c[i - 1])
{
int x = a[i - 1] * b[i - 1];
if (i > 1 && j >= c[i - 1])
dp[i][j] = max(dp[i][j], dp[i - 2][j - c[i - 1]] + x);
else if (i == 1 && j >= c[i - 1])
dp[i][j] = max(dp[i][j], x);
}
}
}
int res = 0;
for (int i = 0; i <= B; ++i)
res = max(res, dp[N][i]);
cout << res << endl;
}F. Pul daraxti
Ushbu masalada daraxtlar soniga e'tibor beradigon bo'lsak, \(30\) dan kichik yoki tengligini ko'ramiz. Bu degani har bir daraxt uchun alohida javob hisoblab oxirida ularning eng katta qiymatini chiqarish kifoya. Biroq, har bir daraxtni qanday hisoblaymiz? Bunda esa avvalo masalani yaxshiroq tushunish uchun biz ko'z oldimizga aylanani va unda n ta node ni keltirishimiz lozim. Bilamizki Azimjon va qirol navbatma navbatdan yurish qiladi va Azimjon birinchi boshlaydi. Demak, aylanadagi yarim node larni Azimjon qolgan yarmini esa qirol oladi(\(n\) ta node uchun maksimum \(\frac{n+1}{2}\) ta node ni Azimjon olishi mumkin). Shunday ekan bizning javobimiz aniq qaysidur uzunligi \(\frac{n+1}{2}\) ga teng bo'lgan qismmassiv summasiga teng bo'ladi. Ammo, bu degani ularning kattasiga degani emas! Chunki Azimjon istalgan bir tugundan boshlaganda Qirol uning yonidagi tugunni tanlab uning rejasini barbod qilishi mumkin. Shuning uchun avval summasi eng kichigi topib olish kerak chunki shundagina aniq qirol u oraliqdan hech qanday pul olmasligi aniq bo'lib qoladi shunga qarab optimal javobni topishimiz mumkin. Masalani toliqroq tushunish uchun eng yuqoridagi video editorialni ko'ring.
Python
def solve(N, A):
a = [0] * (N + 1)
for i in range(1, N + 1):
a[i] = A[i - 1] + a[i - 1]
def f(s, e):
if s <= 0:
return a[e] + (a[N] - a[s + N - 1])
return a[e] - a[s - 1]
px = [0] * N
qx = [0] * N
dq = []
num = []
for i in range(1, N + 1):
px[i - 1] = f(i - (N - 1) // 2, i)
for i in range(N + (N - 1) // 2): #
if num and num[0] == i - ((N - 1) // 2+1):
num.pop(0)
dq.pop(0)
while dq and dq[-1] > px[i % N]:
num.pop()
dq.pop()
dq.append(px[i % N])
num.append(i)
if i - (N - 1) // 2 >= 0:
qx[i - (N - 1) // 2] = dq[0]
return max(qx)
k = int(input())
mx = 0
for i in range(k):
n = int(input())
a = list(map(int, input().split()))
mx = max(solve(n,a),mx)
print(mx)C++
#include <bits/stdc++.h>
using namespace std;
int n;
int summa(int l, int r, vector<int> &pref){
if(l<=0){
return pref[r] + (pref[n] - pref[l + n - 1]);
}
return pref[r] - pref[l-1];
}
int solve(){
cin >> n;
int cc = (n - 1) / 2;
vector<int> arr(n), pref(n+1), circle_pref(n);
deque <array<int, 2>> q;
for(int i = 0; n > i; i++){
cin >> arr[i];
}
for(int i = 0; n > i; i++){
pref[i+1] = pref[i] + arr[i];
}
for(int i = 1; n >= i; i++){
circle_pref[i-1] = summa(i-cc, i, pref);
}
int ans = 0;
for(int i = 0; n + cc > i; i++){
if(!q.empty() && q.front()[1] == i - (cc + 1)){
q.pop_front();
}
while(!q.empty() && q.back()[0] > circle_pref[i % n]){
q.pop_back();
} q.push_back({circle_pref[i%n], i});
if(i >= cc){
ans = max(ans, q.front()[0]);
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
int ans = 0;
while(t--){
ans = max(ans, solve());
}
cout << ans << '\n';
return 0;
}
Telegram kanalimizga obuna bo'ling