摘要
Title: 3559. 围圈报数
Tag: 链表、约瑟夫环
Memory Limit: 64 MB
Time Limit: 1000 ms

3559. 围圈报数

题意

N 个人围成一圈顺序编号，从 1 号开始按 1、2、3 顺序报数，报 3 者退出圈外，其余的人再从 1、2、3 开始报数，报 3 的人再退出圈外，依次类推。
请按退出顺序输出每个退出人的原序号。
要求使用环行链表编程。
思路

n比较小，所以可以用数组模拟链表，可以直接模拟来做

next数组存下一个数的下标，初始化就是环形链表，存前一个人的，也就是存第n个人，要往后报两格，所以两次next操作，到要弹出的点的父亲，然后输出弹出的点，最后再连上链表即可

代码

循环链表做法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

void solve(){
    int n;
    cin >> n;
    vector <int> ne(n + 1);
    for(int i = 1; i < n; ++ i){
        ne[i] = i + 1;
    }
    ne[n] = 1;
    
    int p = n;
    for(int i = 1; i <= n; ++ i){
        p = ne[ne[p]]; // p = 2
        cout << ne[p] << ' '; // ne[p] = 3
        ne[p] = ne[ne[p]]; // ne[p] = 4
    }
    cout << '\n';
    return;
}


int main()
{
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

正常队列做法

/*
* @Author: NEFU AB-IN
* @Date: 2022-07-29 22:54:45
* @FilePath: \Acwing\3559\3559.1.cpp
* @LastEditTime: 2022-07-29 22:57:34
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int INF = INT_MAX;
const int N = 1e6 + 10;

void solve()
{

    int n;
    cin >> n;

    queue<int> q;
    for (int i = 1; i <= n; ++i)
    {
        q.push(i);
    }
    int cnt = 0;
    while (SZ(q))
    {
        auto t = q.front();
        q.pop();
        cnt++;
        if (cnt == 3)
        {
            cnt = 0;
            cout << t << " ";
            continue;
        }
        q.push(t);
    }
    cout << '\n';
    return;
}

signed main()
{
    IOS;
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

3559. 围圈报数

题意

思路

代码