题意:已知URAL 1024 Permutations(LCM)-LMLPHP,可得出 P(1) = 4, P(2) = 1, P(3) = 5,由此可得出 P(P(1)) = P(4) = 2. And P(P(3)) = P(5) = 3,因此URAL 1024 Permutations(LCM)-LMLPHP。经过k次如上变换,最终可得URAL 1024 Permutations(LCM)-LMLPHP,输入保证一定有解,求k。

分析:

1、能用数组表示映射就别用map,很耗时

2、序列中的每个数字经过这种变换都一定会变会自身,例如,一开始P(1) = 4,接下来P(P(1)) = P(4) = 2,再接下来P(P(P(1))) = P(P(4)) = P(2) = 1,只需三次,就可以变回自身(P(P(P(1))) =1),对序列中每个数字求次数,最终求这些次数的最小公倍数即可

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) a < b ? a : b
#define Max(a, b) a < b ? b : a
typedef long long ll;
typedef unsigned long long llu;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {, , -, };
const int dc[] = {-, , , };
const double pi = acos(-1.0);
const double eps = 1e-;
const int MAXN = + ;
const int MAXT = + ;
using namespace std;
int x[MAXN];
int w[MAXN];
set<int> y;
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
int N;
int main()
{
scanf("%d", &N);
for(int i = ; i <= N; ++i)
{
scanf("%d", &x[i]);
w[i] = x[i];
}
for(int i = ; i <= N; ++i)
{
int cnt = ;
while(x[i] != i){
x[i] = w[x[i]];
++cnt;
}
y.insert(cnt);
}
set<int>::iterator it = y.begin();
int ans = *it;
++it;
for(; it != y.end(); ++it){
ans = ans / gcd(ans, *it) * (*it);//求最小公倍数,调用函数耗时
}
printf("%d\n", ans);
return ;
}
05-11 11:05