首页 > 代码库 > URAL 1024 Permutations（LCM）

URAL 1024 Permutations（LCM）

2024-08-19 02:43:57   221人阅读

题意：已知技术分享，可得出 P(1) = 4, P(2) = 1, P(3) = 5，由此可得出 P(P(1)) = P(4) = 2. And P(P(3)) = P(5) = 3，因此技术分享。经过k次如上变换，最终可得技术分享，输入保证一定有解，求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[] = {0, 0, -1, 1};
const int dc[] = {-1, 1, 0, 0};
const double pi = acos(-1.0);
const double eps = 1e-8;
const int MAXN = 1000 + 10;
const int MAXT = 10000 + 10;
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 = 1; i <= N; ++i)
    {
        scanf("%d", &x[i]);
        w[i] = x[i];
    }
    for(int i = 1; i <= N; ++i)
    {
        int cnt = 1;
        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 0;
}

 

URAL 1024 Permutations（LCM）


联系
我们