Powered by:NEFU AB-IN

Link

3559. 围圈报数

• 题意

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

• 思路

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

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

• 代码

  循环链表做法

  #include 
  #include 
  #include 
  
  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;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35

  正常队列做法

  /*
  * @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 
  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;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60