Concours AtCoder Débutants Défi des questions passées 5

Il n'y a rien de particulièrement difficile si vous décidez dans l'ordre en diminuant i de i = N.

N = int(input())
a = list(map(int, input().split()))

t = [0] * N
for i in range(N - 1, -1, -1):
    t[i] = (sum(t[2 * (i + 1) - 1::i + 1]) % 2) ^ a[i]

print(sum(t))
print(*[i + 1 for i in range(N) if t[i] == 1])

ABC080D - Recording

À première vue, il semble que la méthode imos est un coup, mais comme il y a S -0,5, si vous utilisez la méthode imos sans penser à rien, le nombre d'enregistrements consécutifs sur le même canal ne sera de deux que pendant 0,5.

La solution la plus simple est de quitter la méthode imos. Si = 1 au lieu de + = 1, il est possible de doubler, et en fait, c'est correct en termes de temps de traitement.

N, C = map(int, input().split())

tt = [[0] * (10 ** 5 + 1) for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    for i in range(s - 1, t):
        tt[c - 1][i] = 1

ct = [0] * (10 ** 5 + 1)
for i in range(C):
    for j in range(10 ** 5 + 1):
        ct[j] += tt[i][j]

print(max(ct))

Ce n'est pas difficile à faire avec la méthode imos, mais c'est étonnamment difficile à écrire avec élégance. Est-il plus facile de trier et de modifier le mouvement s'il est continu?

from operator import itemgetter

N, C = map(int, input().split())
stc = [list(map(int, input().split())) for _ in range(N)]
stc.sort(key=itemgetter(2, 0))

cs = [0] * (10 ** 5 + 1)
pt, pc = -1, -1
for s, t, c in stc:
    if pt == s and pc == c:
        cs[s] += 1
    else:
        cs[s - 1] += 1
    cs[t] -= 1
    pt, pc = t, c

for i in range(1, 10 ** 5 + 1):
    cs[i] += cs[i - 1]

print(max(cs))

Au fait, en théorie, cela peut être de la mousse, mais si je passais par le canal qui ne toucherait pas autant, j'ai été snipé fermement.

ABC121D - XOR World

Puisque f (A, B) est identique à f (0, A-1) xor f (0, B), g (N) = f (0, N) Il suffit de l'écrire. Vous pouvez compter le nombre de 1 pour chaque chiffre du nombre binaire et le traiter comme pair ou impair.

def h(A, n):
    if A == -1:
        return 0
    return A // (2 * n) * n + max(A % (2 * n) - (n - 1), 0)


def g(A):
    result = 0
    for i in range(48):
        t = 1 << i
        if h(A, t) % 2 == 1:
            result += t
    return result


def f(A, B):
    return g(A - 1) ^ g(B)


A, B = map(int, input().split())

print(f(A, B))

En fait, pour tout n pair, n xor (n + 1) ʻest 1`, vous n'avez donc pas à compter pour chaque chiffre.

def g(A):
    t = ((A + 1) // 2) % 2  #Pour tout même n n^ (n + 1) == 1
    if A % 2 == 0:
        return A ^ t
    return t


def f(A, B):
    return g(A - 1) ^ g(B)


A, B = map(int, input().split())

print(f(A, B))

ABC117D - XXOR

Pour chaque bit de A, additionnez le nombre de bits debout et non debout, et si le nombre de bits debout est plus grand, le bit est 0, et si le nombre de bits non debout est plus grand, le bit est 1 X. Cependant, comme X a une condition de K ou moins, si elle dépasse K, je renoncerai un peu à régler.

N, K = map(int, input().split())
A = list(map(int, input().split()))

bcs = [0] * 41
for i in range(N):
    a = A[i]
    for j in range(41):
        if a & (1 << j) != 0:
            bcs[j] += 1

X = 0
for i in range(40, -1, -1):
    if bcs[i] >= N - bcs[i]:
        continue
    t = 1 << i
    if X + t <= K:
        X += t

result = 0
for i in range(N):
    result += X ^ A[i]
print(result)

ABC094D - Binomial Coefficients

a _{i est le nombre maximum. A _{j est le prochain plus grand nombre, mais _{a _{i C a _{j == _{a _{i C _{a _{i -a _{j et recherchez l'ordre.}}}}}}}}}}

n = int(input())
a = list(map(int, input().split()))

a.sort()
x = a[-1]
b = [(min(e, x - e), e) for e in a[:-1]]
b.sort()
print(x, b[-1][1])

ABC098D - Xor Sum 2

L'addition est une augmentation monotone, mais XOR n'est pas une augmentation monotone car 1 xor 1 est égal à 0. En passant, puisque 0 xor N == 0 + N, "XOR <= addition". Alors, peu importe combien vous augmentez le nombre de r à partir de là, ce ne sera pas toujours le même. De plus, si un certain l <r a la même valeur, la combinaison de l + 1 et r aura également la même valeur. Vous pouvez voir que la méthode Toshakutori est bonne.

N = int(input())
A = list(map(int, input().split()))

result = 0
r = 0
xs = A[0]
cs = A[0]
for l in range(N):
    while r < N - 1 and xs ^ A[r + 1] == cs + A[r + 1]:
        r += 1
        xs ^= A[r]
        cs += A[r]
    result += r - l + 1
    xs ^= A[l]
    cs -= A[l]
print(result)