MISE À JOUR

mise à jour(2024/12/10) : Correction d'une petite erreur dans le code de l'exercice E, merci à @Andyqian7 pour les données de test ! mise à jour(2024/12/15) : Correction d'une formulation problématique dans la solution de l'exercice B, merci à @iy88 pour cette remarque !

Aperçu

Le concours de reprise a été téléchargé sur SYNU OJ, les étudiants de l'école peuvent s'exercer sur la page correspondante.

Rapport de solutions

A. Déplcaement

Une simulation directe suffit.

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int dimension, mouvements;
    cin >> dimension >> mouvements;
    while (mouvements--)
    {
        int coordX, coordY;
        cin >> coordX >> coordY;
        string direction;
        cin >> direction;
        for (int i = 0; i < direction.length(); i++)
        {
            int nouvX = coordX, nouvY = coordY;
            if (direction[i] == 'f')
                nouvY++;
            else if (direction[i] == 'b')
                nouvY--;
            else if (direction[i] == 'l')
                nouvX--;
            else
                nouvX++;

            if (nouvX >= 1 and nouvX <= dimension and nouvY >= 1 and nouvY <= dimension)
            {
                coordX = nouvX, coordY = nouvY;
            }
        }
        cout << coordX << ' ' << coordY << '\n';
    }
}

B. Inspection des rêves

mise à jour(2024/12/15) : En réalité, la valeur \(a_i\) que j'indique ici devrait représenter \(a_{i-1}\) de l'énoncé original, car j'ai décalé l'indice de \(a_i\) lors du traitement des entrées, avec le code for(int i = 1; i <= n + 1; i ++) cin >> a[i];. L'entrée originale était \(a_0 \sim a_n\), mais je l'ai traitée comme \(a_1 \sim a_{n+1}\). La correction du code final n'est cependant pas affectée. Veuillez considérer \(a_i\) dans ce texte comme \(a_{i-1}\) de l'énoncé original !

D'abord, sans considérer la modification de \(b_i\) dans l'énoncé, comment calculons-nous l'énergie initiale \(w\) ? Supposons que nous notons \(f(x)\) l'énergie actuelle lorsque nous atteignons le point \(x\), avant d'avoir reçu \(b_i\) (qui peut être négative), et que nous notons le point \(n + 1\) comme étant le retour au point \(0\). La relation de récurrence pour \(f(x)\) est alors :

[f(x) = \left{ \begin{array}{c} f(x-1) - a_i + b_{i-1} \ (x > 1) \ 0 \ (x=1) \end{array} \right. ]Bien que \(f(x)\) puisse être négatif, ce qui est un état invalide, nous devons rendre tous ces états valides. Supposons que l'énergie initiale soit \(w\), la formule devient :

[f(x) = \left{ \begin{array}{c} f(x-1) - a_i + b_{i-1} \ (x > 1) \ w \ (x=1) \end{array} \right. ]Cela signifie que nous ajoutons \(w\) à tous les \(f(x)\) suivants. Pour valider tous les \(f(i)\) tout en minimisant \(w\), il suffit que \(w\) soit l'opposé de la valeur minimale de tous les \(f(i)\) :

[w = - \min_{i=1}^{n+1}(f(i)) ]C'est la méthode pour calculer \(w\) sans modification. Comment traiter les modifications ? Supposons que le point actuel soit \(p\) et que nous voulions modifier \(b_p \leftarrow 0\). Quel impact cela aurait-il ? Selon la formule ci-dessus, cela affecte toutes les valeurs de \(f(p+1)\) à \(f(n+1)\), les réduisant toutes de \(b_p\). À ce moment-là, selon la formule de calcul de \(w\), une nouvelle valeur minimale pourrait apparaître entre \(f(p+1)\) et \(f(n+1)\), donc :

[w(p) = \min(w, \min_{i=p+1}^{n+1}(f(i)) - b_p) ]Grâce à cette formule, nous voyons que \(\min_{i=p+1}^{n+1}(f(i))\) est en fait le minimum suffixe de \(f(i)\), que nous pouvons précalculer. Chaque calcul de \(w(p)\) est en \(O(1)\), la complexité totale est donc \(O(n)\).

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int nbPoints;
    cin >> nbPoints;
    vector<int> energie(nbPoints + 2), recharge(nbPoints + 1), energieCumul(nbPoints + 2);
    for(int i = 1; i <= nbPoints + 1; i ++) cin >> energie[i];
    for(int i = 1; i <= nbPoints; i ++) cin >> recharge[i];
    int energieInitiale = 0;
    for(int i = 1; i <= nbPoints + 1; i ++)
    {
        energieCumul[i] = energieCumul[i-1] - energie[i] + recharge[i-1];
        energieInitiale = min(energieInitiale, energieCumul[i]);
    }
    vector<int> minSuffixe(nbPoints + 3, 1e9);
    for(int i = nbPoints + 1; i >= 1; i --)
    {
        minSuffixe[i] = min(minSuffixe[i + 1], energieCumul[i]);
    }
    for(int i = 1; i <= nbPoints; i ++)
    {
        cout << -min(energieInitiale, minSuffixe[i + 1] - recharge[i]) << ' ';
    }
}

C. Simulation de cache

Grande simulation, il est en fait beaucoup plus simple de dessiner d'abord un diagramme de flux, ce qui permet de savoir exactement quand enregistrer les réponses.

Les parties en rouge sur le diagramme sont les endroits où il faut enregistrer les réponses.

En réalité, nous n'avons besoin de nous concentrer que sur la mise en œuvre des opérations critiques du processus ci-dessus.

• Comment enregistrer l'ordre des opérations : nous pouvons enregistrer un horodatage pour chaque opération et utiliser un set pour maintenir des pair, où la première dimension stocke l'horodatage et la deuxième dimension stocke \(x\). Comme le set stocke de manière ordonnée, l'horodatage devrait être attribué en ordre inverse, de sorte que dans le set, les horodatages plus petits apparaissent en premier, indiquant qu'ils sont plus récents.
• Vérifier si une donnée est dans le cache : nous pouvons utiliser lower_bound du set, et pour vérifier si \(x\) est dans le cache, nous pouvons rechercher l'horodatage le plus récent de \(x\), ce qui nous permet de juger rapidement et d'obtenir directement l'itérateur de \(x\).
• Supprimer le contenu du cache le plus ancien par rapport au temps actuel : nous pouvons utiliser rbegin() du set, ce qui supprime chaque fois l'élément le plus ancien.
• Vérifier si \(x\) dans le cache a été modifié, nous pouvons utiliser un map comme tableau de marquage.

Points d'attention :

1. N'oubliez pas de mettre à jour l'horodatage de \(x\) après chaque opération (surtout l'horodatage dans le set).
2. N'oubliez pas de marquer lors des modifications et si un nombre marqué doit être supprimé, retirez son marquage.
3. Si le cache est plein et qu'un élément doit être supprimé, tout en écrivant en mémoire, rappelez-vous que lors de l'enregistrement des réponses, l'ordre des opérations d'écriture précède celui des lectures.

using ll = long long;
using paire = pair<int, int>;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tailleCache, nbGroupes, requetes;
    cin >> tailleCache >> nbGroupes >> requetes;
    // tailleCache taille de groupe nbGroupes nombre de groupes
    auto getIdGroupe = [&](int x)
    {
        return x / tailleCache % nbGroupes;
    };
    vector<set<paire>> groupes(nbGroupes); // groupes de cache
    vector<paire> reponses;
    map<int, int> estModifie; // a été modifié
    int horodatage = 0;
    map<int, int> temps; // horodatage
    while(requetes--)
    {
        int operation, donnee;
        cin >> operation >> donnee;
        if(operation == 0) 
        {
            int id = getIdGroupe(donnee);
            auto it = groupes[id].lower_bound({temps[donnee], 0});
            if(it != groupes[id].end() and it -> second == donnee) // si la donnée est déjà dans le cache
            {
                // mettre à jour l'horodatage
                groupes[id].erase(it);
                groupes[id].insert({requetes, donnee});
            }
            else // pas dans le cache
            {
                // le groupe de cache n'est pas plein
                if(groupes[id].size() < tailleCache)
                {
                    // lire directement en mémoire
                    reponses.push_back({0, donnee});
                    groupes[id].insert({requetes, donnee});
                }
                // le groupe de cache est plein
                else
                {
                    // trouver le dernier non modifié, c'est-à-dire celui à remplacer
                    auto tmp = groupes[id].rbegin() -> second;
                    // s'il a été modifié dans le cache
                    if(estModifie[tmp]) 
                    {
                        // d'abord synchroniser la modification en mémoire
                        reponses.push_back({1, tmp});
                        // retirer le marquage de modification
                        estModifie[tmp] = 0;
                    }
                    groupes[id].erase(groupes[id].lower_bound({temps[tmp], tmp}));
                    // puis lire la nouvelle donnée
                    groupes[id].insert({requetes, donnee});
                    reponses.push_back({0, donnee});
                }
            }
        }
        else
        {
            int id = getIdGroupe(donnee);
            auto it = groupes[id].lower_bound({temps[donnee], 0});
            if(it != groupes[id].end() and it -> second == donnee) // si la donnée est déjà dans le cache
            {
                // mettre à jour l'horodatage
                // directement modifier et marquer comme modifié
                groupes[id].erase(it);
                groupes[id].insert({requetes, donnee});
                estModifie[donnee] = 1;
            }
            else
            {
                // le groupe de cache n'est pas plein, d'abord lire, puis modifier
                if(groupes[id].size() < tailleCache)
                {
                    // lire directement en mémoire
                    reponses.push_back({0, donnee});
                    groupes[id].insert({requetes, donnee});
                    estModifie[donnee] = 1;
                }
                else 
                {
                    // trouver le dernier non modifié, c'est-à-dire celui à remplacer
                    auto tmp = groupes[id].rbegin() -> second;
                    // s'il a été modifié dans le cache
                    if(estModifie[tmp]) 
                    {
                        // d'abord synchroniser la modification en mémoire
                        reponses.push_back({1, tmp});
                        // retirer le marquage de modification
                        estModifie[tmp] = 0;
                    }
                    groupes[id].erase(groupes[id].lower_bound({temps[tmp], tmp}));
                    // puis lire la nouvelle donnée
                    groupes[id].insert({requetes, donnee});
                    reponses.push_back({0, donnee});
                    estModifie[donnee] = 1;
                }
            }
        }
        temps[donnee] = requetes;
    }
    for(auto [x, y] : reponses)
    {
        cout << x << ' ' << y << '\n';
    }
}

D. Jeu de la marelle

Cela semble être un BFS en \(O(n)\), mais lors de la construction du graphe, la complexité devient \(O(n^2)\). Comment optimiser ? Nous devons principalement résoudre le problème où un point peut être atteint par plusieurs points, ce qui entraîne une complexité très élevée. En réalité, nous pouvons utiliser un conteneur set, et chaque fois que nous recherchons, si nous avons déjà trouvé un point, nous le supprimons directement de manière violente. Ainsi, chaque point ne sera recherché qu'une seule fois, et la complexité devient \(O(n \log n)\).

En réalité, il existe une approche encore meilleure pour ce problème, qui consiste à maintenir une \(max_R\) pendant le processus de recherche, représentant la limite droite accessible. Chaque recherche ne commence qu'à partir de \(max_R\), mettant à jour \(max_R\) à chaque fois. Comme \(max_R\) est monotone, la complexité est \(O(n)\). Vous pouvez l'implémenter vous-même.

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int nbCases;
    cin >> nbCases;
    vector<int> positions(nbCases + 1), sauts(nbCases + 1), visites(nbCases + 1);
    for(int i = 1; i <= nbCases; i++)
        cin >> positions[i];
    for(int i = 1; i <= nbCases; i++)
        cin >> sauts[i];
    queue<int> file;
    file.push(1);
    visites[1] = 1;
    set<int> nonVisites;
    for(int i = 2; i <= nbCases; i++) nonVisites.insert(i);
    int distance = 0;
    while(file.size())
    {
        int taille = file.size();
        distance++;
        while(taille--)
        {
            auto u = file.front();
            file.pop();
            if(u + sauts[u] >= nbCases) 
            {
                cout << distance << '\n';
                return 0;
            }
            auto it = nonVisites.lower_bound(u + 1);
            vector<int> aSupprimer;
            for(;*it <= u + sauts[u] and it != nonVisites.end(); it++)
            {
                aSupprimer.push_back(*it);
                if(!visites[*it - positions[*it]])
                {
                    visites[*it - positions[*it]] = 1;
                    file.push(*it - positions[*it]);
                }
            }
            for(int i : aSupprimer) nonVisites.erase(i);
        }
    }
    cout << -1 << '\n';
}

E. Cauchemar

La solution de cet exercice est fournie par le membre du groupe Bezime, avec nos remerciements spéciaux ! Orz

Construction de l'arbre cartésien avec une pile monotone, maintenance de maxl et maxr. La réponse est \(\min(f[i][0], f[i+1][0])\). Pour une approche plus détaillée, reportez-vous aux commentaires du code.

mise à jour(2024/12/10) : Modifier la partie de la pile monotone qui parcourt de droite à gauche, changer while (qt && q[qt] <= a[i]) en while (qt && q[qt] < a[i])

using ll = long long;
const int N = 5e6 + 5;

inline void lireEntier(ll &x)
{
    x = 0;
    short signe = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-')
        c = getchar();
    if (c == '-')
        signe = -1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    x *= signe;
}
inline void ecrireEntier(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        ecrireEntier(x / 10);
    putchar(x % 10 + '0');
}

ll nbTests = 1, nbElements, nbModifs, nbRequetes, reponse;
ll valeurs[N], bonus[N], modifications[N], durees[N];
ll sommes[N], maxGauche[N], maxDroite[N];
ll pile[N], ordre[N], sommetPile;
ll maximum;
ll f[N][3];

void parcoursProfondeur(ll x)
{
    ll xl = maxGauche[x], xr = maxDroite[x];
    // Si les 3 valeurs f du côté gauche ne sont pas déterminées, les calculer
    if (!f[xl][0])
        parcoursProfondeur(xl); 
    // Si les 3 valeurs f du côté droit ne sont pas déterminées, les calculer
    if (!f[xr][0])
        parcoursProfondeur(xr);                                                                        
    // Ce sont les sommes de l'intervalle complet (xl+1~xr-1), de l'intervalle gauche (xl+1~x-1) et de l'intervalle droit (x+1~xr-1)
    ll total = sommes[xr - 1] - sommes[xl], gauche = sommes[x] - sommes[xl], droite = sommes[xr - 1] - sommes[x - 1];
    // Ne pas prendre le début minimum d'attaque de tout cet intervalle
    // (si xl<=xr, alors f[xl][1]<=f[xr][2], et mxr[xl] devrait être exactement xr, donc f[xl][1] saute exactement xl+1~xr-1).
    // Tout cet intervalle n'a pas été pris, donc lors du calcul des 3 valeurs f, nous pouvons ajouter librement les valeurs b de l'intervalle
    ll minVal = min(f[xl][1], f[xr][2]);
    // Premier coup soi-même, au moins avec a[x] d'attaque, prendre toutes les valeurs b de l'intervalle
    f[x][0] = max(valeurs[x], minVal - total); 
    // Prendre les valeurs b de l'intervalle gauche, laisser les valeurs b de l'intervalle droite, pour calculer les 3 valeurs f de l'intervalle droite
    f[x][1] = max(valeurs[x], minVal - gauche);
    // Prendre les valeurs b de l'intervalle droite, laisser les valeurs b de l'intervalle gauche, pour calculer les 3 valeurs f de l'intervalle gauche
    f[x][2] = max(valeurs[x], minVal - droite);
}
void resoudre()
{
    lireEntier(nbElements);
    for (ll i = 1; i <= nbElements; i++)
        lireEntier(modifications[i]);
    for (ll i = 1; i <= nbElements; i++)
        lireEntier(durees[i]);
    lireEntier(nbRequetes);
    while (nbRequetes--)
    {
        for (ll i = 1; i <= nbElements; i++)
            valeurs[i] = modifications[i], bonus[i] = durees[i], f[i][0] = 0;
        lireEntier(nbModifs);
        while (nbModifs--)
        {
            ll pos, nouvVal, nouvBonus;
            lireEntier(pos), lireEntier(nouvVal), lireEntier(nouvBonus);
            valeurs[pos] = nouvVal, bonus[pos] = nouvBonus;
        }
        sommetPile = reponse = maximum = 0;
        for (ll i = 1; i <= nbElements; i++)
        {
            // somme préfixe de b
            sommes[i] = sommes[i - 1] + bonus[i]; 
            // enregistrer la valeur maximale de a, la valeur de f ne peut pas dépasser cela
            maximum = max(maximum, valeurs[i]);
            while (sommetPile && pile[sommetPile] <= valeurs[i])
                sommetPile--;
            // premier plus grand à gauche
            maxGauche[i] = ordre[sommetPile]; 
            pile[++sommetPile] = valeurs[i], ordre[sommetPile] = i;
        }
        // donner une valeur initiale aux frontières
        f[0][0] = f[0][1] = f[0][2] = f[nbElements + 1][0] = f[nbElements + 1][1] = f[nbElements + 1][2] = maximum; 
        sommetPile = 0, ordre[0] = nbElements + 1; // nbElements+1 est la frontière droite
        for (ll i = nbElements; i; i--)
        {
            while (sommetPile && pile[sommetPile] < valeurs[i]) // mise à jour : le <= original est maintenant <
                sommetPile--;
            maxDroite[i] = ordre[sommetPile]; // premier plus grand ou égal à droite
            pile[++sommetPile] = valeurs[i], ordre[sommetPile] = i;
        }
        for (ll i = 1; i <= nbElements; i++)
            if (!f[i][0])
                parcoursProfondeur(i); // si la valeur f n'est pas encore déterminée, la calculer
        for (ll i = 1; i < nbElements; i++)
            reponse ^= min(f[i][0], f[i + 1][0]);
        ecrireEntier(reponse), puts("");
    }
}
int main()
{
    while (nbTests--)
        resoudre();
}