Problème A : Maximiser la somme d'une séquence modifiable
Étant donné une séquence d'entiers (positifs, négatifs ou nuls), on peut effectuer une opération un nombre illimité de fois : multiplier deux éléments adjacents par -1. L'objectif est de maximiser la somme de tous les éléments.
L'approche consiste à analyser la parité du nombre d'éléments négatifs dans la séquence d'origine. S'il y en a un nombre impair, il est possible de rendre tous les éléments positifs. Sinon, un élément restera négatif ; on choisit alors celui ayant la plus petite valeur absolue pour limiter la perte.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
int values[MAXN];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int negativeCount = 0;
for (int i = 0; i < n; ++i) {
cin >> values[i];
if (values[i] < 0) {
negativeCount++;
}
values[i] = abs(values[i]);
}
sort(values, values + n);
ll totalSum = (negativeCount % 2 == 0) ? values[0] : -values[0];
for (int i = 1; i < n; ++i) {
totalSum += values[i];
}
cout << totalSum << endl;
return 0;
}
Problème B : Recherche binaire d'une hauteur de coupe
Il s'agit d'un problème classique de recherche binaire sur la réponse. On cherche la plus grande hauteur de coupe H telle que la quantité totale de bois récoltée (la somme des excès au-dessus de H) soit supérieure ou égale à une cible M.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
int treeHeights[MAXN];
int main() {
int n;
ll requiredWood;
cin >> n >> requiredWood;
int maxHeight = 0;
for (int i = 0; i < n; ++i) {
cin >> treeHeights[i];
maxHeight = max(maxHeight, treeHeights[i]);
}
int low = 0, high = maxHeight;
int bestH = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
ll obtainedWood = 0;
for (int i = 0; i < n; ++i) {
if (treeHeights[i] > mid) {
obtainedWood += treeHeights[i] - mid;
}
}
if (obtainedWood >= requiredWood) {
bestH = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << bestH << endl;
return 0;
}
Problème C : Comptage par hachage pour correspondance floue
Le but est de compter les paires de chaînes qui sont identiques après la suppression d'un seul caractère au même index. Une approche naïve en O(n²L) est trop lente. L'optimisation utilise un hachage polynomial. Pour chaque position possible de suppression (de 0 à L-1), on calcule une signature de hachage pour chaque chaîne (la chaîne complète moins ce caractère). Deux chaînes sont comptées comme correspondantes si elles partagent la même signature pour le même index de suppression.
Le calcul initial du hachage pour chaque suppression prend O(L). On l'optimise à O(1) en pré-calculant d'abord le hachage de la chaîne entière et en le modifiant pour exclure le caractère courant.
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int BASE = 131;
const int MAXN = 3e4 + 10;
const int MAXL = 210;
ull power[MAXL];
map<ull, int> hashBuckets[MAXL];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, len;
cin >> n >> len;
// Pré-calcul des puissances de BASE
power[0] = 1;
for (int i = 1; i <= len; ++i) {
power[i] = power[i-1] * BASE;
}
ll totalPairs = 0;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
// Calcul du hachage de la chaîne complète
ull fullHash = 0;
for (char c : s) {
fullHash = fullHash * BASE + (c - 'a' + 1);
}
// Pour chaque index de suppression, calculer le hachage résultant
for (int j = 0; j < len; ++j) {
ull hashWithoutJ = fullHash - (s[j] - 'a' + 1) * power[len - j - 1];
totalPairs += hashBuckets[j][hashWithoutJ];
hashBuckets[j][hashWithoutJ]++;
}
}
cout << totalPairs << endl;
return 0;
}
La complexité est O(LN log N) dans le pire cas avec l'utilisation de map, mais l'algorithme standard utilise des approches comme le tri pour une complexité en O(LN) ou en O(LN log N) optimisé, pouvant obtenir des scores élevés sur les juges en ligne.
Problème D : Requêtes de maximum modulo (Problème de la fleur)
Étant donné une séquence de N entiers, traiter M requêtes de la forme (l, r, k). Pour chaque requête, trouver le maximum de a_i modulo k pour tous les indices i dans l'intervalle [l, r].
Une solution naïve pour chaque requête en O(r-l+1) est trop lente. L'approche optimale utilise la technique de la décomposition en blocs (square root decomposition). On pré-traite les données par blocs.
L'idée clé : pour un modulo k fixé, la valeur maximale dans un intervalle [x, x+k-1] de la valeur réelle est le candidat optimal pour le reste modulo k. On pré-calcule, pour chaque bloc, pour chaque modulo possible k (1 ≤ k ≤ MAX_VAL), la valeur maximale de (a_i modulo k) dans ce bloc. Cela se fait en trouvant d'abord le maximum absolu dans chaque intervalle [t*k, (t+1)*k - 1] sur les valeurs du bloc, puis en soustrayant t*k.
Pour une requête (l, r, k) :
1. On traite les parties partielles au début et à la fin de l'intervalle en parcourant les éléments individuellement.
2. Pour les blocs entiers inclus dans [l, r], on utilise la valeur pré-calculée pour le modulo k.
On prend le maximum de tous ces résultats.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_VAL = 1e5;
const int MAXN = 1e5 + 5;
const int BLOCK_SIZE = 317; // Environ sqrt(MAX_VAL * log(MAX_VAL))
int n, m;
int arrayData[MAXN];
int blockIndex[MAXN];
struct Block {
int start, end;
int maxValueForMod[MAX_VAL + 1]; // maxValueForMod[k] stocke le max de (a[i] % k) dans le bloc pour ce k
};
vector<Block> blocks;
// Pré-traitement des blocs
void preprocessBlocks() {
int numBlocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
blocks.resize(numBlocks);
for (int b = 0; b < numBlocks; ++b) {
blocks[b].start = b * BLOCK_SIZE;
blocks[b].end = min(n - 1, (b + 1) * BLOCK_SIZE - 1);
// Pour chaque modulo k, calculer le maximum de (a[i] % k) dans ce bloc
for (int k = 1; k <= MAX_VAL; ++k) {
int bestRemainder = 0;
// Itérer sur les intervalles [t*k, (t+1)*k - 1]
for (int t = 0; t * k <= MAX_VAL; ++t) {
int intervalStart = t * k;
int intervalEnd = min(MAX_VAL, (t + 1) * k - 1);
int maxInInterval = 0;
// Trouver le max de arrayData[i] dans l'intervalle [intervalStart, intervalEnd] pour i dans le bloc
for (int i = blocks[b].start; i <= blocks[b].end; ++i) {
if (arrayData[i] >= intervalStart && arrayData[i] <= intervalEnd) {
maxInInterval = max(maxInInterval, arrayData[i]);
}
}
if (maxInInterval > 0) {
bestRemainder = max(bestRemainder, maxInInterval - intervalStart);
}
}
blocks[b].maxValueForMod[k] = bestRemainder;
}
}
}
int query(int l, int r, int k) {
int result = 0;
int blockL = blockIndex[l];
int blockR = blockIndex[r];
if (blockL == blockR) {
// Parcours direct si l et r sont dans le même bloc
for (int i = l; i <= r; ++i) {
result = max(result, arrayData[i] % k);
}
} else {
// Partie gauche partielle
for (int i = l; blockIndex[i] == blockL; ++i) {
result = max(result, arrayData[i] % k);
}
// Blocs entiers intermédiaires
for (int b = blockL + 1; b < blockR; ++b) {
result = max(result, blocks[b].maxValueForMod[k]);
}
// Partie droite partielle
for (int i = r; blockIndex[i] == blockR; --i) {
result = max(result, arrayData[i] % k);
}
}
return result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> arrayData[i];
blockIndex[i] = i / BLOCK_SIZE;
}
preprocessBlocks();
while (m--) {
int l, r, k;
cin >> l >> r >> k;
// Ajuster les indices pour qu'ils commencent à 0
cout << query(l - 1, r - 1, k) << "\n";
}
return 0;
}
La complexité de prétraitement est d'environ O((N/B) * (MAX_VAL log MAX_VAL + N)) où B est la taille du bloc, choisie pour équilibrer les coûts. La complexité par requête est O(B + N/B). Avec un choix optimal B ≈ √(MAX_VAL log MAX_VAL), la complexité totale est d'environ O((N+M)√(MAX_VAL log MAX_VAL)).