Powered by:NEFU AB-IN

Link

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;
  }