2025春季算法练习——Week 5

2025-04-05 · 15 分钟阅读 · 算法深搜数论贪心策略动态规划最小生成树 Kruskal 并查集质数筛模拟 Manacher ·

复制链接:

文章目录

题目来自蓝桥云课

19714 数字诗意 | 原题链接

假设数字 $n$ 可以被表示为从 $a$ 到 $a+k-1$ 共 $k$ 个数字的和，则 $n=\frac{k(2a+k-1)}2$，通过观察不难发现，$n$ 一定有奇数因子。也就是说，如果一个数是 $2$ 的幂，那么它一定没有诗意。

令 $n=o\cdot e$，$o$ 为 $n$ 的奇数因子，$e$ 为 $n$ 的偶数因子。当 $o>e$ 时，令 $k=e$，则 $a=\frac{o+1-e}2$，此时 $a\in \mathbb{N_+}$；当 $o<e$ 时，令 $k=o$，则 $a=\frac{e+1-o}2$，此时 $a\in \mathbb{N_+}$。

因此当且仅当 $n\neq2^k$ 时，$n$ 有诗意。

 1_ = int(input().strip())
 2nums = tuple(map(int, input().strip().split()))
 3p2 = set()
 4p = 1
 5while p <= 1e16:
 6    p2.add(p)
 7    p *= 2
 8count = 0
 9for num in nums:
10    if num in p2:
11        count += 1
12print(count)

19715 回文数组 | 原题链接

模拟一下就行。

 1n = int(input().strip())
 2nums = list(map(int, input().strip().split()))
 3mid = n // 2
 4count = 0
 5for i in range(mid):
 6    if nums[i] != nums[n - i - 1]:
 7        if nums[i] > nums[n - i - 1] and nums[i + 1] > nums[n - i - 2] and i + 1 < mid:
 8            min_diff = min(nums[i] - nums[n - i - 1], nums[i + 1] - nums[n - i - 2])
 9            count += min_diff
10            nums[i] -= min_diff
11            nums[i + 1] -= min_diff
12        elif nums[i] < nums[n - i - 1] and nums[i + 1] < nums[n - i - 2] and i + 1 < mid:
13            min_diff = min(nums[n - i - 1] - nums[i], nums[n - i - 2] - nums[i + 1])
14            count += min_diff
15            nums[i] += min_diff
16            nums[i + 1] += min_diff
17
18        if nums[i] > nums[n - i - 1]:
19            count += nums[i] - nums[n - i - 1]
20            nums[i] = nums[n - i - 1]
21        elif nums[i] < nums[n - i - 1]:
22            count += nums[n - i - 1] - nums[i]
23            nums[i] = nums[n - i - 1]
24print(count)

19719 吊坠 | 原题链接

首先用动态规划求出所有字符串两两之间的最大权值，然后用 Kruskal 算法得到一个最大生成树。

 1import sys
 2import heapq
 3
 4data = sys.stdin.read().strip().splitlines()
 5n, m = map(int, data[0].strip().split())
 6s = list()
 7for i in range(1, n + 1):
 8    s.append(data[i].strip())
 9
10edges = list()
11for i in range(n):
12    for j in range(i + 1, n):
13        s1 = s[i] * 2
14        s2 = s[j] * 2
15        dp = [[0 for _ in range(2 * m + 1)] for _ in range(2 * m + 1)]
16        curr_max = 0
17        for k1 in range(1, 2 * m + 1):
18            for k2 in range(1, 2 * m + 1):
19                if s1[k1 - 1] == s2[k2 - 1]:
20                    dp[k1][k2] = dp[k1 - 1][k2 - 1] + 1
21                    if dp[k1][k2] > curr_max:
22                        curr_max = dp[k1][k2]
23        heapq.heappush(edges, (-min(m, curr_max), i, j))
24
25pre = [i for i in range(n)]
26
27def find(x):
28    if pre[x] != x:
29        pre[x] = find(pre[x])
30    return pre[x]
31
32ans = 0
33while edges:
34    w, u, v = heapq.heappop(edges)
35    w = -w
36
37    root1 = find(u)
38    root2 = find(v)
39    if root1 != root2:
40        pre[root1] = root2
41        ans += w
42print(ans)

这道题还用到了破环成链的技巧，对于环形字符串匹配，只需要将字符串复制一遍再求最长公共子串（最长子串长度不能比原串长）。另外最长公共子串必须是连续的，不连续的叫公共子序列。

上面这段代码只能通过部分测试点。

19722 砍柴 | 原题链接

最开始以为是一道博弈论题目，但后来发现这道题用简单的递推就能解决。

定义一个数组 status 并初始化为 $0$。status[i] 记录的是初始长度为 $i$ 时的最终结果。遍历 $i$，如果存在一个质数 $p$ 使得 status[i - p] = 0，则令 status[i] = 1。所有质数用质数筛生成（也可以打表）。

 1MAX_N = int(1e5) + 5
 2ps = [True] * MAX_N
 3ps[0] = ps[1] = False
 4
 5def sieve():
 6    for i in range(2, MAX_N):
 7        if ps[i]:
 8            for j in range(i * i, MAX_N, i):
 9                ps[j] = False
10    primes = list()
11    for i in range(MAX_N):
12        if ps[i]:
13            primes.append(i)
14    return primes
15
16primes = sieve()
17
18dp = [0] * MAX_N
19for i in range(MAX_N):
20    for p in primes:
21        if i >= p:
22            if dp[i - p] == 0:
23                dp[i] = 1
24                break
25        else:
26            break
27
28n = int(input().strip())
29for _ in range(n):
30    i = int(input().strip())
31    print(dp[i])

19720 智力测试 | 原题链接

这道题我不会，我只会骗分……

这道题格子中每行每列都有一个对应的 $(R,C)$ 值，而跳跃规则是：

目标格子只能是 $(R',C)$ 或者 $(R,C')$
目标格子中 $R'>R$ 或者 $C'>C$
若将全部的 $R$ 值排列，当前格子中的 $R$ 与目标格子中的 $R'$ 间不能有其他 $R$ 值，对 $C$ 同理

最朴素的思想就是，先将全部 $R$ 和 $C$ 分别建立一个“跳跃网络”，也就是一个有向图，然后用深搜或者 DP 计算出每次查询的结果。这样只能过一个测试点 QAQ

 1import sys
 2from collections import defaultdict
 3
 4MOD = 1000000007
 5data = sys.stdin.read().strip().splitlines()
 6n, m, t = map(int, data[0].strip().split())
 7r_ = tuple(map(int, data[1].strip().split()))
 8c_ = tuple(map(int, data[2].strip().split()))
 9r, c = list(), list()
10for i in range(n):
11    r.append((r_[i], i))
12r.sort()
13for i in range(m):
14    c.append((c_[i], i))
15c.sort()
16
17r_graph = defaultdict(list)
18c_graph = defaultdict(list)
19
20for i in range(n):
21    j = i
22    while j < n and r[i][0] == r[j][0]:
23        j += 1
24    k = j
25    while k < n and r[j][0] == r[k][0]:
26        r_graph[r[i][1]].append(r[k][1])
27        k += 1
28
29for i in range(m):
30    j = i
31    while j < m and c[i][0] == c[j][0]:
32        j += 1
33    k = j
34    while k < m and c[j][0] == c[k][0]:
35        c_graph[c[i][1]].append(c[k][1])
36        k += 1
37
38def dfs(curr_c, curr_r, dest_c, dest_r, memo):
39    if curr_c == dest_c and curr_r == dest_r:
40        return 1
41
42    if memo[(curr_c, curr_r)] != -1:
43        return memo[(curr_c, curr_r)]
44
45    ans = 0
46    for next_c in c_graph[curr_c]:
47        ans += dfs(next_c, curr_r, dest_c, dest_r, memo)
48        ans %= MOD
49
50    for next_r in r_graph[curr_r]:
51        ans += dfs(curr_c, next_r, dest_c, dest_r, memo)
52        ans %= MOD
53
54    memo[(curr_c, curr_r)] = ans
55    return ans
56
57for i in range(3, t + 3):
58    sr, sc, tr, tc = map(int, data[i].strip().split())
59    memo = defaultdict(lambda: -1)
60    print(dfs(sc - 1, sr - 1, tc - 1, tr - 1, memo))

如果用了 lru_cache 就连一个点都过不了了，全部都段错误。

不要忘记模数！

19721 最大异或结点 | 原题链接

这道题是143. 最大异或对的加强版，这道题中并非任意两个数异或结果都有效。

对原有的 TrieNode 进行改进，添加 NO 和 parent 属性，其中 NO 记录通过当前结点的数字编号，parent 属性分别记录左右子节点中通过数字的父节点编号。在创建 Trie 树时，某个数字沿途经过的全部 TrieNode 结点都应该记录下该数字的编号以及直接相连节点。在后续遍历 Trie 树时，要想判断某个当前路径是否合法，只要判断当前 TrieNode 是否只有一个数通过，且这个数与当前正在遍历的数直接相连，如果是则异或不合法。

 1class TrieNode:
 2
 3    def __init__(self):
 4        self.children = [None, None]
 5        self.NO = set()
 6        self.parent = [set(), set()]
 7
 8n = int(input().strip())
 9nums = tuple(map(int, input().strip().split()))
10parents = tuple(map(int, input().strip().split()))
11
12trie = TrieNode()
13for i in range(n):
14    num = nums[i]
15    parent = parents[i]
16    node = trie
17    for pos in range(32)[::-1]:
18        bit = (num >> pos) & 1
19        if node.children[bit] is None:
20            node.children[bit] = TrieNode()
21        node.NO.add(i)
22        node.parent[bit].add(parent)
23        node = node.children[bit]
24
25max_xor = 0
26for i in range(n):
27    num = nums[i]
28    parent = parents[i]
29    node = trie
30    other = 0
31    for pos in range(32)[::-1]:
32        bit = 1 - ((num >> pos) & 1)
33        if node.children[bit] is not None and (len(node.parent[bit]) != 1 or i not in node.parent[bit]) and (parent not in node.NO or len(node.NO) != 1):
34            other |= bit << pos
35            node = node.children[bit]
36        elif node.children[1 - bit] is not None and (len(node.parent[1 - bit]) != 1 or i not in node.parent[1 - bit]) and (parent not in node.NO or len(node.NO) != 1):
37            other |= (1 - bit) << pos
38            node = node.children[1 - bit]
39    max_xor = max(max_xor, other ^ num)
40
41print(max_xor)

2928 分糖果 | 原题链接

题目描述很奇怪，最开始没有理解“字典序相差尽量小”是什么意思，复盘时看题解才理解：假设有一个包含所有长度在 $10^6$ 以下的字符串的有序列表，两个字符串之间相隔的字符串越少，则两个字符串的字典序相差尽量小。例如 "a" 与 "abc" 间的距离大于 "a" 与 "abbc" 间的距离。为了更好分配全部字符，原始字符串必须要先排序。此时如果要让字典序相差尽量小，则有以下三种情况：

将前 x 个字符依次分配给 x 个人，此时如果最后一个人拿到的字符和其他人不同，那么就没必要再考虑这个人了，因为不论最后这个人后面再加什么字符，他和前面的距离都不会减小，而他自身还会变大，因此这种情况下的最优方案就是最后一人只取一个字符。
如果除去第一轮发的 x 个字符，剩下的字符全部相同，那么可以将剩下字符平分给所有人。需要注意最后一人的字符串一定是最长的那个。
如果剩下的字符各不相同，为了让最后一个人的字符串尽可能小，这个人应该把后面的全部字符都拿走。例如对于 abc 和 abbc，显然后者更小，让尽可能多的相同字符填充能够让字符串在字典序中更靠前。

1n, x = map(int, input().strip().split())
2s = sorted(input().strip())
3
4if s[0] != s[x - 1]:
5    print(s[x - 1])
6elif s[x] == s[-1]:
7    print(s[x - 1] + "".join(s[x:n:x]))
8else:
9    print("".join(s[x - 1 :]))

3518 三国游戏 | 原题链接

如果想要有任意次事件发生后 $X>Y+Z$，则在这任意次事件中至少有一次 $A_i>B_i+C_i$，即 $A_i-B_i-C_i>0$。题目要求能够在尽可能多的事件发生后，仍有 $X>Y+Z$，则可以记录每次事件 $A_i-B_i-C_i$ 的值，如果大于零就直接任其发生，如果小于零就添加到待处理的列表中。当所有正事件发生完后，将待处理的列表按照从大到小排序，也就是对 $X$ 的减损越小越靠前，然后不断将其累加到 $X$ 上直到 $X\leq0$。此时发生的事件数就是能够满足 $X>Y+Z$ 的最大事件数，对 $Y$ 和 $Z$ 同理。

 1n = int(input().strip())
 2_a = list(map(int, input().strip().split()))
 3_b = list(map(int, input().strip().split()))
 4_c = list(map(int, input().strip().split()))
 5
 6def win(a, b, c, n):
 7    minus = list()
 8    ext = 0
 9    count = 0
10    for i in range(n):
11        curr = a[i] - b[i] - c[i]
12        if curr > 0:
13            ext += curr
14            count += 1
15        else:
16            minus.append(curr)
17    minus.sort(reverse=True)
18    for i in range(len(minus)):
19        ext += minus[i]
20        if ext <= 0:
21            break
22        count += 1
23    return count if count else -1
24
25a_win = win(_a, _b, _c, n)
26b_win = win(_b, _c, _a, n)
27c_win = win(_c, _a, _b, n)
28print(max(a_win, b_win, c_win))

3532 平均 | 原题链接

这道题在 AcWing 上做过但是没有写题解。这道题本身不难，非常容易想到的贪心，就是先转换多余且代价小的数。

 1import sys
 2
 3count = [0] * 10
 4price = [list() for _ in range(10)]
 5ext = [False] * 10
 6data = sys.stdin.read().strip().splitlines()
 7n = int(data[0])
 8avg = n // 10
 9for i in range(1, n + 1):
10    ai, bi = map(int, data[i].strip().split())
11    count[ai] += 1
12    price[ai].append(bi)
13    if count[ai] > avg:
14        ext[ai] = True
15
16for i in range(10):
17    price[i].sort(reverse=True)
18
19total = 0
20for i in range(10):
21    if ext[i]:
22        total += sum(price[i][avg:])
23print(total)

3520 翻转 | 原题链接

这道题也简单，模拟一下即可。

 1import sys
 2
 3swap = {'0': '1', '1': '0'}
 4data = sys.stdin.read().strip().splitlines()
 5d = int(data[0].strip())
 6for i in range(1, 2 * d + 1, 2):
 7    t = list(data[i].strip())
 8    s = list(data[i + 1].strip())
 9    if s == t:
10        print(0)
11        continue
12
13    if t[0] != s[0] or t[-1] != s[-1]:
14        print(-1)
15        continue
16
17    ctn = False
18    count = 0
19    for j in range(1, len(t) - 1):
20        if s[j] != t[j]:
21            if s[j - 1] == s[j + 1] and s[j - 1] != s[j]:
22                count += 1
23                s[j] = swap[s[j]]
24            else:
25                print(-1)
26                ctn = True
27                break
28    if ctn:
29        continue
30    print(count)

3521 子矩阵 | 原题链接

这道题用最暴力的方法也能过 7/10 个点……

 1n, m, a, b = map(int, input().strip().split())
 2mat = list()
 3for _ in range(n):
 4    mat.append(list(map(int, input().strip().split())))
 5
 6MOD = 998244353
 7s = 0
 8for i in range(n):
 9    if i + a > n:
10        continue
11    for j in range(m):
12        if j + b > m:
13            continue
14        max_val = 0
15        min_val = float("inf")
16        for p in range(a):
17            for q in range(b):
18                curr = mat[i + p][j + q]
19                max_val = max(max_val, curr)
20                min_val = min(min_val, curr)
21        s += max_val * min_val
22        s %= MOD
23print(s)

我对其略微优化了一下，只在 y 方向使用滑动窗口，每走过一遍就会将所有的队列清空，可以通过 8/10 个点。

 1from collections import deque
 2
 3MOD = 998244353
 4n, m, a, b = map(int, input().strip().split())
 5mat = list()
 6for i in range(n):
 7    mat.append(list(map(int, input().strip().split())))
 8
 9ans = 0
10
11for i in range(a, n + 1):
12    minq = deque()
13    maxq = deque()
14    for j in range(m):
15
16        while minq and minq[0][1] <= j - b:
17            minq.popleft()
18        while maxq and maxq[0][1] <= j - b:
19            maxq.popleft()
20
21        for k in range(i - a, i):
22            curr = mat[k][j]
23            while minq and mat[minq[-1][0]][minq[-1][1]] > curr:
24                minq.pop()
25            minq.append((k, j))
26            while maxq and mat[maxq[-1][0]][maxq[-1][1]] < curr:
27                maxq.pop()
28            maxq.append((k, j))
29
30        if j >= b - 1:
31            ans += mat[minq[0][0]][minq[0][1]] * mat[maxq[0][0]][maxq[0][1]]
32            ans %= MOD
33
34print(ans)

这道题可以先原矩阵中对 x 方向做滑动窗口记录每一段的最值，随后在记录 x 方向最值的矩阵中对 y 方向做滑动窗口记录最值。

 1from collections import deque
 2
 3MOD = 998244353
 4
 5n, m, a, b = map(int, input().split())
 6mat = []
 7for _ in range(n):
 8    row = list(map(int, input().split()))
 9    mat.append(row)
10
11row_min = [[0] * (m - b + 1) for _ in range(n)]
12row_max = [[0] * (m - b + 1) for _ in range(n)]
13
14for i in range(n):
15    q_min = deque()
16    q_max = deque()
17    for j in range(m):
18
19        while q_min and q_min[0] <= j - b:
20            q_min.popleft()
21        while q_max and q_max[0] <= j - b:
22            q_max.popleft()
23
24        while q_min and mat[i][q_min[-1]] >= mat[i][j]:
25            q_min.pop()
26        q_min.append(j)
27
28        while q_max and mat[i][q_max[-1]] <= mat[i][j]:
29            q_max.pop()
30        q_max.append(j)
31
32        if j >= b - 1:
33            row_min[i][j - b + 1] = mat[i][q_min[0]]
34            row_max[i][j - b + 1] = mat[i][q_max[0]]
35
36min_vals = [[0] * (m - b + 1) for _ in range(n - a + 1)]
37max_vals = [[0] * (m - b + 1) for _ in range(n - a + 1)]
38
39for j in range(m - b + 1):
40    q_min = deque()
41    q_max = deque()
42    for i in range(n):
43
44        while q_min and q_min[0] <= i - a:
45            q_min.popleft()
46        while q_max and q_max[0] <= i - a:
47            q_max.popleft()
48
49        while q_min and row_min[q_min[-1]][j] >= row_min[i][j]:
50            q_min.pop()
51        q_min.append(i)
52
53        while q_max and row_max[q_max[-1]][j] <= row_max[i][j]:
54            q_max.pop()
55        q_max.append(i)
56
57        if i >= a - 1:
58            min_vals[i - a + 1][j] = row_min[q_min[0]][j]
59            max_vals[i - a + 1][j] = row_max[q_max[0]][j]
60
61ans = 0
62for i in range(n - a + 1):
63    for j in range(m - b + 1):
64        ans = (ans + min_vals[i][j] * max_vals[i][j]) % MOD
65
66print(ans)

3527 阶乘的和 | 原题链接

这道题乍一看没有什么头绪，只知道数列中最小值的阶乘一定是阶乘的和的因数之一，但不能确保这是最大的 m。观察发现，阶乘是可以“合成的”，例如 $3\times2!=3!,5\times4!=5!$，因此最大 m 就是在所有可合成的数都“合成”结束后最小的数。选用字典来存储每个数字出现的次数，如果某个数字出现的次数足够“合成”，就向比他大一的数字“进位”，要求的就是字典中最小值不为 $0$ 的键。

 1from collections import defaultdict
 2
 3n = int(input().strip())
 4nums = list(map(int, input().strip().split()))
 5nums.sort()
 6
 7count = defaultdict(int)
 8for i in range(n):
 9    num = nums[i]
10    count[num] += 1
11    while count[num] >= num + 1:
12        count[num] -= num + 1
13        count[num + 1] += 1
14        num += 1
15print(min(k for k in count.keys() if count[k] > 0))

3528 奇怪的数 | 原题链接

用爆搜可以过 3/20 个测试点。

 1n, m = map(int, input().strip().split())
 2count = 0
 3
 4
 5def dfs(depth, curr):
 6    global count
 7    if depth == n:
 8        if depth % 2 == 0:
 9            for next_val in [2, 4, 6, 8]:
10                if len(curr) >= 4 and sum(curr[-4:]) + next_val <= m:
11                    count += 1
12            return
13        else:
14            for next_val in [1, 3, 5, 7, 9]:
15                if len(curr) >= 4 and sum(curr[-4:]) + next_val <= m:
16                    count += 1
17            return
18
19    if depth % 2 == 0:
20        for next_val in [0, 2, 4, 6, 8]:
21            if (
22                len(curr) >= 4
23                and sum(curr[-4:]) + next_val <= m
24                or sum(curr) + next_val <= m
25            ):
26                dfs(depth + 1, curr + [next_val])
27
28    else:
29        for next_val in [1, 3, 5, 7, 9]:
30            if (
31                len(curr) >= 4
32                and sum(curr[-4:]) + next_val <= m
33                or sum(curr) + next_val <= m
34            ):
35                dfs(depth + 1, curr + [next_val])
36
37
38dfs(1, list())
39print(count)

这道题我也只会骗分，AC 做法是用动态规划，而且用了一个四维数组，但是我看不懂 QAQ……

3526 子树的大小 | 原题链接

误打误撞暴力做出来了。大体方法就是分别求出这个完全 $m$ 叉树的深度、该完全 $m$ 叉树添加多少节点能将最后一层填满，然后计算第 $n$ 个节点的深度、这个节点有多少兄弟节点这个节点是这一层的第几个、以这个节点为根的子树深度，随后就能计算出子树的最后一层理论上有多少节点、实际上有多少节点，最后就能求出子树总共的节点数量。

 1t = int(input().strip())
 2for _ in range(t):
 3    n, m, k = map(int, input().strip().split())
 4    depth = 0
 5    node_count = 0
 6    while node_count < n:
 7        node_count += m ** depth
 8        depth += 1
 9    last_d = m ** (depth - 1)
10    remain = node_count - n
11
12    k_depth = 0
13    k_count = 0
14    while k_count < k:
15        k_count += m ** k_depth
16        k_depth += 1
17    sib_count = m ** (k_depth - 1)
18    sib_no = sib_count - (k_count - k)
19    ans = 0
20    for d in range(depth - k_depth):
21        ans += m ** d
22    if last_d // sib_count * sib_no <= last_d - remain:
23        ans += m ** (depth - k_depth)
24        print(ans)
25    elif last_d // sib_count * (sib_no - 1) >= last_d - remain:
26        print(ans)
27    else:
28        ans += last_d - remain - (sib_no - 1) * (m ** (depth - k_depth))
29        print(ans)

5003 反异或01串 | 原题链接

爆搜写法：

 1from collections import defaultdict, deque
 2
 3dest = input().strip()
 4memo = defaultdict(lambda: -1)
 5q = deque()
 6q.append(("", False))
 7memo[""] = 0
 8min1 = float("inf")
 9while q:
10    curr, xored = q.popleft()
11    if (len(curr) > 0 and int(curr, 2) == int(dest, 2)) or curr == dest:
12        min1 = min(min1, memo[curr])
13
14    if len(curr) < len(dest):
15        for nxt in [curr + "0", "0" + curr]:
16            if memo[nxt] == -1:
17                q.append((nxt, xored))
18                memo[nxt] = memo[curr]
19        for nxt in [curr + "1", "1" + curr]:
20            if memo[nxt] == -1 or memo[curr] + 1 < memo[nxt]:
21                q.append((nxt, xored))
22                memo[nxt] = memo[curr] + 1
23    if len(curr) > 0:
24        rev = curr[::-1]
25        s_bins = bin(int(rev, 2) ^ int(curr, 2))
26        s_ = s_bins[2:]
27        if memo[s_] == -1 or memo[curr] + 1 < memo[s_] and not xored:
28            q.append((s_, True))
29            memo[s_] = memo[curr]
30
31print(min1)

可以通过 2/20 个测试点。由于只有添加 1 的操作才会记录步数，所以虽然用广搜，但是如果某次异或后 1 的数量反而少了，仍然需要将其添加到队列中。这段代码仍然是错误的，因为在异或后忽略了前导 0，不过我也懒得改一段不可能 AC 的代码。

经过思考不难发现，经过一次翻转异或后，得到的结果会是一个回文串，而根据异或运算的性质，如果想在翻转异或后让新增的 1 尽可能多，则原串中 1 的对称位置一定为 0，此时翻转异或可以让 1 的数量翻倍，并且得到一个回文子串，因此找出目标字符串中含 1 最多的回文子串，最理想情况下该回文子串中有一半 1 是通过翻转异或得到的，而回文子串外的 1 都是直接添加得到的。统计回文子串可以遍历每一个回文中心，也可以使用 Manacher 算法求最长回文子串。

Manacher 算法求最长回文子串：

 1s = "#" + "#".join(list(input().strip())) + "#"  # 预处理
 2l = len(s)
 3radius = [0] * l  # 分别记录以每一个点为回文中心时的回文半径
 4R, C = -1, -1  # 分别记录回文右边界和回文中心
 5max_len = 0
 6max_str = ""
 7
 8for i in range(l):
 9    radius[i] = min(radius[2 * C - i], R - i) if R > i else 1  # 判断当前位置是否超过回文右边界
10    while i + radius[i] < l and i - radius[i] >= 0:
11        if s[i + radius[i]] == s[i - radius[i]]:
12            radius[i] += 1
13        else:
14            break
15
16    if i + radius[i] > R:
17        R = i + radius[i]
18        C = i
19
20    if radius[i] > max_len:
21        max_len = radius[i]
22        max_str = s[i - radius[i] + 1 : i + radius[i]]
23
24print(max_len, "".join(max_str.split("#")))

AC Code：

 1def manacher(s):
 2    s = "#" + "#".join(s) + "#"
 3    l = len(s)
 4    radius = [0] * l
 5    R, C = -1, -1
 6    _1_count = 0
 7
 8    for i in range(l):
 9        radius[i] = min(radius[2 * C - i], R - i) if R > i else 1
10        while i + radius[i] < l and i - radius[i] >= 0:
11            if s[i + radius[i]] == s[i - radius[i]]:
12                radius[i] += 1
13            else:
14                break
15
16        if i + radius[i] > R:
17            R = i + radius[i]
18            C = i
19
20        if (
21            s[i] != "1"
22            and radius[i]
23            and s[i - radius[i] + 1 : i + radius[i]].count("1") > _1_count
24        ):
25            _1_count = s[i - radius[i] + 1 : i + radius[i]].count("1")
26
27    return _1_count // 2
28
29
30s = input().strip()
31total = s.count("1")
32_1_count = manacher(s)
33print(total - _1_count)