编程笔记|蓝桥杯模拟赛收获（3,4题）
本文非原创，仅为个人的学习笔记，借鉴了一些文章链接如下。
C++中sprintf()函数的使用详解
2020年蓝桥杯模拟赛解题报告（CPP版本）
C++中string.find()函数与string::npos
第三题
一棵包含有2019个结点的二叉树，最多包含多少个叶结点？
这道题考察的是二叉树的性质，我不了解所以做错了。
考察性质：
二叉树中度为0的节点总比度为0的节点多一个
证明：
二叉树中总结点个数是度为0、1、2节点的总和:
又因为二叉树除了根节点外，所有节点都有且仅有一个进入节点的枝:
所以有
b为所有分支的总和
这些分支又是每一个节点射出的：
有：
联立1 2 3式即证明
分析
本题要求叶节点最多，也就是最大，令
最小为0，
根据刚刚的性质算出n2=(2019-1)/2=1009，n0=1010。
第四题
在1至2019中，有多少个数的数位中包含数字9？
注意，有的数中的数位中包含多个9，这个数只算一次。例如，1999这个数包含数字9，在计算时只是算一个数。
本题没什么特殊算法，我甚至都没编程，直接手算，包含9的三种情况为(既然要求不重复)：
- 个位包含9的且十位百位不包含9
- 十位包含9的且百位不含9
- 百位包含9的。
一共是164+180+200=544。
一下是老师的参考代码
对于我这个c++连数组都不会的小白来讲，只能说学到了
#include <iostream>
#include<cstdio>
using namespace std;
const int N = 2019;
bool check(int i) {
char s[5];
sprintf(s, "%d", i);
string str(s);
return str.find('9') != string::npos;
}
int main() {
int ans = 0;
for (int i = 9; i <= N; ++i) {
if (check(i)){
ans++;
cout<<ans<<":"<<i<<endl;
}
}
cout << ans << endl;
return 0;
}
sprintf
- 函数原型:sprintf(char *str, const char *format, ...)在头文件cstdio中。
例如
sprintf(str, "Pi 的值 = %f", M_PI)
是将字符串"Pi 的值 = %f"赋值到str所指向的数组，%f表示变量的M_PI的类型。他会被变量替换。 -
C++中M_PI竟然是π，我晕了，这么高级!!!不过要加上头文件"math.h"
string用法
string s;//调用默认构造函数，s为一个空字符串
string s(str);//等价于string s = str;调用拷贝构造函数，s是str的备份
string s(str,strindex);//将字符串str内始于strindex位置的部分当作s的初始值
eg.string str = "123456789";
string s(str,3);//s的初值为str由位置3开始的字符串，即456789
string s(str,stridx,strlen); // 将字符串str由stridx位置起始且长度为strlen的部分最为s的初值，如果strlen大于最大长度，则只截取字符串最大长度
eg.string s(str,3,10);//s=456789,由位置3开始，截取长度为10的部分，由于str剩余部分长度小于10，则截取str剩余最大长度
string s(cstr);//将C风格字符串作为s的初值
eg.string s("hello");//s的初值为hello
string s(cstr,length);//将C风格字符串的length长度部分作为s的初值
eg.string s("hello",2);//s="he"
string s(num,c);//生成一个字符串，包含num个c字符
eg.string s(10,'c');//s的初值为“cccccccccc”
string.find()
???c里面从来都没有这么高级的函数
string中find()返回值是字母在母串中的位置（下标记录），如果没有找到，那么会返回一个特别的标记npos。（返回值可以看成是一个int型的数）
string::npos参数：
npos 是一个常数，用来表示不存在的位置，类型一般是std::container_type::size_type
例如定义一个位置类型
string::size_type pos = strA.find(strB);
接下来就可以用pos变量做逻辑运算了
if(pos != string::npos){}
例如
int idx = str.find("abc");
if (idx == string::npos)
这个代码中idx被定义为int 类型是错误的，必须是 string::size_type pos类型
比较式 idx == string::npos 中，找不到abc会返回-1,如果 idx 的值为-1，由于 idx 和字符串string::npos 型别不同，比较结果可能得到 false。
因此要想判断 find() 的结果是否为npos，最好的办法是直接比较：
if (str.find("abc") == string::npos) { ... }
拓展
string.find_first_of()返回参数首次出现的位置
string.find_last_of()返回参数最后一次出现的位置
