Premièrement, si le bord gauche est vertical, il y a 3 façons de peindre. S'il est horizontal, il y a 6 façons avec 3 * 2. Ensuite, si la verticale vient à côté de la verticale, elle doit être différente de la couleur verticale précédente, donc 2 Si l'horizontale vient à côté de la verticale, si vous décidez du côté supérieur, il y a deux façons car il devrait être différent de la verticale, et il n'y a qu'une seule autre façon sur le côté inférieur, il y a donc deux façons. Horizontal Si la verticale vient à côté de l'horizontale, il n'y a qu'une seule façon car deux couleurs ont déjà été décidées.Lorsque l'horizontale vient à côté de l'horizontale, il y a trois façons comme suit.
0022 0011 0011
1100 1100 1122
Tout ce que vous avez à faire est de faire l'addition.
N = int(input())
S1 = input()
S2 = input()
if S1[0] == S2[0]:
result = 3
else:
result = 6
x = 0
W = len(S1)
while x < W:
if S1[x] == S2[x]:
if x + 1 == W:
break
result *= 2
result %= 1000000007
x += 1
else:
if x + 2 == W:
break
if S1[x + 2] != S2[x + 2]:
result *= 3
result %= 1000000007
x += 2
print(result)
Il n'y a pas de limite au mouvement minimum, alors allez du coin supérieur gauche vers la droite, descendez un à gauche lorsque vous atteignez la fin, descendez d'un à droite lorsque vous atteignez la fin, et ainsi de suite. Ensuite, s'il s'agit d'un nombre impair, si vous répétez l'envoi au carré suivant, ce sera soit un nombre pair, soit seul le dernier carré sera un nombre impair.
H, W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]
result = []
y = 0
while y < H:
x = 0
while x < W:
if a[y][x] % 2 == 1:
if x == W - 1:
if y == H - 1:
break
else:
result.append('%d %d %d %d' % (y + 1, x + 1, y + 2, x + 1))
a[y + 1][x] += 1
else:
result.append('%d %d %d %d' % (y + 1, x + 1, y + 1, x + 2))
a[y][x + 1] += 1
x += 1
if y == H - 1:
break
y += 1
x = W - 1
while x >= 0:
if a[y][x] % 2 == 1:
if x == 0:
if y == H - 1:
break
else:
result.append('%d %d %d %d' % (y + 1, x + 1, y + 2, x + 1))
a[y + 1][x] += 1
else:
result.append('%d %d %d %d' % (y + 1, x + 1, y + 1, x))
a[y][x - 1] += 1
x -= 1
y += 1
print(len(result))
print('\n'.join(result))
ABC096D - Five, Five Everywhere
Si vous divisez par 5, vous pouvez organiser les nombres premiers restants dans l'ordre croissant selon vos besoins. Toute combinaison sera un multiple de 5.
N = int(input())
result = []
sieve = [0] * (55555 + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, 55555 + 1):
if sieve[i] != 0:
continue
if i % 5 == 1:
result.append(i)
if len(result) == N:
break
sieve[i] = i
for j in range(i * i, 55555 + 1, i):
if sieve[j] == 0:
sieve[j] = i
print(*result)
La combinaison de couleurs est 30 </ sub> C 3 </ sub> = 4060, vous pouvez donc faire une recherche complète, mais puisque N ≤ 500, si vous le faites sans réfléchir, * O * (4060 × 500) 2 </ sup> ≒ 10 10 </ sup>) et TLE est inévitable. (I + j) Si vous groupez par le reste de% 3 et comptez les couleurs d'origine, * O * (4060) × 30 × 3 ≒ 3,7 × 10 5 </ sup>), il est donc résolu.
from itertools import permutations
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
a = [[0] * C for _ in range(3)]
for y in range(N):
for x in range(N):
t = ((x + 1) + (y + 1)) % 3
a[t][c[y][x] - 1] += 1
result = float('inf')
for b in permutations(range(C), 3):
t = 0
for i in range(3):
for j in range(C):
t += a[i][j] * D[j][b[i]]
result = min(result, t)
print(result)
J'ai eu l'intuition que le tri par b était une douleur pendant Keyence Programming Contest 2020 B - Robot Arms. C'est un problème de planification. Après cela, je devrais supprimer autant de ponts que nécessaire, mais au début, j'ai enregistré et résolu les ponts supprimés par Segment Tree. Eh bien, * O * ( Je peux le résoudre avec N </ i> log N </ i>), mais j'ai remarqué en regardant le PDF d'explication qu'il était normal de ne retenir que le dernier supprimé.
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
result = 0
t = -1
for a, b in ab:
a, b = a - 1, b - 1
if a <= t < b:
continue
result += 1
t = b - 1
print(result)
Si vous décidez du 1er et du 2ème animaux, vous aurez 1 choix après cela, et si vous faites une erreur, vous saurez qu'il y a une contradiction à la fin. Donc, si vous faites le 1er et le 2ème avec 4 motifs du tour S, W Bon. * O * (4 × 10 5 </ sup>), donc il n'y a pas de problème en termes de montant de calcul.
from itertools import product
N = int(input())
s = input()
swap = {'S': 'W', 'W': 'S'}
for a, b in product('SW', repeat=2):
t = [None] * N
t[0] = a
t[1] = b
for i in range(1, N - 1):
if t[i] == 'S':
if s[i] == 'o':
t[i + 1] = t[i - 1]
elif s[i] == 'x':
t[i + 1] = swap[t[i - 1]]
elif t[i] == 'W':
if s[i] == 'o':
t[i + 1] = swap[t[i - 1]]
elif s[i] == 'x':
t[i + 1] = t[i - 1]
if t[N - 1] == 'S':
if s[N - 1] == 'o' and t[N - 2] != t[0]:
continue
elif s[N - 1] == 'x' and t[N - 2] == t[0]:
continue
elif t[N - 1] == 'W':
if s[N - 1] == 'o' and t[N - 2] == t[0]:
continue
elif s[N - 1] == 'x' and t[N - 2] != t[0]:
continue
if t[0] == 'S':
if s[0] == 'o' and t[N - 1] != t[1]:
continue
elif s[0] == 'x' and t[N - 1] == t[1]:
continue
elif t[0] == 'W':
if s[0] == 'o' and t[N - 1] == t[1]:
continue
elif s[0] == 'x' and t[N - 1] != t[1]:
continue
print(''.join(t))
exit()
print(-1)
Recommended Posts