Jour 1 - Problème 1 : Le Carré Magique Fantastique

Ce problème est une simulation directe de la construction d'un carré magique d'ordre impair. L'objectif est de remplir une matrice de taille $N \times N$ en suivant des règles de positionnement relatives au nombre précédemment placé.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    vector<vector<int>> grille(n + 1, vector<int>(n + 1, 0));
    int r = 1, c = n / 2 + 1;
    grille[r][c] = 1;

    for (int k = 2; k <= n * n; ++k) {
        if (r == 1 && c != n) {
            r = n; c++;
        } else if (c == n && r != 1) {
            c = 1; r--;
        } else if (r == 1 && c == n) {
            r++;
        } else {
            if (grille[r - 1][c + 1] == 0) {
                r--; c++;
            } else {
                r++;
            }
        }
        grille[r][c] = k;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << grille[i][j] << (j == n ? "" : " ");
        }
        cout << endl;
    }
    return 0;
}

Jour 1 - Problème 2 : Transmission d'Information

Le problème demande de trouver la longueur du plus petit cycle dans un graphe où chaque sommet a exactement un degré de sortie égal à 1. Nous pouvons utiliser l'algorithme Union-Find (DSU) avec compression de chemin pour détecter les cycles et calculer leur longueur.

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
int parent[MAXN], dist_to_root[MAXN];
int cycle_minimal = 1e9;

int trouver_racine(int x, int &d) {
    if (parent[x] == x) return x;
    int racine = trouver_racine(parent[x], d);
    d += dist_to_root[parent[x]];
    return racine;
}

void lier(int u, int v) {
    int du = 0, dv = 0;
    int racine_u = trouver_racine(u, du);
    int racine_v = trouver_racine(v, dv);
    
    if (racine_u != racine_v) {
        parent[racine_u] = racine_v;
        dist_to_root[u] = dv + 1;
    } else {
        cycle_minimal = min(cycle_minimal, du + dv + 1);
    }
}

int main() {
    int n, cible;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) parent[i] = i;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &cible);
        lier(i, cible);
    }
    printf("%d\n", cycle_minimal);
    return 0;
}

Jour 1 - Problème 3 : Dou Dizhu

Il s'agit d'un problème complexe de recherche (DFS) combiné à une simulation de jeu de cartes. L'objectif est de trouver le nombre minimum de coups pour se débarrrasser de toutes les cartes. La stratégie consiste à donner la priorité aux cobminaisons spéciales (suites, paires de suites) puis à traiter les cartes restantes de manière optimale.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int nb_cartes, resultat_final;
int main_joueur[15];

void resoudre_restant(int coups_actuels) {
    int stats[5] = {0};
    for (int i = 0; i <= 13; ++i) stats[main_joueur[i]]++;
    
    int c = coups_actuels;
    // Logique simplifiée pour les combinaisons de type 4+2 et 3+1
    while (stats[4] && stats[2] >= 2) { stats[4]--; stats[2] -= 2; c++; }
    while (stats[4] && stats[1] >= 2) { stats[4]--; stats[1] -= 2; c++; }
    while (stats[3] && stats[2]) { stats[3]--; stats[2]--; c++; }
    while (stats[3] && stats[1]) { stats[3]--; stats[1]--; c++; }
    
    resultat_final = min(resultat_final, c + stats[1] + stats[2] + stats[3] + stats[4]);
}

void explorer(int pas) {
    if (pas >= resultat_final) return;
    resoudre_restant(pas);
    
    // Exemple : Exploration des suites simples (longueur >= 5)
    for (int i = 0; i < 8; ++i) {
        for (int len = 5; i + len <= 12; ++len) {
            bool possible = true;
            for (int k = i; k < i + len; ++k) if (main_joueur[k] < 1) possible = false;
            if (!possible) break;
            for (int k = i; k < i + len; ++k) main_joueur[k]--;
            explorer(pas + 1);
            for (int k = i; k < i + len; ++k) main_joueur[k]++;
        }
    }
}

int main() {
    int t;
    cin >> t >> nb_cartes;
    while (t--) {
        memset(main_joueur, 0, sizeof(main_joueur));
        for (int i = 0; i < nb_cartes; ++i) {
            int v, s; cin >> v >> s;
            if (v == 0) main_joueur[13]++; // Joker
            else if (v == 1) main_joueur[11]++;
            else if (v == 2) main_joueur[12]++;
            else main_joueur[v - 3]++;
        }
        resultat_final = nb_cartes;
        explorer(0);
        cout << resultat_final << endl;
    }
    return 0;
}

Jour 2 - Problème 1 : Saut de Pierres

Pour maximiser la distance minimale entre deux pierres, on utilise une recherche binaire sur la réponse. Pour une distance donnée $D$, on vérifie par une approche gloutonne s'il est possible de retirer au plus $M$ pierres pour que chaque intervalle soit au moins de longueur $D$.

#include <iostream>
#include <vector>

using namespace std;

bool est_valide(int dist_min, int n, int m, const vector<int>& pos, int total_len) {
    int retires = 0;
    int dernier = 0;
    for (int i = 1; i <= n; ++i) {
        if (pos[i] - dernier < dist_min) {
            retires++;
        } else {
            dernier = pos[i];
        }
    }
    if (total_len - dernier < dist_min) retires++;
    return retires <= m;
}

int main() {
    int L, N, M;
    cin >> L >> N >> M;
    vector<int> pos(N + 1);
    for (int i = 1; i <= N; ++i) cin >> pos[i];

    int gauche = 0, droite = L, ans = 0;
    while (gauche <= droite) {
        int milieu = gauche + (droite - gauche) / 2;
        if (est_valide(milieu, N, M, pos, L)) {
            ans = milieu;
            gauche = milieu + 1;
        } else {
            droite = milieu - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Jour 2 - Problème 2 : Sous-chaîne

Ce problème se résout par programmation dynamique. Soit $dp[i][j][k][0/1]$ le nombre de façons de former les $j$ premiers caractères de la chaîne $B$ en utilisant $k$ sous-chaînes non chevauchantes des $i$ premiers caractères de $A$. Le dernier état indique si le caractère $A[i]$ est utilisé ou non.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1000000007;
int dp[2][205][205][2];

int main() {
    int n, m, K;
    string A, B;
    cin >> n >> m >> K >> A >> B;
    A = " " + A; B = " " + B;

    dp[0][0][0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        int cur = i % 2, prev = (i - 1) % 2;
        dp[cur][0][0][0] = 1;
        for (int j = 1; j <= m; ++j) {
            for (int k = 1; k <= K; ++k) {
                dp[cur][j][k][0] = (dp[prev][j][k][0] + dp[prev][j][k][1]) % MOD;
                if (A[i] == B[j]) {
                    dp[cur][j][k][1] = (dp[prev][j - 1][k][1] + 
                                       (long long)dp[prev][j - 1][k - 1][0] + 
                                       dp[prev][j - 1][k - 1][1]) % MOD;
                } else {
                    dp[cur][j][k][1] = 0;
                }
            }
        }
    }
    cout << (dp[n % 2][m][K][0] + dp[n % 2][m][K][1]) % MOD << endl;
    return 0;
}

Jour 2 - Problème 3 : Plan de Transport

Pour minimiser le temps de transport maximal, nous utilisons la recherche binaire sur la durée $T$. Pour un $T$ donné, nous identifions tous les chemins dont la longueur est supérieure à $T$. Nous devons alors trouver une arête appartenant à tous ces chemins dont le poids, une fois soustrait, ramène tous les chemins en dessous de $T$. Le calcul de la couverture des arêtes se fait via un tableau de différences sur arbre et le calcul des distances via LCA.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 300005;
struct Edge { int to, next, w; } edges[MAXN * 2];
struct Query { int u, v, lca, dist; } queries[MAXN];
int head[MAXN], depth[MAXN], parent[MAXN][20], dist_from_root[MAXN], weight_to_parent[MAXN];
int diff[MAXN], order[MAXN], edge_cnt, node_cnt, q_cnt, timer;

void build_tree(int u, int p, int d, int w) {
    depth[u] = d;
    parent[u][0] = p;
    dist_from_root[u] = dist_from_root[p] + w;
    weight_to_parent[u] = w;
    order[++timer] = u;
    for (int i = 1; i < 20; ++i) parent[u][i] = parent[parent[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = edges[i].next) {
        if (edges[i].to != p) build_tree(edges[i].to, u, d + 1, edges[i].w);
    }
}

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = 19; i >= 0; --i) if (depth[u] - (1 << i) >= depth[v]) u = parent[u][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; --i) if (parent[u][i] != parent[v][i]) { u = parent[u][i]; v = parent[v][i]; }
    return parent[u][0];
}

bool verify(int limit) {
    int count = 0, max_deficit = 0;
    for (int i = 1; i <= node_cnt; ++i) diff[i] = 0;
    for (int i = 0; i < q_cnt; ++i) {
        if (queries[i].dist > limit) {
            diff[queries[i].u]++; diff[queries[i].v]++;
            diff[queries[i].lca] -= 2;
            count++;
            max_deficit = max(max_deficit, queries[i].dist - limit);
        }
    }
    if (count == 0) return true;
    for (int i = node_cnt; i >= 1; --i) {
        int u = order[i];
        diff[parent[u][0]] += diff[u];
        if (diff[u] == count && weight_to_parent[u] >= max_deficit) return true;
    }
    return false;
}

int main() {
    scanf("%d %d", &node_cnt, &q_cnt);
    for (int i = 0, u, v, w; i < node_cnt - 1; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        edges[++edge_cnt] = {v, head[u], w}; head[u] = edge_cnt;
        edges[++edge_cnt] = {u, head[v], w}; head[v] = edge_cnt;
    }
    build_tree(1, 0, 1, 0);
    int max_d = 0;
    for (int i = 0; i < q_cnt; ++i) {
        scanf("%d %d", &queries[i].u, &queries[i].v);
        queries[i].lca = get_lca(queries[i].u, queries[i].v);
        queries[i].dist = dist_from_root[queries[i].u] + dist_from_root[queries[i].v] - 2 * dist_from_root[queries[i].lca];
        max_d = max(max_d, queries[i].dist);
    }
    int low = 0, high = max_d, result = max_d;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (verify(mid)) { result = mid; high = mid - 1; }
        else low = mid + 1;
    }
    printf("%d\n", result);
    return 0;
}