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

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈