cf每日三题补题

2021-5-14

B. Nice Matrix

思维+贪心:

  • 构造一个每行每列都是回文结构的矩阵——找出使矩阵的f[i][j],f[n+1-i][m+1-j],f[n+1-i][j]+f[i][m+1-j]四点的值变为同一值的最小改变量
  • 如何找出最小改变量?——找四个数中的任意三个数的中位数

证明(数学归纳法)

假设四个数为 a=1,b=20,c=80,d=100

由此可知当b为中位数时:

sum=c-a+d-b(选abc)

sum=d-a+c-b(选abd)

当c为中位数时

sum=d-a+c-b(选acd)

sum=d-b+c-a(选bcd)

结果均为:-a-b+c+ds

由此可知结论正确

注意stl——vector的使用(可以直接将在数组中储存的数直接拿出来进行最小改变量的寻找) 

上一篇:C港口 (差分数组)(第十五届中北大学算法与程序设计竞赛)


下一篇:分享一款网页端CF活动助手 网页打开一键领取所有CF活动