CF(441D Valera and Swaps)置换群-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

CF(441D Valera and Swaps)置换群

简介:

题意:1-n的一个排列 p1, p2, ..., pn,f(p)的定义是此排列要交换最少的数对能够回到原排列1,2,3,4...n。给一个排列p。要将其变换成f值为m的排列,问至少要交换几个数对,并输出字典序最小的那组答案。


解法:处理出全部的置换群,求出环数k,此时f值为n-k。然后推断n-k和m的大小,分为两种操作

           1、加环,这个是在随意元素个数大于1的环内交换随意两个数都能够做到加环

           2、减环,交换随意两个环的随意两个元素。就能够做到将两个环连接起来

           题目要求是输出字典序最小,那么就暴力搞。

代码:


}







本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5239833.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: