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

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 y, x 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).

4
2 3 1 4

3

4
4 4 4 4

⑴

4
2 1 4 3

1

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

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠