蓝桥杯真题

单词分析

1
2
3
4
5
6
from collections import Counter
s = list(input())
s.sort()
d = Counter(s)
print(d.most_common(1)[0][0])
print(d.most_common(1)[0][1])

成绩统计

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
nums = [int(input()) for _ in range(n)]
a = d = 0
for num in nums:
  if num >= 85:
    a += 1
    d += 1
  elif num >= 60:
    d += 1
print(f'{round(d*100/n)}%')
print(f'{round(a*100/n)}%')

门牌制作

1
2
3
4
5
n = 2020
res = 0
for i in range(1, n + 1):
  res += str(i).count('2')
print(res)

数字三角形

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n + 2)] for _ in range(n)]
dp[0][1] = nums[0][0]
for i in range(1, n):
  for j in range(1, i+2):
    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + nums[i][j-1]
if n & 1:
  print(dp[n-1][(n + 1) // 2])
else:
  print(max(dp[n-1][n // 2], dp[n-1][n // 2 + 1]))

卡片

1
2
3
4
5
6
7
8
from sys import exit
nums = [2021] * 10
for i in range(1, 10000):
  for char in str(i):
    nums[int(char)] -= 1
    if nums[int(char)] < 0:
      print(i-1)
      exit(0)

跑步锻炼

1
2
3
4
5
6
7
8
9
10
11
from datetime import datetime,timedelta
start = datetime(2000, 1, 1)
end = datetime(2020, 10, 1)
res = 0
while start <= end:
  if start.day == 1 or start.weekday() == 0:
    res += 2
  else:
    res += 1
  start += timedelta(days=1)
print(res)

蛇形填数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
nums = [[0] * 100 for _ in range(100)]
nums[0][0] = 1
i, j, t = 0, 0, 1
for _ in range(30):
  j += 1
  t += 1
  nums[i][j] = t
  for _ in range(j):
    i += 1
    j -= 1
    t += 1
    nums[i][j] = t
  i += 1
  t += 1
  nums[i][j] = t
  for _ in range(i):
    i -= 1
    j += 1
    t += 1
    nums[i][j] = t
print(nums[19][19])

货物摆放

1
2
3
4
5
6
7
8
9
10
11
12
n = 2021041820210418
nums = []
for i in range(1, int(n ** 0.5) + 1):
  if n % i == 0:
    nums.append(i)
    nums.append(n/i)
res = 0
for i in nums:
  for j in nums:
    if n % (i*j) == 0:
      res += 1
print(res) # 2430

！杨辉三角形

暴力（40%）

1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
nums = []
for i in range(1, 1600):
  nums.append([1] * i + [0])
  for j in range(1, i):
    nums[i-1][j] = nums[i-2][j] + nums[i-2][j-1]
for i, num in enumerate(nums):
  if n in num:
    d = num.index(n)
    res = i * (i+1) // 2 + d + 1
    print(res)
    break

组合数+二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import math
def C(n, m):
  a, b = 1, 1
  for i in range(1, min(m, n-m) + 1):
    a *= n
    n -= 1
    b *= i
  return a // b
  # return math.comb(n, m) # python3.8
def search(x):
  l = x
  r = max(x, n)
  while l < r:
    mid = l + r >> 1
    if C(mid, x // 2) < n:
      l = mid + 1
    else:
      r = mid 
  return l
n = int(input())
for i in range(34, -1, -2):
  t = search(i)
  if C(t, i//2) == n:
    print(t * (t+1) // 2 + i//2 + 1)
    break

时间显示

1
2
3
4
from datetime import datetime, timedelta
stamp = int(input())
d = datetime(1970, 1, 1) + timedelta(milliseconds=stamp)
print(d.strftime('%H:%M:%S'))

裁纸刀

1
2
n, m = 20, 22
print(4 + m - 1 + (n - 1) * m)

路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import math
dp = [0] * 2022
nums = [[float('inf')] * 2022 for _ in range(2022)]
for i in range(1, 2022):
  for j in range(i+1, min(i+22, 2022)):
    d = math.gcd(i, j)
    nums[i][j] = d * i//d * j//d
dp[1] = 0
for i in range(2, 2022):
  t = float('inf')
  for j in range(min(i, 22)):
    t = min(t, dp[i-j] + nums[i-j][i])
  dp[i] = t
print(dp[2021])

排列字母

1
2
3
s = list(input())
s.sort()
print(''.join(s))

答疑

1
2
3
4
5
6
7
8
n = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]
nums.sort(key = lambda x:(x[0] + x[1] + x[2], x[0] + x[1]))
res = last = 0
for num in nums:
  res += last + num[0] + num[1]
  last += num[0] + num[1] + num[2]
print(res)

直线

1
2
3
4
5
6
7
8
9
10
11
12
n, m = 20, 21
res = set()
for x1 in range(n):
  for y1 in range(m):
    for x2 in range(n):
      for y2 in range(m):
        if x1 == x2:
          continue
        k = (y2 - y1) / (x2 - x1)
        b = (x2 * y1 - x1 * y2) / (x2 - x1)
        res.add((k, b))
print(len(res) + n)

特殊日期

1
2
3
4
5
6
7
8
9
10
11
import datetime
start = datetime.datetime(1900, 1, 1)
end = datetime.datetime(9999, 12, 31)
res = 0
while start < end:
  t = start.strftime('%Y %m %d')
  y, m, d = t.split()
  if sum(map(int, y)) == sum(map(int, m)) + sum(map(int, d)):
    res += 1
  start += datetime.timedelta(days=1)
print(res)

纸张尺寸

1
2
3
4
5
6
7
8
9
10
a, b = 1189, 841
res = [(a, b )]
for i in range(9):
  if a < b:
    a, b = b, a
  a //= 2
  res.append((b, a))
s = int(input()[-1])
print(res[s][0])
print(res[s][1])

青蛙过河

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n, x = map(int, input().split())
nums = list(map(int, input().split()))
sums = [0] * n
for i in range(n - 1):
  sums[i + 1] = sums[i] + nums[i]
def check(y):
  for i in range(n - y):
    if sums[i + y] - sums[i] < 2 * x:
      return False
  return True
l, r = 1, n
while l < r:
  mid = l + r >> 1
  if check(mid):
    r = mid
  else:
    l = mid + 1
print(l)

工作时长

1
2
3
4
5
6
7
8
9
10
from datetime import datetime
tmp = []
with open('records.txt') as f:
  for line in f:
    tmp.append(datetime.strptime(line.strip(), '%Y-%m-%d %H:%M:%S'))
tmp.sort()
res = 0
for i in range(0, len(tmp), 2):
  res += (tmp[i + 1] - tmp[i]).total_seconds()
print(int(res))

求和

1
2
3
4
res = 0
for i in range(1, 20230409):
  res += i
print(res)

特殊时间

1
2
3
4
5
6
7
8
9
10
def check(s):
  return s.count('1') == 3 or s.count('2') == 3
tmp = [] #0111, 0222, 1011, 1101, 1110, 1112, 1121, 1222, 1211, 1113, 1114, 1115, 1116, 1117, 1118, 1119
for i in range(1, 13):
  for j in range(1, 31):
    s = f'{i:02d}{j:02d}'
    if check(s):
      tmp.append(s)
res = 4 * (4*9 + 3*3 + 2*4)
print(res)

数位排序

1
2
3
4
n, m = int(input()), int(input())
tmp = list(range(1, n + 1))
tmp.sort(key=lambda x:sum([int(i) for i in str(x)]))
print(tmp[m - 1])

括号序列

！！！

天干地支

1
2
3
4
5
tiangan = ['jia', 'yi', 'bing', 'ding', 'wu', 'ji', 'geng', 'xin', 'ren', 'gui']
dizhi = ['zi', 'chou', 'yin', 'mao', 'chen', 'si', 'wu', 'wei', 'shen', 'you', 'xu', 'hai']
n = int(input()) + 56
a, b = n % 10, n % 12
print(f'{tiangan[a]}{dizhi[b]}')

阶乘的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
nums = list(map(int, input().split()))
nums.sort()
res = nums[0]
count = 0
nex = nums[0] + 1
while True:
  for num in nums:
    if num == res:
      count += 1
  if count % nex == 0:
    count /= nex
    res = nex
    nex += 1
  else:
    break
print(res)

分糖果

1
2
3
4
5
6
7
8
9
10
11
12
n, x = map(int, input().split())
s = list(input())
s.sort()
if s[x - 1] != s[0]:
  print(s[x - 1])
elif s[x] == s[-1]:
  print(s[x - 1], end = '')
  for i in range(x, n, x):
    print(s[i], end = '')
else:
  for i in s[x - 1: ]:
    print(i, end = '')

平面切分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
nums = list(set([tuple(map(int, input().split())) for _ in range(n)]))
res = 1 + len(nums)
lines = []
for k1, b1 in nums:
  point = set()
  for k2, b2 in lines:
    if k1 != k2:
      x = (b2 - b1) / (k1 - k2)
      y = (b1 *k2 - b2*k1) / (k2 - k1)
      point.add((x, y))
  res += len(point)
  lines.append([k1, b1])
print(res)

回路计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def gcd(a, b):
  return a if b == 0 else gcd(b, a % b)
n, state = 21, 1 << 21
g = [[0] * (n + 1) for _ in range(n + 1)]
dp = [[0] * (n + 1) for _ in range(state)]
dp[1][0] = 1
for i in range(n + 1):
  for j in range(n + 1):
    if gcd(i, j) == 1:
      g[i][j] = 1
for i in range(state):
  for j in range(n):
    if i >> j & 1:
      for k in range(n):
        if g[j + 1][k + 1] == 1 and i >> k & 1:
          dp[i][j] += dp[i - (1 << j)][k]
print(sum(dp[-1]))
# print(881012367360)

三国游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
X, Y, Z = list(map(int, input().split())), list(map(int, input().split())), list(map(int, input().split()))
A = sorted([X[i] - Y[i] - Z[i] for i in range(n)], reverse=True)
B = sorted([Y[i] - X[i] - Z[i] for i in range(n)], reverse=True)
C = sorted([Z[i] - X[i] - Y[i] for i in range(n)], reverse=True)
a = b = c = res = 0
for i in range(n):
  a += A[i]
  b += B[i]
  c += C[i]
  if a > 0 or b > 0 or c > 0:
    res += 1
  else:
    break
print(res if res else -1)

左孩子右兄弟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys
sys.setrecursionlimit(100000)
n = int(input())
g = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
  t = int(input())
  g[t].append(i)
def dfs(u):
  if not g[u]:
    return 0
  res = 0
  for i in g[u]:
    res = max(res, dfs(i))
  return len(g[u]) + res
print(dfs(1))

2023

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
res = 0
def check(s):
  for i in range(8):
    if s[i] == '2' and i < 5:
      for j in range(i+1, 8):
        if s[j] == '0' and j < 6:
          for k in range(j+1, 8):
            if s[k] == '2' and k < 7:
              for t in range(k+1, 8):
                if s[t] == '3' and t < 8:
                  return True
  return False
for s in range(12345678, 98765433):
  s = str(s)
  if '2' not in s or '0' not in s or '3' not in s:
    continue
  if check(s):
    res += 1
print(98765433 - 12345678 - res)
# print(85959030)

翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
for _ in range(n):
  res = 0
  t, s = list(input()), list(input())
  m = len(s)
  if s[0] != t[0] or s[-1] != t[-1]:
    res = -1
  else:
    for i in range(1, m-1):
      if s[i] != t[i]:
        if s[i] != s[i-1] and s[i] != s[i+1]:
          res += 1
        else:
          res = -1
          break
  print(res)

123

！！！暴力

1
2
3
4
5
6
7
8
9
10
t = int(input())
nums = [0]
for i in range(1, 3300):
  for j in range(1, i):
    nums.append(j)
for i in range(1, len(nums)):
  nums[i] += nums[i - 1]
for _ in range(t):
  a, b = map(int, input().split())
  print(nums[b] - nums[a-1])

！！！二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
maxn = 1414215
s, a = [0] * maxn, [0] * maxn
for i in range(1, maxn):
  a[i] = a[i - 1] + i
  s[i] = s[i - 1] + a[i]
def presum(x):
  l, r = 0, maxn
  while l < r:
    mid = (l + r + 1)>> 1
    if a[mid] > x:
      r = mid - 1
    else:
      l = mid 
  return s[l] + a[x - a[l]]
T = int(input())
for _ in range(T):
  l, r = map(int, input().split())
  print(presum(r) - presum(l - 1))

平均

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
nums = [[] for _ in range(10)]
for _ in range(n):
  a, b = map(int, input().split())
  nums[a].append(b)
res = 0
n = n // 10
for i in range(10):
  nums[i] = sorted(nums[i])
  res += sum(nums[i][:-n])
print(res)

填充

1
2
3
4
5
6
7
8
9
10
s = input()
judge = ['00', '11', '0?', '?0', '1?', '?1', '11']
i = res = 0
while i < len(s) - 1:
  if s[i: i + 2] in judge:
    i += 2
    res += 1
  else:
    i += 1
print(res)

阶乘约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
dicts = {}
def divisor(x):
  for i in range(2, int(x ** 0.5) + 1):
    while x % i == 0:
      dicts[i] = dicts.get(i, 0) + 1
      x //= i
  if x > 1:
    dicts[x] = dicts.get(x, 0) + 1
for i in range(1, 101):
  divisor(i)
res = 1
for i in dicts.values():
  res *= i + 1
print(res)

子树的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
T = int(input())
for _ in range(T):
  n, m, k = map(int, input().split())
  l = r = k
  res = tmp = 1
  while r * m + 1 < n:
    tmp *= m
    l = l * m - m + 2
    r = r * m + 1
    res += tmp
  l = l * m - m + 2
  res += max(0, n - l + 1)
  print(res)

硬币兑换

1
2
3
4
5
6
nums = [i for i in range(2024)] + [0] * 2023
for i in range(1, 2024):
  nums[2 * i] += i // 2
  for j in range(i + 1, 2024):
    nums[i + j] += i
print(max(nums))

玩具蛇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dicts = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = 0
g = [[False] * 4 for _ in range(4)]
def dfs(x, y, c):
  if c == 16:
    global res
    res += 1
    return
  for i, j in dicts:
    a, b = x + i, y + j
    if 0 <= a < 4 and 0 <= b < 4 and not g[a][b]:
      g[a][b] = True
      dfs(a, b, c + 1)
      g[a][b] = False
for i in range(4):
  for j in range(4):
    g[i][j] = True
    dfs(i, j, 1)
    g[i][j] = False
print(res)

寻找整数

1
2
3
4
5
6
7
8
9
# 11 * 17 = 187
for i in range(187, 10**12, 187):
  if i % 49 == 46 and i % 48 == 41 and i % 47 == 5 and i % 46 == 15 and i % 45 == 29:
    print(i) # 5458460249 12590206409

for i in range(5458460249, 10 ** 17, 7131746160):
  if i % 44 == 33 and i % 43 == 11 and i % 42 == 11 and i % 41 == 1 and i % 40 == 9 \
  and i % 39 == 23 and i % 38 == 37 and i % 37 == 22 and i % 36 == 29 and i % 35 == 4:
    print(i)

合数个数

1
2
3
4
5
6
7
8
9
10
11
n = 2020
state = [True] * (n + 1)
for i in range(2, int(n ** 0.5) + 1):
  if state[i]:
    for j in range(2 * i, n + 1, i):
      state[j] = False
res = 0
for i in range(1, n + 1):
  if state[i]:
    res += 1
print(n - res)

寻找2020

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = 300
g = [input() for _ in range(n)]
res = 0
for i in range(n):
  for j in range(n - 3):
    if g[i][j: j + 4] == '2020':
      res += 1
for i in range(n - 3):
  for j in range(n):
    if g[i][j] == '2' and g[i + 1][j] == '0' and g[i + 2][j] == '2' and g[i + 3][j] == '0':
      res += 1
for i in range(n - 3):
  for j in range(n - 3):
    if g[i][j] == '2' and g[i + 1][j + 1] == '0' and g[i + 2][j + 2] == '2' and g[i + 3][j + 3] == '0':
      res += 1
print(res)

子矩阵

！！暴力（5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MOD = 998244353
n, m, a, b = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
def fun(c, d):
  x, y = float('-inf'), float('inf')
  for i in range(a):
    for j in range(b):
      x = max(x, A[c + i][d + j])
      y = min(y, A[c + i][d + j])
  return (x * y) % MOD
res = 0
for i in range(n - a + 1):
  for j in range(m - b + 1):
    res = (res + fun(i, j)) % MOD
print(res)

管道

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n, m = map(int, input().split())
nums = [list(map(int, input().split())) for _ in range(n)]
def check(time):
  tmp = []
  for i in range(n):
    if time > nums[i][1]:
      l = max(1, nums[i][0] - time + nums[i][1])
      r = min(m, nums[i][0] + time - nums[i][1])
      tmp.append((l, r))
  tmp.sort()
  if not tmp or tmp[0][0] > 1:
    return False
  a = tmp[0][1]
  for l, r in tmp[1:]:
    if a + 1 < l:
      return False
    else:
      a = max(a, r)
  return a == m
l, r = 1, 1000000000
while l < r:
  mid = l + r >> 1
  if check(mid):
    r = mid
  else:
    l = mid + 1
print(l)

异或数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def init(n):
  cnt = 1
  while n:
    if n & 1:
      nums[cnt] += 1
    n >>= 1
    cnt += 1
T = int(input())
for _ in range(T):
  a = list(map(int, input().split()))
  n = a[0]
  nums = [0] * 23
  s = 0
  for i in range(1, n + 1):
    init(a[i])
    s ^= a[i]
  if not s:
    print(0)
  else:
    for i in range(20, 0, -1):
      if nums[i] == 1:
        print(1)
        break
      elif nums[i] % 2 == 1:
        if n % 2 == 1:
          print(1)
        else:
          print(-1)
        break

纯质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 20210605
state = [True] * (n + 1)
for i in range(2, int(n ** 0.5) + 1):
  if state[i]:
    for j in range(2 * i, n, i):
      state[j] = False
res = 0
for i in range(2, n + 1):
  if state[i]:
    for char in str(i):
      if char not in '2357':
        res -= 1
        break
    res += 1
print(res)

互质数的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
a, b = map(int, input().split())
MOD = 998244353
def qpow(a, b):
  res = 1
  while b:
    if b & 1:
      res = res * a % MOD
    b >>= 1
    a = a * a % MOD
  return res
def euler(x):
  res = x
  for i in range(2, int(x ** 0.5) + 1):
    if x % i == 0:
      res *= (1 - 1 / i)
      while x % i == 0:
        x //= i
  if x > 1:
    res *= (1 - 1 / x)
  return int(res)
print(qpow(a, b - 1) * euler(a) % MOD)

最长不下降子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from bisect import bisect_right
n, k = map(int, input().split())
nums = list(map(int, input().split()))
interval = [0] * n
res = []
for i in range(n):
  idx = bisect_right(res, nums[i])
  if idx >= len(res):
    res.append(nums[i])
  else:
    res[idx] = nums[i]
    interval[i] = 1
maxl = tmp = sum(interval[:k])
for i in range(1, n - k + 1):
  tmp = tmp + interval[i + k - 1] - interval[i - 1]
  maxl = max(tmp, maxl)
print(len(res) + maxl)

松散子序列

1
2
3
4
5
6
7
8
9
10
s = list(map(lambda x: ord(x) - 96, list(input())))
n = len(s)
if n <= 2:
  print(max(s))
else:
  dp = [[0] * 2 for _ in range(n)]
  for i in range( n):
    dp[i][1] = max(dp[i - 2]) + s[i]
    dp[i][0] = max(dp[i - 1])
  print(max(dp[-1]))

奇怪的数

！！暴力（10%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def check(num):
  for i in range(len(num) - 4):
    if sum(int(s) for s in num[i: i + 5]) > m:
      return False
  return True
n, m = map(int, input().split())
if n > 10:
  exit(0)
res = 0
for i in range(10 ** n):
  num = str(i).zfill(n)
  if all(int(s) % 2 == j % 2 for j, s in enumerate(num)):
    if check(num):
      res += 1
print(res)

公因数匹配

！！暴力（33.3%）

1
2
3
4
5
6
7
8
9
10
import sys
def gcd(a, b):
  return gcd(b, a % b) if b else a
n = int(input())
nums = list(map(int, input().split()))
for i in range(n):
  for j in range(i + 1, n):
    if gcd(nums[i], nums[j]) > 1:
      print(i + 1, j + 1)
      sys.exit(0)

求因数+堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import heapq
from collections import defaultdict
n = int(input())
nums = list(map(int, input().split()))
facts = defaultdict(list)
for i, num in enumerate(nums):
  for j in range(2, int(num ** 0.5) + 1):
    if num % j == 0:
      heapq.heappush(facts[j], i + 1)
      heapq.heappush(facts[num // j], i + 1)
  heapq.heappush(facts[num], i + 1)
l = r = float('inf')
for v in facts.values():
  if len(v) > 1:
    if l > v[0]:
      l = v[0]
      r = v[1]
    elif l == v[0]:
      r = min(r, v[1])
print(l, r)

保险箱

1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
s = [0] + list(map(int, input()[::-1]))
t = [0] + list(map(int, input()[::-1]))
dp = [[0] * 3 for _ in range(n + 1)]
dp[1][0] = abs(s[1] - t[1])
dp[1][1] = -s[1] + 10 + t[1]
dp[1][2] = s[1] + 10 - t[1]
for i in range(2, n + 1):
  dp[i][0] = min(dp[i-1][0] + abs(s[i] - t[i]), dp[i-1][1] + abs(s[i] + 1 - t[i]), dp[i-1][2] + abs(s[i] - 1 - t[i]))
  dp[i][1] = min(dp[i-1][0] + 10 - s[i] + t[i], dp[i-1][1] + 9 - s[i] + t[i], dp[i-1][2] + 11 - s[i] + t[i])
  dp[i][2] = min(dp[i-1][0] + 10 + s[i] - t[i], dp[i-1][1] + 11 + s[i] - t[i], dp[i-1][2] + 9 + s[i] - t[i])
print(min(dp[n]))

蜂巢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
d1, p1, q1, d2, p2, q2 = map(int, input().split())
def fun(d, p, q):
  if d == 0:
    x = -p + q/2
    y = q
  if d == 1:
    x = -p/2 + q
    y = p
  if d == 2:
    x = p/2 + q/2
    y = p - q
  if d == 3:
    x = p - q/2
    y = -q
  if d == 4:
    x = p/2 - q
    y = -p
  if d == 5:
    x = -p/2 - q/2
    y = q - p
  return x, y
x1, y1 = fun(d1, p1, q1)
x2, y2 = fun(d2, p2, q2)
a, b = abs(x1 - x2), abs(y1 - y2)
if a < b / 2:
  print(int(b))
else:
  print(int(a + b - b // 2))

异或和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n, m = map(int, input().split())
nums = [0] + list(map(int, input().split()))
adj_list = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  u, v = map(int, input().split())
  if u > v:
    u, v = v, u
  adj_list[u].append(v)
def dfs(u):
  res = nums[u]
  for v in adj_list[u]:
    res ^= dfs(v)
  return res 
for _ in range(m):
  li = list(map(int, input().split()))
  if li[0] == 1:
    nums[li[1]] = li[2]
  elif li[0] == 2:
    res = dfs(li[1])
    print(res)

棋盘

！！暴力

1
2
3
4
5
6
7
8
9
n, m = map(int, input().split())
g = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  for i in range(x1, x2 + 1):
    for j in range(y1, y2 + 1):
      g[i][j] = 1 if g[i][j] == 0 else 0
for i in range(1, n + 1):
  print(''.join(map(str, g[i][1:])))

差分+前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n, m = map(int, input().split())
g = [[0] * (n + 1) for _ in range(n + 1)]
diff = [[0] * (n + 2) for _ in range(n + 2)]
def insert(x1, y1, x2, y2, c):
  diff[x1][y1] += 1
  diff[x2 + 1][y1] -= 1
  diff[x1][y2 + 1] -= 1
  diff[x2 + 1][y2 + 1] += 1
for _ in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  insert(x1, y1, x2, y2, 1)
for i in range(1, n + 1):
  for j in range(1, n + 1):
    g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + diff[i][j]
for i in range(1, n + 1):
  for j in range(1, n + 1):
    g[i][j] = 1 if g[i][j] % 2 else 0
for i in range(1, n + 1):
  print(''.join(map(str, g[i][1:])))

美丽的 2

1
2
3
4
5
6
n = 2020
res = 0
for i in range(1, n + 1):
  if '2' in str(i):
    res += 1
print(res)

数的拆分

！！暴力（10%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
T = int(input())
nums = []
for i in range(2, 10000):
  for j in range(2, 1000):
    if i ** j > 1e9:
      break
    nums.append(i ** j)
nums.sort()
def check(a):
  if a in nums:
    return 'yes'
  else:
    for num in nums:
      if a < num:
        return 'no'
      if a % num == 0 and a // num in nums:
        return 'yes'
  return 'no'
for _ in range(T):
  a = int(input())
  print(check(a))

数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
status = [True] * 4001
primes = []
def is_square(x):
  n = round(x ** 0.5)
  return n * n == x
def is_cubic(x):
  n = round(x ** (1/3))
  return n * n * n == x
for i in range(2, 4001):
  if status[i]:
    primes.append(i)
    for j in range(2 * i, 4001, i):
      status[j] = False
def check(a):
  flag = True
  for prime in primes:
    if a % prime == 0:
      t = 0
      while a % prime == 0:
        a //= prime
        t += 1
      if t == 1:
        flag = False
  if flag and (is_square(a) or is_cubic(a)):
    print('yes')
  else:
    print('no')
T = int(input())
for _ in range(T):
  a = int(input())
  if is_square(a) or is_cubic(a):
    print('yes')
  else:
    check(a)

大写

1
2
s = input()
print(s.upper())

重新排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
nums = list(map(int, input().split()))
diff = [0] * (n + 2)
m = int(input())
for _ in range(m):
  l, r = map(int, input().split())
  diff[l] += 1
  diff[r + 1] -= 1
tmps = [0] * (n + 1)
for i in range(1, n + 1):
  tmps[i] = tmps[i - 1] + diff[i]
res1 = res2 = 0
for i in range(n):
  res1 += nums[i] * tmps[i + 1]
nums.sort(reverse = True)
tmps.sort(reverse = True)
for i in range(n):
  res2 += nums[i] * tmps[i]
print(res2 - res1)

消除游戏

！！暴力（58.3%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
s = list(input())
for _ in range(10000):
  n = len(s)
  state = [True] * n
  for i in range(1, n - 1):
    if s[i] == s[i - 1] and s[i] != s[i + 1]:
      state[i] = state[i + 1] = 0
    elif s[i] != s[i - 1] and s[i] == s[i + 1]:
      state[i] = state[i - 1] = 0
  s = [s[i] for i in range(n) if state[i]]
  if len(s) == n:
    break
if s:
  print(''.join(map(str, s)))
else:
  print('EMPTY')

技能升级

！！暴力（40%）

1
2
3
4
5
6
7
8
9
n, m = map(int, input().split())
nums = []
for _ in range(n):
  a, b = map(int, input().split())
  while a > 0:
    nums.append(a)
    a -= b
nums.sort(reverse=True)
print(sum(nums[:m]))

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
n, m = map(int, input().split())
a, b = [], []
for i in range(n):
  x, y = map(int, input().split())
  a.append(x)
  b.append(y)
def check(x):
  cnt = 0
  for i in range(n):
    if a[i] < x:
      continue
    cnt += (a[i] - x) // b[i] + 1
    if cnt >= m:
      return True
  return False
l, r = 0, 1000000
while l <= r:
  mid = l + r >> 1
  if check(mid):
    l = mid + 1
  else:
    r = mid - 1
res = 0
surplus = m
for i in range(n):
  if a[i] < r:
    continue
  t = (a[i] - l) // b[i] + 1
  if a[i] - (t - 1) * b[i] == r:
    t -= 1
  res += t * a[i] - t * (t - 1) * b[i] // 2
  surplus -= t
print(res + surplus * r)

质因数个数

！！暴力（80%）

1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())
primes = []
state = [True] * 5000001
for i in range(2, 5000001):
  if state[i]:
    primes.append(i)
    for j in range(2 * i, 5000001, i):
      state[j] = False
res = 0
for prime in primes:
  if n % prime == 0:
    res += 1
print(res)

！！数学优化（90%）

1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
res = 0
i = 2
while i * i < n:
  if n % i == 0:
    res += 1
    while n % i == 0:
      n //= i
  i += 1 
if n > 1:
  res += 1
print(res)

全排列的价值

1
2
3
4
5
6
7
8
9
10
n = int(input())
nums = [0] + [0] * n
MOD = 998244353 
fac, sum1 = [1] * (n + 1), [1] * (n + 1)
for i in range(2, n + 1):
  fac[i] = fac[i - 1] * i % MOD
  sum1[i] = sum1[i - 1] + i % MOD
for i in range(2, n + 1):
  nums[i] = (i * nums[i - 1] + fac[i - 1] * sum1[i - 1]) % MOD
print(nums[n])

混乱的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
n = int(input())
if n == 10:
  print(5)
  print('5 4 3 2 1')
elif n == 9:
  print(5)
  print('4 3 2 1 1')
elif n == 8:
  print(5)
  print('3 2 2 1 1')
elif n == 7:
  print(5)
  print('3 2 1 1 1')
elif n == 6:
  print(4)
  print('4 3 2 1')
elif n == 5:
  print(4)
  print('3 2 1 1')
elif n == 4:
  print(4)
  print('2 2 1 1')
elif n == 3:
  print(3)
  print('3 2 1')
elif n == 2:
  print(3)
  print('2 1 1')
elif n == 1:
  print(2)
  print('2 1')
else:
  for i in range(100):
    if i * (i - 1) // 2 == n:
      print(i)
      print(*range(i, 0, -1))

完全日期

1
2
3
4
5
6
7
8
9
10
11
from datetime import datetime, timedelta
start = datetime(2001, 1, 1)
end = datetime(2021, 12, 31)
res = 0
while start <= end:
  t = start.strftime("%Y%m%d")
  a = sum([int(i) for i in t])
  if a in [4, 9, 16, 25, 36]:
    res += 1
  start += timedelta(days=1)
print(res)

带宽

1
print(200 // 8)

小蓝的旅行计划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import heapq, sys
n, m = map(int, input().split())
left = [0]
oils = [0] * (n + 1)
oils[0] = m
cost = []
consume = 0
for i in range(1, n + 1):
  a, b, c = map(int, input().split())
  left.append(c)
  if a > m:
    print(-1)
    sys.exit(0)
  if oils[i - 1] < a:
    while cost and oils[i - 1] < a:
      price, idx = cost[0]
      maxadd = min(left[idx], m - oils[i - 1])
      if maxadd >= a - oils[i - 1]:
        maxadd = a - oils[i - 1]
      consume += price * maxadd
      oils[i - 1] += maxadd
      left[idx] -= maxadd
      if left[idx] == 0:
        heapq.heappop(cost)
  if oils[i - 1] < a:
    print(-1)
    sys.exit(0)    
  heapq.heappush(cost, (b, i))
  oils[i] = oils[i - 1] - a
print(consume)

斐波那契与7

1
2
3
# 14, 16, 17, 23, 34, 37, 43, 56  从14开始，60个循环，
# (202202011200 - 14) % 60 = 46
print((202202011200 - 14) // 60 * 8 + 8)

GCD

！！暴力（20%）

1
2
3
4
5
6
7
8
9
10
11
def gcd(a, b):
  return gcd(b, a % b) if b else a
a, b = map(int, input().split())
res = 1
maxgcd = 0
for i in range(1, 1000000):
  t = gcd(a + i, b + i)
  if t > maxgcd:
    res = i
    maxgcd = t
print(res)

！！数学

1
2
3
4
5
6
7
8
a, b = map(int, input().split())
if a > b:
  a, b = b, a
c = b - a
if c < a:
  c = (a // c + 1) * c
k = c - a
print(k)

最小权值

1
2
3
4
5
6
7
dp = [float('inf')] * 2022
dp[0] = 0
for i in range(1, 2022):
  for j in range(i):
    l, r = j, i - j - 1
    dp[i] = min(dp[i], 1 + 2 * dp[l] + 3 * dp[r] + l * l * r)
print(dp[2021])

二进制问题

！！暴力（40%）

1
2
3
4
5
6
7
8
9
10
11
12
13
n, k = map(int, input().split())
def check(x):
  cnt = 0
  while x:
    if x & 1:
      cnt += 1
    x >>= 1
  return cnt == k
res = 0
for i in range(1, n + 1):
  if check(i):
    res += 1
print(res)

最优清零方案

！！暴力（60%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n, k = map(int, input().split())
nums = list(map(int, input().split()))
res = 0
for _ in range(1000):
  for i in range(n - k + 1):
    a = min(nums[i: i + k])
    if a:
      for j in range(i, i + k):
        nums[j] -= a
      res += a
    else:
      res += nums[i]
      nums[i] = 0
  if all(nums):
    break
  for i in range(n - k + 1, n):
    res += nums[i]
    nums[i] = 0
print(res)

！！优化

1
2
3
4
5
6
7
8
9
10
11
12
13
n, k = map(int, input().split())
nums = list(map(int, input().split()))
idx =res = 0
while idx + k - 1 < n:
  mint = min(nums[idx: idx + k])
  imint = nums[idx: idx + k].index(mint)
  if mint > 0:
    for j in range(idx, idx + k):
      nums[j] -= mint
    res += mint
  idx += imint + 1
res += sum(nums)
print(res)

本质上升序列

！！暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
s = 'tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl'
n = 200
tmp = [set(char) for char in s]
for i in range(n):
  for j in range(i):
    if s[j] < s[i]:
      for t in tmp[j]:
        tmp[i].add(t + s[i])
res = set()
for t in tmp:
  for i in t:
    res.add(i)
print(len(res))
# print(3616159)

！！动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
s = 'tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl'
n = 200
tmp = [set(char) for char in s]
for i in range(n):
  for j in range(i):
    if s[j] < s[i]:
      for t in tmp[j]:
        tmp[i].add(t + s[i])
res = set()
for t in tmp:
  for i in t:
    res.add(i)
print(len(res))
# print(3616159)

矩形拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
T = int(input())
def check4(a1, b1, a2, b2, a3, b3):
  for i in [a1, b1]:
    for j in [a2, b2]:
      for k in [a3, b3]:
        if i == j == k:
          return True
        if i == j and a1 + b1 + a2 + b2 - i - j == k:
          return True
        if i == k and a1 + b1 + a3 + b3 - i - k == j:
          return True
        if j == k and a2 + b2 + a3 + b3 - j - k == i:
          return True
  return False
def check6(a1, b1, a2, b2, a3, b3):
  for i in [a1, b1]:
    for j in [a2, b2]:
      for k in [a3, b3]:
        if i == j or j == k or i == k:
          return True
        if i + j == k or i + k == j or j + k == i:
          return True
for _ in range(T):
  a1, b1, a2, b2, a3, b3 = map(int, input().split())
  if check4(a1, b1, a2, b2, a3, b3):
    print(4)
  elif check6(a1, b1, a2, b2, a3, b3):
    print(6)
  else:
    print(8)

重复字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
k = int(input())
s = input()
nums = []
res = 0
if len(s) % k:
  print(-1)
else:
  n = len(s) // k
  for i in range(0, len(s), n):
    nums.append(s[i: i + n])
  a = [[0] * 27 for _ in range(n)]
  for i in range(n):
    for j in range(k):
      a[i][ord(nums[j][i]) - 97] += 1
  for i in a:
    res += sum(i) - max(i)
  print(res)

小蓝做实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = 100000000
state = [True] * (n + 1)
def check(x):
  for i in range(2, int(x ** 0.5) + 1):
    if x % i == 0:
      return False
  return True
for i in range(2, n + 1):
  if state[i]:
    for i in range(i * 2, n + 1, i):
      state[i] = False
res = 0
with open('primes_2.txt') as f:
  for i in f.readlines():
    i = int(i.strip('\n'))
    if i > 1e8:
      if check(i):
        res += 1
    else:
      if state[i]:
        res += 1
print(res)
print(342693)

近似gcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gcd(a, b):
  return gcd(b, a % b) if b else a
n, g = map(int, input().split())
nums = list(map(int, input().split()))
l = r = res = 0
t = -1
for r in range(n):
  a = gcd(g, nums[r])
  if a != g:
    l = t + 1
    t = r
  if r - l + 1 >= 2:
    res += r - l
print(res)

环境治理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
n, q = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(n)]
L = [list(map(int, input().split())) for _ in range(n)]
def check(mid):
  g = [[D[i][j] for j in range(n)] for i in range(n)]
  circle, remain = mid // n, mid % n
  for i in range(n):
    for j in range(n):
      g[i][j] = g[j][i] = max(L[i][j], g[i][j] - circle)
  for i in range(remain):
    for j in range(n):
      g[i][j] = g[j][i] = max(L[i][j], g[i][j] - 1)
  for k in range(n):
    for i in range(n):
      for j in range(n):
        g[i][j] = min(g[i][j], g[i][k] + g[k][j])
  p = sum([sum(i) for i in g])
  return p <= q
l, r = 0, 10000000
while l < r:
  mid = l + r >> 1
  if check(mid):
    r = mid
  else:
    l = mid + 1
print(l if l < 10000000 else -1)

取模

！！暴力（35%）

1
2
3
4
5
6
7
8
9
10
11
12
13
T = int(input())
def check(n, m):
  for x in range(1, m):
    for y in range(x + 1, m + 1):
      if n % x == n % y:
        return True
  return False
for _ in range(T):
  n, m = map(int, input().split())
  if check(n, m):
    print('Yes')
  else:
    print('No')

！！暴力换个顺序就全通过了

1
2
3
4
5
6
7
8
9
10
11
12
13
T = int(input())
def check(n, m):
  for y in range(2, m + 1):
    for x in range(1, y):
      if n % x == n % y:
        return True
  return False
for _ in range(T):
  n, m = map(int, input().split())
  if check(n, m):
    print('Yes')
  else:
    print('No')

！！反证法

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys
T = int(input())
def check(n, m):
  for i in range(1, m + 1):
    if n % i != i - 1:
      return True
  return False
for _ in range(T):
  n, m = map(int, input().split())
  if check(n, m):
    print('Yes')
  else:
    print('No')

和与乘积

！！暴力（30%）

1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
nums = list(map(int, input().split()))
muls, sums = [1] * (n + 1), [0] * (n + 1)
for i in range(1, n + 1):
  muls[i] = muls[i - 1] * nums[i - 1]
  sums[i] = sums[i - 1] + nums[i - 1]
res = 0
for r in range(1, n + 1):
  for l in range(1, i + 1):
    if sums[r] - sums[l - 1] == muls[r] // muls[l - 1]:
      res += 1
print(res)

！！优化–处理连续的1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
n = int(input())
nums = list(map(int, input().split()))
res = cnt = 0
preone = [0] * (n) # 前面有多少个1
for i in range(n):
  preone[i] = cnt
  if nums[i] == 1:
    cnt += 1
  else:
    cnt = 0
for r in range(n):
  he, ji = 0, 1
  l = r
  while l >= 0:
    he += nums[l]
    ji *= nums[l]
    if he == ji:
      res += 1
    if ji - he > l:
      break
    if preone[l] == 0:
      l -= 1
      continue
    if ji <= he:
      he += preone[l]
    else:
      he += preone[l]
      if ji <= he:
        res += 1
    l -= preone[l]
    l -= 1
print(res)

替换字符

！！暴力（40%）

1
2
3
4
5
6
7
8
9
s = list(input())
n = len(s)
m = int(input())
for _ in range(m):
  l, r, x, y = input().split()
  for i in range(int(l), int(r) + 1):
    if s[i - 1] == x:
      s[i - 1] = y
print(''.join(map(str, s)))

！！用replace方法

1
2
3
4
5
6
7
8
9
10
11
s = input()
m = int(input())
for _ in range(m):
  l, r, x, y = input().split()
  l, r = int(l), int(r)
  s1 = s[: l - 1]
  s2 = s[l - 1: r]
  s2 = s2.replace(x, y)
  s3 = s[r:]
  s = s1 + s2 + s3
print(s)

打折

！！暴力（40%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n, m = map(int, input().split())
nums = [[float('inf')] * (n + 1) for _ in range(1001)]
for _ in range(m):
  s, t, p, c = map(int, input().split())
  tmps = []
  for _ in range(c):
    a, b = map(int, input().split())
    tmps.append((a, b * p // 100, b))
  for i in range(1, 1001):
    for tmp in tmps:
      if s <= i <= t:
        nums[i][tmp[0]] = min(nums[i][tmp[0]], tmp[1])
      else:
        nums[i][tmp[0]] = min(nums[i][tmp[0]], tmp[2])
res = float('inf')
for num in nums:
  res = min(res, sum(num[1:]))
print(res)

翻转括号序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n, m = map(int, input().split())
s = input()
nums = [0] * n
for i in range(n):
  if s[i] == '(':
    nums[i] = 1
  else:
    nums[i] = -1
for _ in range(m):
  li = list(map(int, input().split()))
  if li[0] == 1:
    l, r = int(li[1]), int(li[2])
    for i in range(l - 1, r):
      nums[i] *= -1
  if li[0] == 2:
    l = int(li[1]) - 1
    res = t = 0
    for i in range(l, n):
      t += nums[i]
      if t < 0:
        break
      elif t == 0:
        res = i + 1
    print(res)

斐波那契数组

1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())
fib = [1, 1]
res = 0
nums = list(map(int, input().split()))
dic = {}
for i in range(2, 30):
  fib.append(fib[i - 1] + fib[i - 2])
for i in range(n):
  if i >= 30:
    res += 1
  else:
    dic[nums[i] / fib[i]] = dic.get(nums[i] / fib[i], 0) + 1
print(res + min(30, n) - max(dic.values()))

最少的1

！！暴力（30%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fun(x):
  cnt = 0
  while x:
    if x & 1:
      cnt += 1
    x >>= 1
  return cnt
n = int(input())
res = float('inf')
for i in range(2, 1000):
  cnt = fun(n)
  n *= i
  res = min(res, cnt)
print(res)

冰山

！！暴力（80%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n, m, k = map(int, input().split())
nums = {}
a = list(map(int, input().split()))
for i in a:
  nums[i] = nums.get(i, 0) + 1
MOD = 998244353
for _ in range(m):
  x, y = map(int, input().split())
  nums = {k + x: v for k, v in nums.items() if k + x > 0}
  for key, value in nums.copy().items():
    if key > k:
      del nums[key]
      nums[k] = (nums.get(k, 0) + value) % MOD
      nums[1] = (nums.get(1, 0) +(key - k) * value) % MOD
  if y:
    nums[y] = nums.get(y, 0) + 1
  res = 0
  for key, value in nums.items():
    res = (res + key * value) % MOD
  print(res)

六六大顺

！！暴力（30%）

1
2
3
4
5
6
n = int(input())
res = 0
for i in range(n):
  t = i * '4' + '3' + i * '5' + '6'
  res += int(t)
print(res)

补给

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n, d = map(int, input().split())
g = [[0] * n for _ in range(n)]
p = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
  for j in range(i + 1, n):
    t = ((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2) ** 0.5
    if t > d:
      g[i][j] = g[j][i] = float('inf')
    else:
      g[i][j] = g[j][i] = t
# floyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      g[i][j] = min(g[i][j], g[i][k] + g[j][k])
f = [[float('inf')] * n for j in range(1 << n)]
f[1][0] = 0
for j in range(1, 1 << n):
  for i in range(n):
    if (j >> i) & 1:
      for k in range(n):
        if k != i and (j >> k) & 1:
          f[j][i] = min(f[j][i], f[j - (1 << i)][k] + g[k][i])
res = min(f[(1 << n) - 1][i] + g[i][0] for i in range(n))
print(f"{res:.2f}")

分石头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
t=int(input())
def is_prime(i):
  count=0
  j=3
  while 1:
    if(i%j==0):  
      count+=1
      i//=j
      j=2
    j+=1
    if(i==1):break
    if(j*j>=i):
      if(j*j==i): 
        count+=1
      count+=1
      break
  return count%2

for _ in range(t):
  n=int(input())  
  a=list(map(int,input().split())) 
  ou=0;ji=0 
  s=0
  for i in a:
    while i%2==0: 
      i//=2
    if(is_prime(i)==0): 
      ou+=1
    else:ji+=1
  # 如果石子堆数是奇数，或者质数的数量是奇数，则小蓝有必胜策略
  if(len(a)%2==1 or ji%2==1):
    print(1)
  else:
    print(0)

注意

二分找左边界l=mid+1,找右边界r=mid-1，并且mid=l+r+1>>1

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~