普及组CSP-J2024初赛模拟卷1

（1）

01 #include<bits/stdc++.h>

02 using namespace std;

03 int gcd(int a,int b){

04 int tmp;

05 if(b) tmp = a%b;

06 else return a;

07 while(tmp){

08 a = b;

09 b = tmp;

10 tmp = a%b;

11 }

12 return b;

13 }

14 int lcm(int a,int b){

15 return a/gcd(a,b)*b;

16 }

17 int main(){

18 int a,b;

19 cin >> a >> b;

20 cout << gcd(a,b) << endl;

21 return 0;

22 }

(2)

01 #include<bits/stdc++.h>

02 using namespace std;

03 int main()

04 {

05 char s[128] = {0};

06 cin.getline(s,128);

07 for(int i = 0; i < strlen(s); ++i){

08 if(s[i] >= 65 && s[i] <= 90){

09 if(s[i] == 90)

10 s[i] = 65;

11 else

12 s[i] += 1;

13 s[i] ^= ' ';

14 }

15 }

16 cout << s << endl;

17 return 0;

18 }

(3)

01 #include<bits/stdc++.h>

02 using namespace std;

03 int used[20],a[20],n;

04 long long ret=0;

05 bool flag;

06 void dfs(int x)

07 {

08 int i;

09 if(x > n)

10 {

11 flag=1;

12 for(i=1;i<=n;i++)

13 if(a[i]+i > n+2)

14 {

15 flag=0;

16 break;

17 }

18 if(flag) ret++;

19 return;

20 }

21 for(i=1;i<=n;i++)

22 if(used[i]==0)

23 {

24 used[i]=1,a[x]=i;

25 dfs(x+1);

26 used[i]=0,a[x]=0;

27 }

28 }

29 int main()

30 {

31 cin>>n;

32 dfs(1);

33 cout<<ret;

34 return 0;

35 }

三、完善程序（单选题，每小题3分，共计30分）

（1）输入一个十进制正整数n，然后将n转换为二进制数，最后统计二进制数的各位数字，看看一共有多少位为1，然后打印出总数。

输入格式：

第1行输入十进制正整数n。

输出格式：

输出一个整数，表示十进制正整数n转换成的二进制数中有多少位为1。

输入样例：

127

输出样例:

样例说明:

十进制数127转换为二进制数1111111，二进制位一共有7个1，所以输出7。

01 #include<bits/stdc++.h>

02 using namespace std;

03 int a[33],cnt;

04 int main()

05 {

06 int n,sum,x;

07 cin>>n;

08 cnt=0;

09 ①;

10 while(x>0)

11 {

12 a[②]=x%2;

13 ③;

14 }

15 sum=0;

16 for(int i=1;④;i++)

17 if(a[i]==1)

18 ⑤;

19 cout<<sum<<endl;

20 return 0;

21 }

（2）在一个n×n的棋盘上布满了0和1，如图（a）所示（n=7）。为叙述方便，将0用字母表示，如图（b）所示。

跳棋规则如下。

（i）

从某个0格出发，可以向上、下、左、右4个方向连续越过若干个（至少1个）1格后跳入下一个0格。如图（b）所示，从A出发，可跳到B，或者跳到E，但不能直接跳到K。在跳到B之后还可以继续跳到F，在跳到E之后可继续跳到F或K，直到不能再跳为止。

（ii）

每个0格只能到达一次，给出的起始点不能再次到达，也不能越过。跳过的距离为跳过1格的个数加1，如从A到B，跳过距离为3，从B到F，跳过距离为2。

问题：当给出棋盘和起始点之后，最远能跳的距离是多少？

如图（b）所示，从A出发，可跳的路线不止一条，其中一条为：

A – B – F – L – K – E（可能不唯一）

3 2 3 3 3

它的跳过距离为14。

输入格式：

第1行3个整数n（1≤n≤100）、x、y（x，y是起始点坐标，图（b）中A处坐标为1，3）。接下来n行，每行n个数（0或1），数与数之间用一个空格分隔。

输出格式：

一个整数，即最大可跳距离（若不能跳，则输出0）。

输入样例：

4 3 2

1 0 1 0

1 1 1 1

0 0 1 0

1 1 0 1

输出样例:

01 #include<bits/stdc++.h>

02 using namespace std;

03 int n,i,j,k,ans;

04 int a[105][105],vis[105][105];//a表示棋盘，vis统计点是否走过

05 int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};

06 void dfs(int x,int y,int step)

07 {

08 ans=①;

09 for(int i=0;i<4;i++)

10 {

11 int tx=x,ty=y;s=0;

12 while(tx+dx[i]>0 && tx+dx[i]<=n

13 && ty+dy[i]>0 && ty+dy[i]<=n)

14 {

15 tx+=dx[i];

16 ty+=dy[i];

17 s++;

18 if(②)

19 break;

20 }

21 if(t>0 && tx<=n && ty>0 && ty<=n && vis[tx][ty]==0

22 && a[tx][ty]==0 && s!=1)

23 {

24 vis[tx][ty]=1;

25 dfs(tx,ty,③);

26 ④;

27 }

28 }

29 }

30 int main(){

31 int x,y,i,j;

32 cin>>n>>x>>y;

33 for(i=1;i<=n;i++)

34 for(j=1;j<=n;j++)

35 cin>>a[i][j];

36 ⑤;

37 dfs(x,y,0);

38 cout<<ans<<endl;

39 return 0;

40 }