Percer en 2 minutes. Il suffit d'écrire.
D, T, S = map(int, input().split())
if D > S * T:
print('No')
else:
print('Yes')
Passez en 5 minutes, oubliez WA1. + 1 et mourez. Vérifiez combien de caractères différents il y a pendant le décalage et prenez la valeur minimale OK.
S = input()
T = input()
result = float('inf')
for i in range(len(S) - len(T) + 1):
t = 0
for j in range(len(T)):
if S[i + j] != T[j]:
t += 1
result = min(result, t)
print(result)
ABC177C - Sum of product of pairs
Percer dans 4 minutes. Somme cumulative car elle mourra si elle est calculée avec O (* N * 2 </ sup>) à Naive. Si vous allez dans l'ordre à partir de la droite, la somme cumulée ne sera pas effectuée, mais ce n'est pas grave.
from itertools import accumulate
m = 1000000007
N, *A = map(int, open(0).read().split())
result = 0
b = list(accumulate(A))
for i in range(N):
result += A[i] * (b[N - 1] - b[i])
result %= m
print(result)
Postscript: j'ai essayé de le résoudre sans utiliser la somme cumulée.
m = 1000000007
N, *A = map(int, open(0).read().split())
result = 0
a = 0
for i in range(1, N + 1):
result += a * A[N - i]
a += A[N - i]
result %= m
print(result)
Percer en 4 minutes. Comme vous pouvez le voir, Union Find. Il vous suffit de créer autant de groupes que le nombre de personnes appartenant au plus grand syndicat.
from sys import setrecursionlimit, stdin
def find(parent, i):
t = parent[i]
if t < 0:
return i
t = find(parent, t)
parent[i] = t
return t
def unite(parent, i, j):
i = find(parent, i)
j = find(parent, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
readline = stdin.readline
setrecursionlimit(10 ** 6)
N, M = map(int, readline().split())
parent = [-1] * N
for _ in range(M):
A, B = map(lambda x: int(x) - 1, readline().split())
unite(parent, A, B)
print(-min(parent))
Il a éclaté en 23 minutes. Je pensais que je pourrais y aller si je décomposais les facteurs premiers à partir de la droite. Je sentais que je pouvais calculer si c'était coprime ou non, mais cela prenait du temps parce que la performance chuterait, alors je l'ai calculée séparément.
from math import gcd
from functools import reduce
def make_prime_table(n):
sieve = list(range(n + 1))
sieve[0] = -1
sieve[1] = -1
for i in range(4, n + 1, 2):
sieve[i] = 2
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i] != i:
continue
for j in range(i * i, n + 1, i * 2):
if sieve[j] == j:
sieve[j] = i
return sieve
def prime_factorize(n):
result = []
while n != 1:
p = prime_table[n]
e = 0
while n % p == 0:
n //= p
e += 1
result.append((p, e))
return result
def f():
s = set()
for i in range(N - 1, -1, -1):
t = prime_factorize(A[i])
for p, _ in t:
if p in s:
return False
s.add(p)
return True
N, *A = map(int, open(0).read().split())
prime_table = make_prime_table(10 ** 6)
if f():
print('pairwise coprime')
elif reduce(gcd, A) == 1:
print('setwise coprime')
else:
print('not coprime')
Recommended Posts