J'ai participé à AtCoder ABC177, je vais donc l'afficher comme un enregistrement.
Takahashi rencontre Aoki. Le lieu de rendez-vous est à D mètres de la maison de Takahashi, et l'heure de la réunion est T minutes plus tard. M. Takahashi quittera désormais sa maison et se rendra directement au lieu de réunion à S mètres par minute. Serez-vous à temps pour la réunion?
La distance maximale que Takahashi, qui peut se déplacer à S mètres par minute, peut parcourir en T minutes est S * T. Vous pouvez comparer cette valeur avec D. (j'ai obtenu 1WA par erreur pour l'inégalité ())
d, t, s = map(int, input().split())
if s*t >= d:
print("Yes")
else:
print("No")
Deux chaînes S et T sont données. Réécrivez quelques lettres de S pour que T soit une sous-chaîne de S. Au moins combien de caractères dois-je réécrire?
De len (S)> = len (T), déplacez la chaîne de caractères T dans S, et la réponse est la valeur obtenue en soustrayant le nombre maximum de caractères correspondants de len (T).
s = input()
t = input()
sl = len(s)
tl = len(t)
cnt = 0
ans = 0
for i in range(sl-tl+1):
for j in range(tl):
if t[j] == s[i+j]:
cnt += 1
ans = max(cnt, ans)#ans:Nombre maximum de caractères correspondants
cnt = 0
print(tl - ans)
N entiers A1,…, AN sont donnés. Trouvez la somme de Ai × Aj pour toutes les paires (i, j) qui satisfont 1 ≤ i <j ≤ N avec mod (10 ** 9 + 7).
Si vous tournez honnêtement l'instruction for deux fois, ce sera TLE plutôt que O (N ^ 2) ... Quand je l'ai écrit pour le moment, j'ai trouvé ce qui suit. Considérons le temps de ex.i = 1, 2, .... Soit somme = A1 + A2 + ... AN. Quand i = 1 A1 x A2 + A1 x A3 + A1 x A4 + ・ ・ ・ ・ + A1 x AN = A1 x (sum - A1) Quand i = 2 A2 x A3 + A2 x A4 + A2 x A5 + ・ ・ ・ ・ + A2 x AN = A2 x (sum - A1 - A2) Si tel est le cas, il peut être supprimé par O (N). Si vous implémentez cela en Python,
n = int(input())
A = [0]+list(map(int, input().split()))
mod = 10**9 + 7
S = sum(A)
ans = 0
for i in range(1, n):
ans += A[i]*(S-A[i])
ans %= mod
S -= A[i]
print(ans)
Il y a N personnes de 1 à N. Vous recevrez M informations indiquant que "People Ai et People Bi sont amis". La même information peut être donnée plusieurs fois. Si X et Y sont amis et Y et Z sont amis, alors X et Z sont aussi amis. De plus, il n'y a pas d'amitiés qui ne peuvent être dérivées de M éléments d'information. Evil Takahashi essaie de diviser ces N personnes en plusieurs groupes et de créer une situation où tout le monde n'a «pas d'amis dans le même groupe». Combien de groupes dois-je diviser au minimum?
Répondez simplement au nombre maximum d'éléments dans l'ensemble avec UnionFindTree. En effet, le plus grand ensemble peut être décomposé et les éléments des autres ensembles peuvent être affectés à chaque élément. Vous pouvez comprendre l'explication d'UnionFindTree en regardant la vidéo de Katuppa sur Youtube. Les problèmes avec la chaîne'Friend' sont susceptibles d'être utilisés avec UnionFind ()
import sys
sys.setrecursionlimit(10 ** 9)
class UnionFind():
def __init__(self, n):
self.n = n
self.root = [-1]*(n+1)
self.rank = [0]*(n+1)
def find(self, x):#Rechercher des éléments parents
if self.root[x] < 0:
return x
else:
self.root[x] = self.find(self.root[x])#Récursif
return self.root[x]
def unite(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
elif self.rank[x] > self.rank[y]:#Connecté à un arbre profond
self.root[x] += self.root[y]
self.root[y] = x#Soit x le parent de y
else:
self.root[y] += self.root[x]
self.root[x] = y
if self.rank[x] == self.rank[y]:
self.rank[y] += 1
def issame(self, x, y):#x,Déterminer si y est le même ensemble
return self.find(x) == self.find(y)
def count(self, x):#Nombre d'éléments
return (-1)*self.root[self.find(x)]
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
a, b = map(int, input().split())
uf.unite(a, b)
ans = 0
for i in range(n):
ans = max(ans, uf.count(i))
print(ans)
Recommended Posts