CSP-J 练习K卷

（1）

01 #include<bits/stdc++.h>
02 using namespace std;
03 char change(char str)
04 {
05     if(str >= 'a' && str <= 'z')
06         str -= 32;
07     return str;
08 }
09 int main()
10 {
11
12     string s1,s2;
13     cin >> s1 >> s2;
14     int cnt = 0;
15     for(int i = 0; i < s1.size(); i++)
16     {
17         for(int j = 0; j < s2.size(); j++)
18             if(change(s1[i]) == change(s2[j]))
19                 cnt++;
20     }
21     cout << cnt;
22     return 0;
23 }

（2）

01 #include<iostream>
02 using namespace std;
03 int solve(int n,int m)
04 {
05     int i,sum;
06     if(m==1)
07         return 1;
08     sum=0;
09     for(i=1;i<n;i++)
10         sum += solve(i,m-1);
11     return sum;
12 }
13 int main()
14 {
15     int n,m;
16     cin>>n>>m;
17     cout<<solve(n,m)<<endl;
18     return 0;
19 }

（3）

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int MAXN = 2e5 + 5;
04 int nums[MAXN];
05 int left_bound(int n,int target){
06     int left = 0, right = n - 1;
07     while(left <= right){
08         int mid = (left + right) / 2;
09         if(nums[mid] < target)
10             left = mid + 1;
11         else
12             right = mid - 1;
13     }
14     if(left < n && nums[left] == target)
15         return left;
16     return -1;
17 }
18 int right_bound(int n,int target){
19     int left = 0, right = n - 1;
20     while(left <= right){
21         int mid = (left + right) / 2;
22         if(nums[mid] <= target)
23             left = mid +1;
24         else
25             right = mid - 1;
26     }
27     if(right >= 0 && nums[right] == target)
28         return right;
29     return -1;
30 }
31 int main()
32 {
33     int n,c;
34     cin>>n>>c;
35     for(int i = 0; i < n; ++i)
36         cin>>nums[i];
37     sort(nums,nums+n);
38     long long ans = 0;
39     for(int i = 0; i < n; ++i){
40         int left = left_bound(n,nums[i] + c);
41         int right = right_bound(n,nums[i] + c);
42         if(left != -1)
43             ans += right - left + 1;
44     }
45     cout<<ans<<endl;
46     return 0;
47 }

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

（1）

给定一棵树，输出树的根 root、孩子结点最多的结点 max 以及它的孩子结点。

输入格式：

第 1 行输入 n（结点数≤100）和m（边数≤200）。以下 m 行输入每行两个结点 x 和 y，表示 y 是 x 的孩子结点（x，y≤1000）。

输出格式：

第 1 行是树根 root。第 2 行是孩子结点最多的结点 max。第 3 行是 max 的孩子结点。

输入样例：

8 7

4 1

4 2

1 3

1 5

2 6

2 7

2 8

输出样例:

6 7 8

01 #include<bits/stdc++.h>
02 using namespace std;
03 int n,m,tree[105]={0};
04 int main()
05 {
06     int i,x,y,root,maxroot,sum=0,j,Max=0;
07     cin>>n>>m;
08     for(i=1;i<=m;i++)
09     {
10         cin>>x>>y;
11         ①;
12     }
13     for(i=1;i<=n;i++) //找出树的根
14         if(②)
15         {
16             root=i;
17             ③;
18         }
19     for(i=1;i<=n;i++) //找孩子结点最多的结点
20     {
21         sum=0;
22         for(j=1;j<=n;j++)
23             if(tree[j]==i)
24                 sum++;
25             if(④)
26             {
27                 Max=sum;
28                 maxroot=i;
29             }
30     }
31     cout<<root<<endl<<maxroot<<endl;
32     for(i=1;i<=n;i++)
33         if(⑤)
34             cout<<i<<" ";
35     return 0;
36 }

（2）

快速排序是一种高效的排序算法，我们常用的 STL 函数 sort 就是采用快速排序思想实现的。如下代码是一个经典的快速排序过程，输入一个整数 n，然后输入 n 个整数，程序会按照从小到大的顺序将所有整数进行排序并输出。请将程序补充完整。

01 #include<bits/stdc++.h>
02 using namespace std;
03 int a[1005];
04 void quickSort(int a[],int begin,int end)
05 {
06     int i,j,temp;
07     if(begin >= end)
08         return;
09     ①;
10     i = begin;
11     j = end;
12     while(i < j)
13     {
14         while(a[j] > tmp)
15             j--;
16         while(②)
17             i++;
18         if(i != j)
19             swap(a[i],a[j]);
20     }
21     ③;
22     ④;
23     quickSort(a,i+1,end);
24 }
25 int main()
26 {
27     int n;
28     cin>>n;
29     for(int i=1;i<=n;i++)
30         cin>>a[i];
31     ⑤;
32     for(int i=1;i<=n;i++)
33         cout<<a[i]<<" ";
34     return 0;
35 }