Ceci est un article de synthèse pour les débutants des professionnels de la compétition.
La solution que j'écris ici est écrite en regardant les commentaires et les soumissions d'autres personnes. Ce n'est peut-être pas ce que vous avez réellement soumis.
A - Duplex Printing
La question est de savoir combien de feuilles de papier sont nécessaires pour l'impression recto verso de N pages.
Divisez par 2 et arrondissez.
n = int(input())
print((n+1)//2)
B - Bingo La question est de répondre si les numéros et les cartes de bingo donnés sont alignés.
Il était difficile de rechercher le tableau à deux dimensions pour trouver l'élément, j'ai donc utilisé l'opération de remplacement par np.where en utilisant numpy. J'ai également vérifié la présence de bingo en utilisant np.sum () le long des axes vertical et horizontal.
Notez que pypy3 ne peut pas lire numpy.
import numpy as np
S = np.array([list(map(int, input().split())) for _ in range(3)])
n = int(input())
for _ in range(n):
S = np.where(S==int(input()), 0, S)
HBingo = min(np.sum(S, axis=0)) == 0
WBingo = min(np.sum(S, axis=1)) == 0
SBingo = S[2][0] == 0 and S[1][1] == 0 and S[0][2] == 0
BSBingo = S[0][0] == 0 and S[1][1] == 0 and S[2][2] == 0
if HBingo or WBingo or SBingo or BSBingo:
print('Yes')
exit()
print('No')
Cependant, il semble beaucoup plus rapide de rechercher docilement le tableau sans utiliser numpy.
C - Guess The Number
C'est un problème de renvoyer le nombre minimum qui satisfait les conditions du nombre de chiffres reçus et du nombre.
Tout d'abord, créez chaque chiffre avec "-1" comme état initial. Chaque fois qu'une entrée en est reçue, elle est réécrite lorsque "la valeur à réécrire est -1" ou "le nombre à réécrire n'est pas en conflit" est satisfait. En cas de conflit, sortez -1 et quittez.
Enfin, convertissez le chiffre (-1) qui n'a pas été réécrit à la valeur minimale, et vous avez terminé. Convertissez en 1 s'il s'agit du premier chiffre en partant de la gauche (notez que 0 est autorisé lorsque N = 1), et en 0 si c'est après cela.
Notez que le premier chiffre ne peut pas être changé en 0 lorsque $ N \ geq2 $ (une perte).
N, M = map(int, input().split())
ans = [-1] * N
for _ in range(M):
i, n = map(int, input().split())
if (ans[i-1] == -1 or ans[i-1] == n) and not(N > 1 and i == 1 and n == 0):
ans[i-1] = n
else:
print(-1)
exit()
ans = [n if n != -1 else 0 for n in ans]
if ans[0] == 0 and N > 1:
ans[0] = 1
print(*ans, sep='')
D - Friend Suggestions
Compte tenu du statut de SNS, il s'agit de savoir combien de relations sont «amis d'amis» et «ni amis ni ennemis».
Je ne savais pas comment savoir s'ils étaient connectés, alors j'ai abandonné.
J'ai vu le commentaire. Le nombre de candidats amis est le nombre obtenu en soustrayant «le nombre de vos amis», «le nombre de vous-même (1)» et «le nombre de personnes bloquant dans le cluster» du «nombre de personnes dans le cluster qui vous inclut». Sera.
Par conséquent, en tant que tableau, le tableau «clusterI» qui stocke «le cluster auquel appartient chaque élément», le tableau «clusterN» qui stocke «le nombre de personnes dans chaque cluster» et le «nombre de personnes bloquant avec des amis» à dessiner ultérieurement Créez trois tableaux de ʻout`.
clusterI stocke l'index le plus bas du cluster. C'est le problème. Le code suivant modifie le processus de réécriture de l'index avec for.
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def unite(x, y):
CX = clusterI[x]
CY = clusterI[y]
if CX != CY:
if CX < CY:
CX, CY = CY, CX
clusterN[CX] += clusterN[CY]
for i in range(n):
if clusterI[i] == CY:
clusterI[i] = CX
for _ in range(m):
a, b = map(int, input().split())
unite(a-1, b-1)
out[a-1] -= 1
out[b-1] -= 1
for _ in range(k):
a, b = map(int, input().split())
if clusterI[a-1] == clusterI[b-1]:
out[a-1] -= 1
out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)
C'est TLE.
Je l'ai réécrit avec une fonction récursive, faisant référence au code des autres. Je suis passé par là. Le grand défi est que vous n'avez pas les connaissances sur l'exploration.
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def find(x):
if clusterI[x] != x:
minI = find(clusterI[x])
clusterI[x] = minI
return minI
else:
return x
def unite(x, y):
CX = find(x)
CY = find(y)
if CX != CY:
if CX > CY:
CX, CY = CY, CX
x, y = y, x
clusterN[CX] += clusterN[CY]
clusterI[CY] = CX
for _ in range(m):
a, b = map(int, input().split())
unite(a-1, b-1)
out[a-1] -= 1
out[b-1] -= 1
for _ in range(k):
a, b = map(int, input().split())
if find(a-1) == find(b-1):
out[a-1] -= 1
out[b-1] -= 1
out = [out[i] + clusterN[find(i)] - 1 for i in range(n)]
print(*out)
E - Simple String Queries
C'est un problème de vérifier le nombre de types de caractères en répétant l'opération de conversion de la chaîne de caractères en fonction de l'entrée.
Comme toujours, j'ai fait le code suivant d'une manière simple.
import collections
N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
Q1, Q2, Q3 = input().split()
if Q1 == '1':
S[int(Q2)-1] = ord(Q3)
else:
print(len(collections.Counter(S[int(Q2)-1: int(Q3)])))
TLE est sorti.
J'ai regardé le commentaire.
Créez un tableau de 26 éléments avec des informations sur A à Z. La position où le caractère apparaît est stockée dans l'élément. Lors du comptage, vérifiez 26 caractères pour voir s'ils sont dans la plage spécifiée.
Ce qui suit est la mise en œuvre de cela tel qu'il est.
N = int(input())
S = list(str(input()))
def ordN(x):
return ord(x) - ord('a')
li = [[] for _ in range(26)]
for i,s in enumerate(S):
li[ordN(s)].append(i)
for i in range(int(input())):
Q1, Q2, Q3 = input().split()
if Q1 == "1":
Q2 = int(Q2) - 1
if S[Q2] != Q3:
li[ordN(S[Q2])] = [n for n in li[ordN(S[Q2])] if n != Q2]
li[ordN(Q3)].append(Q2)
S[Q2] = Q3
else:
Q2, Q3 = int(Q2)-1, int(Q3)-1
count = 0
for j in range(26):
if [True for n in li[j] if Q2 <= n and n <= Q3]:
count += 1
print(count)
À ce rythme, TLE apparaîtra toujours. Réécrire en faisant référence au code des autres. Conserve la position d'apparence des caractères dans un état trié. De plus, le remplacement et le contrôle de la position sont effectués par dichotomie. La bibliothèque «bisect» est utilisée pour la dichotomie.
Les deux fonctions suivantes sont utilisées.
bisect.bisect_left(list, x)
a = [1, 2, 4, 6, 10]
print(bisect.bisect_left(a, 4)) # 3
Renvoie la position à laquelle le deuxième argument peut être entré dans la liste du premier argument sans rompre l'ordre de tri.
bisect.insort(list, x)
a = [1, 2, 4, 6, 10]
bisect.insort(a, 4)
print(a)# [1, 2, 4, 4, 6, 10]
Insère dans la liste du premier argument sans rompre l'ordre de tri.
Le code suivant a été réécrit en utilisant ceci.
import bisect
N = int(input())
S = list(str(input()))
def ordN(x):
return ord(x) - ord('a')
li = [[] for _ in range(26)]
for i,s in enumerate(S):
li[ordN(s)].append(i)
for i in range(int(input())):
Q1, Q2, Q3 = input().split()
if Q1 == "1":
Q2 = int(Q2) - 1
if S[Q2] != Q3:
I = bisect.bisect_left(li[ordN(S[Q2])], Q2)
li[ordN(S[Q2])].pop(I)
bisect.insort(li[ordN(Q3)], Q2)
S[Q2] = Q3
else:
Q2, Q3 = int(Q2)-1, int(Q3)-1
count = 0
for j in range(26):
I = bisect.bisect_left(li[j], Q2)
if I < len(li[j]) and li[j][I] <= Q3:
count += 1
print(count)
Je suis passé par là.
C'est tout pour cet article.
Recommended Posts