526互联

Floyd 判环

发布时间 2023-11-03 21:44:33作者: 月光幻影

Floyd 判环

  • 设一个环环长为 $ n $，非环长为 $ m $，如何用 $ O_(1) $ 的空间，$ O_(n + m) $ 的时间找到环上的某种信息（如最值）

  • Floyd 判环类似于龟兔赛跑，有一个快指针 rabbit，一个慢指针 turtle，rabbit 的速度是 turtle 的倍数，如果存在环，就会发生套圈，rabbit 从后面追上了 turtle，此时 rabbit 已经遍历完了整个环

  • 用途：求周期性的最值（更节约空间）

        # include <bits/stdc++.h>
    # define int long long
    using namespace std;

    int t;
    int n, k, maxi, up;
    int turtle, rabbit;
    vector <int> st;

    void Turn(int &a){
        if(!a){
            return;
        }
        a = a * a;
        if(a >= up){
            st.clear();
            while(a){
                st.push_back(a % 10);
                a /= 10;
            }
            a = 0;
            for(int i = 1; i <= n; i++){
                a = a * 10 + st.back();
                st.pop_back();
            }
        }
    }

    signed main(){
    //	freopen("1.in", "r", stdin);
        cin >> t;
        while(t--){
            cin >> n >> k;
            turtle = k;
            rabbit = k;
            maxi = k;
            up = pow(10, n);
            do{
                Turn(turtle);
                maxi = max(maxi, turtle);
                
                Turn(rabbit);
                maxi = max(maxi, rabbit);
                Turn(rabbit);
                maxi = max(maxi, rabbit);			
            }while(turtle != rabbit);
            cout << maxi << "\n";
        }
    }