1 条题解
-
1
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
- 上传者