Das Zeugnis von insgesamt N Personen, ehrlich und unfreundlich, wird eingegeben. Die Frage ist, wie viele ehrliche Menschen maximal existieren können. Ich habe ab Dezember angefangen, AtCoder zu machen, um mich an Python zu gewöhnen, und ich habe frühere Fragen der neuesten Leute angesprochen, aber als ich die Eingabe sah, schien mein Kopf einen Fuß zu haben. (Es ist wichtig, das Problem zu lesen, während Sie Sätze und Zahlen in das Notizbuch schreiben.)
Ehrliche Menschen werden durch "1" und unfreundliche Menschen durch "0" dargestellt. Es ist also gut, den Nbit-Status zu haben und alle Straßen zu überprüfen. Es ist eine etwas vollständige Suche.
Wenn N = 3 ist, wird das Bit der Reihe nach von 000 auf 111 gedreht. "001" überprüft das Zeugnis der ersten Person, "010" überprüft das Zeugnis der zweiten Person, "011" überprüft das Zeugnis der ersten und zweiten Person und so weiter. (Worin haben Sie sich verlaufen? "Jetzt 001 ist die erste Person ehrlich mit der zweiten Person, daher muss ich zu diesem Zeitpunkt das Zeugnis der zweiten Person überprüfen, und dann wird das Zeugnis der zweiten Person auch das Zeugnis der n-ten Person sein ... Es macht keinen Sinn, alle Bits zu suchen ... Sie müssen nur das Zeugnis der Person überprüfen, die zu diesem Zeitpunkt das Gebiss hat und ob der Zustand jeder Person korrekt ist.)
import sys
def kensho(x,tlist):
for lis in tlist:
if((x>>(lis[1]-1)) & 1 == lis[2]):
pass
else:
return -1
return bin(x).count('1')
def main():
N = int(input())
xy=[]
ans=0
for i in range(1,N+1):
An= int(input())
for j in range(0,An):
x, y = map(int, input().split())
xy.append([i,x,y])
cnt = N
tlist=[]
for x in range (2 ** cnt):
for y in range(cnt):
if((x>>y) & 1):
for z in xy:
if(z[0]==y+1):
tlist.append(z)
anstack = kensho(x,tlist)
if(ans<anstack):
ans=anstack
del tlist[:]
print(ans)
main()
Ich kann nicht leugnen, dass es ein ziemlich redundanter verdammter Code ist, aber im Moment ist es ein AC-Code. Es dauerte ein oder zwei Stunden, um selbst die C-Frage zu verstehen. ・ Das Gefühl der Befreiung, wenn es gelöst ist, ist gut, aber im eigentlichen Wettbewerb hat es nicht das Stadium erreicht, in dem es schnell gelöst werden kann, so dass es immer noch notwendig ist, Anstrengungen zu unternehmen. v ・. ・ V.
Recommended Posts