现在他想从 s 中,尽可能切割出多个他喜欢的单词,请问最多能切割出多少个?单词指的是由若干个连续的字符组成的子字符串。
代码示例
s = input().strip()
count = 0
i = 0
n = len(s)
while i <= n - 3:
if {s[i], s[i+1], s[i+2]} == {'l', 'q', 'b'}:
count += 1
i += 3else:
i += 1print(count)
L = int(input())
count = 0for xa inrange(1, L + 1):
for ya inrange(1, L + 1):
for xb inrange(1, L + 1):
for yb inrange(1, L + 1):
if xa * xb + ya * yb <= L:
count += 1print(count)
2. 优化枚举
L = int(input())
count = 0for xa inrange(1, L + 1):
for ya inrange(1, L + 1):
max_sum = L
for xb inrange(1, L + 1):
remain = max_sum - xa * xb
if remain <= 0:
break
max_yb = remain // ya
if max_yb >= 1:
count += max_yb
print(count)
3. 数学优化(数论 + 前缀和)
L = int(input())
ans = 0
a = [0] * (L + 1) # a[s] 表示 s 的约数个数
b = [0] * (L + 1) # b[t] 表示前缀和# 步骤 1:计算每个数的约数个数for i inrange(1, L + 1):
for j inrange(i, L + 1, i):
a[j] += 1# 步骤 2:计算约数个数的前缀和for i inrange(1, L + 1):
b[i] = b[i-1] + a[i]
# 步骤 3:统计答案for i inrange(1, L + 1):
ans += a[i] * b[L-i]
print(ans)
小蓝从左到右种了 n 棵小树,第 i 棵树的高度为 hi,相邻树的间隔相同。小蓝想挪走一些树使得剩下的树等间隔分布,且从左到右高度逐渐上升(相邻两棵树高度满足右边的比左边的高),小蓝想知道最多能留下多少棵树。
1. 暴力枚举法
n = int(input())
h = list(map(int, input().split()))
if n == 0:
print(0)
max_len = 1for i inrange(n):
for d inrange(1, n):
current_pos = i
current_len = 1
prev_height = h[current_pos]
next_pos = current_pos + d
while next_pos < n:
if h[next_pos] > prev_height:
current_len += 1
prev_height = h[next_pos]
current_pos = next_pos
next_pos = current_pos + d
else:
breakif current_len >= 2:
if current_len > max_len:
max_len = current_len
print(max_len)
2. 动态规划 (O(n²))
n = int(input())
a = list(map(int, input().split()))
dp = [[1] * (n + 1) for i inrange(n)]
for i inrange(n):
for j inrange(i):
if a[i] > a[j]:
d = i - j
dp[i][d] = max(dp[i][d], dp[j][d] + 1)
ans = 0for row in dp:
ifmax(row) > ans:
ans = max(row)
print(ans)
在一个偏远的图书馆里,有个书架上放着 n 本书,每本书上都标有一个从 1 到 n 的唯一编号。按照规矩,这些书应该按编号从小到大依次排列。可昨天店里人来人往,借书还书忙得不可开交,书架上的顺序出现了错乱。现在,书架上的书变成了 a=(a1,a2,…,an),其中 ai 表示第 i 个位置上的书编号。管理员决定动手整理书架,但时间有限,他希望用最少的操作把书的顺序恢复到正确的排列。每次操作,他可以挑选书架上任意两本书,交换它们的位置。
n = int(input())
nums = list(map(int, input().split()))
ans = 0for i inrange(n):
for j inrange(i+1, n):
x = j - i
ans += (nums[i] ^ nums[j]) * x
print(ans)