第四套CCF信息学奥赛c++ CSP-J认证初级组中小学信奥赛入门组初赛考前模拟冲刺题（完善程序题）

第四套中小学信息学奥赛CSP-J考前冲刺题

三、完善程序题

第一题田忌赛马

田忌赛马，田忌每赢一次齐王的马就得200金，,当然输了就扣200金币，平局则金币数
不变。

#include<iostream>
using namespace std;
int main(){
	int n;
	while(cin>>n&&n!=0){
		int tj[1001],king[1001],count=0;
		int tj_min=0,tj_max=n-1;
		int king_min=0,king_max=n-1;
		for(int i=0;i<n;i++)cin>>tj[i];
		for(int i=0;i<n;i++)cin>>king[i];
		sort(tj,tj+n);
		sort(king,king+n);
		while(n--){
			if(tj[ ①]>king[ ② ]){
				count++;
				tj_max--;
				king_max--;
			}
			else if (tj[ ③ ]<king[ ④ ]){
				count--;
				tj_min++;
				king_max--;
			}
			else
			{
				if(tj[tj_min]>king[king_min]){
					count++;
					__⑤__;
					__⑥__;
				}
				else{
					if(__⑦__)
						count--;
					tj_min++;
					__⑧__;
				}
			}
		}
		cout<<count*200<<endl;
	}
}

程序分析：此程序实现了田忌赛马的计分规则。

游戏的规则如下：田忌和国王赛马，它们之间进行对战。
每人有n个分数。分数是由输入的n个整数数组表示的。输入数组tj表示田忌的分数，输入数组king表示国王的分数。玩家的分数按照从小到大排序。
每轮对战，比较tj数组和king数组中的最大值。如果tj的最大值比king的最大值大，tj获得一分，并将tj数组和king数组中对应的最大值删除。
如果tj的最大值比king的最大值小，tj失去一分，并将tj数组中最小的值删除，king数组中的最大值删除。
如果tj的最大值和king的最大值相等，判断tj的最小值和king的最小值的关系。
如果tj的最小值比king的最小值大，tj获得一分，并将tj数组中最小的值和king数组中最小的值删除。
如果tj的最小值比king的最小值小，tj失去一分，并将tj数组中最小的值删除，king数组中最大的值删除。
最终得分是tj获得的分数乘以200。当n为0时，游戏结束。

单选题

①处和②处应该填

A. tj_max 和 king_max
B. tj_min 和 king_max
C. tj_min 和 king_min
D. tj_max 和 king_min

答案：A

答案分析：从程序分析中可以得知此处应该是A

③处和④处应该填

A. tj_max 和 king_max
B. tj_min 和 king_min
C. tj_min 和 king_max
D. tj_max 和 king_min

答案：C

答案分析：从程序分析中可以得知此处应该是C

⑤处和⑥处应该填

A. lj_min--和 king_min++
B. tj_max++和 king_min++
C. tj_min++和 king_min++
D. lj_max++和 king_min--

答案：C

答案分析：从程序分析中可以得知此处应该是C

⑦处应该填

A. tj[ tj_min ]<king[ king_max]
B. tj[ tj_max]<king[ king_max]
C. j[ tj_min]>king[ king_max]
D. tj[ tj_min]>king[ king_min]

答案：A

答案分析：从程序分析中可以得知此处应该是A

⑧处应该填

A. king_max--
B. king_max++
C. king_min--
D. king_min++

答案：A

答案分析：从程序分析中可以得知此处应该是A

第二题寻路问题

N*N矩阵，其中0是表示可以走的，1表示无法走，矩阵由二维数组表示，左上角角是人口，右下角是出口，只能横着走和竖着走，要求找出最短路径。

#include<iostream>
using namespace std;
int mymax=10000;
int f[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int a[20][20],v[20][20],v1[20][20];
int l=1;
int n;//矩阵的规模
bool check(int x1,int y1){
	if(x1<0 ||x1>=n ||__①__)return false;
	if(a[x1][y1]==1 ||__②__)return false;
	return true;
}
void dfs(int x,int y){
	if(x==n-1 && y==n-1){
		if(l<mymax){
			mymax=l;
			memcpy(v1,v,sizeof(v1));
		}
		return;
	}
	for(int k=0;k<4;k++){
		int x1,y1;
		x1=x+__③__;
		y1=y+__④__;
		if(check(x1,y1)){
			__⑤__;
			__⑥__;
			dfs(x1,y1);
			__⑦__;
			v[x1][y1]=0;
		}
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	}
	dfs(0,0);
	int d=v1[n-1][n-1];
	int x=n-1,y=n-1;
	int k;
	int qn[400][2];
	qn[0][0]=n-1;
	qn[0][1]=n-1;
	for(k=1;;k++){
		x=x-f[d][0];
		y=y-f[d][1];
		qn[k][0]=x;
		qn[k][1]=y;
		d=v1[x][y];
		if(x==0&&y==0)break;
	}
	for(int i=k;i>=0;i--)
		cout<<__⑧__<<","<<__⑨__<<endl;
	return 0;
}

程序分析：此程序通过深度优先搜索算法，解决了一个迷宫问题。

程序读取用户输入的矩阵规模n，然后读取一个n*n的矩阵，其中1表示障碍物，0表示可行的路径。
程序从(0,0)开始搜索，寻找一条从起点到终点(n-1,n-1)的路径，要求路径的长度最小。
程序中使用一个4*2的数组f来表示移动的方向，包括上、下、左、右四个方向。
使用一个二维数组a来表示迷宫的矩阵，数组v用来标记已经访问过的路径，数组v1用来记录最短路径。
变量l表示当前路径的长度，mymax用来记录最短路径的长度。
check函数用来判断当前位置是否可行。
程序中的dfs函数是递归的，它从当前位置开始，按照四个方向进行搜索。如果当前位置是终点，且路径长度小于最短路径长度，则更新最短路径长度和最短路径数组。否则，继续向下一步搜索。
在递归的过程中，l和v数组会相应地进行更新。在搜索结束后，根据v1数组中的记录，从终点开始逆向输出最短路径上的所有点。输出的顺序是从终点到起点。
总的来说，该程序利用深度优先搜索算法，通过递归的方式搜索迷宫中的所有可行路径，找到最短路径，并输出

单选题

①处和②处应该填

A. y1<=0lly1>n 和 v[x1][y1]>0
B. y1<0lly1>=n 和 v[x1][y1]>0
C. yl>0&&y1<=n 和 v[x1][y1]>0
D. y1>0&&y1<n 和 v[x1][y1]>0

答案：B

答案分析：从程序分析中可以得知①处是判断是否越界，②处是判断是否还有其它方向可以走，答案B

③处和④处应该填

A. f[k][0]和 f[k][1]
B. f[k][1]和 f[k][0]
C. f[0][k]和{[1][k]
D. f[1][k]和 f[0][k]

答案：A

答案分析：从程序分析中可以得知此处应该是获取下一个路径位置，答案A

⑤处应该填

A. v[x1][y1]=k+1;
B. v[x1][y1]=k;
C. v[x][y]=k;
D. v[x][y]=k+1;

答案：B