洛谷pP2708 硬币翻转

问题描述

给定长度为 $n$ 的 $01$ 串，定义一次操作为把一个区间 $[l,r]$ 内的 $0$ 变成 $1$，$1$ 变成 $0$。求最少操作次数使得 $01$ 串变成 $11\cdots 1$ 或者 $00\cdots 0$。

约定：

• 区间 $[l,r]$ 指 $[l,r]$ 之间的字符，$1\leq l\leq r\leq n$。

输入格式

第一行一个整数 $n$，表示字符串长度。

第二行一个长度为 $n$ 的 $01$ 串。

输出格式

输出一个数，表示最少操作次数。

样例输入1

3
101

样例输出1

2

样例说明1

将区间 $[1,2]$ 翻转一次，将区间 $[2,3]$ 翻转一次。

样例输入2

5
11111

样例输出2

0

样例说明2

$01$ 串已经为 $11111$。

样例输入3

6
101010

样例输出3

3

样例说明3

将区间 $[2,3]$ 翻转一次，将区间 $[4,5]$ 翻转一次，将区间 $[6,6]$ 翻转一次。

思路分析

我们可以定义一个差异数组 $d$，用来记录 $01$ 串中每一个位置上的字符与目标串 $11\cdots 1$ 或者 $00\cdots 0$ 的字符差异。

最后问题被转化为将这个差异数组的和转换成 $0$ 的问题，因为每一次翻转操作都会将差异数组的和减少 $2\Delta$。

所以问题被转化为了求差异数组中连续的一些子区间，将其和转化成 $0$ 的问题，这个问题可以使用前缀和和哈希表优化求解。

代码实现

n = int(input())
s = input()

d = []
for i in range(n):
    if s[i] == '0':
        d.append(1)
    else:
        d.append(-1)

pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + d[i]

cnt = {}
ans = 0
for i in range(n + 1):
    x = pre[i]
    ans += cnt.get(x, 0)
    cnt[x] = cnt.get(x, 0) + 1
print(ans)

总结

本文是对洛谷 pP2708 硬币翻转题目的一个详细解答，通过前缀和和哈希表的优化，实现了对该问题的高效求解。