【比特杯-C语言大赛】(2018)比特杯C语言大赛题解

第0题

题意

给出一段字符串和一个整数n,输出在字符串中第一次出现n次的字符;
例如: abbbcdeee 3 → b

题解

显然,遍历字符串时用count()函数检测该字符的数量,如果等于n,则输出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,i;
bool vis[300];//记录该字符是否被访问过
string str;
cin >> str >> n;
int len = str.size();
for(i = 0;i < len; i++){
if(vis[(int)str[i]] == false){
vis[(int)str[i]] = true;
if(count(str.begin(),str.end(),str[i]) == n){
cout << str[i] << endl;
break;
}
}
}
if(len == i) cout << "-1" << endl;

return 0;
}

第1题

题意

题目是要输出一个蛇形上三角矩阵
有多组输入样例

输入:

5

输出

1 3 6 10 15
2 5 9 14
4 8 13
7 12
11

题解

设矩阵第一个元素是从第0行第0列开始的;
我们可以观察到,对于第一列,a[i][0] = a[i][0] + i;
然后我们在观察每一行除了第一个元素以外,a[i][j] = a[i][j - 1] + i + j + 1 (i != 0);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define maxn 205
int a[maxn][maxn],n;
int main()
{
while(cin >> n){
for(int i = 0;i < n;i++) fill(a[i],a[i] + n,0);
a[0][0] = 1;
for(int i = 0;i < n; i++){
if(i != 0) a[i][0] = a[i - 1][0] + i;
cout << a[i][0];
for(int j = 1;j < n - i; j++){
a[i][j] = a[i][j - 1] + i + j + 1;
cout << " " <<a[i][j];
}
cout << endl;
}
}

return 0;
}

第2题

题意

第一行输入一个数字n,接下来有n个整数,如果有一个数字出现次数超过n的一半,则输出。否则,输出”-1”。

题解

这道题可以用标准模板库的map来做,建立一个”数字 → 出现次数”的映射。
即map m;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,x = 0;
cin >> n;
map<int,int> m;
for(int i = 0;i < n; i++){
cin >> k;
if(++m[k] > n/2) x = k;
}
cout << x << endl;;

return 0;
}

第3题

题意

有n个相同苹果和k个相同盘子,问有多少种不同的摆法。
例如 7 3 → 8;
样例中,4 1 2和4 2 1 视为同一种。部分盘子可以为空。

题解

在数学中,我们可以发现,如果要得到唯一不同的情况,需要第i个盘子装的水果不比第i - 1个盘子多,否则就会造成重复。
例如:

7 0 0
6 1 0
5 2 0
5 1 1
4 3 0
4 2 1
3 3 1
3 2 2

但是,如果出现

4 1 2
4 0 3
3 1 3

类似的情况,就会发现存在重复,以为某一个元素存在前一个元素比自身要小。
所以我们用搜索来排除这种干扰;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int n,k,cnt = 0;
void dfs(int x,int sum,int num){
if(num > k){
if(sum == n) cnt++;
return;
}
for(int i = x;i >= 0;i--)
dfs(i,i + sum,num + 1);
}
int main()
{
cin >> n >> k;
dfs(n,0,1);
cout << cnt << endl;
return 0;
}

后记

本人才疏学浅,若发现问题,望尊指正。