2021CCF认证第一轮（CSP-J）真题
三、完善程序题
第一题 约瑟夫问题
有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(int i=0;i<n;i++)
if(F[i]==0)
ans=i;
cout << ans <<endl;
return 0;
}程序分析：此程序以是一个解决Josephus问题的算法。
- 程序的主要思路是使用一个布尔数组F来表示每个人的状态，初始时都为0（表示还在圈内）。然后使用变量p表示当前轮到的人是否报数，初始为0。变量c表示已经出列的人数，初始为0。
- 然后使用循环遍历数组F，直到所有人都出列为止。 在循环中，首先判断当前人是否还在圈内，即F[i]是否为0。如果不在圈内，则跳过该人。如果在圈内，则判断当前轮到的人是否需要报数，即p是否为1。如果需要报数，则将当前人标记为已出列（F[i]=1），并将出列人数c加1。然后将p取反，表示下一轮到的人是否报数。最后将i更新为下一个人的位置（(i + 1) % n）。
- 最后，循环结束后，再次遍历数组F，找到最后剩下的人的位置。将数组中值为0的位置记录到变量ans中。如果ans仍为初始值-1，则说明没有人剩下。最后将ans输出。
单选题
①处应该填
A. i < n
B. c < n
C. i < n - 1
D. c < n - 1
答案：D
答案分析：从程序分析中可以得知此处应该是判断是否游戏结束的条件，那就是出圈的人数比输入人数少一，答案D
②处应该填
A. i % 2 ==0
B. i % 2 ==1
C. p
D. !p
答案：C
答案分析：从程序分析中可以得知此处应该是已经报数且数字为1的人，答案C
③处应该填
A. i++
B. i = (i+1) % n
C. c++
D. p ^= 1
答案：C
答案分析：从程序分析中可以得知此处应该是报数为1就表示出圈，出圈人数加1，答案C
④处应该填
A. i++
B. i = (i+1) % n
C. c++
D. p ^= 1
答案：D
答案分析：从程序分析中可以得知此处应该是已经出圈了标记需要重新调整，答案D
⑤处应该填
A. i++
B. i = (i+1) % n
C. c++
D. p ^= 1
答案：B
答案分析：从程序分析中可以得知此处应该是更新下一个报数的人，答案B
第二题 矩形计数
平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次
#include <iostream>
using namespace std;
struct point{
int x, y, id;
};
bool equals(struct point a,struct point b){
return a.x == b.x && a.y == b.y;
}
bool cmp(struct point a, struct point b){
return ①;
}
void sort(struct point A[], int n){
for(int i = 0; i < n; i++)
for(int j = 1; j < n; j++)
if(cmp(A[j], A[j - 1])){
struct point t=A[j];
A[j] = A[j - 1];
A[j - 1] = t;
}
}
int unique(struct point A[],int n){
int t=0;
for(int i = 0; i < n; i++)
if(②)
A[t++] = A[i];
return t;
}
bool binary_search(struct point A[], int n, int x, int y){
struct point p;
p.x = x;
p.y = y;
p.id = n;
int a = 0, b = n - 1;
while(a < b){
int mid=③;
if(④)
a = mid + 1;
else
b = mid;
}
return equals(A[a], p);
}
#define MAXN 1000
struct point A[MAXN];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
scanf("%d %d", &A[i].x, &A[i].y);
A[i].id = i;
}
sort(A,n);
n = unique(A, n);
int ans = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(⑤&& binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)){
ans++;
}
cout << ans << endl;
return 0;
}程序分析：
- 此程序首先，定义了一个point结构体，包含了点的坐标x、y以及id。
- 然后，通过equals函数判断两个point结构体是否相等，即x和y都相等。
- 接下来，通过cmp函数对point数组进行排序。排序规则为先根据x进行排序，如果x相等则按照y进行排序。这样可以保证数组按照x递增、y递增的顺序排列。
- 再接着，通过sort函数对point数组进行排序。
- 然后，通过unique函数将point数组中的重复元素去除。去除的方法是通过遍历数组，如果当前元素与前一个元素不相等，则将当前元素保留，否则舍弃。
- 接下来，通过binary_search函数实现二分查找。查找的方法是先构造一个新的point结构体p，将要查找的x和y赋值给p，然后通过二分查找的方式找到满足条件的点。
- 最后，通过主函数main实现整个功能。首先读入n，表示点的个数。然后利用循环读入每个点的坐标和id。接着对点数组进行排序和去重。然后利用两层循环遍历每对点，判断满足条件的点对个数。最后输出结果。
单选题
①处应该填
A.a.x != b.x ? a.x < b.x : a.id < b.id
B.a.x != b.x ? a.x < b.x : a.y< b.y
C.equals(a,b) ? a.id<b.id:a.x<b.x
D.equals(a,b) ? a.id<b.id: (a.x != b.x ? a.x < b.x : a.y< b.y)
答案：B
答案分析：从程序分析中可以得知此处应该是进行比较实现点排序，首先满足x坐标递增，x坐标一样就进行y坐标递增，答案B
②处应该填
A. i == 0 || cmp(A[i], A[i - 1])
B. t == 0 || equals(A[i], A[t - 1])
C. i == 0 || !cmp(A[i], A[i - 1])
D. t == 0 || !equals(A[i], A[t -1])
答案：D
答案分析：从程序分析中可以得知此处应该是进行去重，当前元素和前一个元素不相同，才进行保留，答案D
③处应该填
A.b – (b – a) / 2 + 1
B.(a + b + 1) >> 1
C.(a + b) >> 1
D.a + (b – a + 1) / 2
答案：C
答案分析：从程序分析中可以得知此处应该是二分查找除以2，二进制右移1位，就相当于除以2，答案C
④处应该填
A.!cmp(A[mid], p)
B.cmp(A[mid], p)
C.cmp(p, A[mid])
D.!cmp(p, A[mid])
答案：B
答案分析：从程序中可以看到是左边界a=mid+1，说明是左边界右移，那也就是左边小于p，答案B
⑤处应该填
A.A[i].x == A[j].x
B.A[i].id < A[j].id
C.A[i].x == A[j].x && A[i].id < A[j].id
D.A[i].x<A[j].x && A[i].y < A[j].y
答案：D
答案分析：从程序分析中可以得知此处应该是举行左下和右上两个点，对应左下xy都小于右上xy，答案D