ABC147 C --HonestOrUnkind2 [Python]

・ ABC147 C --HonestOrUnkind2

Le témoignage d'un total de N personnes, honnêtes et hostiles, est inscrit. La question est de savoir combien de personnes honnêtes peuvent exister au maximum. J'ai commencé à utiliser AtCoder pour m'habituer à Python à partir de décembre, et j'ai touché aux questions des dernières personnes, mais quand j'ai vu l'entrée, ma tête semblait malade. (Il est important de lire le problème en écrivant des phrases et des chiffres dans le cahier).

Solution

Les personnes honnêtes sont représentées par "1" et les personnes peu amicales sont représentées par "0", il est donc bon d'avoir l'état Nbit et de vérifier toutes les rues. C'est une recherche un peu complète.

Si N = 3, le bit passe de 000 à 111 dans l'ordre. "001" vérifie le témoignage de la première personne, "010" vérifie le témoignage de la deuxième personne, "011" vérifie le témoignage de la première et de la deuxième personne, et ainsi de suite. (Pourquoi hésitait-il? "Maintenant, en 001, la première personne est honnête avec la deuxième personne, donc à ce moment je dois vérifier le témoignage de la deuxième personne, puis le témoignage de la deuxième personne donne également le témoignage de la nième personne ... Il ne sert à rien de rechercher tous les bits ... Vous n'avez qu'à vérifier le témoignage de la personne qui a le mors à ce moment-là et si l'état de chaque personne est correct.)

répondre

    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()

Je ne peux pas nier le sentiment que c'est un putain de code assez redondant, mais pour le moment, c'est un code AC. Il a fallu une heure ou deux pour comprendre même la question C. ・ Le sentiment de libération quand il est résolu est bon, mais dans le combat actuel, il n'a pas atteint le stade où il peut être résolu rapidement, il est donc encore nécessaire de faire des efforts. v ・. ・ V