【蓝桥杯集训·每日一题2025】 AcWing 6135. 奶牛体检 python

6135. 奶牛体检

Week 1
2月21日

农夫约翰的 $N$ 头奶牛站成一行，奶牛 $1$ 在队伍的最前面，奶牛 $N$ 在队伍的最后面。

农夫约翰的奶牛也有许多不同的品种。

他用从 $1$ 到 $N$ 的整数来表示每一品种。

队伍从前到后第 $i$ 头奶牛的品种是 $a_i$。

农夫约翰正在带他的奶牛们去当地的奶牛医院进行体检。

然而，奶牛兽医非常挑剔，仅愿意当队伍中第 $i$ 头奶牛为品种 $b_i$ 时对其进行体检。

农夫约翰很懒惰，不想完全重新排列他的奶牛。

他将执行以下操作恰好一次。

• 选择两个整数 $l$ 和 $r$，使得 $1\le l\le r\le N$。反转队伍中第 $l$ 头奶牛到第 $r$ 头奶牛之间的奶牛的顺序。

农夫约翰想要衡量这种方法有多少效果。

对于每一个 $c=0\dots N$，请帮助农夫约翰求出使得恰好 $c$ 头奶牛被检查的不同操作 $(l,r)$ 的数量。

两种操作 $(l_1,r_1)$ 和 $(l_2,r_2)$ 不同，如果 $l_1\ne l_2$ 或者 $r_1\ne r_2$。

输入格式

输入的第一行包含 $N$。

第二行包含 $a_1,a_2,\dots ,a_N$。

第三行包含 $b_1,b_2,\dots ,b_N$。

输出格式

输出 $N+1$ 行，第 $i$ 行包含使得 $i-1$ 头奶牛被检查的不同操作 $(l,r)$ 的数量。

数据范围

$1\le N\le 7500$,
$1\le a_i,b_i\le N$

输入样例1：

3
1 3 2
3 2 1

输出样例1：

3
3
0
0

样例1解释

如果农夫约翰选择 $(l=1,r=1)$，$(l=2,r=2)$ 或 $(l=3,r=3)$，则没有奶牛将会被检查。

注意这些操作并没有改变奶牛的位置。

以下操作会导致一头奶牛被检查。

• $(l=1,r=2)$：农夫约翰反转第一头和第二头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[3,1,2]$。第一头奶牛将会被检查。
• $(l=2,r=3)$：农夫约翰反转第二头和第三头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[1,2,3]$。第二头奶牛将会被检查。
• $(l=1,r=3)$：农夫约翰反转第一头，第二头和第三头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[2,3,1]$。第三头奶牛将会被检查。

输入样例2：

3
1 2 3
1 2 3

输出样例2：

0
3
0
3

样例2解释

三种导致 $3$ 头奶牛被检查的可能操作为 $(l=1,r=1)$，$(l=2,r=2)$ 和 $(l=3,r=3)$。

输入样例3：

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

输出样例3：

0
6
14
6
2
0
0
0

样例3解释

两种导致 $4$ 头奶牛被检查的可能操作为 $(l=4,r=5)$ 和 $(l=5,r=7)$。

方法1：
枚举区间中点，向两边扩展

实现code

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = [0] * (n + 1)

cnt = 0
for i in range(n):
    if a[i] == b[i]:
        cnt += 1

for i in range(n):
    for j in range(2):
        sum = cnt
        for l in range(i, -1, -1):
            r = i + j + abs(l - i)
            if r >= n:
                break
            if a[l] == b[r]:
                sum += 1
            if a[r] == b[l]:
                sum += 1
            if a[l] == b[l]:
                sum -= 1
            if a[r] == b[r]:
                sum -= 1
            ans[sum] += 1
print('\n'.join(map(str, ans)))

代码解释

1. 初始匹配数计算

cnt = 0
for i in range(n):
    if a[i] == b[i]:
        cnt += 1

• 这里计算初始状态下有多少奶牛的位置和品种匹配，即 a[i] == b[i]。
• cnt 表示初始匹配数。

2. 枚举区间中点并向两边扩展

for i in range(n):
    for j in range(2): # 奇数长度区间和偶数长度区间
        sum = cnt
        for l in range(i, -1, -1):
            r = i + j + abs(l - i)
            if r >= n:
                break
            # 更新匹配数
            if a[l] == b[r]:
                sum += 1
            if a[r] == b[l]:
                sum += 1
            if a[l] == b[l]:
                sum -= 1
            if a[r] == b[r]:
                sum -= 1
            ans[sum] += 1

• 外层循环 for i in range(n)：

  • 枚举区间的中点 i。
  • 中点可以是某个位置（奇数长度区间）或两个位置之间（偶数长度区间）。

• 内层循环 for j in range(2)：

  • j 用于区分奇数长度区间和偶数长度区间。
  • 当 j = 0 时，区间长度为奇数，中点为 i。
  • 当 j = 1 时，区间长度为偶数，中点为 i 和 i+1。

• 内层循环 for l in range(i, -1, -1)：

  • 从中点 i 向左扩展，枚举左端点 l。
  • 根据 j 的值计算右端点 r：
    • r = i + j + abs(l - i)。
    • 如果 r >= n，说明右端点超出范围，直接跳出循环。

• 更新匹配数：

  • 反转区间 [l, r] 后，更新匹配数 sum：
    • 如果 a[l] == b[r]，反转后匹配数增加 1。
    • 如果 a[r] == b[l]，反转后匹配数增加 1。
    • 如果 a[l] == b[l]，反转前匹配，反转后不匹配，匹配数减少 1。
    • 如果 a[r] == b[r]，反转前匹配，反转后不匹配，匹配数减少 1。

• 更新答案：

  • 根据当前的匹配数 sum，更新答案数组 ans[sum] += 1。

正确性分析

1. 初始匹配数计算：

   • 正确计算了初始状态下匹配的奶牛数量。

2. 枚举区间中点并向两边扩展：

   • 通过枚举中点 i 和区分奇数/偶数长度区间，确保所有可能的区间 [l, r] 都被覆盖。
   • 反转区间 [l, r] 后，匹配数的更新逻辑正确：
     • 反转后，a[l] 和 b[r] 匹配，a[r] 和 b[l] 匹配。
     • 反转前，a[l] 和 b[l] 匹配，a[r] 和 b[r] 匹配，反转后这些匹配会消失。

3. 时间复杂度：

   • 外层循环 for i in range(n) 和 for j in range(2) 总共迭代 2n 次。
   • 内层循环 for l in range(i, -1, -1) 最多迭代 n 次。
   • 因此，总时间复杂度为 O(N²)。

示例分析

输入样例 1：

3
1 3 2
3 2 1

• 初始匹配数 cnt = 0。
• 枚举所有区间 [l, r]：
  • (l=1, r=1)：反转后匹配数为 0。
  • (l=2, r=2)：反转后匹配数为 0。
  • (l=3, r=3)：反转后匹配数为 0。
  • (l=1, r=2)：反转后匹配数为 1。
  • (l=2, r=3)：反转后匹配数为 1。
  • (l=1, r=3)：反转后匹配数为 1。
• 输出：

  3
  3
  0
  0
  

方法2：
递推：区间DP

思路

1. 问题分析：

   • 农夫约翰的奶牛队伍有 N 头奶牛，每头奶牛有一个品种。
   • 兽医只愿意检查队伍中第 i 头奶牛为品种 b[i] 的情况。
   • 农夫约翰可以选择一个区间 [l, r] 反转奶牛的顺序，恰好执行一次。
   • 需要计算对于每个 c = 0...N，有多少种操作 (l, r) 使得恰好 c 头奶牛被检查。

2. 关键观察：

   • 反转区间 [l, r] 后，区间内的奶牛顺序会反转，而区间外的奶牛顺序不变。
   • 反转后，区间内的匹配数会发生变化，而区间外的匹配数不变。

3. 动态规划设计：

   • 定义 dp[l][r] 表示反转区间 [l, r] 后的匹配数。
   • 初始化：
     • 单个区间 [i, i] 的反转匹配数为 cnt（初始匹配数）。
     • 区间长度为 2 的情况需要单独处理。
   • 转移：
     • 对于区间 [l, r]，反转后的匹配数等于 dp[l + 1][r - 1] + cost，其中 cost 是反转区间 [l, r] 带来的匹配数变化。

4. 统计结果：

   • 遍历所有区间 [l, r]，统计每种匹配数对应的操作数量。

代码解释

1. 初始匹配数计算

cnt = 0
for i in range(n):
    if a[i] == b[i]:
        cnt += 1

• 计算初始状态下有多少奶牛的位置和品种匹配，即 a[i] == b[i]。
• cnt 表示初始匹配数。

2. DP 数组初始化

for i in range(n):
    dp[i][i] = cnt

• 初始化单个区间 [i, i] 的反转匹配数。
• 对于单个区间，反转后匹配数不变，因此 dp[i][i] = cnt。

3. 初始化区间长度为 2

for i in range(n-1):
    l, r = i, i+1
    cost = 0
    if a[l] == b[r]:
        cost += 1
    if a[r] == b[l]:
        cost += 1
    if a[l] == b[l]:
        cost -= 1
    if a[r] == b[r]:
        cost -= 1
    dp[l][r] = cnt + cost

• 单独处理区间长度为 2 的情况，避免越界。
• 计算反转后的匹配数，并更新 dp[l][r]。

4. DP 转移

for len in range(3, n + 1):
    for l in range(n - len + 1):
        r = l + len - 1
        cost = 0
        if a[l] == b[r]:
            cost += 1
        if a[r] == b[l]:
            cost += 1
        if a[l] == b[l]:
            cost -= 1
        if a[r] == b[r]:
            cost -= 1
        dp[l][r] = dp[l + 1][r - 1] + cost

• 枚举区间长度 len，从 3 到 n。
• 对于每个区间 [l, r]，计算反转后的匹配数：
  • 如果 a[l] == b[r]，反转后匹配数增加 1。
  • 如果 a[r] == b[l]，反转后匹配数增加 1。
  • 如果 a[l] == b[l]，反转前匹配，反转后不匹配，匹配数减少 1。
  • 如果 a[r] == b[r]，反转前匹配，反转后不匹配，匹配数减少 1。
• 更新 dp[l][r] 的值。

5. 统计结果

for l in range(n):
    for r in range(l, n):
        ans[dp[l][r]] += 1

• 遍历所有区间 [l, r]，统计每种匹配数对应的操作数量。

6. 输出结果

print('\n'.join(map(str, ans)))

• 输出每种匹配数对应的操作数量。

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢