Қиматро ҳамчун индекс бо cnt[x]++ истифода баред, то ки қимати аз ҳама зиёд, адади намерасида ва ҷуфтҳои қиматҳои баробарро ёбед.
Масъалаҳо оид ба шумориши қиматҳо: ададҳои намерасида, қиматҳое, ки як маротиба меоянд, қимати аз ҳама зиёд ва ҷуфтҳои баробар.
cnt[x]++;vector<int> c(101) аст. Он чанд катак дорад ва индекси охирини он чанд аст?2 1 0: катаки 2 ду бор зиёд шуд, катаки 0 як бор, катаки 1 ҳеҷ гоҳ. 2. 101 катак. Индекси охирин 100 аст.Муаллима 30 баҳои санҷишӣ дорад, ҳар кадом аз 1 то 5. Вай мехоҳад бидонад, ки чанд хонанда ҳар як баҳоро гирифтааст. Бо василаҳое, ки шумо медонед, ба чанд тағйирёбанда эҳтиёҷ мешуд? Чанд сатри if?
Баҳо адади хурд аст ва адади хурд метавонад индекс шавад. Барои ҳар қимати имконпазир як ҳисобкунак дар вектор созед: cnt[v] нишон медиҳад, ки қимати v чанд бор дида шудааст. Вақте қимати x-ро мехонед, намепурсед, ки он кадом аст. Шумо рост ба катаки он меравед: cnt[x]++.
Даҳ хонанда барои ҷои сафари мактабӣ овоз медиҳанд. Ҳар овоз адад аз 1 то 5 аст. Чоп кунед, ки ҳар ҷой чанд овоз гирифт.
Вуруд
Баромад
Вектор 6 катак дорад, чунки индекси калонтарин 5 аст. Катаки 0 ҳеҷ гоҳ истифода намешавад. Барои ҳар қимат if нест: худи қимат қуттии худро меёбад.
Шаш овозро қадам ба қадам гузаред:
n - 1 чиптаи гуногун аз 1 то n баргардонида шуд. Кадом чипта намондааст? Ҳар чиптаеро, ки дидед, нишон кунед. Дар ҳар катаки vector<bool> true ё false меистад:
Бо n = 6 ва чиптаҳои 4 1 6 2 3 барнома 5-ро чоп мекунад. Нишон кардани як чипта як қадам аст ва пурсидани «оё дида шуд?» низ як қадам аст. Ҷустуҷӯ лозим нест.
Баъд аз шумориш аз болои қиматҳо гузашта, ҳисобкунакҳоро нигаред. Санҷиш > аст, на >=, бинобар ин ҳангоми баробарӣ қимати хурдтар мемонад:
Барои ададҳои 2 4 2 5 4 2 4 қиматҳои 2 ва 4 ҳар кадом 3 бор меоянд. Барнома best = 2 ва different = 3-ро меёбад.
Индекс манфӣ шуда наметавонад. Агар қиматҳо аз -1000 то 1000 бошанд, онҳоро лағжонед: cnt[x + 1000]-ро истифода баред ва векторро 2001 катак дароз кунед. Қимати -3 дар катаки 997 ва қимати 0 дар катаки 1000 мебошад.
Вақте қиматро баръакс чоп мекунед, 1000-ро боз кам кунед.
Чанд ҷуфти (i, j) бо i < j ададҳои баробар доранд? Вақте x-и нав вомехӯрад, бо ҳар x-и пештара ҷуфт мешавад. Чунин ҷуфтҳо cnt[x] мебошанд. Аввал онҳоро илова кунед ва танҳо баъд адади навро шумор кунед:
Барои 1 2 1 1 2 барнома 4-ро чоп мекунад. 1-и дуюм бо як 1-и пештара, 1-и сеюм бо ду 1-и пештара ва 2-и дуюм бо як 2-и пештара ҷуфт мешавад. Бо 10⁵ адади баробар ҷавоб тақрибан 5 · 10⁹ мешавад, бинобар ин pairs навъи long long аст. Агар ду сатрро ҷой иваз кунед, ҳар адад бо худаш низ ҷуфт мешавад.
Вектор барои ҳар қимати имконпазир як катак лозим дорад. Агар шарти масъала 1 ≤ a_i ≤ 10⁹ гӯяд, вектори 10⁹ + 1 ҷузъи int 4 ГБ мешавад, ки аз маҳдудияти ҳофизаи масъала хеле зиёд аст. Қиматҳо то тақрибан 10⁶ мувофиқанд. Барои қиматҳои калон ё барои калимаҳо, дарси баъдӣ map-ро нишон медиҳад.
cnt[x]++.seen[x] = true нишон кунед. Қимати бештар вомехӯрда: сикл бо >. Қиматҳои гуногун: катакҳои бо cnt[v] > 0-ро бишуморед.cnt[x + 1000].cnt[x]-ро пеш аз шумориши x илова кунед, дар long long.10
3 5 1 3 3 2 5 3 1 4
1: 2
2: 1
3: 4
4: 1
5: 2
Шумориш роҳи танзим кардан низ ҳаст. Ҳар қиматро бишуморед, баъд ҳар қиматро cnt[v] бор аз хурдтарин v то калонтарин нависед. Ин танзими шуморишӣ ном дорад ва Ҳаролд Сьюард онро соли 1954 тавсиф кардааст. Он бидуни муқоисаи ду адад танзим мекунад.
cnt[x]++ мешуморам.Нависед: чаро ин усулро ҳангоме, ки қиматҳо то 10⁹ мерасанд, истифода бурдан мумкин нест?
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> cnt(6, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
for (int v = 1; v <= 5; v++) {
cout << v << ": "
<< cnt[v] << "\n";
}
return 0;
}
Қиматҳо аз -1000 то 1000 мераванд ва дар cnt[x + 1000] шумурда мешаванд. Ҳисобкунаки қимати -3 дар кадом катак аст?
Ин барнома чӣ чоп мекунад?
Дар сикле, ки қимати бештар вомехӯрдаро меҷӯяд, cnt[v] > cnt[best]-ро ба cnt[v] >= cnt[best] иваз мекунед. Вақте ду қимат баробар зиёд меоянд, барнома акнун бо калонтари онҳо ҷавоб медиҳад.
Дар 5 1 5 1 1 5 2 чанд ҷуфти мавқеъҳои i < j ададҳои баробар доранд?
Дар шарт 1 <= a_i <= 10^9 навишта шудааст. Чаро vector<int> cnt(1000000001) нақшаи бад барои шумориши қиматҳост?
Чор сатри тани сиклро ба тартиби дуруст гузоред, то барнома ҷуфтҳои ададҳои баробарро бишуморад.
vector<bool> seen(n + 1, false);
for (int i = 0; i < n - 1; i++) {
int t;
cin >> t;
seen[t] = true;
}
for (int t = 1; t <= n; t++) {
if (!seen[t]) {
cout << t << "\n";
}
}
int best = 1;
for (int v = 1; v <= 5; v++) {
if (cnt[v] > cnt[best]) {
best = v;
}
}
int different = 0;
for (int v = 1; v <= 5; v++) {
if (cnt[v] > 0) {
different++;
}
}
vector<int> cnt(2001, 0);
cnt[x + 1000]++;
long long pairs = 0;
for (int x : a) {
pairs += cnt[x];
cnt[x]++;
}
vector<int> a(4, 0);
a[2]++;
a[2]++;
a[0]++;
cout << a[2] << " "
<< a[0] << " "
<< a[1];
vector<int> a =
{2, 4, 2, 0, 4, 4};
vector<int> cnt(5, 0);
for (int x : a) {
cnt[x]++;
}
cout << cnt[cnt[4]];
for (int i = 0; i < n; i++) {
// the four lines go here
}