1 条题解

  • 1
    @ 2026-9-11 18:15:35
    using namespace std;
    int main() {
        int N, M, Q;
        scanf("%d %d %d", &N, &M, &Q);
        vector<int> p(M + 1);
        for (int i = 1; i <= M; i++) scanf("%d", &p[i]);
    
        // 路径:c[0]=M,c[j+1]=P[c[j]]-1,直到 0
        vector<int> c;
        c.push_back(M);
        while (c.back() != 0) c.push_back(p[c.back()] - 1);
        int L = (int)c.size() - 1;           // 路径长度(c[0..L-1] 为路径位置,c[L]=0)
    
        vector<int> depth(M + 1, -1);        // 路径深度
        for (int j = 0; j < L; j++) depth[c[j]] = j;
    
        // 环:不在路径上的位置构成若干不相交的环
        vector<int> cycId(M + 1, -1), idxIn(M + 1, 0);
        vector<vector<int>> cycs;
        for (int s = 1; s <= M; s++) {
            if (depth[s] != -1 || cycId[s] != -1) continue;
            vector<int> cyc;
            int x = s;
            do {
                cycId[x] = (int)cycs.size();
                idxIn[x] = (int)cyc.size();
                cyc.push_back(x);
                x = p[x] - 1;
            } while (x != s);
            cycs.push_back(cyc);
        }
    
        int T = N - M + 1;                   // 洗牌阶段步数
        for (int qi = 0; qi < Q; qi++) {
            int q;
            scanf("%d", &q);
            int t = N - q + 1;               // 该位置的牌是第 t 步被取走的
            int ans;
            if (t <= T) {                    // 洗牌阶段
                if (t <= L) ans = c[L - t];          // 初始牌沿链离开
                else ans = M + t - L;                // 从下方进入的牌按序离开
            } else {                         // 收尾阶段(少于 M 张,依次取走)
                int pp = M - q;              // 收尾时该牌在窗口中的位置
                int j = depth[pp];
                if (j != -1) {
                    if (j < T) ans = N + 1 - j;      // 进入的牌
                    else ans = c[j - T];             // 残留的初始牌
                } else {                             // 环上的牌:按环反向旋转 T 步
                    int r = (int)cycs[cycId[pp]].size();
                    int k = ((idxIn[pp] - T) % r + r) % r;
                    ans = cycs[cycId[pp]][k];
                }
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    
    
    

    信息

    ID
    2117
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者