Možno si viete predstaviť, aké množstvo zbytočných vecí sa nazbiera za roky v T2. Miška sa rozhodla to zmeniť a vyhodiť všetky zbytočné veci. Zobrala jednu zbytočnú vec zo všetkých miest, kde sa skrývala, a vyniesla ju do koša. Kým sa však stihla vrátiť, všetky uvoľnené miesta už boli zapratané ďalšou kopou vecí. To ju neskutočne naštvalo, a tak zase zobrala nejakú vec a vyniesla ju preč. Keď sa však vrátila, našla ešte väčší neporiadok… To sa už všetci vo všetkom začali strácať. Dá sa vôbec ešte zistiť, koľko máme čoho?
Majme reťazec zložený z malých písmen anglickej abecedy. Postupne prebehne $m$ zmien, pričom pri každej nahradíme všetky výskyty jedného konkrétneho písmena novým reťazcom písmen. Zistite počet výskytov hľadaného písmena po všetkých zmenách.
V prvom riadku vstupu sú medzerou oddelené dve čísla $n$ a $m$, kde $n$ udáva počet znakov vo vstupnom reťazci a $m$ udáva počet zmien.
V druhom riadku sa nachádza reťazec, ktorý popisuje uloženie vecí na začiatku. Nasleduje $m$ riadkov, v ktorých sa nachádza medzerou oddelené písmeno a reťazec, ktorým máme písmeno nahradiť. Všetky reťazce sa skladajú výhradne z malých písmen anglickej abecedy.
Na poslednom riadku sa nachádza písmeno, na ktoré sa pýtame.
V jednotlivých sadách platia nasledujúce obmedzenia:
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $1 \leq n \leq$ | $100$ | $1\,000$ | $1\,000$ | $10^5$ |
| $1 \leq m \leq$ | $20$ | $100$ | $1\,000$ | $10^4$ |
Maximálna dĺžka nahrádzajúceho reťazca je v prvých troch sadách $50$ a v poslednej $1\,000$.
Vypíšte jedno číslo - počet výskytov písmena, na ktoré sa pýtame v poslednom riadku vstupu. Keďže toto číslo môže byť veľmi veľké, vypíšte ho ako zvyšok po delení $10^9+7$.
5 5
abcde
a aha
b tu
u je
e volne
v miesto
t
3
Postupne nám vychádzajú reťazce: abcde –> ahabcde –> ahatucde –> ahatjecde
–> ahatjvolnecdvolne –> ahatjmiestoolnecdmiestoolne. Vidíme, že na konci sa
v reťazci nachádzajú tri písmená t.
Najjednoduchšie je nasimulovať si jednotlivé zmeny. Pre každú zmenu nájdeme všetky výskyty daného písmena a postupne ich nahradíme daným reťazcom. Takto pre každú zmenu musíme prejsť celý reťazec v čase $O(n)$, čím dostaneme časovú zložitosť $O(n \cdot m)$. Netreba však zabúdať na to, že dĺžka reťazca sa pri nahrádzaní postupne zväčšuje. Skutočná časová zložitosť by tak rástla a program by bol pre väčšie vstupy extrémne pomalý.
Môžeme si uvedomiť, že presný tvar výsledného reťazca nás vôbec nezaujíma.
Keďže sa pýtame len na konečný počet nejakého písmena, stačí si po celý čas
pamätať len to, koľkokrát sa jednotlivé písmená v reťazci momentálne nachádzajú.
Ak máme napríklad zmeniť písmeno a za reťazec bcd, stačí sa pozrieť, koľko
a-čok momentálne máme. Ak ich je päť, vieme, že do reťazca pribudne päť b-čok,
päť c-čok a päť d-čok. Zároveň nesmieme zabudnúť, že týchto päť a-čok z reťazca
zmizlo, takže ich počet musíme vynulovať (respektíve zobrať do úvahy aj to,
či sa písmeno a nenachádza aj v nahrádzajúcom reťazci).
Keďže možných znakov v reťazci je konštantne veľa ($26$), vytvoríme si pole alebo slovník, kde si pre každé písmenko budeme pamätať jeho aktuálny počet. Na začiatku si raz prejdeme vstupný reťazec a spočítame začiatočné výskyty, čo nám zaberie čas $O(n)$. Následne spracujeme $m$ zmien. Pre každú zmenu zistíme aktuálny počet nahrádzaného písmena. Tento počet pripočítame každému písmenu, ktoré sa nachádza v nahrádzajúcom reťazci (tento reťazec musíme raz prejsť), a nakoniec aktuálny počet nahrádzaného písmena vynulujeme. Ak má nahrádzajúci reťazec maximálnu dĺžku $k$, potom spracovať jednu zmenu vieme v čase $O(k)$. Zmien je $m$, teda časová zložitosť spracovania zmien je $O(k \cdot m)$. Výsledná časová zložitosť tohto riešenia je $O(n + k \cdot m)$. Keďže si pamätáme len tabuľku výskytov pre $26$ písmen, pamäťová zložitosť je konštantná, teda $O(1)$.
n, i = map(int, input().split())
zaciatocny_str = input()
pocet = {}
abc = 'abcdefghijklmnopqrstuvwxyz'
for p in abc:
pocet[p] = 0
for p in zaciatocny_str:
pocet[p] += 1
for _ in range (i):
old, new = input().split()
k = pocet[old]
for p in new:
pocet[p] += k
pocet[old] -= k
hladane = input()
print(pocet[hladane] % 1000000007)
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, ops;
if (!(cin >> n >> ops)) return 0;
string zaciatok;
cin >> zaciatok;
vector<long long> pocet(26, 0);
long long MOD = 1000000007;
for (char c : zaciatok) {
pocet[c - 'a']++;
}
for (int i = 0; i < ops; ++i) {
string old_str, new_str;
cin >> old_str >> new_str;
char old_char = old_str[0];
long long k = pocet[old_char - 'a'];
for (char c : new_str) {
pocet[c - 'a'] = (pocet[c - 'a'] + k) % MOD;
}
pocet[old_char - 'a'] = (pocet[old_char - 'a'] - k + MOD) % MOD;
}
string hladane_str;
cin >> hladane_str;
char hladane = hladane_str[0];
cout << pocet[hladane - 'a'] % MOD << endl;
return 0;
}
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete