Калид дар ин ҷо чист?

Калидеро ёбед, ки масъала сабтҳоро аз рӯи он гурӯҳбандӣ мекунад, барои ҳар калид хулосаро дар луғат нигоҳ доред ва охирин ҷойи қиматро дар хотир доред.

Назария

Дарси 2 аз 5

Хониш: 39 дақиқа

Саволҳо: 7

Маҷмуъ ва луғат маълумотро аз рӯи калид нигоҳ медоранд. Аксар масъалаҳо дар бораи сабтҳо (ном, адад, сана, холҳо) осон мешаванд, агар аввал ба як савол ҷавоб диҳед: калид чист? Он гоҳ контейнер худ аз худ ёфт мешавад.

Барои ҳар ҳарф як маҷмуъ

Маҷмуъ метавонад нигоҳ дорад, ки чизҳо дар куҷо ҳастанд. Ин масъаларо гиред:

Дар сатри якум сатр аз ҳарфҳои хурд, дар сатри дуюм q аст. Дар ҳар як аз q сатри баъдӣ фосилаи l r аст, мавқеъҳо аз 1 ҳисоб мешаванд. Барои ҳар фосила ҳарфҳои гуногуни байни l ва r-ро бо тартиби алифбо чоп кунед.

Ҳар дафъа ҳар мавқеъи фосилаи дарозро аз нав дидан суст аст. Ба ҷои ин барои ҳар ҳарф як маҷмуъи мавқеъҳоро нигоҳ доред. Он гоҳ як lower_bound барои ҳар ҳарф ба саволи «оё ин ҳарф дар байни l ва r ҳаст?» ҷавоб медиҳад: аввалин мавқеъи он дар l ё баъд аз он бояд вуҷуд дошта бошад ва аз r зиёд набошад.

Вуруд

Баромад

vector<set<int>> pos(26) 26 маҷмуъи холӣ аст, барои ҳар ҳарф яктоӣ, ва s[i] - 'a' маҷмуъи лозимиро интихоб мекунад.

Сабтҳо аз рӯи калид гурӯҳбандӣ мешаванд

Қимати луғат метавонад вектор бошад. Он гоҳ ҳар калид рӯйхати худашро ҷамъ мекунад.

Дар сатри якум n, дар сатри дуюм n адади бутун аст, дар мавқеъҳои аз 1 то n. Барои ҳар қимати гуногун, аз хурд ба калон, мавқеъҳоеро чоп кунед, ки он дар онҳо меояд.

Вуруд

Баромад

where[x] ҳангоми бори аввал омадани x вектори холӣ аст ва push_back ҳар мавқеъро бо тартиб илова мекунад. Ҳамин шакл ҳар гуна сабтро аз рӯи ҳар калид гурӯҳбандӣ мекунад: баҳоҳои хонанда дар зери номи хонанда.

Хулоса барои ҳар калид

Аксар вақт танҳо хулосаи гурӯҳ лозим мешавад: ҷамъ, бузургтарин, чанд бор бузургтарин омадааст.

Ҳар натиҷа номи даста ва хол аст. Барои ҳар даста бо тартиби алифбо беҳтарин холи он ва шумори маротибае, ки даста онро гирифтааст, чоп кунед.

Барои ҳар адади лозимӣ як луғат нигоҳ доред, дар ин ҷо best ва times, ва бо омадани ҳар натиҷа сабтҳои дастаро нав кунед.

Хулоса барои ҳар калид: беҳтарин хол ва чанд бор

C++

1#include <bits/stdc++.h>

2using namespace std;

4int main() {

5 ios_base::sync_with_stdio(false);

6 cin.tie(NULL);

8 vector<string> team = {

9 "owls", "cats", "owls",

10 "cats", "owls"

11 };

12 vector<int> score = {

13 70, 50, 90, 50, 90

14 };

15 map<string, int> best, times;

16 for (int i = 0; i < 5; i++) {

17 string t = team[i];

18 int s = score[i];

19 // натиҷаи аввал ё рекорди нав

20 if (!best.count(t) ||

21 s > best[t]) {

22 // рекорди нав, як бор дидем

23 best[t] = s;

24 times[t] = 1;

25 } else if (s == best[t]) {

26 // боз беҳтарин хол

27 times[t]++;

28 }

29 }

30 for (auto p : best) {

31 cout << p.first << " "

32 << p.second << " "

33 << times[p.first] << "\n";

34 }

35 return 0;

36}

Дастаҳо

сатр 8

Панҷ натиҷа: даста…

team5 катак

"owls"

"cats"

"owls"

"cats"

"owls"

score5 катак

—

map<string, int> bestЛуғат

холӣ

map<string, int> timesЛуғат

холӣ

i—t—p—

1 / 35

Барои ҳар ҳарф як маҷмуъ

Сабтҳо аз рӯи калид гурӯҳбандӣ мешаванд

Хулоса барои ҳар калид

Машқ: мултимаҷмуъҳо ва калидҳо

Охирин бор онро дар куҷо дидам?

Дарозтарин порчаи бе такрор

Аз рӯи калид танзим шудааст, ба ҳар тараф

Кадом контейнер?

Худатон иҷро кунед

Худро санҷед

Вазифаи хонагӣ

Хулоса