résultat

スクリーンショット 2020-10-03 11.47.56.png

Impressions

Je pense que le mouvement minimum a été fait. Je pense que c'était bien de pouvoir lire le problème D sans abandonner. J'ai pu comprendre les problèmes B et C en regardant les réponses, mais je vais sauter cette fois parce que c'était une solution qui semble difficile à apprendre.

Problème A

Normalement, j'aimerais considérer DP pour un tel problème, mais c'est difficile car $ n $ vaut au plus 10 $ ^ {18} $. Par conséquent, nous allons mener l'expérience en pensant qu'elle peut avoir une sorte de règle **.

De plus, quand aux coordonnées $ x $, $ x + 1 $ et $ x + 6 $ sont tous les deux un sur-ensemble de jeu, les deux $ x + 2 $ et $ x + 5 $ sont un sur-ensemble de jeu, $ x + 3 Si $ et $ x + 4 $ sont tous les deux un sur-ensemble de jeu, alors ce $ x $ est également un sur-ensemble de jeu. Par conséquent, si vous regardez le sur-volume de jeu ci-dessus, ** le sur-volume de jeu augmentera dans l'ordre **. ** Expérimentez pour réfléchir à la façon d'augmenter la masse excessive du jeu ** et la figure ci-dessous.

Si vous l'écrivez comme ci-dessus, lorsqu'il y a un ensemble de surmasse de jeu, les cases qui sont ** 9 ou plus de la plus petite surasse de jeu (✳︎) de ce groupe seront toujours la surasse de jeu **. Par conséquent, lorsque le carré de (✳︎) existe aux coordonnées de 10 ou plus, le jeu est terminé. Par conséquent, s'il y a un carré (✳︎), No est sorti et sort. Aussi, pour déterminer l'existence d'un ensemble de surmasse de jeu, préparez une structure d'ensemble «b» qui gère le sur-ensemble de jeu, et dans l'ordre à partir de la plus grande masse de jeu $ x $, $ x + 1, x + 3, x + 5 Découvrez si l'un des $ est inclus dans le $ b $.

Ensuite, lorsque des carrés ** (squ) existent à des coordonnées de 9 ou moins **, recherchez le carré sur lequel le jeu est terminé par le carré 9 → 1, et les nouveaux jeux créés sont de l'ordre de $ b $. Tout ce que vous avez à faire est de le stocker et de déterminer finalement si $ b $ contient 1.

`A.py`


n,k=map(int,input().split())
a=list(map(int,input().split()))
b=set(a)
for i in range(k-1,-1,-1):
    if a[i]<=9:
        break
    else:
        if a[i]+1 in b:
            print("No")
            exit()
        if a[i]+3 in b:
            print("No")
            exit()
        if a[i]+5 in b:
            print("No")
            exit()
for j in range(9,0,-1):
    if j in b:
        if j+1 in b:
            if j-3>=1:
                b.add(j-3)
        if j+3 in b:
            if j-2>=1:
                b.add(j-2)
        if j+5 in b:
            if j-1>=1:
                b.add(j-1)
if 1 in b:
    print("No")
    exit()
print("Yes")

Problème B, C

Je vais sauter cette fois.

Problème D

Je pense que c'était le problème le plus simple cette fois.

Les scores peuvent être ** calculés pour chaque bit ** car il n'y a que des opérations et au niveau du bit ou et du bit. De plus, il n'y a que deux valeurs initiales pour chaque bit, 0 ou 1, et si vous ** pré-calculez le score pour chaque bit **, vous ne pouvez voir tous les bits que lorsque la valeur initiale est donnée ** Vous pouvez le trouver sur. Par conséquent, le tableau à enregistrer dans le pré-calcul est défini comme check et $ check [i] [j]: = $ (score lorsque la valeur initiale du bit $ i $ est $ j $, mais $ j = 0,1 $) (✳︎). Nous envisagerons de le demander ci-dessous.

Pensez maintenant à calculer le score en regardant le bit $ i $ et en regardant $ a \ _i $ dans l'ordre lorsque sa valeur initiale est $ k $. De plus, l'entier que j'ai selon l'énoncé du problème est $ x $ (bien sûr, $ x = k $ au début). Et quand vous regardez le $ j $ e entier (le bit $ i $ est représenté par $ a \ _ {ji} $), vous avez l'entier $ x $ (mais la valeur du bit $ i $) Étant donné que l'opération à effectuer est soit $ et $ soit $ ou $. À ce stade, le changement de $ x $ et le changement de $ chèque [i] [k] $ sont indiqués dans le tableau ci-dessous.

En créant un tableau comme ci-dessus **, vous pouvez saisir visuellement $ x $ et le score **, et vous pouvez simplement faire une boucle autour des variables $ i, k, j $. .. De plus, si vous avez $ check [i] [j] $, vous pouvez facilement calculer la requête simplement en ajoutant et en multipliant.

(✳︎)… Pour être exact, $ check [i] [j] \ times 2 ^ i $ est le score pour ce bit.

`D.py`


n,q=map(int,input().split())
a=list(map(int,input().split()))
check=[[0,0] for i in range(32)]
s=list(map(int,input()))
for i in range(32):
    #Si l'état initial est 0 ou 1
    for k in range(2):
        x=k
        for j in range(n):
            if (a[j]>>i)&1:
                if s[j]==0:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=0
                        x=1
                else:
                    if x==0:
                        check[i][k]+=1
                        x=1
                    else:
                        check[i][k]+=0
                        x=1
            else:
                if s[j]==0:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=1
                        x=0
                else:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=0
                        x=1
#print(check)
t=list(map(int,input().split()))
for _ in range(q):
    z=t[_]
    ans=0
    for i in range(32):
        ans+=(check[i][(z>>i)&1]*(2**i))
        #print(ans)
    print(ans)

Après le problème E