Gestion des entrées multiples

Pour les problèmes avec plusieurs jeux de données, initialisez les variables à l'intérieur de la boucle de test pour éviter toute réutilisation indésirable des résultats précédents. Lors de l'affichage, utilisez des fonctions appropriées pour vider le tampon de sortie. Évitez les initialisations répétées de tableaux de grande taille qui pourraient causer des dépassements de temps. Pour les petites données, commencez par une recherche exhaustive avant d'explorer des propriétés mathématiques. Dans les algorithmes de recherche en profondeur, tracez l'arbre récursif pour clarifier le rôle des variables de contrôle. N'oubliez pas de réinitialiser les tableaux de visite et les structures de données entre les tests.

Segments maximaux dans une séquence

Problème : Identifier le plus long segment non strictement croissant dans une liste d'entiers. Approche en deux passes pour déterminer les limites des segments.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int nb_tests;
    cin >> nb_tests;
    while (nb_tests--) {
        int taille;
        cin >> taille;
        vector<int> donnees(taille);
        for (int i = 0; i < taille; ++i) cin >> donnees[i];
        int depart = 0, longueur_max = 0;
        for (int pos = 1; pos < taille; ++pos) {
            if (donnees[pos] < donnees[pos-1]) {
                longueur_max = max(longueur_max, pos - depart);
                depart = pos;
            }
        }
        longueur_max = max(longueur_max, taille - depart);
        cout << longueur_max << endl;
    }
    return 0;
}

Cette implémentation utilise une unique boucle pour calculer les longueurs de segments sans variable globale.

Protection des cellules dans une grille

Problème : Compter les cellules marquées 'P' qui ne sont pas adjacentes à des mines '*' dans une grille 2D. Solutions par parcours de voisinage.

#include <iostream>
#include <vector>
using namespace std;

const int DX[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int DY[] = {1, 0, -1, -1, -1, 0, 1, 1};

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int lignes, colonnes;
        cin >> lignes >> colonnes;
        vector<vector<char>> grille(lignes + 2, vector<char>(colonnes + 2, '.'));
        for (int i = 1; i <= lignes; ++i) {
            for (int j = 1; j <= colonnes; ++j) {
                cin >> grille[i][j];
            }
        }
        // Marquage des plantes menacées
        for (int i = 1; i <= lignes; ++i) {
            for (int j = 1; j <= colonnes; ++j) {
                if (grille[i][j] == '*') {
                    for (int d = 0; d < 8; ++d) {
                        int ni = i + DX[d], nj = j + DY[d];
                        if (grille[ni][nj] == 'P') grille[ni][nj] = 'X';
                    }
                }
            }
        }
        int compteur = 0;
        for (int i = 1; i <= lignes; ++i) {
            for (int j = 1; j <= colonnes; ++j) {
                if (grille[i][j] == 'P') compteur++;
            }
        }
        cout << compteur << endl;
    }
    return 0;
}

Les directions sont prédéfinies dans des tableaux constants pour plus de clarté, et la grille est bordée de '.' pour éviter les vérifications limites.

Calculs avec modulo sur de grands entiers

Problème : Évaluer une expression arithmétique impliquant de grands nombres représentés en chaînes, avec application du modulo à chaque étape pour éviter les dépassements.

#include <iostream>
#include <string>
using namespace std;

const int MODULUS = 998244353;

int main() {
    int nb_cas;
    cin >> nb_cas;
    while (nb_cas--) {
        string premier, second;
        cin >> premier >> second;
        long long val1 = 0, val2 = 0;
        for (char chiffre : premier) {
            val1 = (val1 * 10 + (chiffre - '0')) % MODULUS;
        }
        for (char chiffre : second) {
            val2 = (val2 * 10 + (chiffre - '0')) % MODULUS;
        }
        long long resultat = (val1 * second.size() + val2 * premier.size()) % MODULUS;
        cout << resultat << endl;
    }
    return 0;
}

Les conversions sont effectuées caractère par caractère avec application immédiate du modulo pour conserver les valeurs dans des plages gérables.

Sommation avec modulo et grand n

Pour calculer la somme 1+2+...+n où n peut atteindre 10^10000, applqiuez le modulo à chaque addition intermédiaire.

long long somme = 0;
for (int i = 1; i <= n; ++i) {
    somme = (somme + i) % 1000000007;
}
// Cette méthode garantit l'absence de dépassement de capacité.

L'approche incrémentale avec modulo à chaque pas est cruciale lorsque n est extrêmement grand.

Simulation avec gestion de la précision

Problème : Traiter des calculs en virgule flottante sans erreur d'arrondi. Technique de mise à l'échelle entière pour éviter les imprécisions.

// Exemple conceptuel : multiplier par 10 pour travailler avec des entiers
// avant de reconvertir en virgule flottante si nécessaire.

Pour les problèmes nécessitant une haute précision, transformez les valeurs en entiers en multipliant par une puissance de 10, effectuez les calculs, puis redivisez.

Parcours d'arbre et comptage conditionnel

Problème : Parcourir un arbre non orienté et compter les nœuds à une profodneur impaire, puis dériver une formule combinatoire.

#include <iostream>
#include <vector>
using namespace std;

vector<int> adjacences[200001];
bool marque[200001];
int compteur = 0;

void explorer(int noeud, int profondeur) {
    if (marque[noeud]) return;
    marque[noeud] = true;
    if (profondeur % 2 != 0) compteur++;
    for (int voisin : adjacences[noeud]) {
        explorer(voisin, profondeur + 1);
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            adjacences[i].clear();
            marque[i] = false;
        }
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            adjacences[u].push_back(v);
            adjacences[v].push_back(u);
        }
        compteur = 0;
        explorer(1, 0);
        cout << compteur * (compteur + 1) / 2 << endl;
    }
    return 0;
}

La fonction récursive utilise des paramètres exlpicites pour la profondeur et réinitialise les structures globales pour chaque test.

Optimisation par tri et sélection gloutonne

Problème : Maximiser une valeur sous des contraintes de sélection consécutive. Solution par tri décroissant et distribution limitée.

// Pseudo-code illustratif :
// 1. Trier les éléments par valeur décroissante.
// 2. Parcourir la liste en respectant les restrictions de placement.
// 3. Accumuler la valeur totale si les conditions sont satisfaites.

Cette stratégie combine le tri avec une gestion des quotas pour éviter les configurations invalides.

Programmation dynamique pour les sous-séquences

Problème : Compter le nombre de sous-séquences formant un motif spécifique dans une chaîne de caractères. Approche par accumulation d'états.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int longueur;
    cin >> longueur;
    string texte;
    cin >> texte;
    long long etatC = 0, etatO = 0, etatW = 0;
    for (char car : texte) {
        if (car == 'C') etatC++;
        else if (car == 'O') etatO += etatC;
        else etatW += etatO;
    }
    cout << etatW << endl;
    return 0;
}

Les compteurs sont mis à jour séquentiellement pour refléter les transitions d'état sans stocker la chaîne complète.

Ces exemples couvrent des techniques variées, notamment la recherche exhaustive, le traitement de graphes, la manipulation de données numériques et l'optimisation par programmation dynamique, essentielles pour résoudre des problèmes de compétition.