#4347. CSP 2021 普及组级第一轮:完善程序第一题

CSP 2021 普及组级第一轮:完善程序第一题

(Josephus 问题)有n个人围成一个圈,依次标号 0 至 n−1。从 0 号开始,依次0,1,0,1,... 交替报数,报到 1 的人会离开,直至圈中只剩下一个人。求最后剩下人的编号。

#include <iostream>

using namespace std;

const int MAXN = 1000000;
int F[MAXN];

int main() {
    int n;
    cin >> n;
    int i = 0, p = 0, c = 0;
    while (①) {
        if (F[i] == 0) {
            if (②) {
                F[i] = 1;
                ③;
            }
            [④]; 
        }
        [⑤]; 
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    cout << ans << endl;
    return 0;
}

1、①处应填( )

{{ select(1) }}

  • i<n
  • c<n
  • i<n-1
  • c<n-1

2、②处应填( )

{{ select(2) }}

  • i%2==0
  • i%2==1
  • p
  • !p

3、③处应填( )

{{ select(3) }}

  • i++
  • i = (i + 1) % n
  • c++
  • p^=1

4、④处应填( )

{{ select(4) }}

  • i++
  • i = (i + 1) % n
  • c++
  • p^=1

5、⑤处应填( )

{{ select(5) }}

  • i++
  • i = (i + 1) % n
  • c++
  • p^=1