#cspjc2025w2. 2025csp-j初赛完善程序2

2025csp-j初赛完善程序2

2025csp-j初赛完善程序1

每小题3 分

1.第二题

(精明与糊涂) 有 N个人,分为两类: i) 精明人:永远能正确判断其他人是精明还是糊涂; ii)糊涂人:判断不可靠,会给出随机的判断。

​ 已知精明人严格占据多数,即如果精明人有 k个,则满足 k>N/2。

​ 你只能通过函数 query(i,j)让第 i个人判断第 j个人:返回 true 表示判断结果为“精明人”;返回 false 表示判断结果为“糊涂人”。你的目标是,通过这些互相判断,找出至少一个百分之百确定的精明人。同时,你无需关心 query(i,j)的内部实现。

​ 以下程序利用“精明人占多数”的优势。设想一个“消除”的过程,让人们互相判断并进行抵消。经过若干轮抵消后,最终留下的候选人必然属于多数派,即精明人。

​ 例如,假设有三人 0,1,2。如果 0说 1 是糊涂人,而 1 也说 0 是糊涂人,则 0和 1 至少有一个是糊涂人。程序将同时淘汰 0 和 1。由于三人里至少有两个精明人,我们确定 2 是精明人。

​ 试补全程序。

#include <iostream>
#include <vector>
using namespace std;
 
int N;
bool query(int i, int j);
 
int main() {
    cin >> N;
 
    int candidate = 0;
    int count = __①__;
    for (int i = 1; i < N; ++i) {
        if (__②__) {
            candidate = i;
            count = 1;
        } else {
            if (__③__) {
                __④__;
            } else {
            count++;
            }
        }
    }
    cout << __⑤__ << endl;
    return 0;
}

1.①处应填( ){{ select(1) }}

  • 0
  • 1
  • N
  • -1

2.②处应填( ){{ select(2) }}

  • count < 0
  • count == 1
  • count == 0
  • query(candidate, i) == false

3.③处应填( ) {{ select(3) }}

  • query(candidate, i) == false
  • query(i, candidate) == true
  • query(candidate, i) == false && query(i, candidate) == false
  • query(candidate, i) == false || query(i, candidate) == false

4.④处应填( ) {{ select(4) }}

  • count--
  • break
  • count++
  • candidate = i

5.⑤处应填( ) {{ select(5) }}

  • N - 1
  • count
  • candidate
  • 0