网站静态页面,网站好玩代码和特效,网站商城系统,国内可用的免费云端服务器6135. 奶牛体检
Week 1 2月21日 农夫约翰的 N N N 头奶牛站成一行#xff0c;奶牛 1 1 1 在队伍的最前面#xff0c;奶牛 N N N 在队伍的最后面。
农夫约翰的奶牛也有许多不同的品种。
他用从 1 1 1 到 N N N 的整数来表示每一品种。
队伍从前到后第 i i i 头奶牛的…
6135. 奶牛体检
Week 1 2月21日 农夫约翰的 N N N 头奶牛站成一行奶牛 1 1 1 在队伍的最前面奶牛 N N N 在队伍的最后面。
农夫约翰的奶牛也有许多不同的品种。
他用从 1 1 1 到 N N N 的整数来表示每一品种。
队伍从前到后第 i i i 头奶牛的品种是 a i a_i ai。
农夫约翰正在带他的奶牛们去当地的奶牛医院进行体检。
然而奶牛兽医非常挑剔仅愿意当队伍中第 i i i 头奶牛为品种 b i b_i bi 时对其进行体检。
农夫约翰很懒惰不想完全重新排列他的奶牛。
他将执行以下操作恰好一次。
选择两个整数 l l l 和 r r r使得 1 ≤ l ≤ r ≤ N 1≤l≤r≤N 1≤l≤r≤N。反转队伍中第 l l l 头奶牛到第 r r r 头奶牛之间的奶牛的顺序。
农夫约翰想要衡量这种方法有多少效果。
对于每一个 c 0 … N c0…N c0…N请帮助农夫约翰求出使得恰好 c c c 头奶牛被检查的不同操作 ( l , r ) (l,r) (l,r) 的数量。
两种操作 ( l 1 , r 1 ) (l_1,r_1) (l1,r1) 和 ( l 2 , r 2 ) (l_2,r_2) (l2,r2) 不同如果 l 1 ≠ l 2 l_1 \neq l_2 l1l2 或者 r 1 ≠ r 2 r_1 \neq r_2 r1r2。
输入格式
输入的第一行包含 N N N。
第二行包含 a 1 , a 2 , … , a N a_1,a_2,…,a_N a1,a2,…,aN。
第三行包含 b 1 , b 2 , … , b N b_1,b_2,…,b_N b1,b2,…,bN。
输出格式
输出 N 1 N1 N1 行第 i i i 行包含使得 i − 1 i−1 i−1 头奶牛被检查的不同操作 ( l , r ) (l,r) (l,r) 的数量。
数据范围 1 ≤ N ≤ 7500 1 \le N \le 7500 1≤N≤7500, 1 ≤ a i , b i ≤ N 1 \le a_i,b_i \le N 1≤ai,bi≤N
输入样例1
3
1 3 2
3 2 1输出样例1
3
3
0
0样例1解释
如果农夫约翰选择 ( l 1 , r 1 ) (l1,r1) (l1,r1) ( l 2 , r 2 ) (l2,r2) (l2,r2) 或 ( l 3 , r 3 ) (l3,r3) (l3,r3)则没有奶牛将会被检查。
注意这些操作并没有改变奶牛的位置。
以下操作会导致一头奶牛被检查。 ( l 1 , r 2 ) (l1,r2) (l1,r2)农夫约翰反转第一头和第二头奶牛的顺序因此新队伍中每头奶牛的品种将为 [ 3 , 1 , 2 ] [3,1,2] [3,1,2]。第一头奶牛将会被检查。 ( l 2 , r 3 ) (l2,r3) (l2,r3)农夫约翰反转第二头和第三头奶牛的顺序因此新队伍中每头奶牛的品种将为 [ 1 , 2 , 3 ] [1,2,3] [1,2,3]。第二头奶牛将会被检查。 ( l 1 , r 3 ) (l1,r3) (l1,r3)农夫约翰反转第一头第二头和第三头奶牛的顺序因此新队伍中每头奶牛的品种将为 [ 2 , 3 , 1 ] [2,3,1] [2,3,1]。第三头奶牛将会被检查。
输入样例2
3
1 2 3
1 2 3输出样例2
0
3
0
3样例2解释
三种导致 3 3 3 头奶牛被检查的可能操作为 ( l 1 , r 1 ) (l1,r1) (l1,r1) ( l 2 , r 2 ) (l2,r2) (l2,r2) 和 ( l 3 , r 3 ) (l3,r3) (l3,r3)。
输入样例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 4 4 头奶牛被检查的可能操作为 ( l 4 , r 5 ) (l4,r5) (l4,r5) 和 ( l 5 , r 7 ) (l5,r7) (l5,r7)。 方法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 和 i1。 内层循环 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(N²)。 示例分析
输入样例 1
3
1 3 2
3 2 1初始匹配数 cnt 0。枚举所有区间 [l, r] (l1, r1)反转后匹配数为 0。(l2, r2)反转后匹配数为 0。(l3, r3)反转后匹配数为 0。(l1, r2)反转后匹配数为 1。(l2, r3)反转后匹配数为 1。(l1, r3)反转后匹配数为 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, i1cost 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 如果有更多问题或需要进一步的帮助可以在评论区留言讨论哦 如果喜欢的话请给博主点个关注 谢谢
