Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (010 --014 Recherche complète: Recherche complète de bits)
1. Objet
Résolvez 100 questions passées que les débutants et les intermédiaires devraient résoudre en Python. L'objectif est de devenir bleu clair lorsque vous avez terminé de tout résoudre.
Cet article s'intitule "010 - 014 Recherche complète: recherche complète de bits".
2. Résumé
Jusqu'à présent, itertools.product était utilisé pour générer `(0, 1)` lors d'une recherche de bits complète, mais j'ai essayé de le résoudre avec un décalage de bits pour plus tard. ..
3. Histoire principale
010 --014 Recherche complète: recherche complète de bits
010. ALDS_5_A - Round Round
Répondre
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
check_list = [0] * (2000 * 20 + 1)
for i in range(2**n):
total = 0
for j in range(n):
if (i >> j) & 1:
total += A[j]
check_list[total] = 1
for m in M:
if check_list[m]:
print('yes')
else:
print('no')
Détermine si tous les éléments de la liste A sont "utilisés" ou "non utilisés", et si la somme est incluse dans la liste M```. Au début, j'ai utilisé le code suivant, mais c'était une triple boucle for et je ne pouvais pas y arriver à temps. Étant donné que la vitesse est plus lente lorsque le total '' calculé est comparé au m '' à chaque fois, la liste de contrôle '' avec le total '' calculé en indice est marquée. Vous devez vérifier à nouveau l'indice m '' après cela.
#Je ne peux pas arriver à temps
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
for m in M:
ans = 'no'
for i in range(2**n):
total = 0
for j in range(n):
if (i >> j) & 1:
total += A[j]
if total == m:
ans = 'yes'
break
print(ans)
Répondre
N, M = map(int, input().split()) #N est le nombre d'interrupteurs, M est le nombre d'ampoules
lights = [[0] * N for _ in range(M)]
for i in range(M):
temp = list(map(int, input().split())) #Le 0 indique le nombre de commutateurs et le premier commutateur et les suivants indiquent les commutateurs.
k = temp[0]
switches = temp[1:]
for j in range(k):
lights[i][switches[j]-1] = 1
P = list(map(int, input().split())) #S'allume lorsque le nombre divisé par 2 est égal à l'élément
answer_count = 0
for i in range(2**N): #recherche de bits
flag = True
for k in range(M): #Découvrez toutes les ampoules
count = 0
for j in range(N): #Exécuter pour les nombres avec 1 drapeau en bit
if (i >> j) & 1:
count += lights[k][j]
if count % 2 != P[k]: #Si même une ampoule ne correspond pas à p, définissez l'indicateur sur Faux et interrompez
flag = False
break
if flag: #Effacer tout et augmenter le nombre si l'indicateur est vrai
answer_count += 1
print(answer_count)
L'énoncé du problème est un peu difficile à comprendre. Comme il est difficile de gérer la façon dont l'entrée est donnée, nous avons conçu un moyen de recevoir l'entrée et avons créé un tableau bidimensionnel d'ampoules sur l'axe vertical et des commutateurs sur l'axe horizontal. Dans cet agencement, 1 est défini lorsque chaque ampoule et interrupteur sont connectés, et 0 est défini lorsqu'ils ne sont pas connectés.
Si ce tableau est créé, la recherche de bits peut être effectuée facilement. La politique est
- Créez un réseau bidimensionnel d'ampoules et d'interrupteurs comme décrit ci-dessus
- Pour tous les commutateurs, recherche de bits complète pour activer ou désactiver (réalisée par i et j dans l'instruction for)
- Vérifiez si toutes les ampoules sont allumées dans l'état de chaque bit (réalisé par k dans l'instruction for)
- Lorsque vous vérifiez si l'ampoule est allumée, mettez les informations avec
, et lorsque `` `flagdevient`` False```, ``pause '' - Comptez le nombre d'états où
devient `` Trueet c'est la réponse est.
012. AtCoder Beginner Contest 002 D --Faction
Répondre
import itertools
N, M = map(int, input().split()) #N est le nombre de membres, M est le nombre de relations
members = list(range(N))
relation = [[0] * N for _ in range(N)] #Matrice de relation
for _ in range(M):
x, y = map(int, input().split())
x -= 1
y -= 1
relation[x][y] = 1
relation[y][x] = 1
max_answer = 0
for group_num in range(1, N+1): #Essayez toutes les personnes du groupe
temp_answer = 0
for c in itertools.combinations(members, group_num): #Lister un nombre spécifique de membres
flag = True
for base_c in c: #Une personne qui vérifie les relations
for check_c in c: #Membres à vérifier
if base_c == check_c: #Ne me vérifie pas
continue
if relation[base_c][check_c] == 0: #Rompre immédiatement s'il n'y a pas de relation
flag = False
break
if not flag:
break
if flag: #OK uniquement lorsque l'indicateur est vrai
temp_answer = group_num
max_answer = max(max_answer, temp_answer)
print(max_answer)
Je ne pouvais pas le faire sans utiliser itertools, donc je n'avais pas d'autre choix que d'utiliser itertools.J'ai utilisé des combinaisons.
Le code est devenu un peu plus compliqué, mais ce que nous faisons est simple:
1. ```N```N'importe quel nombre de personnes à extraire des membres de la Diète```group_num``Spécifier. Ce 1~Je ferai tout le chemin jusqu'à N personnes
2. ```N```personne```members```De```group_num```Listez tous les cas pour extraire des personnes
3.Chaque membre(```base_c```)À propos des membres extraits en 2 ci-dessus(```check_c```)Vérifiez si vous savez
4.Veillez à ne pas vous vérifier lors de la vérification, et si vous ne faites pas connaissance, immédiatement```break```je ferai
5.Tous les législateurs(```base_c```)Lorsqu'il est jugé qu'il existe une relation de connaissance(```flag==True```)Est-ce```group_num```Est un candidat pour la réponse
6. 1~Répéter 6```group_num```La valeur maximale est la réponse
est.
---
### 013. [JOI 2008 Qualifications 5-galette de riz](https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e)
####Répondre
```python
import numpy as np
R, C = map (int, input (). Split ()) # R: vertical, C: horizontal
grid = np.array([list(map(int, input().split())) for _ in range(R)])
max_answer = 0
for i in range(2**R):
copy_grid = grid.copy () # Faire une copie car elle réécrira la matrice
for row in range(R):
if (i >> row) & 1: # Effectuer une recherche de bits pour un petit nombre de directions de ligne
copy_grid [row ,:] = copy_grid [row ,:] ^ 1 # Inverser 0,1 avec opération sur bit
col_sum = copy_grid.sum (axis = 0) # Trouver la somme de chaque colonne
for col in range(C):
if col_sum [col]> = R // 2 + 1: # 1 Retourne là où il y en a beaucoup
copy_grid[:, col] = copy_grid[:, col] ^ 1
answer = R * C - copy_grid.sum()
max_answer = max(max_answer, answer)
print(max_answer)
Comme vous pouvez le voir dans l'indice, la limite supérieure de R est petite, alors effectuez une recherche complète de R et effectuez des ajustements précis sur le côté C. La politique est 1.Essayez tous les endroits pour retourner dans la direction R 2.Après avoir retourné dans la direction R, comme un réglage fin dans la direction C, retournez uniquement la partie où il y a beaucoup de rangées qui valent 1. 3.Comptez le nombre de 0 dans la matrice résultante(Carré entier-total) 4.La réponse est celle qui prend le maximum de chaque résultat compté
est.
La méthode de conversion de 0 en 1 et de 1 en 0, qui est une opération à retourner, est une opération de bits.^1Est utilisé.
014. Square869120Contest #4 B - Buildings are Colorful!
####Répondre
import itertools
N, K = map (int, input (). Split ()) # N est le nombre de bâtiments, peignez plus de K couleur
A = list(map(int, input().split()))
N_index = list (range (1, N)) # Parce que l'extrême gauche est fixe
min_cost = float('inf')
pour target_indexes dans itertools.combinations (N_index, K-1): Essayez toutes les méthodes pour sélectionner K-1 à partir de # N_index
cost = 0
copy_A = A.copy()
for i in target_indexes:
if copy_A[i] <= max(copy_A[:i]):
diff = max (copy_A [: i]) --copy_A [i] # Pour le bâtiment cible, rendez-le 1 plus grand que max du bâtiment à gauche de celui-ci
copy_A[i] += diff + 1
cost += diff + 1
min_cost = min(min_cost, cost)
print(min_cost)
La politique est
1.Le bâtiment le plus à gauche est fixe
2.À partir du deuxième bâtimentK-1Essayez tout le chemin pour choisir
3.Index du bâtiment sélectionnétarget_indexes Entreposer et vérifier la hauteur de chaque bâtiment
4.bâtimentiLa hauteur maximale du bâtiment avant cela+Construire pour être 1iAjustez la hauteur ducostAgréger comme
5.Après avoir fait tout ce qui précèdecostLa réponse est celle qui prend la valeur minimale de
est.
Recommended Posts