洛谷 P1996 约瑟夫问题

// P1996 的第 ① 版：把第 5 章那个「关键的一步」原样搬过来
//
// ★★★ 这一版是**对的算法，错的题**。
//   第 5 章后半场的全部力气都花在「不要模拟那个圈」上，最后得到三行递推：
//       f(1) = 0;  f(i) = (f(i-1) + m) % i;   答案 = f(n) + 1
//   它把 O(n²) 压成了 O(n)，而且一个数组都不用开 —— 那一章是这么收尾的。
//
//   可 P1996 要的是**依次出圈的 n 个编号**，不是最后剩下的那一个。
//   而这个递推之所以快，恰恰是因为它**把出圈过程整个跳过了** ——
//   它算的是「幸存者在最后那一层的位置」，中间谁先谁后，它压根没经手。
//
// ⇒ 优化掉的正是这道题要的东西。样例一比就现形：要 10 个数，它只打 1 个。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int f = 0;                       // f(1) = 0（0 基编号）
    for (int i = 2; i <= n; i++) f = (f + m) % i;
    cout << f + 1 << '\n';           // 换回 1 基
    return 0;
}

// P1996 约瑟夫问题（能 AC 的那一版）：拿 vector 当那个圈，谁出局就删谁
//
// 和第 5 章 josephBrute.cpp 只差一处：出局的人**要打出来**，而且要打全 n 个。
//   pos = (pos + m - 1) % size    ← 那个 -1：当前这个人自己就要报「1」
//   erase 之后 pos 正好落在下一个人身上（后面的元素整体往前挪了一格），
//   所以下一轮直接接着算，不用再 +1。
//
// n, m ≤ 100，这一版**已经足够 AC**（最多挪 100×100 = 一万个元素）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> circle(n);
    iota(circle.begin(), circle.end(), 1);   // 1, 2, …, n

    int pos = 0;
    while (!circle.empty()) {
        pos = (pos + m - 1) % (int)circle.size();
        cout << circle[pos] << ' ';
        circle.erase(circle.begin() + pos);  // ← 这一行是 O(size)
    }
    cout << '\n';
    return 0;
}

// 换一把尺子：三种写法各自「碰了多少个元素」
//
// 用法：./p1996Count <n> <m>        打三种写法碰的次数
//       ./p1996Count <n> <m> csv    只打 `键,值`，给 check:viz 用
//
// 三把尺子量的是同一件事 —— **为了找到并删掉下一个人，一共动了多少下**：
//   ② erase：每次 erase 要把后面的元素整体往前挪一格，挪几个就算几下
//   ③ 标记 ：每往后走一格（不管那格是死是活）算一下
//   ④ 树状数组：树状数组里每循环一次算一下（add 和 kth 都算）
//
// ★ 这道题的规模（n ≤ 100）上三者根本分不出高下 —— 这也是正文要讲的一半。
//   把 n 拉大，形状才露出来：前两个是 O(n²)，第三个是 O(n log n)。

#include <bits/stdc++.h>
using namespace std;

int n, m;

long long countErase() {
    vector<int> c(n);
    iota(c.begin(), c.end(), 1);
    long long ops = 0;
    int pos = 0;
    while (!c.empty()) {
        pos = (pos + m - 1) % (int)c.size();
        ops += (long long)c.size() - pos - 1;   // erase 要挪走的元素个数
        c.erase(c.begin() + pos);
    }
    return ops;
}

long long countMark() {
    vector<char> dead(n, 0);
    long long ops = 0;
    int cur = 0;
    for (int left = n; left > 0; left--) {
        int step = (m - 1) % left;
        while (dead[cur]) { cur = (cur + 1) % n; ops++; }
        for (int i = 0; i < step; i++)
            do { cur = (cur + 1) % n; ops++; } while (dead[cur]);
        dead[cur] = 1;
        do { cur = (cur + 1) % n; ops++; } while (left > 1 && dead[cur]);
    }
    return ops;
}

vector<int> bit_;
long long bitOps = 0;
void add(int i, int v) { for (; i <= n; i += i & -i) { bit_[i] += v; bitOps++; } }
int kth(int r, int LOG) {
    int p = 0;
    for (int step = LOG; step > 0; step >>= 1) {
        bitOps++;
        if (p + step <= n && bit_[p + step] < r) { p += step; r -= bit_[p]; }
    }
    return p + 1;
}
long long countFenwick() {
    bit_.assign(n + 1, 0);
    bitOps = 0;
    int LOG = 1;
    while ((LOG << 1) <= n) LOG <<= 1;
    for (int i = 1; i <= n; i++) add(i, 1);
    int k = 1;
    for (int left = n; left > 0; left--) {
        int r = (k + m - 2) % left + 1;
        int who = kth(r, LOG);
        add(who, -1);
        k = (r > left - 1) ? 1 : r;
    }
    return bitOps;
}

int main(int argc, char** argv) {
    n = (argc > 1) ? atoi(argv[1]) : 10;
    m = (argc > 2) ? atoi(argv[2]) : 3;
    bool csv = (argc > 3 && string(argv[3]) == "csv");
    long long a = countErase(), b = countMark(), c = countFenwick();
    if (csv) {
        printf("n,%d\nm,%d\nerase,%lld\nmark,%lld\nfenwick,%lld\n", n, m, a, b, c);
    } else {
        printf("n = %d, m = %d\n", n, m);
        printf("② vector::erase   挪了 %lld 个元素\n", a);
        printf("③ 标记 + 跳过     走了 %lld 格\n", b);
        printf("④ 树状数组        循环了 %lld 次\n", c);
    }
    return 0;
}