Problema Tăietura – ONI 2017, Clasa a 10-a
Rezumat
Se dă un vector format din numere întregi. O tăietură în poziția reprezintă o secvență a vectorului ce conține poziția Valoarea unei tăieturi este dată de suma tuturor elementelor ce trec prin ea. Se definește funcția drept numărul de tăieturi în de sumă Trebuie să aflăm valoarea acestei funcții pentru fiecare cuprins între și
Soluție
Construim un vector de sume parțiale: pentru strict pozitiv, și Putem observa că orice tăietură cu suma are sumele parțiale de la capete egale. Mai exact, dacă o tăietură cu suma începe pe poziția și se termină pe poziția atunci Motivul este că suma acestei tăieturi este dată de
Considerăm că avem elemente din cu valoarea și că înainte de poziția avem Atunci, în poziția acestea determină tăieturi cu suma Deci, pentru orice cuprins între și trebuie incrementată cu Putem face asta foarte eficient folosind Șmenul lui Mars, dar mai întâi trebuie să explic cum am implementat partea din paragraful anterior.
Ne interesează ca pentru fiecare sumă parțială să reținem pozițiile pe care apare aceasta. Pentru că sumele astea aparțin unui interval foarte mare, nu puteam folosi un vector de frecvență, așa că am ales un std::map< long long int, std::vector<int> >
, numit hash
. Cheia este suma parțială, iar valoarea este vectorul cu pozițiile sale, ordonat crescător, și indexat de la În timp ce am citit elementele, am construit map
-ul; nu avea sens să rețin și vectorul de sume parțial în sine.
Apoi, am parcurs sumele parțiale din hash
(nu contează ordinea), folosind iteratorul sum
. Pentru fiecare poziție pe care apare sum.first
în v
(poziție care în sum.second
se află pe poziția i
), am adunat la mars[i + 1]
pe sum.second.size() - 2 * i - 1
. La final, afișăm vectorul mars
exact ca în varianta clasică a șmenului, la fiecare pas adunând pe v[i - 1]
la v[i]
.
Relația precedentă nu e prea intuitivă, dar merge demonstrată matematic destul de ușor. Pentru simplitate, considerăm că rezolvăm problema doar pentru suma parțială sum
. Să zicem că suntem pe poziția i
în hash[sum].second
, și că notăm cu n
pe hash[sum].second.size()
. Atunci, din Șmenul lui Mars rezultă că pentru orice j
cuprins între hash[sum].second[i] + 1
și hash[sum].second[i + 1]
, afișăm:
Ceea ce este echivalent cu formula scrisă mai sus, dedusă din regula produsului:
Sursă C++
#include <map>#include <vector>#include <fstream>
#define DMAX 100010
std::ifstream fin("taietura.in");std::ofstream fout("taietura.out");
int n;long long int mars[DMAX];std::map< long long int, std::vector<int> > hash;
int main() { fin >> n; hash[0].push_back(0);
long long int sum = 0; for (int i = 1; i <= n; i++) { int val; fin >> val; hash[sum += val].push_back(i); }
for (auto sum : hash) for (int i = 0; i < sum.second.size(); i++) mars[sum.second[i] + 1] = 1LL * sum.second.size() - 2 * i - 1;
for (int i = 1; i <= n; i++) fout << (mars[i] += mars[i - 1]) << ' '; fout << '\n'; return 0;}
Dacă ai vreo nedumerire cu privire la problema Tăietura, lasă un comentariu și te voi ajuta