模拟赛整理 - 环

题解

题意

给出1-n的全排列 a[i], 给出 q 个询问 (x, m)

解

算法1

考虑倍增
预处理出每个点跳2^i步到达的点
对于每次询问logn查询
时间复杂度nlogn

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define f(x, y, z) for(int x = (y); x <= (z); ++x)
int a[1048576], F[31][1048576], *an = a;
bool vi[1048576];
int main(){
    freopen("kengdie.in", "r", stdin);
    freopen("kengdie.out", "w", stdout);
    while(scanf("%d", an) != EOF) ++an;
    *an = 0; *(an + 1) = 1000086;
    memset(vi, 0, sizeof(vi));
    int n = 0, *i = a;
    if((an - a) & 1){
        F[0][++n] = *i; vi[*i] = 1; ++i;
    }
    for(; i != an; i += 2){
        int *j = i + 1;
        if(*j > 1000000 || vi[*i]) break;
        F[0][++n] = *i; vi[*i] = 1;
        F[0][++n] = *j; vi[*j] = 1;
    }
    f(j, 1, 30) f(i, 1, n) F[j][i] = F[j - 1][F[j - 1][i]];
    for(; i != an; i += 2){
        int x = *i, T = *(i + 1);
        f(j, 0, 30) if(T & (1 << j)) x = F[j][x];
        printf("%d\n", x);
    }
    return 0;
}

算法2

我们考虑对于每次询问，只会在该点所在的环内查询，那么就可以将所有的环记录下来，就可以O(1)查询，记录环的时候，用vector存储每个环，记录环的时间复杂度为O(n)，整个算法的时间复杂度为O(n).

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
vector <int> vec[N];
int wei[N], bel[N], A[N];
bool vis[N];
int n, x, m;
int each[N]; 
int vecjs;
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
void Calc() {
    if(m == 0) {printf("%d\n", x); return ;}
    int a = A[x];
    m --;
    int which_vec = bel[a];
    int which_wei = wei[a];
    int Size = vec[which_vec].size();
    int ans = (m + which_wei) % Size;
    if(!ans) printf("%d\n", vec[which_vec][Size - 1]);
    else printf("%d\n", vec[which_vec][ans - 1]);
}
void Work_3() {
    Calc();
    while(scanf("%d%d", &x, &m) == 2) Calc();
    exit(0);
}
void Work_2() {
    for(int i = 1; i <= n; i ++) vis[i] = 0;
    vecjs = 0;
    for(int i = 1; i <= n; i ++) {
        if(vis[A[i]]) continue ;
        vecjs ++;
        vec[vecjs].push_back(A[i]);
        each[vecjs] ++;
        bel[A[i]] = vecjs;
        wei[A[i]] = each[vecjs];
        vis[A[i]] = 1;
        A[0] = A[i];
        for(int j = 0; (j = A[j]) && (!vis[A[j]]); ) {
            vec[vecjs].push_back(A[j]);
            each[vecjs] ++;
            bel[A[j]] = vecjs;
            wei[A[j]] = each[vecjs];
            vis[A[j]] = 1;
        }
    }
    Work_3();
}
int main() {
    freopen("kengdie.in", "r", stdin);
    freopen("kengdie.out", "w", stdout);
    int a = read(), b = read();
    n = 2;
    A[1] = a, A[2] = b;
    vis[a] = 1, vis[b] = 1;
    n = 2;
    for(; ;) {
        int a = read();
        if(vis[a]) x = a, m = read(), Work_2();
        else A[++ n] = a, vis[a] = 1;
    }
    return 0;
}