Ich war so müde, dass ich kurz zuvor 20 Minuten lang ein Nickerchen machte und mein Bestes gab.
aising2020A - Number of Multiples
Brechen Sie in anderthalb Minuten durch. Schreiben Sie einfach gemäß den Bedingungen des Problems. Es braucht Zeit, daher denke ich nicht daran, es mit * O * (1) zu lösen.
L, R, d = map(int, input().split())
result = 0
for i in range(L, R + 1):
if i % d == 0:
result += 1
print(result)
Nachtrag: * O * (1)
L, R, d = map(int, input().split())
print(R // d - (L - 1) // d)
Brechen Sie in 2 Minuten durch. Schreiben Sie einfach gemäß den Bedingungen des Problems.
N = int(input())
a = list(map(int, input().split()))
result = 0
for i in range(N):
if (i + 1) % 2 == 1 and a[i] % 2 == 1:
result += 1
print(result)
Nachtrag: Ich hätte die gerade Zahl aufschneiden sollen ...
N, *a = map(int, open(0).read().split())
print(sum(1 for e in a[::2] if e % 2 == 1))
Es brach in 6 ½ Minuten durch. N ≤ 10 4 </ sup> Also dachte ich, es würde sogar in einer Dreifachschleife passieren. Tatsächlich passierte es.
N = int(input())
result = [0] * (N + 1)
for x in range(1, 101):
for y in range(1, 101):
for z in range(1, 101):
n = x * x + y * y + z * z + x * y + y * z + z * x
if n > N:
break
result[n] += 1
print(*result[1:], sep='\n')
aising2020D - Anything Goes to Zero
Ich konnte nicht durchbrechen. Als A = B * C, dachte ich, dass ich mit A% m = (B% m) * (C% m)% m eine große Anzahl von Resten bekommen könnte, also baute ich es damit, aber TLE Ich bin mir nicht sicher, weil ich den RE und den RE bekomme. Der erste Prozess kann durch Vorberechnung * O * (1) sein, aber was soll ich nach dem zweiten tun?
Nachtrag: Der von * f * (* n ) zurückgegebene Maximalwert ist log 2 </ sub> ( n *), also 2 2 × 10 5 </ sup> </ sup > → 2 × 10 5 </ sup> → 17,6 → 4,1 → 2,0 → 1 → 0 und es konvergiert im Handumdrehen. Ich hätte es also nur beim ersten Mal tun sollen. Schauen Sie sich TLE * f * ( Es war dumm zu rennen, um zu beschleunigen * n *).
RE wurde ursprünglich ausgegeben, als nur ein Bit gesetzt war und als das einzige gesetzte Bit invertiert wurde, wurde * popcount * nicht als 0 bemerkt und durch 0 geteilt. TLE Wurde * O * ( N </ i>) angezeigt, ohne zu wissen, dass sogar log 2 </ sub> (* X *) 2 × 10 5 </ sup> ist > log X </ i>), weil es geschrieben wurde.
Obwohl die Idee richtig war, hatte ich das Gefühl, dass ich sie aufgrund einiger Auslassungen nicht lösen konnte.
def popcount(n):
return bin(n).count("1")
def f(n):
if n == 0:
return 0
return 1 + f(n % popcount(n))
N = int(input())
X = input()
c = X.count('1')
t1 = [0] * N
t1[0] = 1 % (c + 1)
for i in range(1, N):
t1[i] = (t1[i - 1] << 1) % (c + 1)
x1 = 0
for i in range(N):
if X[i] == '0':
continue
x1 += t1[N - 1 - i]
if c - 1 != 0:
t2 = [0] * N
t2[0] = 1 % (c - 1)
for i in range(1, N):
t2[i] = (t2[i - 1] << 1) % (c - 1)
x2 = 0
for i in range(N):
if X[i] == '0':
continue
x2 += t2[N - 1 - i]
result = []
for i in range(N):
if X[i] == '0':
n = (x1 + t1[N - 1 - i]) % (c + 1)
elif X[i] == '1':
if c - 1 == 0:
result.append(0)
continue
n = (x2 - t2[N - 1 - i]) % (c - 1)
result.append(1 + f(n))
print(*result, sep='\n')
Recommended Posts