「UOI 2016 Stage 4 Day1」硬汉俱乐部 题解

题目大意

有 $N$ 个俱乐部成员，初始时按 $1$ 到 $N$ 排名。比赛进行 $M$ 个回合，每回合：

• 排名前 $K$ 的人参与比赛
• 其中第 $A_i$ 个人被淘汰并移到排名末尾
• 记录被淘汰者的原始排名

已知比赛结束后的排名 $P$，求比赛开始前的排名。

解题思路

关键观察

这是一个逆向模拟问题。我们需要从最终状态反推初始状态。

正向过程分析

每回合的操作：

1. 取出前 $K$ 个人：$[r_1, r_2, \dots, r_K]$
2. 淘汰第 $A_i$ 个人 $r_{A_i}$
3. 将 $r_{A_i}$ 移到末尾
4. 其他人保持相对顺序

逆向推导策略

从最后一轮开始往前推，对于每一轮：

设当前斯特凡的位置为 pos，该轮淘汰的位置为 eliminated：

• 情况1：如果 pos == N

  • 说明斯特凡是这一轮被淘汰的人
  • 在轮次开始时，他应该在 eliminated 位置
  • 更新：pos = eliminated

• 情况2：如果 pos >= eliminated

  • 斯特凡在淘汰者之后（或相同，但相同已被情况1处理）
  • 当淘汰者回到前面时，斯特凡位置会后移
  • 更新：pos++

• 情况3：如果 pos < eliminated

  • 斯特凡在淘汰者之前
  • 位置不受影响

代码实现

#include <iostream>
#include <vector>
using namespace std;

long long solve(long long N, long long K, long long M, vector<int>& A, long long final_rank) {
    long long pos = final_rank;
    
    for (int i = M - 1; i >= 0; i--) {
        int eliminated = A[i];
        
        if (pos == N) {
            // 斯特凡是这一轮被淘汰的人
            pos = eliminated;
        } else if (pos >= eliminated) {
            // 斯特凡在淘汰者之后，位置后移
            pos++;
        }
        // 否则位置不变
    }
    
    return pos;
}

int main() {
    long long N, K, M, P;
    cin >> N >> K >> M;
    
    vector<int> A(M);
    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }
    cin >> P;
    
    long long initial_rank = solve(N, K, M, A, P);
    cout << initial_rank << endl;
    
    return 0;
}

算法正确性

样例验证

输入：

6 2 3
1 2 1
5

逆向推导过程：

• 最终排名：5
• 第3轮：淘汰第1名
  • pos=5 >= 1 → pos=5+1=6
• 第2轮：淘汰第2名
  • pos=6 == N=6 → pos=2
• 第1轮：淘汰第1名
  • pos=2 >= 1 → pos=2+1=3

输出：3 ✓

逻辑解释

• 第3轮：淘汰第1名，斯特凡在第5名（在淘汰者之后），当淘汰者回到前面时，斯特凡从第5名后移到第6名
• 第2轮：淘汰第2名，斯特凡在第6名（就是被淘汰的人），所以在轮次开始时他在第2名
• 第1轮：淘汰第1名，斯特凡在第2名（在淘汰者之后），当淘汰者回到前面时，斯特凡从第2名后移到第3名

复杂度分析

• 时间复杂度：$O(M)$，每个回合处理一次
• 空间复杂度：$O(M)$，存储淘汰记录

总结

本题的巧妙之处在于：

1. 逆向思维：从结果反推原因
2. 位置追踪：专注于斯特凡一个人的位置变化
3. 分类讨论：根据相对位置关系决定如何调整

这种逆向模拟的方法在解决类似的序列变换问题时非常有效。