Les résultats de cette fois

Impressions de cette époque

Je pense que ça s'est bien passé cette fois. Cependant, je suis déçu car je n'ai pas pu résoudre le problème D qui semblait être résolu à temps en raison du chevauchement avec le déjeuner. Cependant, il me semblait être capable de résoudre le problème à ce niveau, alors je pensais avoir un peu grandi. Cette fois, j'ai pu régler le problème calmement, donc je pense que c'est la raison de la victoire.

Problème A

Sur la base des valeurs données de $ r, g, b, w $, il est jugé si chaque caractère devient une circonstance une fois arrangé. De plus, vous pouvez sélectionner $ r, g, b $ un par un et les changer en $ w $ autant que possible, mais ** cette opération ne change pas les cotes et les cotes de chacun **, donc ceci Vous n'avez qu'à penser à deux façons de le faire une fois ou non.

En vertu de cela, lorsque la somme des valeurs de $ r, g, b, w $ (la longueur de la phrase) est paire, toute valeur de ** $ r, g, b, w $ est paire **. Si vous en avez un, vous pouvez le faire. De plus, en changeant $ r, g, b $ en $ w $ une fois, le pair et la bizarrerie de ** $ r, g, b, w $ sont inversés **, donc $ r, g, b, w $ Vous pouvez faire une diffusion si une valeur est impaire.

Par contre, lorsque la durée de la diffusion est impaire, un seul des ** $ r, g, b, w $ doit être impair **. De plus, compte tenu de l'inversion du pair et du impair, il est possible de faire une circulation même si un seul des $ r, g, b, w $ est pair.

`A.py`


for _ in range(int(input())):
    r,g,b,w=map(int,input().split())
    if (r+g+b+w)%2==0:
        if r%2==0 and g%2==0 and b%2==0 and w%2==0:
            print("Yes")
        elif r%2==1 and g%2==1 and b%2==1 and w%2==1:
            print("Yes")
        else:
            print("No")
    else:
        x=[r%2,g%2,b%2,w%2]
        if x.count(1)==1:
            print("Yes")
        elif x.count(0)==1 and r>0 and g>0 and b>0:
            print("Yes")
        else:
            print("No")

Problème B

Pensez à faire avancer les échecs comme Luke et à suivre les cases sur n'importe quelle grille. Même si vous suivez les nuages sombres, le 埒 ne s'ouvrira pas, alors considérez ** suivre dans un certain ordre **.

Au début, je pensais que je le suivrais sur un tourbillon, mais je l'ai trouvé encombrant à mettre en œuvre, alors j'ai pensé que je le suivrais ligne par ligne **. En d'autres termes, pensez à suivre comme indiqué dans la figure ci-dessous.

Ici, seulement (1) après avoir tracé toutes les lignes supérieures, ** continuez à remonter jusqu'à la ligne inférieure ** et (2) ** lorsque vous vous déplacez entre les lignes, vous devez vous déplacer ** par les carrés de contact. Attention, l'implémentation ressemble à ceci:

① peut être implémenté en concaténant avec list (range (x, -1, -1)) + list (range (x + 1, n)), et ② indique si les carrés en contact sont la colonne la plus à gauche ou la colonne la plus à droite. Il peut être implémenté en divisant le cas par.

`B.py`


n,m,x,y=map(int,input().split())
x-=1;y-=1
ans=[]
ans.append([x,y])

now=0
for i in list(range(x,-1,-1))+list(range(x+1,n)):
    now=1-now
    if i==x:
        ans+=[[i,j] for j in range(m) if j!=y]
    else:
        if now:
            ans+=[[i,j] for j in range(m)]
        else:
            ans+=[[i,j] for j in range(m)][::-1]
for i in ans:
    print(i[0]+1,i[1]+1)

Problème C

Au début, j'ai pensé à décider pour que les bits ne se tiennent pas dans l'ordre à partir du chiffre supérieur, mais j'ai senti qu'il serait difficile de décider goulûment du chiffre du milieu **.

Lorsque vous choisissez quelque chose (nombre) comme ce problème, les perspectives s'améliorent souvent lorsque l'on considère DP . De plus, c'est aussi un facteur décisif que le calcul du bit qui facilite la sauvegarde de l'état et que le ou pour chaque bit ne prenne que cette plage de $ 0 \ leqq a_i, b_i <2 ^ 9 $ ( limite le nombre d'états **). Par conséquent, considérez le DP suivant.

$ dp [i] [j]: = $ (Y a-t-il un cas où c'est $ j $ lors de la prise ou pour chaque bit jusqu'à $ a_i $)

Considérant un tel DP, si $ dp [i-1] [j] = 1 $ et $ b_k (1 \ leqq k \ leqq m) $ est sélectionné pour $ a_i $, c'est comme suit. Sera.

dp[i][j\|(a\_i \\& b\_k)]=1

Par conséquent, ce DP peut être calculé en environ $ n \ fois m \ fois 2 ^ 9 $ fois, vous pouvez donc écrire un programme suffisamment rapide.

`C.py`


n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
change=[[a[i]&b[j] for j in range(m)]for i in range(n)]
dp=[[0]*(2**9) for i in range(n)]

for i in range(n):
    if i==0:
        for k in range(m):
            dp[0][change[i][k]]=1
        continue
    for j in range(2**9):
        if dp[i-1][j]==1:
            for k in range(m):
                dp[i][j|change[i][k]]=1

for j in range(2**9):
    if dp[-1][j]==1:
        print(j)
        break

Problème D

Au début, j'ai mal compris le problème et j'ai pensé que le tableau $ a $ serait traité tel quel. ** Si vous regardez l'exemple, ** cela n'aurait pas dû être une erreur, alors réfléchissez-y et utilisez-le ensuite (dans ce cas, vous pouvez le résoudre en utilisant DP).

Tout d'abord, il est évident que vous souhaitez sélectionner le plus grand. À ce stade, si $ a \ _i> m $, il ne sera pas possible de le sélectionner dans le $ d $ jour suivant, donc commencez par le diviser en l'élément ** $ a \ _i> m $ et l'élément $ a \ _i \ leqq m $. ** Stocker dans le tableau ʻe, f`. De plus, on suppose que «e» et «f» sont classés par ordre décroissant.

Ici, si vous connaissez le nombre d'éléments qui sont ** $ a \ _i> m $, vous pouvez connaître le nombre d'éléments qui peuvent être sélectionnés parmi les éléments qui sont ** $ a \ _i \ leqq m $, donc ** $ a \ _i Supposons qu'il y ait des éléments $ k $> m $ **. De plus, comme vous pouvez facilement le voir, $ k $ est inférieur ou égal à len (f). Ici, en considérant l'arrangement de $ k $ $ a \ _i (> m) $ pour que $ a \ _i (\ leqq m) $ puisse être sélectionné autant que possible, l'arrangement suivant est optimal.

Par conséquent, à ce moment, $ a \ _i (\ leqq m) $ peut être sélectionné pour $ n- $ {$ (k-1) \ times (d + 1) + 1 $}. Notez également que $ (k-1) \ times (d + 1) + 1 \ leqq n $ doit être satisfait (le maximum $ k $ qui satisfait cela est $ K '$). .. De plus, même si ** $ n- $ {$ (k-1) \ times (d + 1) + 1 $} dépasse len (e), seuls ceux inclus dans ʻe` peuvent être sélectionnés (✳︎). ) ** Notez s'il vous plaît.

De plus, si vous augmentez ** $ k $ de 1, le nombre qui peut être sélectionné parmi ʻe` diminue de $ d + 1 $ **, donc ** $ k $ à $ 0 $ ~ $ K '$ tout en gérant la différence ** Recherchez le plus grand nombre d'entre eux. De plus, $ k = 0 \ rightarrow 1 $ augmente de $ 1 $ au lieu de $ d + 1 $, donc considérez $ k = 0 $ séparément. À ce stade, vous devriez considérer la somme de «e».

De cette façon, la valeur maximale obtenue pour chaque $ k $ devrait être sortie comme réponse.

(J'ai remarqué plus tard, mais je pense que l'implémentation de (✳︎) était plus claire si j'essayais de réduire ** $ k $.)

`D.py`


n,d,m=map(int,input().split())
a=list(map(int,input().split()))
e,f=[i for i in a if i<=m],[i for i in a if i>m]
e.sort(reverse=True)
f.sort(reverse=True)
c=len(e)
if c==n:
    print(sum(a))
    exit()
#a[i]>m peut être sélectionné de manière appropriée jusqu'à max
l=1
r=min((n-1)//(d+1)+1,len(f))
#k's range 
#e,f 's sum
ans=sum(e)
nowe,nowf=0,0
for i in range(l,r+1):
    if i==l:
        nowe=sum(e[:n-(1+(l-1)*(d+1))])
        nowf=sum(f[:l])
        ans=max(nowe+nowf,ans)
        continue
    nowe-=sum(e[n-(1+(i-1)*(d+1)):n-(1+(i-1-1)*(d+1))])
    nowf+=f[i-1]
    ans=max(nowe+nowf,ans)
print(ans)

Après le problème E

Je vais sauter cette fois

[PYTHON] Codeforces Round # 664 (Div.2) Examen Bacha (8/13)