Обсуждение:cpp/string/basic string view
Сортировка слиянием (Сложность: O(NlogN)) void merge_sort(vector<int>& v, int begin, int end) {
// Для отрезков длиной 1 не выполняем никаких операций.
// Это так называемый "базовый" (крайний) случай рекурсии, который
// гарантирует, что алгоритм закончит своё выполнение.
if (begin == end) {
return;
}
int mid = (begin + end) / 2;
// Рекурсивные вызовы алгоритма.
merge_sort(v, begin, mid);
merge_sort(v, mid + 1, end);
// Собственно слияние.
vector<int> t;
for (int i = begin, j = mid + 1; i <= mid || j <= end;) {
// Если одна из частей закончилась, добавляем элемент из другой
if (i > mid) {
t.push_back(v[j++]);
} else if (j > end) {
t.push_back(v[i++]);
// Иначе добавляем меньший из текущих элементов
} else if (v[i] <= v[j]) {
t.push_back(v[i++]);
} else {
t.push_back(v[j++]);
}
}
// Копируем отсортированный отрезок из временного массива в v.
for (int i = 0; i < t.size(); i++) {
v[begin + i] = t[i];
}
} Стандартные алгоритмы сортировки // std::sort в С++ принимает два random-access итератора. void sort(iterator first, iterator last); Для сортировки контейнеров, предоставляющих итераторы random-access (std::vector, std::deque, и т.д.) чаще всего используются методы begin и end:
sort(v.begin(), v.end()); // весь вектор sort(v.begin() + i, v.begin() + j); // отрезок v[i; j) Важно помнить, что как и все алгоритмы стандартной библиотеки, std::sort принимает, что итераторы обозначают начало включительно, а конец - не включительно.
Для сортировки “старых” массивов используется автоматическое преобразование указателя в итератор:
int a[N]; sort(a, a + N); Сортировка сложных типов. Собственные компараторы
- include <bits/stdc++.h>
using namespace std;
struct team {
string name; int tasks; // количество решённых задач int penalty; // штраф
}; // cmp(A, B) == true тогда и только тогда, когда команда // A в таблице результатов должна оказаться выше команды B. bool cmp(team a, team b) {
return a.tasks > b.tasks
|| (a.tasks == b.tasks && a.penalty < b.penalty);
} int main() {
vector<team> teams {
{"Team BSEU", 9, 300},
{"Team BSU", 10, 350},
{"Team BSUIR", 9, 200}
};
sort(teams.begin(), teams.end(), cmp);
for (team t: teams) {
cout << t.name << endl;
}
}
//Считаем, что входные данные уже введены. long long nb, ns, nc; long long pb, ps, pc; long long r;
//Количество необходимых кусков хлеба, колбасы и сыра для одного гамбургера. //Рассчитывается из строки рецепта. long long tb, ts, tc;
//Возможно ли приготовить h гамбургеров. bool possible(long long h) {
long long cost_b = max(0ll, (tb * h - nb) * pb); long long cost_s = max(0ll, (ts * h - ns) * ps); long long cost_c = max(0ll, (tc * h - nc) * pc);
return cost_b + cost_s + cost_c <= r;
}
//Можно заметить, что это не стандартный бинарный поиск //по элементу, а поиск первого "невозможного" количества //гамбургеров (аналог std::upper_bound). //В реализации таких функций часто допускаются ошибки //в строках подобных 32 и 34, но они быстро выявляются и //исправляются тестированием на сэмплах. long long max_possible() {
long long l = 0, r = 1e14;
while (l < r) {
long long m = (l + r) / 2;
if (possible(m)) {
l = m + 1;
} else {
r = m;
}
}
return l - 1; //l == r == первое "невозможное" количество
} iterator lower_bound(iterator begin, iterator end, int value, comparator comp); iterator upper_bound(iterator begin, iterator end, int value, comparator comp); set<int> s; // ... set<int>::iterator it = s.lower_bound(k);
map<int, string> m; // ...
// бинарный поиск для std::map ведётся по ключам map<int, string>::iterator it = m.lower_bound(k); int binsearch_array(vector<int>& a, int val) {
int l = 0, r = a.size() - 1;
while (r > l) {
int m = (l + r) / 2; //целочисленное деление!
if (a[m] < val) {
l = m + 1;
} else if (a[m] > val) {
r = m - 1;
} else {
return m;
}
}
//l == r == искомый индекс
//Если искомого элемента не было в массиве,
//бинарный поиск найдёт следующий после него элемент.
//Чтобы распознать этот случай, мы используем дополнительное сравнение.
if (a[l] == val) {
return l;
} else {
return -1;
}
}
- include <bits/stdc++.h>
using namespace std;
vector<int> z_function(const string& s) {
vector<int> z(s.length(), 0);
for (int i = 1, l = 0, r = 0; i < s.length(); i++) {
if (i <= r) {
z[i] = min(z[i - l], r - i + 1);
}
while (i + z[i] < s.length()) {
if (s[i + z[i]] == s[z[i]]) {
z[i]++;
} else {
break;
}
}
if (z[i] > 0 && i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
int main() {
string s, t; cin >> s >> t;
vector<int> z = z_function(t + '#' + s);
int t_len = t.length();
for (int i = 0; i < s.length(); i++) {
if (z[t_len + 1 + i] == t_len) {
cout << "s[" << i << ".." << i + t_len - 1 << "] = t" << endl;
}
}
} vector<int> graph[100000]; char color[100000]; //Цвет будем представлять типом char
//0 - вершина ещё не покрашена; 1, 2 - различные цвета.
inline char invert(int c) {
return c == 1 ? 2 : 1;
}
void dfs(int v, char c) { //c - цвет текущей вершины
color[v] = c;
for (int u: graph[v]) {
if (color[u] == 0) { //непосещённая вершина
dfs(u, invert(c));
} else if (color[u] == c) {
cout << "Graph is not bipartite." << endl;
exit(0);
}
}
} Алгоритм Флойда-Уоршелла for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][k] < INF && dp[k][j] < INF) { //явная проверка
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
} алгоритм Крускала
- include <bits/stdc++.h>
using namespace std;
int p[100000]; int rk[100000];
void init_dsu() {
for (int i = 0; i < 100000; i++) {
p[i] = i;
rk[i] = 1;
}
}
int get_root(int v) {
if (p[v] == v) {
return v;
} else {
return p[v] = get_root(p[v]); //На выходе из рекурсии переподвешиваем v
}
}
bool merge(int a, int b) {
int ra = get_root(a), rb = get_root(b);
if (ra == rb) {
return false;
} else {
if (rk[ra] < rk[rb]) {
p[ra] = rb;
} else if (rk[rb] < rk[ra]) {
p[rb] = ra;
} else {
p[ra] = rb;
rk[rb]++;
}
return true; }
}
//Тип для представления рёбер. struct edge {
int a, b, len;
bool operator<(const edge& other) {
return len < other.len;
}
};
int main() {
vector<edge> edges; //Ввод edges...
sort(edges.begin(), edges.end());
int mst_weight = 0;
init_dsu();
for (edge e: edges) {
if (merge(e.a, e.b)) { //Если a и b находятся в разных компонентах,
mst_weight += e.len; //Добавить ребро в минимальный остов.
}
}
cout << "Minimum spanning tree weight: " << mst_weight << endl;
} dsu int p[100000]; int rk[100000];
void init_dsu() {
for (int i = 0; i < 100000; i++) {
p[i] = i;
rk[i] = 1;
}
}
int get_root(int v) {
if (p[v] == v) {
return v;
} else {
return p[v] = get_root(p[v]); //На выходе из рекурсии переподвешиваем v
}
}
bool merge(int a, int b) {
int ra = get_root(a), rb = get_root(b);
if (ra == rb) {
return false;
} else {
if (rk[ra] < rk[rb]) {
p[ra] = rb;
} else if (rk[rb] < rk[ra]) {
p[rb] = ra;
} else {
p[ra] = rb;
rk[rb]++;
}
return true; }
} Очередь с приоритетом std::priority_queue<T> bool empty(); unsigned int size(); T top(); //"Верхний" элемент. По умолчанию - максимум. void push(T x); //Добавить элемент в очередь. void pop(); //Извлечь элемент.
struct heap {
vector<int> tree;
heap() {
tree.push_back(0); //Мы собираемся работать в 1-индексации, поэтому
//просто поместим в tree[0] произвольное значение.
}
void push(int x) {
tree.push_back(x);
sift_up(tree.size() - 1);
}
int max() {
if (tree.size() > 1) {
return tree[1];
} else {
//Ошибка: попытка найти максимум в пустой куче
}
}
void pop() {
if (tree.size() > 1) {
tree[1] = tree.back();
tree.pop_back();
sift_down(1);
} else {
//Ошибка: попытка извлечь максимум из пустой кучи
}
}
//Проталкивание вверх.
void sift_up(int v) {
if (v == 1) {
return; //Больше некуда подниматься.
}
if (tree[v / 2] < tree[v]) {
swap(tree[v], tree[v / 2]);
sift_up(v / 2);
}
}
//Проталкивание вниз
void sift_down(int v) {
if (v * 2 >= tree.size()) {
return; //Больше некуда спускаться.
}
//Индекс большего дочернего элемента
int max_idx;
if (v * 2 + 1 == tree.size()) { //Если можно спуститься только влево
max_idx = v * 2;
} else if (tree[v * 2] >= tree[v * 2 + 1]) {
max_idx = v * 2;
} else {
max_idx = v * 2 + 1;
}
if (tree[v] < tree[max_idx]) {
swap(tree[v], tree[max_idx]);
sift_down(max_idx);
}
}
bool empty() {
return tree.size() == 1;
}
}; ДП на дереве
- include <bits/stdc++.h>
using namespace std;
vector<int> tree[100000]; int c[100000]; //массив со значениями вершин
int dp[100000]; int ans[100000];
void dfs(int v, int p = -1) {
for (int u: tree[v]) { //сначала считаем ДП для всех дочерних вершин
if (u != p) {
dfs(u, v);
}
}
//Считаем dp[v]
dp[v] = c[v];
for (int u: tree[v]) {
if (u != p) {
dp[v] = max(dp[v], dp[u] + c[v]);
}
}
//Считаем ans[v]: вариант 1 ans[v] = dp[v];
//Считаем ans[v]: вариант 2
for (int u: tree[v]) {
if (u != p) {
ans[v] = max(ans[v], ans[u]);
}
}
//Считаем ans[v]: вариант 3
//если есть как минимум две дочерних вершины (не считая родительскую)
if (tree[v].size() >= 3 || (p == -1 && tree[v].size() >= 2)) {
int f_max = INT_MIN, s_max = INT_MIN; //первый и второй максимумы
for (int u: tree[v]) {
if (u != p) {
if (dp[u] >= f_max) {
s_max = f_max;
f_max = dp[u];
} else if (dp[u] > s_max) {
s_max = dp[u];
}
}
}
ans[v] = max(ans[v], f_max + s_max + c[v]); }
}
int main() {
//Ввод дерева и массива c...
dfs(0);
cout << ans[0];
}
- include <bits/stdc++.h>
using namespace std;
int a[100000]; int dp[100000];
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
dp[i] = 1; //Мы можем начать новую подпоследовательность
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1); //Или продолжить уже начатую.
}
}
}
int ans = *max_element(dp, dp + n); //C++11 cout << ans;
}
- include <bits/stdc++.h>
using namespace std;
int c[1000][1000]; int dp[1000][1000];
int main() {
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> c[i][j];
}
}
dp[0][0] = c[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i || j) { //цикл не должен заходить в клетку (0, 0)
dp[i][j] = INT_MIN; //код рассчёта максимума получился
//достаточно длинным из-за дополнительных
//проверок на выход за границы матрицы
if (i - 1 >= 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j] + c[i][j]);
}
if (j - 1 >= 0) {
dp[i][j] = max(dp[i][j], dp[i][j - 1] + c[i][j]);
}
}
}
}
cout << dp[n - 1][m - 1];
} using namespace std;
vector<int> graph[100000]; bool used[100000]; int dst[100000]; int pr[100000]; //имя prev уже используется библиотекой, поэтому назовём массив pr
int main() {
//Ввод графа...
for (int i = 0; i < 100000; i++) {
dst[i] = -1;
}
queue<int> q; q.push(0); used[0] = true; dst[0] = 0; pr[0] = -1; //Пометка, означающая, что у вершины 0 нет предыдущей.
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int neighbor: graph[cur]) {
if (!used[neighbor]) {
q.push(neighbor);
used[neighbor] = true;
dst[neighbor] = dst[cur] + 1;
pr[neighbor] = cur; //сохранение предыдущей вершины
}
}
}
//Восстановим кратчайший путь до вершины k (которую, предполагается, мы уже ввели) //Для восстановления пути пройдём его в обратном порядке, начиная с j, и развернём.
vector<int> path;
int cur = k; //текущая вершина пути path.push_back(cur);
while (pr[cur] != -1) { //пока существует предыдущая вершина
cur = pr[cur]; //переходим в неё
path.push_back(cur); //и дописываем к пути
}
reverse(path.begin(), path.end());
cout << "Shortest path between vertices 1 and " << k + 1 << " is: " << endl;
for (int v: path) {
cout << v + 1 << ", ";
}
} Реализация с восстановлением пути
- include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
vector<pair<int, int>> graph[100000]; int ans[100000]; int pr[100000]; //prev
int main() {
//Ввод графа и вершин start и end.
for (int i = 0; i < n; i++) {
ans[i] = INF;
pr[i] = -1; //Значение, обозначающее что из этой вершины возвращаться некуда
}
ans[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, start});
while (!q.empty()) {
pair<int, int> c = q.top();
q.pop();
int dst = c.first, v = c.second;
if (ans[v] < dst) {
continue;
}
for (pair<int, int> e: graph[v]) {
int u = e.first, len_vu = e.second;
int n_dst = dst + len_vu;
if (n_dst < ans[u]) {
ans[u] = n_dst;
pr[u] = v;
q.push({n_dst, u});
}
}
}
vector<int> path;
int cur = end; path.push_back(cur);
while (pr[cur] != -1) {
cur = pr[cur];
path.push_back(cur);
}
reverse(path.begin(), path.end());
cout << "Shortest path between vertices " << start + 1 << " and " << end + 1 << " is: " << endl;
for (int v: path) {
cout << v + 1 << ", ";
}
}