2020-2021:teams:namespace:week_summary_11 [CVBB ACM Team]

Warning: session_start(): open(/tmp/sess_cc3e2bf5836faeef88984d9ec62ab28a, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: mkdir(): No space left on device in /data/wiki/lib/plugins/dw2pdf/vendor/mpdf/mpdf/src/Cache.php on line 19

Temporary files directory "/data/wiki/data/tmp/dwpdf/410/" is not writable

Writing /data/wiki/data/cache/8/878e000dca5c08fe55e62fff31fad8b7.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:namespace:week_summary_11 [CVBB ACM Team]

2020-2021:teams:namespace:week_summary_11

这是本文档旧的修订版！

团队训练

牛客多校第三场

牛客多校第四场

李淳一

比赛

团体比赛。

学习总结

本周在学习压力不比学期差的同时，打了三场比赛。心情实在一般。

本周推荐

题目名称及来源

牛客第三场比赛的E题，是算法的优秀例题。

标签

图论、动态规划。

题意

两个置换（长度为偶数n）由不交的对换填满，并且这两个置换也不相交。对于一个给定向量，一个置换在上面的权重是对换距离差之和。

求距离差之和的最小值。

题解

首先看成图论问题。对换看成边，则被填满的置换就可以看成饱和对集。

两个饱和对集不相交，叠加在一起必然构成若干个圈。因此直接考虑回路上的和。

圈长为偶数，至少是4。求和最大值最终会变为不相邻取数的最小值问题，是典型的动态规划问题，直接求解即可。

评论

本题设计巧妙，结论深刻而优秀，是难得一见的好题。

胡湘鹏

比赛

学习总结

本周推荐

题目名称及来源

tag

题意

题解

comment

马逸行

比赛

学习总结

本周推荐

题目名称及来源

tag

题意

题解

comment

页面链接

本页面的时间范围是2020.07.18-2020.07.24的周报

前一篇：week_summary_10

后一篇：week_summary_12

2020-2021/teams/namespace/week_summary_11.1595489501.txt.gz · 最后更改: 2020/07/23 15:31 由 great_designer