国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > 综合技术 > Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan dfs+最小公倍数

Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan dfs+最小公倍数

来源:程序员人生   发布时间:2017-04-08 13:58:06 阅读次数:3872次

C. Arpa's loud Owf and Mehrdad's evil plan
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As you have noticed, there are lovely girls in Arpa’s land.

People in Arpa's land are numbered from 1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crushi.

Someday Arpa shouted Owf loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.

The game consists of rounds. Assume person x wants to start a round, he calls crushx and says: "Oww...wwf" (the letter w is repeatedt times) and cuts off the phone immediately. If t > 1 then crushx calls crushcrushx and says: "Oww...wwf" (the letter w is repeated t - 1times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (t = 1). This person is called theJoon-Joon of the round. There can't be two rounds at the same time.

Mehrdad has an evil plan to make the game more funny, he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from yx would become the Joon-Joon of the round. Find such t for Mehrdad if it's possible.

Some strange fact in Arpa's land is that someone can be himself's crush (i.e. crushi = i).

Input

The first line of input contains integer n (1 ≤ n ≤ 100) — the number of people in Arpa's land.

The second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush.

Output

If there is no t satisfying the condition, print . Otherwise print such smallest t.

Examples
input
4
2 3 1 4
output
3
input
4
4 4 4 4
output
input
4
2 1 4 3
output
1
Note

In the first sample suppose t = 3.

If the first person starts some round:

The first person calls the second person and says "Owwwf", then the second person calls the third person and says "Owwf", then the third person calls the first person and says "Owf", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is1.

The process is similar for the second and the third person.

If the fourth person starts some round:

The fourth person calls himself and says "Owwwf", then he calls himself again and says "Owwf", then he calls himself for another time and says "Owf", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when x is 4.

In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.



Source

Codeforces Round #383 (Div. 2)


My Solution

题意:当1个人开始是另外一个人结束,但这个人开始时前面那个人结束,具体还是请看题吧,哈哈


dfs+最小公倍数

每一个人只能且必须处于1个环中,自环也是环,如果环的元素个数是奇数则这个环必须是ansi =  k*cnt,如果是偶数则 ans = k * (cnt / 2);//这个是自己画图发现的规律。

这题不用多想甚么优化的方法,弄复杂了反而容易错(比如笔者自己 T _ T ),n <= 100,直接对每个点每层dfs时cnt++,

直到找到 目标 find(u, v),,或找到根节点时,或 cnt > 100 时return。//这个100是自己设定的,即最多100个节点cnt大于100说明ans = ⑴。

比如

5
2 4 3 1 2

这组数据。

找出每一个环的ansi,然后对这些ansi取最大公约数便可,a、b最大公约数等于 a * b / (gcd(a, b)),且注意中间进程溢出,由于这里有 a * b了

复杂度 O(n^2)


#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const int maxn = 1e2 + 8;

int cnt;
bool flag[maxn];
queue<int> que;

int father[maxn], _rank[maxn];
inline void DisjointSet(int n)
{
    for(int i = 0; i <= n; i++){
        father[i] = i;
    }
}

inline bool _find(int v, int u)
{
    if(father[v] == u){
        //cout << cnt << endl;
        if(cnt % 2 == 1){
            que.push(cnt);
        }
        else{
            que.push(cnt / 2);
        }
        return true;
    }
    else if(father[v] == v){
        return false;
    }
    else{
        cnt++;
        if(cnt == 1024) return false;
        if(!_find(father[v], u)){
            return false;
        }
        else return true;
    }
}

inline LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    DisjointSet(n);
    for(int i = 1; i <= n; i++){
        cin >> father[i];
    }

    LL ans = 1;
    for(int i = 1; i <= n; i++){
        cnt = 1;
        if(!_find(i, i)){
            ans = 1024;
            break;
        }
    }
    if(ans != 1024){
        ans = que.front();
        que.pop();
        while(!que.empty()){
            ans = (ans * que.front()) / gcd(ans, que.front());
            //!WA 61 这里溢出了,换成LL 以后过了, 毕竟求的是最小公倍数
            que.pop();
        }
        cout << ans << endl;
    }
    else cout << ⑴ << endl;



    #ifdef LOCAL
    memset(flag, false, sizeof flag);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}



  Thank you!

                                                                                                                                               ------from ProLights

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生