【藍橋杯集訓·每日一題2025】 AcWing 6135. 奶牛體檢 python

6135. 奶牛體檢

Week 1
2月21日

農夫約翰的 $N$ 頭奶牛站成一行，奶牛 $1$ 在隊伍的最前面，奶牛 $N$ 在隊伍的最后面。

農夫約翰的奶牛也有許多不同的品種。

他用從 $1$ 到 $N$ 的整數來表示每一品種。

隊伍從前到后第 $i$ 頭奶牛的品種是 $a_i$ 。

農夫約翰正在帶他的奶牛們去當地的奶牛醫院進行體檢。

然而，奶牛獸醫非常挑剔，僅愿意當隊伍中第 $i$ 頭奶牛為品種 $b_i$ 時對其進行體檢。

農夫約翰很懶惰，不想完全重新排列他的奶牛。

他將執行以下操作恰好一次。

選擇兩個整數 $l$ 和 $r$ ，使得 $1 \leq l \leq r \leq N$ 。反轉隊伍中第 $l$ 頭奶牛到第 $r$ 頭奶牛之間的奶牛的順序。

農夫約翰想要衡量這種方法有多少效果。

對于每一個 $c = 0 \dots N$ ，請幫助農夫約翰求出使得恰好 $c$ 頭奶牛被檢查的不同操作 $(l, r)$ 的數量。

兩種操作 $l_1,r_1)$ 和 $l_2,r_2)$ 不同，如果 $l_1 \neq l_2$ 或者 $r_1 \neq r_2$ 。

輸入格式

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

第二行包含 $a_1,a_2,…,a_N$ 。

第三行包含 $b_1,b_2,…,b_N$ 。

輸出格式

輸出 $N + 1$ 行，第 $i$ 行包含使得 $i ? 1$ 頭奶牛被檢查的不同操作 $(l, r)$ 的數量。

數據范圍

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

輸入樣例1：

3
1 3 2
3 2 1

輸出樣例1：

樣例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：

樣例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：

樣例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 += 1for i in range(n):for j in range(2):sum = cntfor l in range(i, -1, -1):r = i + j + abs(l - i)if r >= n:breakif a[l] == b[r]:sum += 1if a[r] == b[l]:sum += 1if a[l] == b[l]:sum -= 1if a[r] == b[r]:sum -= 1ans[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 = cntfor l in range(i, -1, -1):r = i + j + abs(l - i)if r >= n:break# 更新匹配數if a[l] == b[r]:sum += 1if a[r] == b[l]:sum += 1if a[l] == b[l]:sum -= 1if a[r] == b[r]:sum -= 1ans[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。

正確性分析

初始匹配數計算：
- 正確計算了初始狀態下匹配的奶牛數量。
枚舉區間中點并向兩邊擴展：
- 通過枚舉中點 i 和區分奇數/偶數長度區間，確保所有可能的區間 [l, r] 都被覆蓋。
- 反轉區間 [l, r] 后，匹配數的更新邏輯正確：
  - 反轉后，a[l] 和 b[r] 匹配，a[r] 和 b[l] 匹配。
  - 反轉前，a[l] 和 b[l] 匹配，a[r] 和 b[r] 匹配，反轉后這些匹配會消失。
時間復雜度：
- 外層循環 for i in range(n) 和 for j in range(2) 總共迭代 2n 次。
- 內層循環 for l in range(i, -1, -1) 最多迭代 n 次。
- 因此，總時間復雜度為 O(N2)。

示例分析

輸入樣例 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

思路

問題分析：
- 農夫約翰的奶牛隊伍有 N 頭奶牛，每頭奶牛有一個品種。
- 獸醫只愿意檢查隊伍中第 i 頭奶牛為品種 b[i] 的情況。
- 農夫約翰可以選擇一個區間 [l, r] 反轉奶牛的順序，恰好執行一次。
- 需要計算對于每個 c = 0...N，有多少種操作 (l, r) 使得恰好 c 頭奶牛被檢查。
關鍵觀察：
- 反轉區間 [l, r] 后，區間內的奶牛順序會反轉，而區間外的奶牛順序不變。
- 反轉后，區間內的匹配數會發生變化，而區間外的匹配數不變。
動態規劃設計：
- 定義 dp[l][r] 表示反轉區間 [l, r] 后的匹配數。
- 初始化：
  - 單個區間 [i, i] 的反轉匹配數為 cnt（初始匹配數）。
  - 區間長度為 2 的情況需要單獨處理。
- 轉移：
  - 對于區間 [l, r]，反轉后的匹配數等于 dp[l + 1][r - 1] + cost，其中 cost 是反轉區間 [l, r] 帶來的匹配數變化。
統計結果：
- 遍歷所有區間 [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+1cost = 0if a[l] == b[r]:cost += 1if a[r] == b[l]:cost += 1if a[l] == b[l]:cost -= 1if a[r] == b[r]:cost -= 1dp[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 - 1cost = 0if a[l] == b[r]:cost += 1if a[r] == b[l]:cost += 1if a[l] == b[l]:cost -= 1if a[r] == b[r]:cost -= 1dp[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
如果有更多問題或需要進一步的幫助，可以在評論區留言討論哦！
如果喜歡的話，請給博主點個關注謝謝