总结

• 又是笨比的一周，只做出1题。
• T1 数学
• T2 前后缀分解
• T3 dp
• T4 贪心平均数
• 

小美的外卖订单编号

链接: 小美的外卖订单编号

1. 题目描述

2. 思路分析

• 由于数据是1开始的，先减1，取模后再+1

3. 代码实现

def solve():m, x = RI()x = (x - 1) % mprint(x + 1)

小美的加法

链接: 小美的加法

1. 题目描述

2. 思路分析

• 一个傻的做法是前后缀分解。
• 其实扫一遍，枚举两个数，s减去即可。

3. 代码实现

#       ms
def solve():n, = RI()a = RILST()s = sum(a)ans = 0for i in range(n - 1):ans = max(ans, s - a[i] - a[i + 1] + a[i] * a[i + 1])print(ans)#       ms
def solve1():n, = RI()a = RILST()p = [0] + list(accumulate(a))s = list(accumulate(a[::-1]))[::-1] + [0]ans = p[-1]for i in range(n - 1):ans = max(ans, p[i] + a[i] * a[i + 1] + s[i + 2])print(ans)

小美的01串翻转

链接: 小美的01串翻转

1. 题目描述

2. 思路分析

• 看数据可以n方。
• 那么枚举每个子段，dp即可。

3. 代码实现

#       ms
def solve():s, = RS()n = len(s)ans = 0for l in range(n):x = y = 0if s[l] == '1':x = 1else:y = 1for r in range(l + 1, n):if s[r] == '1':x, y = y + 1, xelse:x, y = y, x + 1ans += min(x, y)print(ans)#       ms
def solve1():s, = RS()n = len(s)f = [[0, 0] for _ in range(n)]ans = 0for l in range(n):f[l] = [0, 0]f[l][int(s[l]) ^ 1] = 1for r in range(l + 1, n):if s[r] == '1':f[r] = [f[r - 1][1] + 1, f[r - 1][0]]else:f[r] = [f[r - 1][1], f[r - 1][0] + 1]ans += min(f[r])print(ans)

小美的数组操作

链接: 小美的数组操作

1. 题目描述

2. 思路分析

• 容易想到，要使众数最多，那么数量不是n就是n-1。
• 当sum能整除n时，一定可以使所有数变成同一个数，就是平均数，直接计算即可。
• 否则，可以尝试把其中n-1个变成一样的，另一个数承载垃圾操作。那么这个数一定是最大的数或者最小的数。
  • 那目标数字应该是这n-1个数的平均数，步数才是最小的。注意这个数可能不是整数，s/t,s/t+1都试试。

3. 代码实现

def f(a, t):x = y = 0for v in a:if v > t:x += v - telse:y += t - vreturn max(x, y)#       ms
def solve():n, = RI()a = RILST()s = sum(a)if s % n == 0:t = s // nans = 0for v in a:ans += max(0, v - t)print(ans)else:a.sort()t = (s - a[-1]) // (n - 1)ans = min(f(a[:-1], t), f(a[:-1], t + 1))t = (s - a[0]) // (n - 1)ans = min(ans, f(a[1:], t), f(a[1:], t + 1))print(ans)

六、参考链接

• 无