ConanKIDの小窝

ConanKIDの小窝

P3095 题解

posted on 2021-10-03 15:05:59 | under 题解 |

这里补一个 $O(nq)$ 的做法。

暴力 $O(nm)$ 显然是不行的。但我们看到 $q$ 的范围很小,只有 $5000$,所以考虑对每个询问,用 $O(n)$ 或 $O(m)$ 的时间解决掉。

考虑倒推。我们从后往前模拟每次置换,求出当前牌在本轮置换以前的位置。这样单次询问的复杂度就做到$O(n)$了。

时间卡的有点紧,吸了口氧跑过去了。

代码很短。

#include<bits/stdc++.h>
using namespace std;
int n, m, q;
int rep[100005];
inline int read() {
    int x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    return x;
}
int main() {
    n = read(); m = read(); q = read();
    for (int i = 1; i <= m; i++)
        rep[read()] = i;//rep[i]表示对于一个排列置换后,位置i上原本的数
    for (int i = 1; i <= q; i++) {
        int x = read(), pl = n - x + 1;
        for (int j = n - x + 1; j >= 1; j--)
            if (pl <= j + m - 1 && j + m - 1 <= n) pl = j + rep[pl - j + 1] - 1;//模拟倒推
        printf("%d\n", pl);
    }
    return 0;
}