2020-2021:teams:namespace:week_summary_11
这是本文档旧的修订版！
目录
团队训练
李淳一
比赛
团体比赛。
学习总结
本周在学习压力不比学期差的同时，打了三场比赛。心情实在一般。
本周推荐
题目名称及来源
牛客第三场比赛的E题，是算法的优秀例题。
标签
图论、动态规划。
题意
两个置换（长度为偶数n）由不交的对换填满，并且这两个置换也不相交。对于一个给定向量，一个置换在上面的权重是对换距离差之和。
求距离差之和的最小值。
题解
首先看成图论问题。对换看成边，则被填满的置换就可以看成饱和对集。
两个饱和对集不相交，叠加在一起必然构成若干个圈。因此直接考虑回路上的和。
圈长为偶数，至少是4。求和最大值最终会变为不相邻取数的最小值问题，是典型的动态规划问题，直接求解即可。
评论
本题设计巧妙，结论深刻而优秀，是难得一见的好题。
胡湘鹏
比赛
学习总结
本周推荐
题目名称及来源
tag
题意
题解
comment
马逸行
比赛
学习总结
本周推荐
题目名称及来源
tag
题意
题解
comment
页面链接
2020-2021/teams/namespace/week_summary_11.1595489501.txt.gz · 最后更改: 2020/07/23 15:31 由 great_designer
