P4849 难忘的生日（基础）

解题思路

**第一步，把问题看成“报数淘汰”。**礼物围成一圈，从1号开始，每人数到3就拆开，拆掉后下一份礼物接着数。问最后拆的是几号。这就是经典的“约瑟夫环”问题，报数间隔是3。

**第二步，想一个递推的好办法。**如果我们知道只有i-1份礼物时，最后剩下的那份在“0、1、2、…、i-2”编号里的位置是r，那么当礼物数变成i份时，多出来的那一份正好插在报数前进3步的地方，所以新的位置就是 (r+3) % i。从i=2开始一步步递推到n，就得到了最后剩下的位置。

**第三步，把位置转成编号。**递推得到的是从0开始数的位置，最后输出时要加1，才是真正的礼物编号。

**第四步，注意边界情况。**题目说n可以等于0。如果没有礼物，就没有“最后拆的礼物”，这时候输出0比较稳妥。另外n=1时只有1份礼物，直接拆它，答案就是1，递推公式从2开始，也正好不会出错。

**举例子验证。**n=10时，按递推一步步算：从1份礼物位置0开始，依次推过去，最后算出的位置是3，加1等于4，所以答案是4号，和样例一致。

参考代码

// P4849 难忘的生日：约瑟夫环，从1开始1,2,3报数，报3的拆开，求最后一个
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int main() {
    scanf("%d", &n);
    if (n <= 0) {  // 没有礼物的情况
        printf("0\n");
        return 0;
    }
    int r = 0;  // 递推：约瑟夫环幸存者(0为基)
    for (int i = 2; i <= n; i++) r = (r + 3) % i;
    printf("%d\n", r + 1);
    return 0;
}

复杂度分析

递推只需要从2循环到n，一共n-1次取模运算，每次都是O(1)，所以总时间是O(n)。n最大只有40，几乎瞬间就算完。空间上只用了几个变量，是O(1)。这道题用递推比用数组模拟一圈圈拆礼物快得多，代码也很短。