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

Les résultats de cette fois

スクリーンショット 2020-08-13 14.18.37.png

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.

IMG_0536.JPG

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.

IMG_0537.PNG

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

Recommended Posts

Codeforces Round # 658 (Div.2) Examen Bacha (7/29)
Codeforces Round # 654 (Div.2) Critique Bacha (8/18)
Codeforces Round # 594 (Div.2) Examen Bacha (10/29)
Codeforces Round # 609 (Div.2) Critique Bacha (10/8)
Codeforces Round # 597 (Div.2) Examen Bacha (10/27)
Codeforces Round # 651 (Div.2) Critique Bacha (8/20)
Codeforces Round # 659 (Div.2) Critique Bacha (8/5)
Codeforces Round # 610 (Div.2) Critique Bacha (10/5)
Codeforces Round # 479 (Div.3) Examen Bacha (9/25)
Codeforces Round # 603 (Div.2) Examen Bacha (10/15)
Codeforces Round # 600 (Div.2) Examen Bacha (10/21)
Codeforces Round # 481 (Div.3) Examen Bacha (9/24)
Codeforces Round # 639 (Div.2) Examen Bacha (9/4)
Codeforces Round # 521 (Div.3) Examen Bacha (10/9)
Codeforces Round # 652 (Div.2) Examen Bacha (8/24)
Codeforces Round # 606 (Div.3) Examen Bacha (10/13)
Codeforces Round # 613 (Div.2) Examen Bacha (10/1)
Codeforces Round # 665 (Div.2) Examen Bacha (8/23)
Codeforces Round # 592 (Div.2) Examen Bacha (11/03)
Codeforces Round # 662 (Div.2) Critique Bacha (8/8)
Codeforces Round # 618 (Div.2) Examen Bacha (9/26)
Codeforces Round # 648 (Div.2) Critique Bacha (9/5)
Codeforces Round # 676 (Div.2) Examen Bacha (10/31)
Codeforces Round # 675 (Div.2) Examen Bacha (10/30)
Codeforces Round # 486 (Div.3) Examen Bacha (9/23)
Codeforces Round # 671 (Div.2) Examen Bacha (9/22)
Codeforces Round # 669 (Div.2) Examen Bacha (9/9)
Codeforces Round # 672 (Div.2) Examen Bacha (10/16)
Codeforces Round # 638 (Div.2) Examen Bacha (9/16)
Codeforces Round # 663 (Div.2) Examen Bacha (8/13)
Codeforces Round # 668 (Div.2) Examen Bacha (9/7)
Codeforces Round # 663 (Div.2) Examen Bacha (8/16)
Codeforces Round # 609 (Div.2) Examen Bacha (10/6)
Codeforces Round # 645 (Div.2) Critique Bacha (9/10)
Codeforces Round # 664 (Div.2) Examen Bacha (8/13)
Codeforces Round # 660 (Div.2) Critique Bacha (8/4)
Codeforces Round # 643 (Div.2) Révision
Codeforces Round # 679 (Div.2) Révision (10/25)
Codeforces Round # 657 (Div.2) Révision
Code de l'éducation forces Round 93 Bacha Review (8/17)
Code de l'éducation forces Round 94 Bacha Review (9/3)
Code de l'éducation forces Round 91 Bacha Review (7/28)
Code de l'éducation forces Round 88 Bacha Review (8/4)
Code de l'éducation forces Round 86 Bacha Review (9/17)
Code de l'éducation forces Round 89 Bacha Review (9/8)
Code de l'éducation forces Round 92 Bacha Review (7/30)
Code de l'éducation forces Round 90 Bacha Review (8/19)
Codeforces Round # 609 (Div.2) (jusqu'à B)
Code de l'Éducation Forces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Round # 626 B.Compte des sous-rectangles