一.认识蓝桥杯赛制

  • 分组:大学A/B组,985、211高校只能报A组,其他学校自选

  • 题型

    • 结果填空题:解唯一,无需写出计算过程,可编程、计算器、Excel计算,填结果即可
    • 程序填空题:给出某一解法的代码,补全空缺部分
    • 编程大题:用到标准输入与标准输出,按题目要求格式给出解
  • C/C++组大题注意事项

    • 程序处理完数据后记得 return0,不要等待下一个用例输入
    • 解答要符合ANSI C++标准,不要乱调用API
    • 头部要明确#include <xxx>
  • 注意时间复杂度和空间复杂度

    1
    2
    3
    4
    5
    6
    7
    8
    o(1)		常数阶
    O(logn) 对数阶
    o(n) 线性阶
    o(nlogn) 线性对数阶
    o(n²) 平方阶
    o(n³) 立方阶
    o(2^n) 指数阶
    o(n!) 阶乘阶

二.字符串和日期处理

输出图形

[大题]例1-打印规律金字塔

要求:当输入4或字母D时,分别输出以下图形

1
2
3
4
5
6
7
8
9
   1
121
12321
1234321

A
ABA
ABCBA
ABCDCBA

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;

int main() {
char c;
cin >> c;
if(c>='A' && c<='Z'){
for(int i=1;i<=c-'A'+1;i++){
//打印空格
for(int j=1; j<=c-'A'+1-i; j++){
cout<<" ";
}
//先打递增字母
for(int j=1; j<=i; j++){
cout<< (char)('A'+j-1);
}
//打印递减部分
for(int j=i-1; j>=1;j--){
cout<< (char)('A'+j-1);
}
cout << endl;
}
}else{
for(int i=1;i<=c-'1'+1;i++){
//打印空格
for(int j=1; j<=c-'1'+1-i; j++){
cout<<" ";
}
//先打递增字母
for(int j=1; j<=i; j++){
cout<< (char)('1'+j-1);
}
//打印递减部分
for(int j=i-1; j>=1;j--){
cout<< (char)('1'+j-1);
}
cout << endl;
}
}
return 0;
}
/*总结:主要考察ASCII码的应用*/

[大题]例2-造房子

假设*为宝藏,我们要建房子保护它

要求输入宝藏布局m(行)和n(列),当输入3 4时输出如下

1
2
3
4
5
6
7
+-+-+-+-+
|*|*|*|*|
+-+-+-+-+
|*|*|*|*|
+-+-+-+-+
|*|*|*|*|
+-+-+-+-+

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int main() {
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<"+-";
}
cout << "+"<< endl;
for(int j=1;j<=m;j++){
cout<<"|*";
}
cout << "|"<< endl;
}
for(int j=1;j<=m;j++){
cout<<"+-";
}
cout << "+"<< endl;
return 0;
}

/*总结:此题要点为观察+-符号和宝藏的关系,较简单*/

字符串处理

  • C++常用的字符串处理函数:
    • strcpy(x,y),将y字符串复制到x
    • strcat(x,y),将y字符串拼接到x后面
    • strcmp(x,y),每个字符依次比较,完全相等返回0,否则返回第一个差值
    • strlen(x),获取字符串x的长度,注意最好不要放在循环条件里(时间开销大)

[填空]例3-对称是一种美

要求输入与输出如下所示

输入1时,输出A

输入2时,输出ABA

输入3时,输出ABACABA

输入4时,输出ABACABADABACABA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <string.h>

char res[5000000];
int main() {
int n;
scanf("%d",&n);
int len = 0;
for(int i=1; i<=n; i++){

/*在此处完善代码*/

res[len] = 'A'+i-1;
len = strlen(res);
}
printf("%s\n",res);
return 0;
}

参考代码

1
2
strcat(res+len+1, res);
/*总结:此题考察了数组名与指针的关系,以及字符串拼接*/

[大题]例4-寻找字符串

有一个字符串为aba,可得它在另一个字符串abababa出现了3次,输入包含两行,第一行为被搜索的字符串(abababa),第二行为要搜索的字符串(aba),字符串长度不大于1000,输出出现次数

输入样例

1
2
ossosso
osso

输出

1
2

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
char s1[1005], s2[1005];
int main() {

fgets(s1, 1004, stdin); //fgets()是个坑,会读取换行符,可以换gets函数
fgets(s2, 1004, stdin);
int len1 = strlen(s1) - 1, len2 = strlen(s2) - 1; //除去换行符
int ans = 0;
for(int i=0; i+len2-1 < len1; i++){
bool matched = true;
for(int j=0; j<len2;j++){
if(s1[i+j]!=s2[j]){
matched = false;
break;
}
}
if(matched){
ans++;
}
}
printf("%d\n",ans);
return 0;
}

日期处理

  • 闰年的定义:

    • 年份非百且能被4整除的年份
    • 能被400整除的年份
    1
    if(year%400==0 || (year%100!=0 && year%4==0))
  • 快速计算星期几(不太可能记下来)

    1
    2
    3
    4
    /*蔡基姆拉尔森计算公式 y/m/d代表年月日*/
    w = (d+2*m+3*(m+1)/5 +y+y/4-y/100+y/400)%7
    w = w+1
    //注意1,2月当做上一年13、14月计算

    [填空]例5-推算星期几

输入年、月、日,推算出那天是星期几

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <string>
using namespace std;
int whatday(int y, int m, int d){

//补全代码,返回正确的星期,用0-6表示星期一到星期天

}
string weekday[7] = {"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
int main() {
int y,m,d;
cin >> y >> m >> d;
cout << weekday[whatday(y,m,d)] << endl;
return 0;
}

参考代码 常见解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int ans = 0;
for (int i=1; i<y; i++){
if(( i%100!=0 && i%4==0 ) || i%400==0){
ans += 366%7;
ans %= 7;
}else{
ans += 365%7;
ans %= 7;
}
}
for(int i=1; i<m; i++){
if(i==1 || i==3 || i==5 || i==7 || i==8|| i==10|| i==12){
ans += 31%7;
ans %= 7;
}else if(i==4 || i==6 || i==9 || i==11){
ans += 30%7;
ans %= 7;
}else if((y%100!=0 && y%4==0) || i%400 ==0){
ans += 29%7;
ans %= 7;
}else{
ans += 28 % 7;
ans %=7;
}
}
ans += (d-1) % 7;
ans %= 7;
return ans;

[大题]例6-求纪念日

输入4个整数y,m,d,k表示一对情侣在一起的日期,求他们k天纪念日具体是哪一天?

输入样例

1
2016 10 1 100

输出样例

1
2017-01-09

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
//用数组表示每个月份天数(闰年2月另算)
int day[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int main() {
int y,m,d,k;
scanf("%d%d%d%d",&y,&m,&d,&k);
for(int i=1; i<=k; i++){
if((y%100!=0 && y%4==0) || y%400 == 0 ){
day[2] = 29;
}else{
day[2] = 28;
}

if(d == day[m]){
d = 1;
m++;
continue; //注意这个continue的用途,防止d再次++
}
if(m == 13){
m = 1;
y++;
}
d++;
}
printf("%0d-%02d-%02d\n", y, m, d);
return 0;
}

/*总结:考察闰年的判断、月份天数,注意continue的坑*/

综合练习

综合1-统计字符串 [*]

输入一个字符串(小于100个字符),统计其中A的数量并输出

输入样例

1
fdAdAkljfJNnA

输出样例

1
3

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<cstring>

char s[105];
int main() {

int len, cnt=0;
scanf("%s",s);
len = strlen(s);
for(int i=0; i<len; i++){
if(s[i]=='A'){
cnt++;
}
}
printf("%d\n",cnt);
return 0;
}
/*此题考查strlen函数和字符转换ASCII码方法,较简单*/

综合2-找最长字符串[*]

输入格式:第一行为输入的字符串个数N (0<N<100)

接下来N行是不同字符串

1
2
3
3d
hello
a

输出格式:输出最长的字符串

1
hello

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cstring>
char s[105], ans[105];
int anslen = 0;
int main() {

int N, len;
scanf("%d", &N);
for(int i =0;i <N; i++){
scanf("%s",s);
len = strlen(s);
if (len > anslen){
anslen = len;
strcpy(ans, s);
}
}
printf("%s\n",ans);
return 0;
}

/*此题主要考查strcpy函数,较简单*/

综合3-修改字符串[*]

输入一个长度大于10小于1000的字符串,要求把所有大小写字母改成下一个字母,如z改成a,Z改成A,其他字符不变

输入样例

1
Afd6gVBZaf4

输出样例

1
Bge6hWCAbg4

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <cstring>

char s[1005];
int main() {
int len;
scanf("%s", &s);
len = strlen(s);
for(int i =0; i<len; i++){
if(s[i] == 'z'){
s[i] = 'a';
}else if(s[i] == 'Z'){
s[i] = 'A';
}else if(s[i]>='A' && s[i]<='Z' || s[i]>='a' && s[i]<='z'){ //注意这里的判断条件,容易忽略
s[i]++;
}

}
printf("%s\n",s);
return 0;
}

综合4-判断超级偶数 [**]

从键盘输入一个位数最多达到10000的整数(long long也存不下),判断他是不是偶数,是则输出YES,否则输出NO

输入样例

1
3242398979

输出样例

1
NO

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <cstring>
char s[10005];
int main() {
int len;
scanf("%s", &s);
len = strlen(s);
if((s[len-1] - '0')%2 == 0){
printf("YES\n");
}else{
printf("NO\n");
}
}
/*此题技巧是将数字按字符串来处理取出末位,比较巧妙*/

综合5-字符倒序输出[*]

输入样例

1
1234567890

输出样例

1
0987654321

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<cstring>

char s[100005];
int main() {
int len ;
scanf("%s", s);
len = strlen(s);
for(int i = len -1;i>=0;i--){
printf("%c",s[i]);
}
printf("\n");
return 0;
}
/*考查字符串和字符的关系,数组长度一般小于10^5不会超限*/

综合6-输出最后单词长度[**]

输入一行字符串s,长度不超过10000

1
Welcome to 515code

输出最后一个单词长度

1
7

参考代码

1
2
3
4
5
6
7
8
9
#include<cstdio>
#include<cstring>
char s[10005];
int main(){
while(scanf("%s",&s)!=EOF);
printf("%d\n",strlen(s));
return 0;
}
/*此题值的一看,使用了EOF的小技巧,scanf在读取到空格时会停止并重新读取下一个,因此while循环实际上读到的是最后一个单词*/

综合7-真题-打印十字图[***]

小明为某机构设计了一个十字型的徽标。

输入格式

一个正整数 n (n<30) 表示要求打印图形的层数。

输出格式

对应包围层数的该标志

输入样例

1
1

输出样例

1
2
3
4
5
6
7
8
9
..$$$$$..
..$...$..
$$$.$.$$$
$...$...$
$.$$$$$.$
$...$...$
$$$.$.$$$
..$...$..
..$$$$$..

输入样例

1
3

输出样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
..$$$$$$$$$$$$$..
..$...........$..
$$$.$$$$$$$$$.$$$
$...$.......$...$
$.$$$.$$$$$.$$$.$
$.$...$...$...$.$
$.$.$$$.$.$$$.$.$
$.$.$...$...$.$.$
$.$.$.$$$$$.$.$.$
$.$.$...$...$.$.$
$.$.$$$.$.$$$.$.$
$.$...$...$...$.$
$.$$$.$$$$$.$$$.$
$...$.......$...$
$$$.$$$$$$$$$.$$$
..$...........$..
..$$$$$$$$$$$$$..

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
char s[125][125]; //4n+5行列,当n=30时为125,节省空间
int main(){
int n;
scanf("%d",&n);

//遍历表盘为'.'
for(int i=0;i<4*n+5; i++){
for(int j=0;j<4*n+5; j++){
s[i][j] = '.';
}
}

//先打十字 中心坐标[2n+2][2n+2]
int center = 2*n+2;
s[center][center] = '$';
for(int i=1;i<=2;i++){
s[center+i][center] = '$';
s[center-i][center] = '$';
s[center][center+i] = '$';
s[center][center-i] = '$';
}
//打印包围圈
for(int i=1;i<=n;i++){
//左上角
int k=center-2*i;
int m=center-2*i-2;
s[k][m+1]='$';
s[k][m+2]='$';
s[k-1][m+2]='$';
//上方
for(int j=1;j<=4*i+1;j++){
s[k-2][m+2+j-1]='$';
}
//左方
for(int j=1;j<=4*i+1;j++){
s[k+j-1][m]='$';
}
//右上角
k=center-2*i;
m=center+2*i+2;
s[k][m-1]='$';
s[k][m-2]='$';
s[k-1][m-2]='$';
//右方
for(int j=1;j<=4*i+1;j++){
s[k+j-1][m]='$';
}
//左下角
k=center+2*i;
m=center-2*i-2;
s[k][m+1]='$';
s[k][m+2]='$';
s[k+1][m+2]='$';
//下方
for(int j=1;j<=4*i+1;j++){
s[k+2][m+2+j-1]='$';
}
//右下方
k=center+2*i;
m=center+2*i+2;
s[k][m-1]='$';
s[k][m-2]='$';
s[k+1][m-2]='$';
}
//输出图像
for(int i=0; i<4*n+5; i++){
printf("%s\n",s[i]);
}
return 0;
}
/*此题考查图像规律,下面详细解释我的算法*/

此题看着输出像一个长方形,但画出来后发现其实是正方形

打印十字图原理

首先,把表盘遍历为 ‘.’符号

第一步:先定位中心点,把5*5的十字打印出来

第二步:定位这四个点,打印十字外一侧红色包围圈

打印十字图外层包围圈

其中用到等差数列原理,不过不知道我的这个算法空间、时间会不会超限。

综合8-计算一年放假多少天[***]

日历有 阳历(公历) 和 阴历(农历) 之分。每年都有法定节假日,这些分成三类——双休、阳历节假日、阴历节假日。

1.双休

周六和周日 2 天

2.阳历节假日

1)元旦:阳历每年 1 月 1 日,放假 1 天

2)劳动节:阳历每年 5 月 1 日,放假 1 天

3)国庆节:阳历每年 10 月 1 日,放假 3 天

4)圣诞节:阳历每年 12 月 25 日,放假 1 天 3.阴历节假日

1)春节:阴历每年 1 月 1 日,放假 3 天

2)清明节:阳历每年 4 月 4 - 6 日之间的某天,放假 1 天

3)端午节:阴历每年 5 月 5 日,放假 1 天

4)中秋节:阴历每年 8 月 15 日, 放假 1 天

当节假日和双休重合时,双休 不延后 也 不提前,保证节假日之间不会重合。现在给你某年的所有阴历节假日的 阳历 日期,以及当年的 1 月 1 日是星期几,请你计算出这一年(阳历 1 月 1 日到 12 月 31 日)放了多少天假(包括双休、阳历节假日和阴历节假日)。

输入格式

第一行输入年份y(1900<y≤2050)。

接下来 4 行,每行输入两个整数 m,d, 依次表示春节、清明节、端午节和中秋节的阳历日期。 最后一行一个整数表示当年 1 月 1 号是星期几(一周内的第几天,每周从星期一开始计数,即星期一为第一天)。

1
2
3
4
5
6
2017
1 28
4 4
5 30
10 4
7

输出格式

输出一个整数,表示当年放假的天数。

1
113

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
int day[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; //写入每月天数,2月要做判断
int mm[10] = {1, 5, 10, 10, 10, 12}; //固定放假的月份
int dd[10] = {1, 1, 1, 2, 3, 25}; //对应上一个数组放假的日期
int nextday(int &m, int &d){
if(d == day[m]){
m++;
d = 1;
}else{
d++;
}
}
int main() {
int y, w, m, d, f, ans;
scanf("%d", &y);

//若为闰年要给2月加一天
if(y%4==0 && y%100!=0 || y%400==0){
day[2] = 29;
}
//读取四行 春节 清明节 端午节 中秋节的阳历日期
for (int i=6; i<10; i++){
scanf("%d%d", &mm[i], &dd[i]);
}
//读取当年1月1号是星期几
scanf("%d", &w);
m = 1;
d = 1;
f = 0;
ans = 0;
while(m != 13){
//判断春节
if(m == mm[6] && d == dd[6]){
ans++;
f = 2;
}else if(f){
ans++;
f--;
}else if( w==6 || w==7){
ans++; //周末
}else{
for(int i=0; i<10; i++){
//找节日
if(m == mm[i] && d == dd[i]){
ans++;
break;
}
}
}
//下一天是几月几号
nextday(m, d);
//下一天星期+1
w = w + 1;
if(w == 8){
w = 1;
}
}
printf("%d\n",ans);
return 0;
}

三.使用Sort排序(C++)

  • 若对一个数组元素进行交换,例如元素按顺序排序,我们可以使用C++的强大工具——sort

  • 头文件 #include <algorithm>

  • 举例:sort(arr, arr+5),代表排序arr[0]到arr[4],因此注意sort后面要多写一位

  • sort的参数

    1
    2
    3
    // 第三个参数为排序方法,grater代表从大到小排序
    // 若不填第三个参数,则默认从小到大排序
    sort(arr, arr+5, greater<int>)

[大题]例1-计算班级前K名平均成绩[*]

输入格式,一共输入三行

第一行:班级人数N (1到30人)

第二行:为N个分数 (整数),用空格隔开

第三行:计算前K名分数的人数K

1
2
3
10
93 85 77 68 59 100 43 94 75 82
4

输出格式:输出前K名同学的分数平均数,四舍五入保留两位小数

1
93.00

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <algorithm>
using namespace std; //用greater排序要加这行
int score[31];
int main() {
int N, K, sum;
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d", &score[i]);
}
scanf("%d", &K);
sort(score, score+N, greater<int>());
sum = 0;
for(int i=0; i<K; i++){
sum += score[i];
}
printf("%.2f\n", 1.0*sum/K); //注意输出格式,保留两位小数
return 0;
}

[大题]例2-分数段统计[*]

老师想进行班级名次排序和各分数段的人数统计工作。

要求将N名同学的考试成绩放在A数组中,各分数段的人数放在B数组中:成绩为100的人数存到b[1]中,成绩90到99的人数存在b[2]中,成绩80到89的人数存在b[3]中,成绩70到79的人数存到b[4]中,成绩60到69的人数存在b[5]中,成绩60以下的人数存在b[6]中。

输入格式:共两行

第一行:班级人数N (1到30)

第二行:N个分数(整数),用空格隔开

1
2
10
93 85 77 68 59 100 43 94 75 82

输出格式:若干行

前N行:每行一个整数,为从高到低排序的分数

最后一行:各个分数段人数,即按顺序输出b数组

1
2
3
4
5
6
7
8
9
10
11
100
94
93
85
82
77
75
68
59
43
1 2 2 2 1 2

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
using namespace std; //用greater排序要加这行
int score[31];
int b[7];
int main() {
int N;
scanf("%d",&N);
for(int i=0; i<N; i++){
scanf("%d",&score[i]);
}
//排序
sort(score,score+N,greater<int>());
//输出N行排序后的分数
for(int i=0; i<N; i++){
printf("%d\n",score[i]);
}
for(int i=0; i<N; i++){
if(score[i] == 100){
b[1]++;
}else if(score[i] >= 90){
b[2]++;
}else if(score[i] >= 80){
b[3]++;
}else if(score[i] >= 70){
b[4]++;
}else if(score[i] >= 60){
b[5]++;
}else{
b[6]++;
}
}
//输出各分数段人数
for(int i=1; i<=6; i++){
//注意输出的空格,最后一个不输出空格
if(i != 6){
printf("%d ",b[i]);
}else{
printf("%d", b[i]);
}
}
return 0;
}
/*此题考查sort中内置的greater排序方法,较简单*/

[大题]例3-自定义排序方法[*]

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std; //用greater排序要加这行
bool cmp(int x, int y){
return x>y; //注意不要用≥,会造成一些错误
}
int main() {
int arr[10];
for(int i=0;i<10;i++){
cin >> arr[i];
}
sort(arr, arr+10, cmp); //传入自定义排序cmp方法
for(int i=0; i<10; i++){
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
/*自己实现了一个greater排序方法*/

[大题]例4-整数的余数排序[*]

现有N个正整数,均小于10000。现在需要将这些正整数按照除以3的余数从小到大排序。即除以3余0的数排在除以3余1的数前面,如果余数相等则按照正整数值从小到大排序。

输入格式为两行

第一行:一共整数的个数N 0<N<101

第二行:用空格隔开的N个正整数,均小于10000

输出格式

一行,按题目要求排序后的N个正整数,用空格隔开

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<algorithm>
using namespace std;
int num[105];
bool cmp(int x, int y){ //自定义排序函数
if(x % 3 != y % 3){
return x % 3 > y % 3;
}else{
return x < y;
}
}
int main(){
int N;
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d",&num[i]);
}
sort(num, num+N; cmp);
for(int i=0; i<N; i++){
if(i != N-1){
printf("%d ", num[i]);
}else{
printf("%d\n", num[i]); //注意最后一个元素不要输出空格
}
}
}
/*学会写自定义的排序函数会让此题变得十分简单*/

[大题]例5-结构体排序说明[*]

假设我们要以结构体保存学生名字与4科分数,我们怎么按名字排序(长短),又怎么按4科分数依次排序呢?

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

struct Student{
string name;
int score[4];
};

//实际上我们可以定义多个比较方法,需要时再去调用
bool cmp_name(Student x, Student y){
return x.name < y.name;
}

bool cmp_score(Student x, Student y){
if(x.score[0]!=y.score[0]){
return x.score[0] > y.score[0];
}
if(x.score[1]!=y.score[1]){
return x.score[1] > y.score[1];
}
if(x.score[2]!=y.score[2]){
return x.score[2] > y.score[2];
}
if(x.score[3]!=y.score[3]){
return x.score[3] > y.score[3];
}
}
int main() {
Student stu[3];
for(int i=0; i<3; i++){
cin >> stu[i].name;
for(int j=0; j<4; j++){
cin >> stu[i].score[j];
}
}
sort(stu, stu+3, cmp_score);
for(int i=0; i<3; i++){
cout << stu[i].name << ": ";
for(int j=0; j<4; j++){
cout << stu[i].score[j] << " ";
}
cout << endl;
}

return 0;
}

[大题]例6-排序评奖-结构体[**]

假设所在班级有N名同学,期末考试进行了语数英、体育四门课程考试,班主任要将这N名学生中总分前3名定为本学期的 ”学习标兵“。现给出这N名学生的姓名和各科成绩,请你编程找到总分前三名,并依次输出他们的姓名,所给数据不会出现总分相同情况。

输入格式

输入包含N+1行,第一行有一个正整数N表示班级人数 (3到40人),接下来N行为每个学生的考试信息,依次为:姓名、数学成绩、语文成绩、英语成绩和体育成绩,用空格隔开。注意姓名都用小写字母(不超过10个),成绩为不超过200的非负整数。

1
2
3
4
5
4
jing 98 90 87 74
ming 96 92 85 97
jun 95 78 56 91
hong 95 100 85 78

输出格式

输出包含三行,分别是第一名到第三名同学的名字

1
2
3
ming
hong
jing

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>
using namespace std;

struct Student{
char name[15];
int score[4];
};

bool cmp(Student x, Student y){
int sumx = x.score[0] + x.score[1] +x.score[2] +x.score[3];
int sumy = y.score[0] + y.score[1] +y.score[2] +y.score[3];
return sumx > sumy;
}

Student stu[45];
int main(){
int N;
scanf("%d",&N);
for(int i=0; i<N; i++){
scanf("%s", stu[i].name);
for(int j=0; j<4; j++){
scanf("%d", &stu[i].score[j]);
}
}
sort(stu, stu+N, cmp);
for(int i=0; i<3; i++){
printf("%s\n",stu[i].name);
}
return 0;
}
/*此题主要考察结构体的定义及sort排序方法*/

注意:班级排序的若要按姓名排序,使用strcmp(a,b)<0即可,这个函数返回值意义是若a排在前面,则返回一个差值,这个差值小于0

[大题]例7-浮点数排序[**]

假设有N个正浮点数,均小于10000.0,现在需要将这些浮点数按照距离它最近的整数的差从小到大排序。浮点数与距离最近的整数的差越小,这个浮点数排位便越靠前,若差相等,按照浮点数值从小到大排序。

判断浮点数相等使用如下语句

1
2
3
if(fabs(a-b) < EPSILON){
//执行两个浮点数相等时的操作,其中EPSLION为常量=10^-6
}

输入格式

一共两行,第一行为一个整数N (0到100)

第二行为空格隔开的N个正浮点数

1
2
9
1.001 2.1 3.2 4.0001 5.000001 6.9 7.2 8.001 9.0

输出格式

输出一行,为按题目要求排序后的N个正浮点数,四舍五入保留6位小数,按空格隔开。

1
9.000000 5.000001 4.000100 1.001000 8.001000 2.100000 6.900000 3.200000 7.200000

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPSLION = 1e-6;
double num[105];

bool cmp(double a, double b){
double da = fabs(a - round(a)); //round函数为四舍五入浮点数
double db = fabs(b - round(b)); //fabs函数为求绝对值
if(fabs(da-db) < EPSLION){
return a < b;
}
return da < db;
}
int main(){
int N;
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%lf", &num[i]);
}
sort(num, num+N, cmp);
for(int i=0; i<N; i++){
if(i!=N-1){
printf("%lf ", num[i]);//不指定保留几位默认6位
}else{
printf("%lf\n", num[i]);
}
}
return 0;
}

/*此题除了考查sort排序,还考察了math模块下的fabs和round函数*/
//顺便说下C++中快速四舍五入保留n位有效数字的方法
cout<<setiosflags(ios::fixed)<<setprecision(1); //四舍五入保留1位
cout << 2.56; //输出结果为2.6

[大题]例8-分数线[**]

某学校举办了一场计算机竞赛选拔赛,现在大家的成绩已经出来了。老师需要确定决赛名单。

为了鼓励大家,老师希望获奖人数不少于参赛总人数的一半,因此老师需要确定一个获奖分数线,在分数线及以上的同学可以获奖,除此之外,分数线越高越好。

输入格式:

第一行:一个整数n,表示参赛总人数(0到10000)

第二行:n个参赛同学的分数(整数),用空格隔开

1
2
7
76 71 42 4 27 27 20

输出格式:

输出一行,包括两个整数,分别为分数线和获奖人数,用空格隔开

1
27 5

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>
using namespace std;

int score[10001];
int main(){

int n;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d",&score[i]);
}
sort(score,score+n, greater<int>());
printf("%d ",score[(n-1)/2]); //找中位数

int cnt = 0;
for(int i=0; i<n; i++){
if(score[i] >= score[(n-1)/2]){
cnt++;
}else{
break;
}
}
printf("%d\n", cnt);
return 0;
}
/*此题考查基本的sort方法,求中位数的方法*/

[大题]例9-红绿蓝珠子[**]

有一个罐子,里面装着红、绿、蓝色的玻璃珠若干,分别用R G B表示。现希望把他们排成一行,按照字典顺序排列(B->G->R),然后以一红二绿三蓝为一组串成一串幸运珠,多余的放回罐子中,那么能串多少串幸运珠呢?

输入格式

输入为一行,由若干个R G B乱序组成的字符串,长度小于10000,每个字母至少出现一次

1
RGGBBB

输出格式

第一行:排序完成后的字符串

第二行:一个整数,为串成的幸运珠条数

1
2
BBBGGR
1

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[10005];
int main(){
int len, r, g, b;
scanf("%s",&s);
len = strlen(s);
sort(s, s+len);
printf("%s\n", s);
r = 0;
g = 0;
b = 0;

for(int i=0; i<len; i++){
if(s[i] == 'R'){
r++;
}else if(s[i] == 'G'){
g++;
}else{
b++;
}
}
printf("%d\n", min(r, min(g/2, b/3))); //巧妙运用min函数
return 0;
}
/*除了考查排序外,还考察了组合问题,实际上是求珠子的限制量(最小值)*/

[大题]例10-整数排序进阶[**]

有N个正整数均小于10000,现在要将这些正整数每一位数字相加的和从小到大排序。若各位相加相等,则按正整数值从小到大排序。

输入格式:

第一行为一个整数N (0<N<101)

第二行为用空格隔开的N个正整数

1
2
4
20 12 1 11

输出格式:

一行,为排序后N个正整数,用空格隔开

1
1 11 20 12

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <algorithm>
using namespace std;
int num[105];
bool cmp(int a, int b){
int suma=0,sumb=0;
int tempa = a, tempb = b;
while(a){
suma += a%10;
a/=10;
}
while(b){
sumb += b%10;
b/=10;
}
if(suma==sumb){
return tempa<tempb;
}
return suma<sumb;
}
int main(){
int N;
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d", &num[i]);
}
sort(num, num+N, cmp);
for(int i=0; i<N; i++){
if(i!=N-1){
printf("%d ",num[i]);
}else{
printf("%d",num[i]);
}
}
return 0;
}
/*此题考查取位数的方法,即一个数对10取余,再除以10的反复循环*/

[大题]例11-抢气球[***]

小朋友下课在抢气球,每个气球在墙壁上有一定高度,当小朋友跳起来时,手能够到的高度要大于等于气球的高度才能摘下气球。为了公平,老师让跳的低的小朋友先跳。小朋友贪心,会把跳起来能摘到的气球全摘了。

很巧的是,每个小朋友跳起来手能够到的高度不一样。

输入格式:

第一行输入两个空格分隔的整数n,m(1≤n, m≤1000) ,n表示小朋友的数量,m表示气球的数量。

第二行输入n个正整数,用空格隔开,第i个数表示第i个小朋友能跳起来够着的高度ai(1≤ai≤10^5)

第三行输入m个正整数,用空格隔开,第i个数hi表示气球的高度(1≤hi≤10^5)

1
2
3
5 6
3 7 9 6 4
1 2 3 4 5 6

输出格式:

一共n行,每行一个整数,第i行表示第i个小朋友获得气球的数量

1
2
3
4
5
3
0
0
2
1

参考代码 算法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <algorithm>
using namespace std;
struct Children{
int a; //能够到的高度
int id; //编号
};
bool cmp(Children x, Children y){
return x.a < y.a;
}

int ans[1005]; //存输出结果,小朋友摘了几个
int h[1005]; //存气球高度
bool used[1005]; //用来标记气球是否被摘
Children child[1005];
int main(){

int n, m;
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++){
scanf("%d",&child[i].a);
child[i].id=i;
}
for(int i=0; i<m; i++){
scanf("%d",&h[i]);
}
sort(child, child+n, cmp);
//摘气球
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!used[j] && h[j]<=child[i].a){
ans[child[i].id]++;
used[j] = true;
}
}
}

for(int i=0; i<n; i++){
printf("%d\n",ans[i]);
}
return 0;
}

参考代码 算法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <algorithm>
using namespace std;
struct Children{
int a; //能够到的高度
int id; //编号
};
bool cmp(Children x, Children y){
return x.a < y.a;
}

int ans[1005]; //存输出结果,小朋友摘了几个
int h[1005]; //存气球高度
Children child[1005];
int main(){

int n, m, p;
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++){
scanf("%d",&child[i].a);
child[i].id=i;
}
for(int i=0; i<m; i++){
scanf("%d",&h[i]);
}
sort(child, child+n, cmp);
sort(h, h+m);
p=0;
//摘气球
for(int i=0; i<n; i++){
while(p<m && h[p]<=child[i].a){
ans[child[i].id]++;
p++;
}
}

for(int i=0; i<n; i++){
printf("%d\n",ans[i]);
}
return 0;
}
/*注意此题要按小朋友编号输出,不是从矮到高排序输出*/

聪明的你想一想,上面两个算法哪个时间复杂度更低?

四.快速提升代码能力题解

  • 注意代码风格(缩进、空格、换行)

  • 来看看一些特别的题目吧~

例1-a+b问题

输入两个整数a,b,输出两个整数的和

输入格式:

第一行输入一个整数T,表示要计算的次数

接下来T行每行输入两个用空格隔开的整数a,b

1
2
3
4
5
6
5
1 2
3 4
5 6
7 8
9 10

输出格式

对于每次输入a,b,输出a+b的值,结果保证在32位整形(int)范围内

1
2
3
4
5
3
7
11
15
19

竞赛技巧:这里可以边读入边输出,不用连续读入再连续输出

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main(){
int T, a, b;
cin >> T;
for(int i=1; i<=T; i++){
cin >> a >> b;
cout<< a+b <<endl;
}
return 0;
}
/*小提示:cout和cin效率没有printf和scanf高,在处理大量数据的情况下要优先选择c语言*/

例2-斐波那契数列

相信大家学过斐波那契数列,它是1,1,2,3,5,8,13,21…

用fn表示斐波那契数列第n项,则f1=f2=1,fn=fn-1+fn-2(n>2)

输入一个n,求fn对(10^9+7)取模的结果

输入格式

输入一个整数n(1≤n≤100000)

1
3

输出格式

输出fn mod 1000000007的值

1
2

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int mod =1e9+7;
int f[10005];
int main(){
int n;
cin >> n;
f[1] = 1;
f[2] = 1;
for(int i=3; i<=n; i++){
f[i] = (f[i-1] + f[i-2])%mod;
}
cout << f[n] << endl;
return 0;
}
/*这里采用了斐波那契数列的性质:后一个数对某个数取模等于 前两个数取模的结果相加 再对某个数取模,切勿将斐波那契数列一项项算出来,那样肯定超时间和空间*/

例3-矩阵旋转

给出一个n*m的整数矩阵,请你把这个矩阵顺时针旋转90°后输出

输入格式

第一行输入两个整数n, m (1≤n, m≤200),用空格隔开

接下来n行,每行输入m个整数,表示输入的矩阵,矩阵中元素都是int范围整数

1
2
3
4
3 4
-1 3 6 3
7 7 9 1
10 3 4 6

输出格式

输出m行,每行n个空格隔开的整数,表示旋转后的矩阵。行末不要输出多余的空格。

1
2
3
4
10 7 -1
3 7 3
4 9 6
6 1 3

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int num[205][205];
int main(){
int n, m;
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0;j<m;j++){
cin >> num[i][j];
}
}
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(j!=n-1){
cout << num[n-1-j][i] << " ";
}else{
cout << num[n-1-j][i] << endl;
}
}
}
return 0;
}
/*将矩阵旋转90°,仔细观察可得到过程*/

例4-最大子阵

给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中元素的和最大。其中,A的子矩阵指在A中行和列均连续的一部分。

输入格式

输入第一行包括两个整数n,m(1≤n,m≤50),分别表示矩阵A的行数与列数

接下来n行每行m个整数,表示矩阵Aij (-1000≤Aij≤1000)

1
2
3
4
3 3
2 -4 1
-1 2 1
4 -2 2

输出格式

输出一行,包含一个整数,为A中最大子矩阵的元素和

1
6

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
int A[55][55];
int main(){
int n, m, ans;
cin >> n >> m;
ans = -1005;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> A[i][j];
}
}

for(int i=0; i<n; i++){
for(int j=i;j<n;j++){
for(int k=0;k<m;k++){
for(int l =k; l<m; l++){
int temp = 0;
for(int p = i;p <= j; p++){
for(int q=k; q<=l; q++){
temp+=A[p][q];
}
}
if(temp > ans){
ans = temp;
}
}
}
}
}
cout << ans << endl;
return 0;
}
/*不推荐这种最暴力的方法,后续动态规划会有讲到*/

例5-去重与排序随机数

n (1≤ n ≤ 1000 )个1到1000的随机整数,对于其中重复的数字,只保留一个,把其余相同的数去掉。然后再把这些数从小到大排序。

输入格式

第一行为一个正整数n

第二行有n个用空格隔开的正整数

1
2
10
20 40 32 67 40 20 89 300 400 15

输出格式

第一行输出一个整数m,表示不相同随机数的个数

第二行输出m个用空格隔开的正整数,为排序好的

1
2
8
15 20 32 40 67 89 300 400

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
using namespace std;
int num[105], ans[105];
int main(){
int n;
cin >> n;
for(int i=0; i<n; i++){
cin >> num[i];
}
sort(num, num+n);
int m =0;
//去重
for(int i=0; i<n; i++){
if(i!=0 && num[i] != num[i-1]){
ans[m++] = num[i-1];
}
}
//注意最后一位数不要漏掉
ans[m++] = num[n-1];
cout << m << endl;
for(int i=0; i<m; i++){
if(i != m-1){
cout << ans[i] <<" ";
}else{
cout << ans[i] << endl;
}
}
return 0;
}
/*此题注意去重时最后一个数的判断不要漏掉*/

例5-进制转换

输入一个十进制数N,将他转换为R进制数输出。在10≤R≤16的情况下,分别用ABCDEF表示。

输入格式

输入包含两个整数N(N<10000)和R(2≤R≤16)。注意N可能是负整数。

1
23 12

输出格式

输出一行,表示转换后的数字

1
18

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
char ans[105];
int main(){
int N, R, m=0, now;
cin >> N >> R;
if(N<0){
cout << "-";
N = -N;
}
while(N){
now = N % R;
if(now<=9){
ans[m++] = '0' + now;
}else{
ans[m++] = 'A' + now - 10;
}
N /= R;
}
if(m==0){
cout << 0;
}
for (int i= m -1; i>=0; i--){ //倒序输出
cout << ans[i];
}
cout << endl;
return 0;
}
/*此题考查进制数转换过程,在数据结构的栈应用中有讲解*/

例6-回文数

一个正整数,若交换高低位以后和原数相等,那么称这个数为回文数。比如121,2332是回文数,而13,4567不是。

任意一个正整数,若其不是回文数,将该数交换高低位后和原数相加得到一个新的数。如果新数不是回文数,重复这个变换,直到得到一个回文数为止。例如,57变换后得到132 (57+75),132得到363 (132+231),361为回文数。

曾有数学家猜想:对于任意正整数,经过有限次上述变换后一定能得出一个回文数。

输入格式

第一行输入一个整数n

1
349

输出格式

第一行输出一个正整数,表示得到回文数的最少变换次数。接下来一行输出变换过程,用”—>”连接。保证最后生成的数在int范围内。

1
2
3
349--->1292--->4213--->7337

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
int num[1005];
int digit[1005];
bool judge(int x){
int cnt=0;
while(x){
digit[cnt++] = x%10;
x/=10;
}
for(int i=0; i<cnt/2;i++){
if(digit[i]!=digit[cnt-1-i])
return false;
}
return true;
}
int rev(int x){
int ret = 0;
while(x){
ret = ret*10+x%10;
x/=10;
}
return ret;
}

int main() {
int n, m=0;
cin >> n;
num[m++] = n;
while(!judge(n)){
n += rev(n);
num[m++] = n;
}

cout << m-1 << endl;
for(int i=0; i<m; i++){
if(i!=m-1){
cout << num[i] << "--->";
} else{
cout << num[i] <<endl;
}
}
return 0;
}
/*此题考查数的反转、位数比较等知识点*/

例7-机器人

你在生日时收到了一份礼物,是一个智能机器人。这个机器人有四个指令:

1.forward x,前进x米

2.back x,先向后转,然后前进x米

3.left x,先向左转,然后前进x米

4.right x,先向右转,然后前进x米

现在把机器人放在坐标轴原点,起始朝向为x轴正方向。经过一系列指令后,你能计算出它的位置吗。坐标轴上一个单位长度为一1。

输入格式

第一行输入一个整数n(1≤n≤100)表示指令的个数。

接下来n行每行输入上面的指令,其中-1000≤x≤1000

1
2
3
4
5
6
7
8
9
10
11
10
back -9
left 3
left 8
back 15
right 10
right -7
right -3
left 11
right 17
left 3

输出格式

输出两个整数x,y表示机器人的最后坐标,用空格隔开。

1
9 -7

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
int dx[4] = {0,-1,0,1}; //坐标系上左下右
int dy[4]={1,0,-1,0};
char op[15];
int main(){
int n, d = 3,x,nowx,nowy; //d为当前方向,即对应上面数组的右方向
cin >> n;
nowx = 0;
nowy = 0;
for(int i=0; i<n; i++){
cin >> op >> x;
if(op[0]=='b'){ //技巧:四个方向首字母不一样,可以此作为判断
d = (d+2)%4;
}else if(op[0]== 'l'){
d = (d+1)%4;
}else if(op[0] == 'r'){
d = (d+3)%4;
}
nowx += dx[d] * x;
nowy += dy[d] * x;
}
cout << nowx << " " << nowy <<endl;
return 0;
}
/*此题考查数组和坐标系的结合应用,要注意机器人的当前方向*/

五.枚举算法

  • 能用枚举法解决的问题往往是最简单的一类题目,有以下共同特点
    • 解枚举的范围是有穷的
    • 检验条件是确定的

例1-找回文数字

观察数字:12321、123321都有个共同特点:无论从左往右还是从右往左读都是相同的,这样的数字叫回文数字。现在要从5位或6位十进制数字中找出各位数字之和等于n的回文数字。

输入格式

输入一个整数n (10≤n≤100)

1
50

输出格式

输出所有各个数之和等于n的5位和6位整数,每个数字一行,从小到大排序输出。若没有满足条件的数字输出-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
799997
889979
889988
898889
898898
899969
899996
979979
988889
989969
989987
997799
998879
998897
999959
999995

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
int n;
int digit[6];
bool judge(int x){
int m = 0, sum = 0;
while(x){
digit[m++] = x%10;
sum += x%10;
x /= 10;
}
if(sum!=n){
return false;
}
for(int i; i< m/2; i++){
if(digit[i]!=digit[m-1-i]){
return false;
}
}
return true;
}
int main() {
cin >> n;
bool f = false;
for(int i=10000; i<1000000; i++){
if(judge(i)){
cout << i << endl;
f = true;
}
}
if(!f){
cout << -1 << endl;
}
return 0;
}
/*此题考查回文数的判断,较简单*/

例2-生日蜡烛

某人从某年开始每年举办一次生日Party,并且每次都要吹灭与他年龄数相同的根数的蜡烛。到现在他一共吹灭了236根蜡烛,那么他是几岁开始过生日Party的呢?假设这个人年龄不可能超过200岁。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int main(){
for(int i=1; i<=200; i++){
int can = 0, j = i; //can为吹的蜡烛总数
while(can < 236 && j< 200){
can += j;
j++;
}
if(can == 236){
cout << i << endl;
}
}

return 0;
}
/*在不能确定循环次数的情况下,优先使用while循环*/

例3-奖券数目

有人很迷信数字,比如带4的数字不吉利。某抽奖活动的奖券号码是5位数(10000~99999),要求其中不带4的号码。主办方请你计算下,如果发行号码n到m之间的奖券,在任何两张奖券不重复的情况下,可发行多少张?

输入格式

输入一行,为空格隔开的两个整数n,m (10000≤n<m≤99999)

1
10000 99999

输出格式

输出一个整数,为可发出奖券的数目

1
52488

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
bool judge(int x){
while(x){
if(x%10==4){
return true;
}
x/=10;
}
return false;
}
int main(){
int n,m, cnt = 0;
cin >> n >> m;
for(int i=n; i<=m; i++){
if(!judge(i)){ //返回true代表有4
cnt++;
}
}
cout << cnt << endl;
return 0;
}
/*此题考查数字的拆分,较简单*/

六.常用STL(Standard Library)

vector数组

  • 假设想开一个数组,但是不确定长度,可以使用vector动态数组

  • 引用库

    1
    2
    3
    4
    5
    #include <vector>
    using namespace std;
    int main(){
    return 0;
    }
  • 构建动态数组:

    1
    2
    //其中a为数组名,T为类型名称,可以说int float double等等
    vector<T> a;
  • 插入元素(数组尾部)

    1
    2
    3
    4
    5
    6
    7
    8
    #include <vector>
    using namespace std;
    int main(){
    vector<int> vec;
    vec.push_back(1); //[1]
    vec.push_back(2); //[2]
    return 0;
    }
  • 获取长度

    1
    vec.size();
  • 访问元素和赋值方法与普通数组一样

  • 删除元素(最后一个元素)

    1
    vec.pop_back();
  • 清空并释放内存

    1
    2
    3
    //也可用clear方法,但这不会清空数组占用内存
    //vector<int> vec;
    vector<int>().swap(vec);
  • vector还可以存储自定义结构体

  • vector的构造函数快速初始化

    1
    vector<int> vec(n,1);	//第一个参数为初始化数组长度,第二个参数代表初始化数组值为1,不填默认为0
  • 用vector构造二维数组

    1
    2
    3
    vector<vector<int>> vec2;
    //构造一个n行m列二维数组,并全部初始化为0
    vector<vector<int>> vec2(n, vector<int>(m,0));
  • 下面试着打印一个以下效果的乘法口诀表试试吧!

    1
    2
    3
    4
    5
    1*1=1	
    2*1=2 2*2=4
    3*1=3 3*2=6 3*3=9
    4*1=4 4*2=8 4*3=12 4*4=16
    5*1=5 5*2=10 5*3=15 5*4=20 5*5=25

    参考代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include <iostream>
    #include <vector>
    using namespace std;

    int main() {
    vector<vector<int>> v2d;
    for(int i=0; i<5; i++){
    v2d.push_back(vector<int>());
    }
    for(int i=0;i<v2d.size();i++){
    for(int j=0; j<=i; j++){
    v2d[i].push_back((i+1)*(j+1));
    }
    }
    for(int i=0; i<v2d.size();i++){
    for(int j=0; j<v2d[i].size(); j++){
    cout << i+1 << "*" << j+1<< "=" << v2d[i][j] << "\t";
    }
    cout << endl;
    }
    return 0;
    }

集合-set

集合是由不重复的数据构成的,例如{1,2,3}

C++中常用的是set

1
2
3
4
#include <set>
using namespace std;

set<T> s;
  • 插入元素 时间复杂度o(logn)

    1
    2
    3
    4
    set<string> country;
    country.insert("China"); //{"China"}
    country.insert("America"); //{"China","America"}
    //再次插入相同的元素不会被插入
  • 删除元素 时间复杂度o(logn)

    1
    2
    country.erase("America");	//{"China"}
    //删除不存在的元素不会报错,不会执行任何操作
  • 判断元素是否存在 时间复杂度o(logn)

    1
    2
    country.count("China");
    //若存在返回1,否则返回0
  • 使用迭代器访问元素

    1
    2
    3
    4
    for(set<string>::iterator it = country.begin(); it!=country.end(); it++){
    cout << *it <<endl;
    }
    //C++中遍历set是从小到大遍历,即排序好了
  • 获取元素个数 o(1)

    1
    country.size();
  • 清空 o(n)

    1
    country.clear();
  • 用set存储结构体,需要重载运算符 <

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct Node{
    int x, y; //若x一致,比较y
    bool operator<(const Node &rhs) const{
    if(x == a.x){
    return y < rhs.y;
    }else{
    return x < rhs.x;
    }
    }
    };

    set保存结构体并输出-参考代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #include <iostream>
    #include <set>
    using namespace std;
    struct Point{
    int x, y;
    bool operator <(const Point &rhs) const {
    if(x == rhs.x){
    return y < rhs.y;
    }else{
    return x < rhs.x;
    }
    }
    };


    int main(){
    int n=2;
    set<Point> p;
    //插入结构体
    for(int i=0; i<n; i++){
    Point temp;
    cin >> temp.x >> temp.y;
    p.insert(temp);
    }
    //输出结构体
    for(set<Point>::iterator it = p.begin(); it != p.end(); it++){
    cout << it -> x << " " << it -> y<<endl;
    }

    }

集合-map

结构为key-value,且key唯一

1
2
#include <map>
using namespace std;
  • 构造一个映射

    1
    2
    map<T1,T2> m;
    //这样就定义了一个名为m的从T1到T2类型映射
  • 插入映射 o(logn)

    1
    2
    3
    map<string, int> dict;
    dict.insert(make_pair("Banana",1));
    //若key已存在,不会插入新的value
  • 访问映射

    1
    2
    3
    dict["Banana"];		//这样可以获得1
    //若访问一个不存在的key,会自动生成映射,value默认值为0或空字符串(取决于value类型)
    dict["Banana"] = 2; //更改value
  • 判断key是否存在 o(logn)

    1
    2
    dict.count("Banana");
    //存在返回1,否则返回0
  • 迭代器访问map

    1
    2
    3
    4
    for(map<string,int>::iterator it = dict.begin(); it != dict.end(); it++){
    cout << it->first << "->" << it->second <<endl; //first是key,second是value
    }
    //按照key从小到大遍历
  • 清空map o(n)

    1
    dict.clear();

    参考代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #include <iostream>
    #include <map>
    using namespace std;
    int main(){
    map <string, int> dict; //声明map
    dict["Tom"] = 1; //访问并赋值
    dict["Mary"] = 2;
    dict["Hlo"] = 3;

    if(dict.count("Mary")){
    cout << "Mary id is" << dict["Mary"] << endl;
    dict["Mary"] = 10;
    }

    for(map<string,int>::iterator it = dict.begin(); it != dict.end(); it++){
    cout << it->first << "->" << it->second << endl;
    }

    dict.clear();
    return 0;
    }

    //输出结果(可以看到是排序后输出):
    Mary id is2
    Hlo->3
    Mary->10
    Tom->1

综合例题

例1-打印锯齿矩阵

锯齿矩阵是指每一行包含的元素个数不相同的矩阵,例如

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

现读入若干整数(x,y)表示在第x行的末尾上加上一个元素y。输出最终的锯齿数组,初始时矩阵为空。

输入格式

第一行输入两个整数n,m(1≤n, m≤10000),其中n表示锯齿数组行数,m表示插入元素总数。

接下来一共m行,每行两个整数x,y(1≤x≤n,0≤y≤10000),表示在第x行的末尾插入一个元素y。

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

输出格式

一共输出n行,每行若干个用空格分隔的整数。如果某行没有任何元素,输出一个空行。

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;
vector<int> mat[10005]; //定义vector
int main(){
int n, m, x, y;
cin >> n >> m;
for(int i=0;i<m;i++){
cin >> x >> y;
mat[x].push_back(y);
}
for(int i=1; i<=n ;i++){
for(int j=0; j< mat[i].size(); j++){
if(j!=mat[i].size()-1){
cout << mat[i][j] << " ";
}else{
cout << mat[i][j] << endl;
}
}
cout << endl; //注意空行
}
return 0;
}
/*此题考查动态数组的定义,用vector会使这种题变得很简单*/

例2-福尔摩斯破案

最近某地连续发生了多起盗窃案件,根据监控和路人提供的线索得知,这是-一个犯罪团伙。并且还知道这个犯罪团伙中每个人的身高、体重、年龄。警察想知道这个犯罪团伙中的每个人是不是本市的(如果本市有这个特征的人就视为是本市的)。但本市人口太多,又不能一个一个排查。警察又急需来帮忙解决这个棘手的问题。

输入格式
第一行将会输入两个数字n (1≤n≤2*10^5) 和 m (1≤m≤10^4)。 n代表本市的人口数目,m代表犯罪团伙的数量。
后面n行每行有3个数字代表本市每个人的身高、体重、年龄。然后会有m行每行有3个数字,代表犯罪团伙每个人的身高、体重、年龄。

1
2
3
4
5
6
3 2
166 50 30
178 60 23
132 40 15
167 50 30
178 60 23

输出格式

输出m行,每行输出一个”yes”或”no”,分别代表罪犯是本市的和不是本市的。

1
2
no
yes

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <set>
using namespace std;
struct people{
int h;
int w;
int age;
people(int _h, int _w, int _age){ //重写一个构造函数,方便后面传值
h = _h;
w = _w;
age = _age;
}
bool operator<(const people &rhs) const{ //用set之前随意重写排序方法
if(h!=rhs.h){
return h < rhs.h;
}
if(w!=rhs.w){
return w < rhs.w;
}
return age < rhs.age;
}
};
set<people> s;
int main(){
int n,m,h,w,age;
cin >> n >> m;
for(int i=0; i<n; i++){
cin >> h >> w >> age;
s.insert(people(h,w,age));
}
for(int i=0;i<m;i++){
cin >> h >> w >> age;
if(s.count(people(h,w,age))){
cout << "yes" << endl;
}else{
cout << "no" << endl;
}
}
}
/*此题考查set集合与运算符重载,若不重载运算符存结构体时set无法排序会报错*/

例3-藏书计算

小明有个学霸同学,家中藏书真可谓汗牛充栋。小明想考一考学霸,给学霸出了-道难题。小明问这么多书籍,到底有多少本不一样的书,每样书的名字是什么? (因为有的书名是一样的,所以我们把它们视为同样的书) 学霸就是学霸,张口就说出了答案。不知道你是否也是学霸? 一起来挑战下?

输入格式

第一行是书籍总量 n(1≤n≤10^6)

然后有n行书名(书名是一个英文字符串,字符串的长度小于100,中间没有空格)。

1
2
3
4
5
4
English
Math
Chinese
Chinese

输出格式

第一行是不同书籍的数量

然后按照书名的字典序输出书名和数量。

1
2
3
4
3
Chinese 2
English 1
Math 1

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <map>
#include <string>
using namespace std;
map <string, int> book;
int main(){
int n;
string name;
cin >> n;
for(int i=0; i<n; i++){
cin >> name;
book[name]++; //若key不存在默认生成value为0,然后++添加数量
}
cout << book.size() << endl;
for(map<string, int>::iterator it = book.begin(); it!=book.end(); it++){
cout << it->first << " " << it->second << endl;
}
return 0;
}

由于题目给的n在六次方内,一般大于五次方的话用cout和cin效率较低,容易超时,下面用scanf和printf再写一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <map>
#include <string>
using namespace std;
map <string, int> book;
char name[105]; //创建一个数组来读取书名
int main(){
int n;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%s", name);
book[name]++; //若key不存在默认生成value为0,然后++添加数量
}
printf("%d\n", book.size());
for(map<string, int>::iterator it = book.begin(); it!=book.end(); it++){
printf("%s %d\n",(it->first).c_str(), it->second); //注意c_str用法
}
return 0;
}
/*此题考查map集合的使用方法,并且要注意由于数据量过大的时间超限问题*/

例4-堆积木

小明有n块积木,编号分别为1到n,一开始,小明把第i块积木放在位置i。小明进行m次操作,每次操作小明都把位置b上的积木整体移动到位置a上面。比如1位置的积木是1,2位置的积木是2,那么把位置2的积木移动到位置1后,位置1上的积木从下到上依次为1,2。

输入格式

第一行输入两个整数n, m(1≤n≤10000,0≤m≤10000)

接下来m行,每行输入两个整数a,b(1≤a, b≤n),如果a,b相等则本次不需要移动

1
2
3
4
5
4 4
3 1
4 3
2 4
2 2

输出格式

输出n行,第i行输出位置i从下到上的积木编号

1
2
3
4

2 4 3 1


参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <vector>
using namespace std;
vector<int> v[10005];
int main(){
int n, m, a, b;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
v[i].push_back(i);
}
for(int i=0; i<m; i++) {
scanf("%d%d", &a, &b);
if (a == b) {
continue;
}
for (int j = 0; j < v[b].size(); j++) {
v[a].push_back(v[b][j]);
}
vector<int>().swap(v[b]); //清空内存,防止爆栈
}

for(int i=1; i<=n; i++){
for(int j=0; j<v[i].size(); j++){
if(j!=v[i].size()-1){
printf("%d ",v[i][j]);
}else{
printf("%d",v[i][j]);
}
}
printf("\n"); //注意换行要放这里,若行为空也一样会输出空行
}
return 0;
}

例5-计算集合的并

给你两个集合,计算其并集,即{A}+{B}

输入格式

第一行输入两个数字n, m(0<n, m≤10000),分别表示集合A和集合B的元素个数

后两行分别表示集合A和集合B的元素(int),每个元素之间用一个空格隔开

1
2
3
1 2
1
1 2

输出格式

输出一行元素,表示合并后的集合,要求从小到大输出,元素之间用一个空格隔开

1
1 2

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <set>
using namespace std;
set<int> s;
int main(){
int n, m, x, cnt=0;
scanf("%d%d",&n,&m);
for(int i=0; i<n+m; i++){
scanf("%d", &x);
s.insert(x);
}
for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
if(cnt!=s.size()-1){
printf("%d ", *it);
cnt++;
}else{
printf("%d\n", *it);
}
}
return 0;
}
/*此题考查set集合与迭代器的使用,较简单*/

例6-小明学英语

小明快要考六级了,这几天他每天早上都起来背单词。小红喜欢时不时考一考小明:小红问小明一个单词,如果小明背过这个单词,他会把这个单词的意思告诉小红,否则会跟小红说还没背过。单词是由连续的大写或小写字母组成,但是不区分大小写。比如Love和love是同一个单词。

输入格式

首先输入一个n(1≤n≤10000)表示事件数。接下来n行每行表示一个事件。每个事件输入一个整数d和一个单词word(长度不大于20),用空格隔开。如果d=0,表示小明记住了这个单词,如果d=1,表示这是一个测试,测试小明是否认识这个单词(小红不会告诉小明单词是什么意思)。事件的输入是按照先后顺序输入的。

1
2
3
4
5
6
5
0 we
0 are
1 family
0 Family
1 Family

输出格式

对于小红的每次测试,如果小明认识这个单词输出Yes,否则输出一行No

1
2
No
Yes

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <set>
#include <string>
using namespace std;
string word;
set<string> s;
int main(){
int n, d;
cin >> n;
for(int i=0; i<n; i++){
cin >> d >> word;
for(int j=0; j< word.size(); j++){ //将大写字母转换为小写字母
if(word[j]>='A' && word[j]<= 'Z'){
word[j] -= 65;
}
}
if(d == 0){
s.insert(word);
}else{
if(s.count(word)){
cout << "Yes\n" << endl;
}else{
cout << "No\n" << endl;
}
}
}
}
/*此题考查set集合的应用,注意先排除大写字母的干扰*/

例7-小明转专业(转专业真题)

小明在转学校计算机专业时,曾在上机考试遇到过这样一个题:

给定n个整数,求里面出现次数最多的数,如果有多个重复出现的数,求出值最大的一个。当时可是把小明难住了,现在请你来解决一下。

注:此题为天津理工大学2018级转计算机专业c语言上机题1

输入格式

第一行输入一个整数n(1≤n≤100000),接下来一行输入n个int范围的整数

1
2
5
1 1 2 3 4

输出格式

输出出现次数最多的数和出现的次数,用一个空格隔开。如果有多个重复出现次数一样的数,输出值最大的那个。

1
1 2

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <map>
using namespace std;
map<int, int> mp;
int main(){
int n, x, ans, time; //ans存输出的数,time存出现的次数
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &x);
mp[x]++; //若key不存在,value默认值为0,再+1
}
time = 0;
for(map<int, int>::iterator it = mp.begin(); it!=mp.end(); it++){
if( (it->second)>= time ){ //比较出现次数,若次数更多则赋值
time = (it->second);
ans = (it->first);
}
}
printf("%d %d\n", ans, time);
}
/*此题考查map的综合应用。在转专业考试时,小明的思路是开拓一个大于输入个数n的数组,将出现的数次数存在该数对应下标位置的数组中。
此方法有很大的缺点:浪费了大量空间,最后还要遍历一遍数组找次数相等但值最大的元素。如果运用stl中的map集合,这种题会变得非常简单。*/

例8-水果店

小明经营着一个不大的水果店。他认为生存之道是经营最受顾客欢迎的水果。现在他想要一份水果销售状况的明细表,这样就可以很容易掌握所有水果的销售情况。小明告诉你每一笔销售记录的水果名称,产地和销量,请你帮他生成明细表。

输入格式

第一行是一个整数N(0<N≤1000),表示共有N次成功的交易。随后有N行数据,每行表示一次交易,由水果名称(小写字母,长度不超过100)和交易的产地(小写字母,长度不超过100)水果数目(正整数,不超过长度1000)组成。

1
2
3
4
5
6
5
apple shandong 3
pineapple guangdong 1
sugarcane guangdong 1
pineapple guangdong 3
pineapple guangdong 1

输出格式

请你输出一份排版格式正确(请分析样本输出)的水果销售明细表。这份表包括所有水果的名称、产地和销量。水果先按产地分类,产地按字母顺序排序。同一产地的水果按照名称排序,名称按字母顺序排序。

1
2
3
4
5
guangdong
|----pineapple(5)
|----sugarcane(1)
shandong
|----apple(3)

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <map>
using namespace std;
map<string, map<string, int>> mp;
string s1,s2;
int d;
int main(){
int n;
cin >> n;
for(int i=0; i<n; i++){
cin >> s1 >> s2 >> d;
mp[s2][s1] += d;
}
for(map<string,map<string, int>>::iterator it1 = mp.begin(); it1 != mp.end(); it1++){
cout << (it1->first) << endl;
for(map<string, int>::iterator it2 = (it1->second).begin(); it2!=(it1->second).end(); it2++){
cout << " |----" << (it2->first) << "(" << (it2->second) <<")" << endl;
}
}
return 0;
}
/*此题考查map的高级应用:在map中再嵌套一个map,重点是要学会存入和读取map中的map。*/

七.栈与递归

  • 栈是一种特殊的线性结构,有后进先出的特性,只能在一端进行操作

    参考入栈、出栈、取栈顶元素代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    #include <iostream>
    using namespace std;
    struct Stack{
    int data[10000];
    int top = -1;
    //进栈
    void push(int x){
    top++;
    if(top<10000){
    data[top]=x;
    } else{
    top--;
    cout<<"Stack overflow!"<<endl;
    }
    }
    //出栈
    void pop(){
    if(top>=0){
    top--;
    }
    }
    //求栈顶元素
    int topval(){
    if(top>=0){
    return data[top];
    }
    return 0;
    }
    };
    int main(){
    Stack s;
    for(int i=1; i<=10; i++){
    s.push(i);
    }
    for(int i=1;i<=10;i++){
    cout<<s.topval()<<" ";
    s.pop();
    }
    return 0;
    }
  • 在C++标准库中,提供了stack,功能齐全且易于使用,如stack <T> s代表定义了一个存储T类型的栈s。你可以对他进行push\pop\top\empty\size等函数的调用

    方法 功能 参数类型 返回值类型
    push 压入元素到栈顶 T
    pop 弹出栈顶元素
    top 返回栈顶元素
    empty 判断栈是否为空 bool
    size 栈的元素个数 非负整数

递归

  • 递归是编程中应用广泛的一个技巧,就是函数调用函数自身

  • 递归例子-汉诺塔(可自行百度问题)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    #include <iostream>
    #include <stack>
    using namespace std;
    stack<int> S[3]; //三个柱子
    void move(int x, int y){
    int temp = S[x].top();
    S[x].pop();
    S[y].push(temp);
    cout << x << "-->" << y << endl;
    }
    //A为圆盘一开始所在柱子, B为中间柱子, C代表目标柱,n代表移动盘子个数
    void hanoi(int A, int B, int C, int n){
    //递归终止条件
    if(n == 1){
    move(A, C); //从A柱子直接移动到C柱子
    return;
    }
    hanoi(A,C,B,n-1);
    move(A,C);
    hanoi(B,A,C,n-1);

    }
    int main(){
    int n;
    cin >> n;
    for(int i=n; i>=1; i--){ //大盘子先进栈
    S[0].push(i);
    }
    hanoi(0,1,2,n);
    while(!S[2].empty()){
    cout << S[2].top() << " ";
    S[2].pop();
    }
    return 0;
    }

综合例题

例1-小明吃桃

小明买了一堆桃子不知道个数,第一天吃了一半的桃子,还不过瘾,又吃多了一个。以后他每天吃剩下的桃子的一半还多一个,到n天只剩下一个桃子了。小明想知道一开始买了多少桃子。

输入格式

输入一个整数n(2≤n≤30)

1
2

输出格式

输出买的桃子的数量

1
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
int n;
int f(int x){
if(x == n){ //到第n天只剩下一个桃子
return 1;
}else{
return (f(x+1)+1)*2;
}
}
int main(){
scanf("%d", &n);
printf("%d\n",f(1));
return 0;
}
/*此题考查递归,注意终止条件*/

例2-修改后的斐波那契数列

相信很多人都学过斐波那契数列,它是:1,1,2,3,5,8,13,21…这样一个数列

用fn表示斐波那契数列的第n项,则有:f1=f2=1, fn=fn-1+fn-2(n>2)

为了提高难度,现修改了公式,新的公式:f1=f2=1, fn=afn-1+fn-2 (n>2)

输入格式

输入每行包括四个整数 n(1≤n≤100) ,a(1≤a≤10),b(1≤b≤10),p(1≤p≤2000)

1
3 1 1 1000

输出格式

输出fn对p取模的值

1
2

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
int ans[2005];
bool vis[2005];
int f(int n, int a, int b, int p){
if(vis[n]){
return ans[n];
}
vis[n] = true;
if(n == 1||n == 2){
return ans[n] = 1%p;
}else{
return ans[n] = (a*f(n-1, a, b, p) % p + b*f(n-2,a,b,p) % p)%p;
}
}
int main(){
int n, a, b, p;
scanf("%d%d%d%d", &n,&a,&b,&p);
printf("%d\n",f(n,a,b,p));
return 0;
}

例3-快速幂

x^y相信大家都会计算(for循环相乘),但y很大时怎么办?

小明研究发现,找到了一个好办法,公式如下

1
2
3
f(x,y) = f(x,y/2)*f(x,y/2) ----------- y%2==0 && y>0
f(x,y) =1 ------------------------------ y=0
f(x,y) = f(x,y/2)*f(x,y/2) *x -------- y%2==1 && y>0

(当然这不是快速幂的最好写法)

输入格式

第一行输入整数t(t≤100)

随后t行,每行三个整数x(1≤x≤10^9),y(1≤y≤10^18),p(1≤p≤10^9)

1
2
1
2 10 10000

输出格式

输出x^y%p的值

1
1024

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
long long f(long long x, long long y, long long p){
if (y == 0){
return 1%p;
}else if (y % 2==0){
long long temp = f(x, y/2, p);
return temp*temp % p; //注意要用temp保存下来,否则递归两次浪费时间
}else{
long long temp = f(x, y/2, p);
return temp*temp % p * x % p;
}
}
int main(){
int t;
long long x,y,p;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld", &x, &y, &p);
printf("%lld\n", f(x,y,p));
}
return 0;
}
/*此题考查递归,注意由于元素过大要用long long类型保存,不能完全计算出来再取模,容易超空间*/

例4-弹簧板

有一个小球落在一串连续的弹簧板上,小球落到某一个弹簧板后,会被弹到某一个地点,直到小球被弹到弹簧板以外的地方。

假设有n个连续的弹簧板,每个弹簧板占一个单位举例。第i个弹簧板能选择把小球向前弹a[i]个距离,或者向前弹b[i]个距离。比如位置1的弹簧能让小球前进2个距离到达位置3。

现在小球掉到了1弹簧板上面,请你帮忙计算小球最少会被弹起多少次,才会弹出弹簧板。1号弹簧板也算一次。

输入格式

第一行输入一个n代表有n个弹簧板(1≤n≤200)

第二行输入n个数字,中间用空格隔开。第i个数a[i](0<a[i]<30)代表第i个弹簧板可以让小球移动的距离。

第二行输入n个数字,中间用空格隔开。第i个数b[i](0<b[i]<30)代表第i个弹簧板可以让小球移动的距离。

1
2
3
5
2 2 3 1 2
1 2 3 4 1

输出格式

输出一个整数,表示小球被弹起的最小次数

1
2

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <algorithm>
using namespace std;
int a[205],b[205];
int ans[205];
bool vis[205];
int n;
int f(int x){ //传入一次前进距离,返回弹起次数
if(x >= n){
return 0;
}
if(vis[x]){
return ans[x];
}
vis[x] = true;
return ans[x] = min(f(x+a[x]), f(x+b[x])) + 1;
}
int main(){
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
}
for(int i=0; i<n; i++){
scanf("%d", &b[i]);
}
printf("%d\n",f(0));
}
/*此题考查递归条件的判断,有一定难度*/

例5-最大公约数

最大公约数相信大家都会计算,但怎么用计算机快速的计算呢?

f(x,y) = f(y, x%y), y>0

f(x,y) = x , x=0

输入格式

第一行输入一个整数t (t≤100)

然后有t行,每行有两个整数x(1≤x≤10^9),y(1≤y≤10^9)

1
2
1
6 8

输出格式

输出x,y的最大公约数

1
2

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
int gcd(int x, int y){
if(y == 0){
return x;
} else{
return gcd(y, x%y);
}
}
int main(){
int t,x,y;
scanf("%d", &t);
while (t--){
scanf("%d%d", &x, &y);
printf("%d", gcd(x,y));
}
return 0;
}

例6-括号匹配

小明在纸上写了一个字符串,只包含’(‘和’)’ 。一个’(‘能匹配一个’)’,但是匹配的’(‘必须出现在’)’之前。请你帮小明判断下他写的字符串能否完全匹配,如果能则输出括号的位置。(匹配的括号不能交叉,只能嵌套)

输入格式

一行输入一个字符串只含有’(‘和’)’ ,输入的字符串长度不大于50000

1
(())

输出格式

如果输出的括号不匹配,输出一行”No”,否则输出一行”Yes”,接下来里若干行每行输出两个整数,用空格隔开,表示所有匹配对的括号的位置(下标从1开始)。可以按任意顺序输出。

1
2
3
Yes
2 3
1 4

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
stack<int> st;
char s[50005];
int ans[50005];
int main(){
scanf("%s", &s);
int len = strlen(s);
bool b = true;
for(int i=0;i<len;i++){
if(s[i]=='('){
st.push(i+1); //注意题目要求下标从1开始
}else{
if(!st.empty()){
ans[i+1]=st.top(); //获取栈顶元素(位置)
st.pop();
} else{ //右括号多余
b=false;
break;
}
}
}
if(!st.empty()){ //左括号多余
b=false;
}
if(!b){
printf("No\n");
}else{
printf("Yes\n");
for(int i=1; i<=len; i++){
if(ans[i]){
printf("%d %d\n",ans[i],i);
}
}
}

return 0;
}
/*括号匹配类似的题都可以使用栈进行操作,本题答案不唯一,只要输出全部匹配的位置就行*/

例7-网页跳转

小明每天都在使用一款名为”515code游览器”的软件,软件一共有三种操作:打开页面、前进、后退。它们的功能如下所示:

  • 打开页面:在地址栏中输入网址,并跳转到相应页面
  • 后退:返回到上一次游览的界面
  • 前进:返回到上次后退前的界面,如果上一次操作是打开界面,则无法前进

现在,小明打开了这个软件,进行了一系列操作,你需要输出他每次操作后所在页面的地址。

输入格式

第一行输入一个整数n(0<n≤100000),表示小明的操作次数

接下来n行,每行输入一个字符串,如果是VISIT,后面接着输入一个不含有空格和换行的网址(长度小于100),表示小明在游览器中输入的网址;如果是BACK,表示小明点击了后退按钮;如果是FORWARD,表示小明点击了前进按钮。

1
2
3
4
5
6
7
8
9
10
11
10
VISIT https://www.baidu.com/
VISIT https://www.515code.com/
BACK
BACK
FORWARD
FORWARD
BACK
VISIT https://www.google.com/
FORWARD
BACK

输出格式

对于每次操作,如果小明操作成功,输出小明操作后的网址,否则输出Ignore。假设小明输入的网址都是合法的。

1
2
3
4
5
6
7
8
9
10
11
https://www.baidu.com/
https://www.515code.com/
https://www.baidu.com/
Ignore
https://www.515code.com/
Ignore
https://www.baidu.com/
https://www.google.com/
Ignore
https://www.baidu.com/
Process finished with exit code 0

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <stack>
#include <string>
using namespace std;
string op, s;
stack<string> s1, s2; //s2记录被s1弹出的记录
int main(){
int n;
scanf("%d", &n);
for(int i=0; i<n; i++){
cin >> op;
if(op == "VISIT"){
cin >> s;
while(!s2.empty()){
s2.pop();
}
s1.push(s); //访问网站时,网址压入s1栈中
}else if(op == "BACK"){
if(s1.size()<=1){ //无法后退
cout << "Ignore" <<endl;
continue;
}
s2.push(s1.top()); //s1出栈的记录保存在s2中
s1.pop();
}else{
if(s2.empty()){ //无法前进
cout << "Ignore" <<endl;
continue;
}
s1.push(s2.top()); //s2出栈的记录保存在s1中
s2.pop();
}
cout << s1.top()<< endl;
}
return 0;
}

/*此题考查栈的设计应用,注意判断两个栈的出栈和入栈条件,容易出错!*/

八.深度优先搜索

  • 深度优先搜索(dfs)是一种算法,注重的是思想,把所有可行的方案都列出来不断的去尝试,直到找到问题的解

  • 经典:迷宫问题

    给定任意一个迷宫地图,求解路径

    输入样例

    1
    2
    3
    4
    5
    6
    5 6
    ....S*
    .***..
    .*....
    *.**..
    .E....

    输出样例

    1
    2
    3
    4
    5
    ....+*
    .***+.
    .*..+.
    *.**+.
    .E+++.

    参考代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    #include <iostream>
    #include <string>
    using namespace std;
    int n, m;
    string maze[110];
    bool vis[110][110];
    int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; //左下右上四个方向
    bool in(int x, int y){
    return 0<=x && x<n && 0<=y && y<m;
    }
    bool dfs(int x, int y){
    if(maze[x][y] == 'E'){
    return true;
    }
    vis[x][y]=1; //表示此坐标已经访问过
    maze[x][y] ='+'; //标记通路

    for(int i=0; i<4; i++){
    int tx = x + dir[i][0];
    int ty = y + dir[i][1];
    if(in(tx, ty) && maze[tx][ty]!='*' && !vis[tx][ty]){
    if(dfs(tx, ty)){
    return true;
    }
    }
    }

    vis[x][y]=0;
    maze[x][y]='.';
    return false;

    }

    int main(){
    //输入迷宫地图,'.'代表通路,'*'代表墙壁,'S'代表起点,'E'代表终点
    cin >> n >> m;
    for(int i=0; i<n; i++){
    cin >> maze[i];
    }
    int x, y;
    for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
    if(maze[i][j] == 'S'){
    x = i, y = j;
    }
    }
    }
    if(dfs(x,y)){
    for(int i=0; i<n; i++){
    cout << maze[i] << endl;
    }
    } else{
    cout << "走不通" << endl;
    }
    }

例题1-中国象棋

中国象棋博大精深,其中马的规则最为复杂,也是最难操控的一颗棋子。

我们都知道象棋中马走”日”,比如在 (2, 4)位置的一个马,跳一步能到达的位置有 (0, 3),(0, 5),(1, 2),(1, 6),(3, 2),(3, 6),(4, 3),(4, 5)

深度优先搜索例题-中国象棋

小明正在和小红下棋,小明正在进行战略布局,他需要把在 (x,y)位置的马跳到 (x’, y’) 位置,以达到威慑的目的。

但是棋盘大小有限制,棋盘是一个 10*9 的网格,左上角坐标为 (0, 0),右下角坐标为 (9, 8),马不能走出棋盘,并且有些地方已经有了棋子,马也不能跳到有棋子的点。

蒜头君想知道,在不移动其他棋子的情况下,能否完成他的战略目标。

输入格式

一共十行,每行一个长度为9的字符串

输入表示这个棋盘,用’.’表示空位置,用’#’表示该位置有棋子,用’S’表示马的初始位置,用’T’表示马需要跳到的位置。

输入保证一定只存在一个’S’和一个’T’。

1
2
3
4
5
6
7
8
9
10
.#....#S#
..#.#.#..
..##.#..#
......##.
...T.....
...#.#...
...#.....
...###...
.........
.##......

输出格式

如果在不移动其他棋子的情况下,马能从’S’跳到’T’,那么输出一行”Yes”,否则输出一行”No”

1
Yes

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
char s[10][10];
//定义八个方向,分别为上图所示的点
int dir[8][2] = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
bool vis[10][10]; //记录是否访问过
bool f = false;
bool in(int x, int y){
return 0<=x && x<10 && 0<=y && y<9;
}
void dfs(int x, int y){
vis[x][y] = true;
if(f){
return;
}
if(s[x][y]=='T'){
f = true;
}
for(int i=0; i<8; i++){
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(in(tx, ty) && s[tx][ty] != '#' && !vis[tx][ty]){
dfs(tx, ty);
}
}
}
int main(){
int x, y;
for(int i=0; i<10; i++){
scanf("%s", &s[i]);
}
for(int i=0; i<10; i++){
for(int j=0; j<9; j++){
if(s[i][j] == 'S'){ //找到马的位置
x = i;
y = j;
}
}
}
dfs(x, y); //搜索
if(f){
printf("Yes\n");
}else{
printf("No\n");
}
return 0;
}
/*此题考查dfs,注意返回条件与边界条件的判断,容易出错*/

例题2-踏青

小明和他的朋友周末相约去召唤师峡谷踏青。他们发现召唤师峡谷的地图是由一块一块格子组成,有的格子上是草丛,有的是空地。草丛通过上下左右4个方向拓展其他草丛形成一片草地,任何一片草地中的格子都是草丛,并且所有格子之间都能通过上下左右联通。如果用’#’代表草地,’.’代表空地,下面的峡谷则有2片草地

1
2
##..
..##

处在同一片草地的2个人可以互相看到,空地看不到草地里面的人。他们发现有一个朋友不见了,现在需要分头去找,每个人负责一片草地,小明想知道他们至少需要多少人

输入格式

第一行输入n,m(1≤n , m≤100)表示峡谷大小

接下来n行字符串表示峡谷的地形

1
2
3
4
5
6
5 6
.#....
..#...
..#..#
...##.
.#....

输出格式

1
5

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
char mp[105][105];
bool vis[105][105];
int n, m;
void dfs(int x, int y){
//判断边界和特殊情况
if(x<0 || x>=n || y<0 || y>=m || vis[x][y] || mp[x][y]=='.'){
return;
}
vis[x][y] = true;
dfs(x-1, y);
dfs(x+1, y);
dfs(x,y-1);
dfs(x,y+1);
}
int main(){
int cnt=0;
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++){
scanf("%s",mp[i]);
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!vis[i][j] && mp[i][j] =='#'){
dfs(i, j); //搜索
cnt++;
}
}
}
printf("%d\n",cnt);
}
/*本题其实就是求有多少片草地,利用深搜标记连续的草地(即一片草丛),注意边界条件判断*/

例题3-迷宫问题的方案数

给出一个迷宫,求其路径的方案数目

输入格式

第一行输入两个整数n(1≤n≤11),m(1≤m≤11)表示迷宫的行和列

然后有一个n*m的地图,地图由四部分组成,’.’表示可以通行的路,’#’表示迷宫的墙,’s’表示起点,’e’表示终点

1
2
3
4
5
6
5 5
s####
..###
..###
..###
....e

输出格式

输出一个整数,表示’s’到’e’的所有方案数

1
1

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
int n,m,x,y,ans; //x,y为起始点坐标
char mp[15][15];
bool vis[15][15];
void dfs(int x, int y){
if(x<0 || x>=n || y<0 || y>=m || vis[x][y] || mp[x][y]=='#'){
return;
}
if(mp[x][y] == 'e'){
ans++;
return;
}
vis[x][y] = true; //标记已访问过
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
vis[x][y] = false; //取消标记,因为要计算多条路径
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",&mp[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mp[i][j]=='s'){
x=i;
y=j;
}
}
}
dfs(x,y);
printf("%d\n",ans);
return 0;
}

正在持续更新,4月13日已更新