Stratégie
Étape 1
Liste de vérification (B-ALIVE) :
- ⭐️
Bordure: Si vous ne pouvez pas obtenir la solution, vérifiez toujours toutes les limites !!! Tableau: Ne vous trompez pas sur la taille du tableau (multipliez par \(k\), les arêtes bidirectionnelles nécessitent un doublement, etc.)Long: Utilisezlong long(1ll << x),mmulavec1llInitialisation: Pour plusieurs tests, les tableaux doivent être vidés, évitezmemset, même pour un seul test, n'oubliez pas d'initialiserValeur: Portée des structures de données comme les arbres binaires (valeurs pondérées)Dépassement: Attention auxMLE(dépassement de mémoire) etTLE(dépassement de temps)- 'Définition' : Essayez de décomposer les macros
Étape 2
Préparation :
- Thème
- Sauvegarde automatique
- Applaudissements
- Extraits de code
- init
- arête
- mod
- lecture/écriture
- arbre segment
- ensemble disjoint
- dinic
Étape 3 (10 min)
Lisez l'énoncé, les plages de données, et simulez les exemples.
8:40
Étape 4 (3h)
Des problèmes simples aux plus complexes, concevez et implémentez toutes les solutions, ne passez pas plus d'1h sur un problème. Si vous ne trouvez pas de piste, implémentez une solution brute.
Si après 10 minutes il n'y a aucun progrès, ou après 20 minutes aucune solution, passez à autre chose et implémentez une solution brute.
À tuojours garder en tête : notez les approches, propriétés, et équations.
- Inversez (si c'est difficile, considérez les contributions, réfléchissez à la réponse)
- Transformez (en sous-problèmes, transformation du problème)
- Observez les propriétés
- Simplifiez les propriétés
- Faites des conjectures audacieuses
- Construisez des bijections
- Spécifiez des éléments
- Considérez diverses approches brutes
Vérifiez la validité, les détails, et la complexité temporelle des solutions.
Enregistrez le score.
11:40
Étape 5 (1h)
Complétez les éléments manquants.
12:40
Étape 6 (20 min)
Vérifiez la liste de contrôle et les fichiers.
13:00
Fondamentaux
Partage_Linux``` sudo mount -t fuse.vmhgfs-fuse .host:/ /mnt/hgfs -o allow_other
Initialisation du compilateur Sublime Text```
{
"shell_cmd": "g++ -std=c++14 -Wall -O2 \"${file}\" -o \"${file_path}/${file_base_name}\"",
"file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
"working_dir": "${file_path}",
"selector": "source.c++",
"variants":
[
{
"name": "Exécuter",
"shell_cmd": "g++ -std=c++14 -Wall -O2 \"${file}\" -o \"${file_path}/${file_base_name}\" && \"${file_path}/${file_base_name}\""
}
]
}
À retenir par cœurinit
// Auteur: Aquizahv
#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
#define Pour(i, x, y) for (int i = x; i <= y; i++)
#define Rof(i, x, y) for (int i = x; i >= y; i--)
using ll = long long;
using pii = pair<int, int>;
const int N = ;
int main()
{
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
}
fastio
int lire()
{
bool f = 1; int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{ if (ch == '-') f = !f; ch = getchar(); }
while (ch >= '0' && ch <= '9')
{ x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return f ? x : -x;
}
void ecrire(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
ecrire(x / 10);
putchar((x % 10) ^ 48);
}
mod
int A(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
int A(initializer_list<int> t) { int res = 0;
for (auto i : t) res = A(res, i); return res; }
void SA(int &x, int y) { x = A(x, y); }
int S(int x, int y) { return A(x, MOD - y); }
int W(int x, int y) { return 1ll * x * y % MOD; }
int W(initializer_list<int> t) { int res = 1;
for (auto i : t) res = W(res, i); return res; }
void SW(int &x, int y) { x = W(x, y); }
int P(int x, int y) { int res = 1, t = x % MOD;
while (y) { if (y & 1) res = W(res, t);
t = W(t, t); y >>= 1; }
return res; }
int D(int x, int y) { return W(x, P(y, MOD - 2)); }
int Q(int x) { return W(x, x); }
pb_ds
__gnu_pbds::tree<pii, __gnu_pbds::null_type, less<pii>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> s[N];
Clap``` // Auteur: Aquizahv #include <bits/stdc++.h> using namespace std;
int main() { for (int i = 1; i <= 10000; i++) { cout << "Cas #" << i << endl; system("./data"); system("./bf"); system("./mon"); if (system("diff bf.out mon.out")) return 0; } return 0; }
Mathématiques
==
Théorie des nombres
--
Exgcd```
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
CRT (moins bien qu'ExCRT)``` // https://www.luogu.com.cn/problem/P1495#include <bits/stdc++.h> using namespace std; #define int long long const int N = 15; int n, x[N], X = 1, y[N], z[N], ans;
int exgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= (a / b) * x; return d; }
int inv(int a, int b) { int x, y; exgcd(a, b, x, y); return (x % b + b) % b; }
int mmul(int x, int y, int p) { int res = 0, t = x % p; while (y) { if (y & 1) res = (res + t) % p; t = (t + t) % p; y >>= 1; } return res; }
signed main() { #ifdef aquazhao freopen("data.in", "r", stdin); // freopen("data.out", "w", stdout); #endif cin >> n; for (int i = 1; i <= n; i++) { scanf("%lld%lld", x + i, y + i); X *= x[i]; } for (int i = 1; i <= n; i++) { int tmp = X / x[i]; z[i] = tmp * inv(tmp, x[i]); ans = (ans + mmul(y[i] % X, z[i] % X, X)) % X; } cout << ans << endl; return 0; }
ExCRT```
// Auteur: Aquizahv
#include <bits/stdc++.h>
#define ll __int128
#define inf 0x3f3f3f3f
#define lnf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 1e5 + 5;
int n;
ll a[N], b[N];
inline void ecrire(ll x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
ecrire(x / 10);
putchar((x % 10) ^ 48);
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
ll resoudre(ll &x, ll a, ll b, ll c)
{
ll y;
ll d = exgcd(a, b, x, y);
if (c % d)
{
puts("AbsoluTe disoRdeR");
exit(0);
}
x *= c / d;
ll p = b / d;
x = (x % p + p) % p;
return d;
}
ll excrt()
{
for (int i = 2; i <= n; i++)
{
ll x;
ll d = resoudre(x, a[1], a[i], b[i] - b[1]);
b[1] = (x * a[1] + b[1]) % (a[1] * a[i] / d);
a[1] = a[1] * a[i] / d;
}
return b[1];
}
int main()
{
#ifdef Aquizahv
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin >> n;
long long x, y;
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &x, &y), a[i] = x, b[i] = y;
ecrire(excrt());
return 0;
}
Lucas``` int C(int x, int y) {
Algèbre linéaire
----
Élimination de Gauss```
// https://www.luogu.com.cn/problem/P3389
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n;
double a[N][N], ans[N];
const double eps = 1e-7;
int main()
{
#ifdef aquazhao
freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
#endif
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n + 1; j++)
scanf("%lf", &a[i][j]);
for (int i = 1; i <= n; i++)
{
int r = i;
for (int j = i + 1; j <= n; j++)
if (fabs(a[r][i]) < fabs(a[j][i]))
r = j;
if (fabs(a[r][i]) < eps)
{
puts("Pas de solution");
return 0;
}
if (i != r)
swap(a[i], a[r]);
double d = a[i][i];
for (int j = i; j <= n + 1; j++)
a[i][j] /= d;
for (int j = i + 1; j <= n; j++)
{
d = a[j][i];
for (int k = i; k <= n + 1; k++)
a[j][k] -= a[i][k] * d;
}
}
ans[n] = a[n][n + 1];
for (int i = n - 1; i >= 1; i--)
{
ans[i] = a[i][n + 1];
for (int j = i + 1; j <= n; j++)
ans[i] -= a[i][j] * ans[j];
}
for (int i = 1; i <= n; i++)
printf("%.2lf\n", ans[i]);
return 0;
}
Base linéaire``` const int N = 100, w = 30; int n, s, a[N];
void inserer(int x) { for (int k = w; k >= 0; k--) if (x & (1 << k)) { if (a[k] == 0) { a[k] = x; return; } else x ^= a[k]; } }
int qmax() { int res = 0; for (int k = w; k >= 0; k--) res = max(res, res ^ a[k]); return res; }
Théorie des arbres
==
Point de division central```
int sz[N], dp[N];
bool vis[N];
pii getroot(int u, int fa, int Sz)
{
pii res = {inf, 0};
dp[u] = sz[u] = 1;
for (auto v : e[u])
if (v != fa && !vis[v])
{
res = min(res, getroot(v, u, Sz));
sz[u] += sz[v];
dp[u] = max(dp[u], sz[v]);
}
return min(res, {max(dp[u], Sz - sz[u]), u});
}
void cal(int u)
{
//
}
void starch(int u)
{
cal(u);
vis[u] = true;
for (auto v : e[u])
if (!vis[v])
starch(getroot(v, 0, sz[v]).second);
}
Théorie des graphes
Plus courts chemins
Floyd``` for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
Dijkstra```
void Dijkstra(int st)
{
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[st] = 0;
priority_queue<int> q;
q.push(st);
while (!q.empty())
{
int u = q.top();
q.pop();
if (vis[u])
continue;
vis[u] = true;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].v, w = e[i].w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
q.push(v);
}
}
}
}
Bellman Ford``` void BellmanFord(int st) { memset(dis, 0x3f, sizeof(dis)); dis[st] = 0; for (int k = 1; k <= n; k++) for (int i = 1; i <= pos; i++) dis[e[i].v] = min(dis[e[i].v], dis[e[i].u] + e[i].w); }
SPFA```
void SPFA(int s)
{
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
queue<int> q;
q.push(s);
while (q.size())
{
int u = q.front();
q.pop();
vis[u] = false;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].v, w = e[i].w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if (!vis[v])
vis[v] = true, q.push(v);
}
}
}
}
Tarjan
Composantes fortement connexes``` int dfn[N], low[N], dfncnt, stk[N], tp; bool instk[N]; int scccnt, id[N], sz[N]; vector scc[N]; void tarjan(int u) { dfn[u] = low[u] = ++dfncnt; stk[++tp] = u; instk[u] = true; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (instk[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { int v; scccnt++; do { v = stk[tp--]; instk[v] = false; id[v] = scccnt; scc[scccnt].push_back(v); sz[scccnt]++; } while (v != u); } }
Arêtes pont```
int dfncnt, dfn[N], low[N];
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfncnt;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u])
bridge[i] = bridge[i ^ 1] = true;
}
else if (v != fa && dfn[v] < dfn[u])
low[u] = min(low[u], dfn[v]);
}
}
Points d'articulation (arbre carré-cercle)``` int dfncnt, dfn[N], low[N], stk[N], tp; bool instk[N]; int bcccnt, id[N]; int tarjan(int u, int fa) { int res = 1, son = 0; dfn[u] = low[u] = ++dfncnt; stk[++tp] = u; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (!dfn[v]) { son++; res += tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) { bcccnt++; int x; do { x = stk[tp--]; id[x] = bcccnt; addEdge2(n + bcccnt, x); } while (x != v); addEdge2(n + bcccnt, u); } } else if (v != fa) low[u] = min(low[u], dfn[v]); } if (!fa && !son) { bcccnt++; addEdge2(n + bcccnt, u); } return res; }
Structures de données
====
Ensemble disjoint```
struct ensemble_disjoint
{
int f[N];
void init(int lmt)
{
for (int i = 1; i <= lmt; i++)
f[i] = i;
}
int trouver(int u)
{
if (f[u] == u)
return u;
return f[u] = trouver(f[u]);
}
bool fusionner(int u, int v)
{
int x = trouver(u), y = trouver(v);
if (x == y)
return false;
f[x] = y;
return true;
}
} ds;
Arbre segment
Arbre segment (ajout ponctuel, ajout d'intervalle ; maximum d'intervalle)``` #define fils_gauche u + u #define fils_droit u + u + 1 int mx[ND], tag[ND]; void pushup(int u) { mx[u] = max(mx[fils_gauche], mx[fils_droit]); } void ajouter(int u, int x) { mx[u] += x; tag[u] += x; } void pushdown(int u) { if (!tag[u]) return; ajouter(fils_gauche, tag[u]); ajouter(fils_droit, tag[u]); tag[u] = 0; } void mettreAJour(int u, int l, int r, int it, int x) { if (l == r) { mx[u] += x; return; } pushdown(u); int mid = (l + r) >> 1; if (it <= mid) mettreAJour(fils_gauche, l, mid, it, x); else mettreAJour(fils_droit, mid + 1, r, it, x); pushup(u); } void mettreAJour2(int u, int l, int r, int L, int R, int x) { if (L <= l && r <= R) { ajouter(u, x); return; } if (R < l || r < L) return; pushdown(u); int mid = (l + r) >> 1; mettreAJour2(fils_gauche, l, mid, L, R, x); mettreAJour2(fils_droit, mid + 1, r, L, R, x); pushup(u); } int interroger(int u, int l, int r, int L, int R) { if (L <= l && r <= R) return mx[u]; if (R < l || r < L) return -inf; pushdown(u); int mid = (l + r) >> 1; return max(inetrroger(fils_gauche, l, mid, L, R), interroger(fils_droit, mid + 1, r, L, R)); }
Arbre segment à nœuds dynamiques (ajout ponctuel, ajout d'intervalle ; maximum d'intervalle)```
#define fg son[u][0]
#define fd son[u][1]
int tot = 1, son[ND][2], mx[ND], tag[ND];
void pushup(int u)
{
mx[u] = max(mx[fg], mx[fd]);
}
void ajouter(int u, int x)
{
tag[u] += x;
mx[u] += x;
}
void pushdown(int u)
{
if (!fg)
fg = ++tot;
if (!fd)
fd = ++tot;
if (!tag[u])
return;
ajouter(fg, tag[u]);
ajouter(fd, tag[u]);
tag[u] = 0;
}
void mettreAJour1(int u, int l, int r, int it, int x)
{
if (l == r)
{
mx[u] += x;
return;
}
pushdown(u);
int mid = (l + r) >> 1;
if (it <= mid)
mettreAJour1(fg, l, mid, it, x);
else
mettreAJour1(fd, mid + 1, r, it, x);
pushup(u);
}
void mettreAJour2(int u, int l, int r, int L, int R, int x)
{
if (L <= l && r <= R)
{
ajouter(u, x);
return;
}
if (R < l || r < L)
return;
pushdown(u);
int mid = (l + r) >> 1;
mettreAJour2(fg, l, mid, L, R, x);
mettreAJour2(fd, mid + 1, r, L, R, x);
pushup(u);
}
int interroger(int u, int l, int r, int L, int R)
{
if (L <= l && r <= R)
return mx[u];
if (R < l || r < L)
return -inf;
pushdown(u);
int mid = (l + r) >> 1;
return max(interroger(fg, l, mid, L, R), interroger(fd, mid + 1, r, L, R));
}
Arbre d'hôte (ajout ponctuel ; maximum d'intervalle)``` int tot, son[ND][2], mx[ND]; void pushup(int u) { mx[u] = max(mx[son[u][0]], mx[son[u][1]]); } int mettreAJour(int v, int l, int r, int it, int x) { int u = ++tot; mx[u] = mx[v]; son[u][0] = son[v][0], son[u][1] = son[v][1]; if (l == r) { mx[u] += x; return u; } int mid = (l + r) >> 1; if (it <= mid) son[u][0] = mettreAJour(son[u][0], l, mid, it, x); else son[u][1] = mettreAJour(son[u][1], mid + 1, r, it, x); pushup(u); return u; } int interroger(int u, int l, int r, int L, int R) { if (L <= l && r <= R) return mx[u]; if (R < l || r < L) return -inf; int mid = (l + r) >> 1; return max(interroger(son[u][0], l, mid, L, R), interroger(son[u][1], mid + 1, r, L, R)); }
Arbre d'hôte (étiquette paresseuse) (ajout d'intervalle ; maximum d'intervalle)```
int tot, son[ND][2], tag[ND], mx[ND];
void pushup(int u)
{
mx[u] = max(mx[son[u][0]], mx[son[u][1]]);
}
void copier(int u, int v)
{
son[u][0] = son[v][0], son[u][1] = son[v][1];
tag[u] = tag[v], mx[u] = mx[v];
}
void ajouter(int u, int x)
{
mx[u] += x;
tag[u] += x;
}
void pushdown(int u)
{
int fg = ++tot, fd = ++tot;
copier(fg, son[u][0]), copier(fd, son[u][1]);
son[u][0] = fg, son[u][1] = fd;
if (!tag[u])
return;
ajouter(son[u][0], tag[u]);
ajouter(son[u][1], tag[u]);
tag[u] = 0;
}
void mettreAJour(int u, int l, int r, int L, int R, int x)
{
if (L <= l && r <= R)
{
mx[u] += x;
return;
}
if (R < l || r < L)
return;
pushdown(u);
int mid = (l + r) >> 1;
mettreAJour(son[u][0], l, mid, L, R, x);
mettreAJour(son[u][1], mid + 1, r, L, R, x);
pushup(u);
}
int interroger(int u, int l, int r, int L, int R)
{
if (L <= l && r <= R)
return mx[u];
if (R < l || r < L)
return -inf;
pushdown(u);
int mid = (l + r) >> 1;
return max(interroger(son[u][0], l, mid, L, R), interroger(son[u][1], mid + 1, r, L, R));
}
int main()
{
int racine, racine2 = ++tot;
// mise à jour
copier(racine2, racine);
mettreAJour(racine2, 1, n, l, r, x);
int racine3 = ++tot;
// interrogation
cout << interroger(racine3, 1, n, l, r) << endl;
return 0;
}
Arbres équilibrés
Treap sans rotation``` // Supporte l'insertion, la suppression, la séparation, la fusion, la recherche du k-ième élément, la recherche du rang, etc. int son[N][2], val[N], rank[N], sz[N]; int construire(int x) { int u = ++tot; sz[u] = 1, val[u] = x, rank[u] = rand(); return u; } void pushup(int u) { sz[u] = sz[fg] + 1 + sz[fd]; } void separer(int u, int cle, int &x, int &y) // x <= cle, y > cle { if (!u) { x = y = 0; return; } if (val[u] <= cle) x = u, separer(fd, cle, fd, y); else y = u, separer(fg, cle, x, fg); pushup(u); } void separer2(int u, int cle, int &x, int &y) // sz[x] == cle { if (!u) { x = y = 0; return; } if (sz[fg] < cle) x = u, separer(fd, cle - sz[fg] - 1, fd, y); else y = u, separer(fg, cle, x, fg); pushup(u); } int fusionner(int u, int v) { if (!u || !v) return u ^ v; if (rank[u] > rank[v]) { fd = fusionner(fd, v); pushup(u); return u; } else { son[v][0] = fusionner(u, son[v][0]); pushup(v); return v; } } void inserer(int cle) { int x, y; separer(racine, cle, x, y); racine = fusionner(fusionner(x, construire(cle)), y); } void supprimer(int cle) { int x, y, z; separer(racine, cle, x, z); separer(x, cle - 1, x, y); y = fusionner(son[y][0], son[y][1]); racine = fusionner(fusionner(x, y), z); }
Décomposition d'arbres
--
Décomposition en chaînes lourdes```
int pere[N], sz[N], fils[N], profondeur[N], top[N], dfncnt, dfn[N], dfd[N], dfx[N];
void dfs1(int u, int dep)
{
sz[u] = 1;
profondeur[u] = dep;
for (int v : g[u])
if (v != pere[u])
{
pere[v] = u;
dfs1(v, dep + 1);
sz[u] += sz[v];
if (sz[v] > sz[fils[u]])
fils[u] = v;
}
}
void dfs2(int u, int anc)
{
dfn[u] = ++dfncnt;
dfx[dfncnt] = u;
top[u] = anc;
if (fils[u])
{
dfs2(fils[u], anc);
for (int v : g[u])
if (v != pere[u] && v != fils[u])
dfs2(v, v);
}
dfd[u] = dfncnt;
}
struct arbre_segment
{
int sum[ND], tag[ND], len[ND];
void pushup(int u)
{
sum[u] = sum[fg] + sum[fd];
}
void pushdown(int u)
{
if (!tag[u])
return;
ajouter(fg, tag[u]);
ajouter(fd, tag[u]);
tag[u] = 0;
}
void ajouter(int u, int x)
{
sum[u] += len[u] * x;
tag[u] += x;
}
void construire(int u, int l, int r)
{
len[u] = r - l + 1;
if (l == r)
{
sum[u] = a[dfx[l]];
return;
}
int mid = (l + r) >> 1;
construire(fg, l, mid);
construire(fd, mid + 1, r);
pushup(u);
}
void mettreAJour(int u, int l, int r, int L, int R, int x)
{
if (L <= l && r <= R)
{
ajouter(u, x);
return;
}
if (R < l || r < L)
return;
pushdown(u);
int mid = (l + r) >> 1;
mettreAJour(fg, l, mid, L, R, x);
mettreAJour(fd, mid + 1, r, L, R, x);
pushup(u);
}
int interroger(int u, int l, int r, int L, int R)
{
if (L <= l && r <= R)
return sum[u];
if (R < l || r < L)
return 0;
pushdown(u);
int mid = (l + r) >> 1;
return interroger(fg, l, mid, L, R) + interroger(fd, mid + 1, r, L, R);
}
} t;
void chemin_ajout(int u, int v, int x)
{
while (top[u] != top[v])
{
if (profondeur[top[u]] < profondeur[top[v]])
swap(u, v);
t.mettreAJour(1, 1, n, dfn[top[u]], dfn[u], x);
u = pere[top[u]];
}
if (profondeur[u] < profondeur[v])
swap(u, v);
t.mettreAJour(1, 1, n, dfn[v], dfn[u], x);
}
int chemin_somme(int u, int v)
{
int res = 0;
while (top[u] != top[v])
{
if (profondeur[top[u]] < profondeur[top[v]])
swap(u, v);
res += t.interroger(1, 1, n, dfn[top[u]], dfn[u]);
u = pere[top[u]];
}
if (profondeur[u] < profondeur[v])
swap(u, v);
return res + t.interroger(1, 1, n, dfn[v], dfn[u]);
}
Chaînes de caractères
KMP``` const int N = 1e6 + 5; int n, m; int nxt[N]; // longueur de la bordure du préfixe du t char s[N], t[N];
int main() { scanf("%s%s", s + 1, t + 1); n = strlen(s + 1); m = strlen(t + 1); for (int i = 2; i <= m; i++) { int j = nxt[i - 1]; while (j > 0 && t[i] != t[j + 1]) j = nxt[j]; if (t[i] == t[j + 1]) nxt[i] = j + 1; } for (int i = 1, j = 0; i <= n; i++) { while (j > 0 && s[i] != t[j + 1]) j = nxt[j]; if (s[i] == t[j + 1]) j++; if (j == m) printf("%d\n", i - m + 1); } for (int i = 1; i <= m; i++) printf("%d%c", nxt[i], " \n"[i == m]); return 0; }
Automate AC```
// Auteur: Aquizahv
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5, S = 2e6 + 5;
int n, ans[N];
char s[S], t[N];
struct AC_auto
{
int racine = 1, tot = racine, trie[N][30], echec[N], tag[N];
vector<int> id[N], g[N];
void inserer(int cnt)
{
int pos = strlen(t + 1), u = racine;
for (int i = 1; i <= pos; i++)
{
int d = t[i] - 'a';
if (!trie[u][d])
trie[u][d] = ++tot;
u = trie[u][d];
}
id[u].push_back(cnt);
}
void init_echec()
{
queue<int> q;
q.push(racine);
echec[racine] = racine;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
if (!trie[u][i])
trie[u][i] = u == racine ? 1 : trie[echec[u]][i];
else
{
echec[trie[u][i]] = u == racine ? racine : trie[echec[u]][i];
g[echec[trie[u][i]]].push_back(trie[u][i]);
q.push(trie[u][i]);
}
}
}
}
void Paire()
{
int pos = strlen(s + 1);
int u = racine;
for (int i = 1; i <= pos; i++)
{
u = trie[u][s[i] - 'a'];
tag[u]++;
}
}
int dfs(int u)
{
int res = tag[u];
for (int v : g[u])
res += dfs(v);
for (int i : id[u])
ans[i] = res;
return res;
}
void debug(int u)
{
for (int i = 0; i < 26; i++)
if (trie[u][i])
{
cout << u << ' ' << char('a' + i) << ' ' << trie[u][i] << endl;
debug(trie[u][i]);
}
}
} ac;
SA``` struct SA { int n, s[N], sa[N], rk[N], sa2[N], _rk[N], cnt[N], h[N]; void construire(int m) { for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++; for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i; for (int w = 1, p = 0; p != n; m = p, w <<= 1) { int pos = 0; for (int i = n - w + 1; i <= n; i++) sa2[++pos] = i; for (int i = 1; i <= n; i++) if (sa[i] > w) sa2[++pos] = sa[i] - w; memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= n; i++) cnt[rk[i]]++; for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; for (int i = n; i >= 1; i--) sa[cnt[rk[sa2[i]]]--] = sa2[i]; memcpy(_rk, rk, sizeof(rk)); p = 0; for (int i = 1; i <= n; i++) { if (_rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + w] == _rk[sa[i - 1] + w]) rk[sa[i]] = p; else rk[sa[i]] = ++p; } } for (int i = 1, k = 0; i <= n; i++) { if (rk[i] == 1) continue; k = max(k - 1, 0); while (s[i + k] == s[sa[rk[i] - 1] + k]) k++; h[rk[i]] = k; } } };
Divers
==
SA```
struct noeud
{
//
noeud operator*(const double T) const
{
//
}
} res;
noeud calculer(noeud cur, double T)
{
noeud nouv;
//
if (nouv.w < res.w)
res = nouv;
}
double Alea() { return (double)rand() / RAND_MAX; }
void SA()
{
double T = 100000;
noeud cur = res, nouv;
while (T > 0.001)
{
nouv = calculer(cur, T);
double delta = nouv.w - cur.w;
if (exp(-delta / T) > Alea())
cur = nouv;
T *= 0.99;
}
for (int i = 1; i <= 1000; i++)
calculer(cur, T);
}
const double TL = 1;
int main()
{
#ifdef Aquizahv
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
srand(time(0));
while ((double)clock() / CLOCKS_PER_SEC < TL)
SA();
}
Grande précision``` int t[LEN]; const int k = 10; struct grand_nombre { int len, a[LEN], op; grand_nombre() { len = 0, memset(a, 0, sizeof(a)), op = 1; } void init(int x) { if (x < 0) op = -1, x = -x; while (x) { a[++len] = x % k; x /= k; } } void lire() { char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') op *= -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { t[++len] = ch ^ 48; ch = getchar(); } for (int i = 1; i <= len; i++) a[i] = t[len - i + 1]; if (len == 1 && a[1] == 0) len = 0; } void ecrire() { if (op == -1) putchar('-'); if (len == 0) putchar('0'); for (int i = len; i >= 1; i--) putchar(a[i] ^ 48); } bool operator<(const grand_nombre t) const { if (op * t.op == -1) return op < t.op; int res = 0; if (op == -1) res = 1; if (len != t.len) return res ^ (len < t.len); for (int i = len; i >= 1; i--) if (a[i] != t.a[i]) return res ^ (a[i] < t.a[i]); return false; } grand_nombre operator+(grand_nombre t) const { if (op * t.op == -1) { t.op *= -1; return *this - t; } grand_nombre nouv; nouv.op = op; nouv.len = max(len, t.len); int o = 0; for (int i = 1; i <= nouv.len; i++) { nouv.a[i] = a[i] + t.a[i] + o; o = nouv.a[i] / k; nouv.a[i] %= k; } while (o) { nouv.a[++nouv.len] = o % k; o /= k; } return nouv; } grand_nombre operator-(grand_nombre t) const { if (op * t.op == -1) { t.op *= -1; return *this + t; } grand_nombre nouv; if ((op == 1 && *this < t) || (op == -1 && t < *this)) { nouv = t - *this; nouv.op = -1; return nouv; } nouv.op = op; nouv.len = len; for (int i = 1; i <= len; i++) nouv.a[i] = a[i] - t.a[i]; for (int i = 1; i <= nouv.len; i++) if (nouv.a[i] < 0) nouv.a[i] += k, nouv.a[i + 1]--; while (nouv.len > 0 && nouv.a[nouv.len] == 0) nouv.len--; if (nouv.len == 0) nouv.op = 1; return nouv; } grand_nombre operator(int t) const { grand_nombre nouv; if (t == 0) { nouv.len = 0; return nouv; } nouv.op = op * t / abs(t); t = abs(t); nouv.len = len; for (int i = 1; i <= len; i++) nouv.a[i] = a[i] * t; int o = 0; for (int i = 1; i <= nouv.len; i++) { nouv.a[i] += o; o = nouv.a[i] / k; nouv.a[i] %= k; } while (o) { nouv.a[++nouv.len] = o % k; o /= k; } if (nouv.len == 0) nouv.op = 1; return nouv; } grand_nombre operator/(int t) const { grand_nombre nouv; nouv.op = op * t / abs(t); t = abs(t); nouv.len = len; int o = 0; for (int i = len; i >= 1; i--) { o = o * k + a[i]; nouv.a[i] = o / t; o %= t; } while (nouv.len > 0 && nouv.a[nouv.len] == 0) nouv.len--; return nouv; } };