Les résultats de cette fois

Impressions de cette époque

Je n'ai pas compris le problème C pendant 10 minutes, donc quand je suis passé au problème D, j'ai continué à faire des bogues dans l'implémentation **. Quand j'ai résolu le problème C après l'avoir terminé, je pouvais le résoudre en moins de 10 minutes, alors j'ai fait une erreur en résolvant le problème ... Plus tard, j'étais impatient de voir le classement de mon ami, alors j'aimerais essayer d'éliminer une telle impatience.

Problème A

C'était un problème de bâillon ...

Premièrement, $ p $ est au moins la valeur maximale contenue dans $ p \ _i, p \ _ {i + 1},… p \ _ {j-1}, p \ _j $ de l'ordre de $ 1 $ ~ $ n $ Ce sera $ j-i + 1 $. Aussi, pour tout entier non négatif $ A, B $, de $ A \ ou \ B \ geqq A, B $, $ p \ _i \ ou \ p \ _ {i + 1} \ ou \… \ ou \ p \ _ {j-1} \ ou \ p \ _ j \ geqq j-i + 1 $ tient. Par conséquent, puisque la condition est satisfaite pour toute séquence de nombres, il suffit de sortir une séquence appropriée.

`A.py`


for _ in range(int(input())):
    n=int(input())
    print(" ".join(map(str,range(1,n+1))))

Problème B

Je me demandais si cela serait fait avec BFS etc. parce que cela change la grille, mais c'était un problème de bâillon suite au problème A.

Envisagez de vous déplacer uniquement vers la droite ou vers le bas et d'atteindre (n, m) depuis n'importe quel carré. Ici, les ** modèles qui ne peuvent pas être atteints ** sont des modèles qui pénètrent vers le bas ou vers la droite. Par conséquent, pour éviter un tel schéma, toutes les cellules à l'extrême droite sont D et toutes les cellules du bas sont R. De plus, si vous pouvez modifier ces carrés, vous pouvez toujours atteindre (n, m) même si d'autres carrés sont le point de départ.

De ce qui précède, la réponse est (la cellule la plus à droite est le nombre de R) + (la cellule la plus basse est le nombre de D).

`B.py`


for _ in range(int(input())):
    n,m=map(int,input().split())
    a=[input() for i in range(n)]
    ans=0
    for i in range(m-1):
        ans+=(a[n-1][i]=="D")
    for i in range(n-1):
        ans+=(a[i][m-1]=="R")
    print(ans)

Problème C

J'avais une politique pendant le concours, mais quand je l'ai jetée et résolu le problème D, j'ai manqué de temps. ** Je vais essayer de résoudre les problèmes qui semblent être résolus **.

Premièrement, on suppose que deux côtés non orientés du sujet peuvent être dessinés pour un certain $ i $ ($ (i, j_1), (i, j_2) $) **, et ainsi de suite.

A partir de la figure ci-dessus, (le nombre de parties ①), (le nombre de parties ②), $ i <j \ _1, j \ _2 $ sont établis. De plus, comme $ j \ _1 <j \ _2, j_2 <j_1 $ tient, vous pouvez également dessiner un côté non dirigé avec $ (j_1, j_2) $, et $ i, j \ _1, j \ _2 $ Vous pouvez passer de l'un à l'autre.

Par conséquent, considérons une séquence de nombres (** événements supplémentaires **) qui n'a pas de cycle. Ici, puisque le résultat ci-dessus est valable pour tout $ i $, il n'y a pas de cycle dans la séquence ** où il n'y a pas de minimum $ i $. Une telle séquence n'est pas seulement une séquence monotone telle que $ 1,2,3,4 $, mais également une séquence telle que $ 1,4,3,2 $ qui n'a qu'une seule valeur maximale. De plus, lorsqu'il y a une valeur maximale, le nombre sera $ N $. De plus, si la valeur maximale atteint la position $ i $ ème, ce sera comme indiqué dans la figure ci-dessous.

Ici, l'ordre des nombres qui viennent à $ 1 $ ~ $ i-1 $, $ i + 1 $ ~ $ N $ th est uniquement déterminé en sélectionnant les nombres, donc la valeur maximale $ N $ est le $ i $ th. Le numéro sera organisé selon $ \ _ {N-1} C \ _ {i-1} $. De plus, si vous trouvez la somme de $ i = 1 $ ~ $ N $, alors $ \ _ {N-1} C \ _ {i-1}, \ _ {N-1} C \ _ {i-1}, …, \ _ {N-1} C \ _ {i-1} = 2 ^ {N-1} $.

D'après ce qui précède, le nombre de colonnes sans cycles est $ 2 ^ {N-1} $, et le nombre total de colonnes avant est $ N! $, Donc $ N! -2 ^ {N-1} $ est la réponse.

`C.py`


n=int(input())
def modpow():
    ret=1
    for i in range(n-1):
        ret*=2
        ret%=(10**9+7)
    return ret
def perm():
    ret=1
    for i in range(n):
        ret*=(i+1)
        ret%=(10**9+7)
    return ret

print((perm()-modpow())%(10**9+7))

Problème D

Le problème est de trouver le nombre minimum de fois pour changer le nombre de sorte que tous les nombres de 1 dans une sous-matrice carrée de n'importe quelle longueur paire soient impairs.

Ici, si vous combinez quatre matrices carrées d'une longueur de 2, vous pouvez créer une matrice carrée d'une longueur de 4, mais lorsque le nombre de 1 dans la matrice carrée d'une longueur de 2 est impair, la longueur est Le nombre de 1 dans une matrice carrée avec un 4 est pair. Par conséquent, quand il est $ n, m \ geqq 4 $, il est nécessaire de sortir -1. Dans ce qui suit, considérons le cas de $ n <4 $ ou $ m <4 $. Notez également qu'il s'agit de $ n \ leqq m $ (je ne l'ai pas remarqué lors du concours).

(1) Lorsque $ n = 1 $

Comme il n'y a pas de sous-matrice carrée de longueur égale, il n'est pas nécessaire de la changer, il suffit de sortir 0.

(2) Quand $ n = 2,3 $

Il y a toujours un nombre minimum de fois dans ces cas (la preuve est omise). Au début, je pensais utiliser la méthode gourmande pour décider les colonnes dans l'ordre **, mais j'ai abandonné la méthode gourmande car la classification des cas est compliquée et la ** méthode gourmande ne peut être justifiée **. J'ai fait.

Ici, ** DP **, considérant que ** les colonnes sont décidées dans l'ordre ** et que chaque colonne ne vaut que 2 $ ^ n $ à partir de $ n = 2,3 $ ** Je pense que vous pouvez avoir l'idée. DP peut être défini comme suit.

$ dp [i] [j]: = $ (Nombre minimum de changements lorsque la colonne $ i $ est fixe et devient $ j $ lorsque la colonne $ i $ est considérée comme un nombre binaire)

Ici, considérons la transition de DP de $ dp [i-1] [j] $ à $ dp [i] [k] $. Puisque $ 1 \ leqq j, k \ leqq 2 ^ n $, la transition est représentée par une double boucle (** il y a plusieurs états! **). De plus, lorsque $ j et k $ sont déterminés, il est calculé à l'avance si le nombre de 1 dans les colonnes $ i-1 $ et $ i $ dans la matrice carrée d'une longueur de 2 est tout impair. Peut être fait (bitcheck [j] [k]). De plus, le nombre d'essais requis pour passer de $ a [i] $ à $ k $ peut être pré-calculé (bitcalc [a [i]] [k] vu comme un nombre binaire). Sur cette base, la transition de DP est la suivante.

Quand $ bitcheck [j] [k] = True $, $ dp [i] [k] = dp [i-1] [j] + bitcalc [a [i] $ notation en bits $] [k] $

De plus, étant donné que TL est assez strict et ** beaucoup d'entrée **, vous devez utiliser ʻinput = sys.stdin.readline` pour accélérer l'entrée (cela peut ne pas être nécessaire si l'implémentation est bonne). Hmm.).

`D.py`


import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[[int(j) for j in input()[:-1]] for i in range(n)]
if n>=4 and m>=4:
    print(-1)
    exit()
if n==1 or m==1:
    print(0)
    exit()
inf=10000000000000
if n==2 or m==2:
    bitcheck=[[0]*4 for i in range(4)]
    for j in range(4):
        for k in range(4):
            for i in range(1):
                if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
                    bitcheck[j][k]=False
                    break
            else:
                bitcheck[j][k]=True
    bitcalc=[[0]*4 for i in range(4)]
    for j in range(4):
        for k in range(4):
            for i in range(2):
                if ((j>>i)&1)^((k>>i)&1):
                    bitcalc[j][k]+=1
    if n==2:
        n,m=m,n
        b=[list(x) for x in zip(*a)]
    else:
        b=[i for i in a]
    dp=[[inf]*4 for i in range(n)]
    for i in range(n):
        if i!=0:
            for j in range(4):
                for k in range(4):
                    if bitcheck[j][k]:
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2][k])
        else:
            for k in range(4):
                dp[i][k]=bitcalc[b[i][0]+b[i][1]*2][k]
    print(min(dp[n-1]))
    exit()
if n==3 or m==3:
    bitcheck=[[0]*8 for i in range(8)]
    for j in range(8):
        for k in range(8):
            for i in range(2):
                if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
                    bitcheck[j][k]=False
                    break
            else:
                bitcheck[j][k]=True
    bitcalc=[[0]*8 for i in range(8)]
    for j in range(8):
        for k in range(8):
            for i in range(3):
                if ((j>>i)&1)^((k>>i)&1):
                    bitcalc[j][k]+=1
    if n==3:
        n,m=m,n
        b=[list(x) for x in zip(*a)]
    else:
        b=[i for i in a]
    dp=[[inf]*8 for i in range(n)]
    for i in range(n):
        if i!=0:
            for j in range(8):
                for k in range(8):
                    if bitcheck[j][k]:
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k])
        else:
            for k in range(8):
                dp[i][k]=bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k]
    print(min(dp[n-1]))
    exit()

Après le problème E

Je vais sauter cette fois

Codeforces Round # 663 (Div.2) Examen Bacha (8/13)