POJ2369 Permutations【置换群】
2024-08-27 22:48:52
题目链接:
http://poj.org/problem?id=2369
题目大意:
给定一个序列。问最少须要多少次置换才干变为 1、2、…、N 的有序序列。比方说给
定5个数的序列 4 1 5 2 3。表示置换为:
( 1 2 3 4 5 ) ,即 (1 4 2)(3 5)
4 1 5 2 3
解题思路:
对于每一位找到自己轮换内轮换到自己的次数。求不相交的轮换之间的次数的公倍数,
即为终于结果。
AC代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std; int GCD(int a,int b)
{
if(b == 0)
return a;
return GCD(b,a%b);
} int LCM(int a,int b)
{
return a / GCD(a,b) * b;
} int A[1100],vis[1100];//vis[]标记轮换 int main()
{
int N;
while(~scanf("%d",&N))
{
memset(vis,0,sizeof(vis));
for(int i = 1; i <= N; ++i)
scanf("%d",&A[i]);
int Ans = 1;
for(int i = 1; i <= N; ++i)
{
int tmp = A[i];
int Num = 1;
vis[i] = 1;
while(tmp != i && !vis[tmp])
{
vis[tmp] = 1;
tmp = A[tmp];
Num++;
}
Ans = LCM(Ans,Num);
}
printf("%d\n",Ans);
} return 0;
}
最新文章
- 转:JQuery实现下拉框的数据加载和联动
- ruby -- 进阶学习(十四)设置background-image(解决无法获取图片路径问题)
- QUnit使用笔记-2同步与异步处理方式
- 2016年7月2日 星期六 --出埃及记 Exodus 14:29
- HTML 编辑器
- 让EntityFramework6支持SQLite
- NetBeans平台中调用状态栏
- c++11之右值引用
- https 方式使用git@osc设置密码的方式
- 【转】如何用WINDBG分析64位机上32位程序的DUMP文件
- 眼见为实(1):C++基本概念在编译器中的实现
- Topcoder SRM 656 (Div.1) 250 RandomPancakeStack - 概率+记忆化搜索
- HDU-2059龟兔赛跑(基础方程DP-遍历之前的所有状态)
- EF连接MySQL数据Web.Config配置
- STM32F4 串口实验中收不到超级终端发送的数据,调试工具却可以
- 56.两数之和.md
- 物联网架构成长之路(3)-EMQ消息服务器了解
- CSS3实现图片循环旋转
- 程序员必知的8大排序(四)-------归并排序,基数排序(java实现)
- at 命令
热门文章
- 垃圾回收器(GC)
- vue-lazyload插件
- UT源码+105032014018
- Fiddler 接口测试(Composer)的使用方法
- [Java] 使用 Apache的 Commons-net库 实现FTP操作
- 【codeforces 496E】Distributing Parts
- poj3134 Power Calculus IDA*
- Linux防火墙iptables安装配置--使用远程工具Xmanager和ftp服务安装配置
- 洛谷 P2128 赤壁之战
- Android Camera子系统之Linux C应用开发人员View