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

开发者社区> 技术mix呢> 正文

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,如需转载请自行联系原作者

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

相关文章
+关注
2884
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载