Les résultats de cette fois

Impressions de cette époque

J'ai essayé de poser deux questions à la fois en m'en tenant au problème B, mais je n'ai pas pu le résoudre. C'était très décevant car la 200e place n'était pas un rêve si elle était résolue. Je travaillerai dur chaque jour pour passer ce niveau de problèmes pendant le concours un jour.

De plus, j'ai oublié le problème après avoir examiné le problème du bacha d'Edufo que j'ai résolu la semaine dernière, donc si je le résolve pour qu'il ne se produise pas dans le futur ** je vais certainement l'examiner le lendemain ** je veux

Problème A

** J'ai mal compris le préfixe commun le plus long comme étant la plus longue sous-chaîne commune **, et c'était dangereux car il semblait être un DP.

Puisqu'il s'agit du préfixe commun le plus long, $ s [i], s [i + 1] $ devrait être différent du montant de $ a [i] $ donné. De plus, pour faciliter la mise en œuvre, ** seul a ou b ** est utilisé dans la chaîne de caractères. De plus, puisque $ a [i] $ peut être jusqu'à 50, la longueur de la chaîne de caractères de sortie ** est unifiée à 50 **.

Si la chaîne de caractères à afficher au $ i $ th est $ s [i] $, le $ s [i + 1] $ est différent du $ s [i] $ du front au $ a [i] $ th ( A devrait être b, b devrait être a) et $ a [i] + 1 $ devrait être identique à partir du troisième.

`A.py`


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    s="a"*50
    ans=[s]
    for i in range(n):
        s=""
        for j in range(50):
            if j<a[i]:
                s+=ans[-1][j]
            else:
                if ans[-1][j]=="a":
                    s+="b"
                else:
                    s+="a"
        ans.append(s)
    for i in range(n+1):
        print(ans[i])

Problème B1, problème B2

Tout d'abord, je pensais économiser le nombre de secondes (ou la hauteur de la vague) à chaque point et faire DP, mais ** le problème B2 semblait être trop tard, donc $ O (N) J'ai pensé à une nouvelle politique ** qui serait de $.

Ici, le temps qui peut être à chaque point est $ 0 $ ~ $ min (k, l-d_i) $ et $ 2t-min (k, l-d_i) $ sous $ mod \ 2K $. Cela devient ~ $ 2t-1 $, et vous pouvez voir que c'est une ** section continue **. De plus, comme il faut 1 seconde pour nager jusqu'au point suivant, ** Pensez à la partie commune de la section en décalant la section? Je pensais **, mais je ne pouvais pas avoir l'idée de combiner les sections en une seule, ou j'ai oublié de penser au cas où la section serait de 2k $ (décrit plus tard), alors j'ai dû aller jusqu'au regret.

(À partir de là, ce sera une considération après le concours.)

Tout d'abord, dans ce qui précède, la section est divisée en deux, mais si c'est $ -min (k, l-d_i) $ ~ $ min (k, l-d_i) $, ** combinez les sections en une seule **. Je peux. De plus, il est facile à manipuler car il devient symétrique ** en ** 0.

Sur cette base, considérons ** la méthode gloutonne **, qui est à la base du problème de transition ** (puis DP). Nous traiterons ici du cinquième échantillon. L'entrée est la suivante. (Vous pouvez également voir que la méthode gourmande doit être effectuée avec ** $ O (N) $ **.)

7 2 3
3 0 2 1 3 0 1

De plus, la section de l'entrée ci-dessus est indiquée ci-dessous. L'axe du temps est de haut en bas.

Envisagez la transition du côté gauche (plus près de la plage) dans la figure ci-dessus, mais un exemple est montré dans la figure ci-dessous. La ligne rouge montre comment il faut 1 seconde pour passer au point suivant de la transition.

Ici, la flèche rouge va en diagonale vers le bas, de sorte que la source de la ** flèche doit être aussi haute que possible ** (pour tenir dans l'intervalle). De plus, si la section est de 2k $, vous pouvez toujours y rester **, vous pouvez donc partir à tout moment. Par conséquent, j'ai essayé de sélectionner la partie supérieure de la section ** comme source de la flèche **, mais cela ne fonctionne pas pour la flèche verte. Si la pointe de la flèche est au-dessus de la section comme ceci, vous pouvez déplacer la flèche ** de sorte que la pointe de la flèche soit en haut de la section. En répétant cela, si la pointe de la flèche ne s'étend pas au-delà de la section dans n'importe quelle section, Oui, et s'il y a même une section qui dépasse, le numéro peut être sorti.

`B.py`


#Simulez avec avidité
#Être aussi petit que possible
for _ in range(int(input())):
    n,k,l=map(int,input().split())
    d=list(map(int,input().split()))
    seg=[]
    for i in range(n):
        if l-d[i]<0:
            print("No")
            break
        #Assurez-vous que la fin est égale ou supérieure à 0
        seg.append([-min(l-d[i],k),min(l-d[i],k)])
    else:
        now=seg[0][0]
        for i in range(1,n):
            if seg[i]==[-k,k]:
                now=seg[i][0]
            else:
                now+=1
                if now<seg[i][0]:
                    now=seg[i][0]
                elif now>seg[i][1]:
                    print("No")
                    break
        else:
            print("Yes")

Problème C

Est-ce que c'est bon ou mauvais parce que je l'ai passé à moitié avec Esper?

Dans ce qui suit, le $ i $ th de $ a, b $ sera $ a_i, b_i $, et les alphabets plus grands (ou plus petits) seront classés par ordre alphabétique.

C'était juste une question de cupidité. Pour le moment, $ a_i, b_i sera simulé en changeant $ alphabets différents, mais ** se déplace dans une direction qui ne cause aucune perte **. Avant cela, vous ne pouvez pas passer de $ a $ à $ b $ quand $ a_i> b_i $, car ce problème ne peut que rendre l'alphabet plus grand (sinon, il passe toujours de $ a $ à $ b $). Vous pouvez).

Tout d'abord, puisque vous ne pouvez que agrandir l'alphabet, vous pouvez voir qu'il semble préférable de choisir l'alphabet plus petit ** $ a $ **. Ici, quand il n'y a qu'un seul alphabet que vous voulez changer $ a $, vous ne changez que cet alphabet, mais quand il y a plusieurs alphabets que vous voulez changer ** $ a $ **, tous les alphabets correspondent à chacun. Il est préférable de choisir le plus petit des alphabets $ b $ que vous faites. En effet, il n'y a pas de perte même si vous le modifiez **, et il est possible que vous puissiez en créer de nouveaux avec le même alphabet (c'est le premier modèle de l'exemple. ** ← Si vous ne comprenez pas, essayez l'exemple! **).

Puisqu'il y a au plus 20 alphabets qui apparaissent dans $ a et b $, la simulation peut être complétée en environ 20 fois, et vous pouvez écrire un programme suffisamment rapide.

`C.py`


for _ in range(int(input())):
    n=int(input())
    a=list(input())
    b=list(input())
    for i in range(n):
        if a[i]>b[i]:
            print(-1)
            break
    else:
        s=sorted(list(set(a)|set(b)))
        ans=0
        for j in s:
            f=False
            x=set()
            for k in range(n):
                if a[k]==j and a[k]!=b[k]:
                    x.add(b[k])
                    f=True
            x=sorted(list(x))
            for k in range(n):
                if a[k]==j and a[k]!=b[k]:
                    a[k]=x[0]
            if f:ans+=1
        print(ans)

Problème après D

Je vais sauter cette fois

[PYTHON] Codeforces Round # 659 (Div.2) Critique Bacha (8/5)