蓝桥杯考试知识点
算法模块
1.判断质数：
1
2
3
4
5
6
7
8
9
10
| bool isPrime(int n)
{
if(n<=1) return false;
for(int i=2;i*i<=n;i++)
{
if(n%i==0) return false;
}
return true;
}
|
2.数字反转
1
2
3
4
5
6
7
8
9
10
11
12
13
|
bool isReverse(int n)
{
int s=0,k=n;
while(n>0)
{
s=s*10;
s=s+k%10;
k=k/10；
}
if(s==n) return true;
return false;
}
|
3.寻找最大公约数的递归算法
1
2
3
4
5
6
7
| int gcd(int a,int b)
{
if(y)
return gcd(b,a%b)
else
return a;
}
|
基础语法
常见函数
取整函数
1.floor函数 向下取整 floor中文名为地板，即向下取整。
2.ceil函数 向上取整 ceil中文名为天花板，即向上取整。
3.round函数 四舍五入 round中文名为四舍五入。
memset函数
memset函数
memset函数的原型：
void memset(voidstr, int c, size_t n)
STL函数
C++中的字符串函数
1
2
3
4
5
6
7
8
9
| void test()
{
string str1;
string str2("123456789");
string str3("12345", 0, 3);
string str4("0123456", 5);
string str5(5, '1');
string str6(str2, 2);
}
|
字符串比较：
1 ++字符串支持常见的比较操作符（>,>=,<,<=,==,!=），按字典序逐个比较
2.Compare函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| {
void test3()
{
string A("aBcd");
string B("Abcd");
string C("123456");
string D("123dfg");
cout << "A.compare(B)：" << A.compare(B)<< endl;
cout << "A.compare(2, 3, B):" <<A.compare(2, 3, B)<< endl;
cout << "A.compare(2, 3, B, 2, 3):" << A.compare(2, 3, B, 2, 3) << endl;
cout << "C.compare(0, 3, D, 0, 3)" <<C.compare(0, 3, D, 0, 3) << endl;
}
}
|
3.string的插入push——back(),insert()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| {
void test4()
{
string s1;
s1.push_back('a');
s1.push_back('b');
s1.push_back('c');
cout<<"s1:"<<s1<<endl;
s1.insert(s1.begin(),'1');
cout<<"s1:"<<s1<<endl;
}
}
|
Substr拷贝函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s="sfsa";
string a=s.substr(0,3);
string b=s.substr();
string c=s.substr(2,3);
cout<<a<<endl;
cout<<b<<endl;
cout<<c<<endl;
return 0;
}
|
效果如图：
布尔类型的全排列函数
next_permutation(a.begin(), a.end())
Vetor数组（动态可变数组）
学习数组视频 Vector数组
下面是学习笔记：
Vector数组的引用格式
队列栈有点类似
1
2
3
4
5
6
7
8
| #include<bits/stdc++.h>
{
int main(void)
{
vector<int> a;
}
}
|
字符串的比较字符
vector数组的访问&修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<bits/stdc++.h>
int main(void)
{
vector<int> a;
a.push_back(1);
a.push_back(2);
a.push_back(3);
printf("%d",a.size);
for(int i=0;i<a.szie();i++>)
{
printf("%d",a[i]);
}
return 0;
}
|
如何在vector插入新的元素（四个函数）
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<bits/stdc++.h>
int main(void)
{
vector<int> g;
g.push_back(1);
g.emplace_back(2);
g.insert(g.begin(),3);
g.insert(g.begin(),3,3);
g.emplace(g.begin(),4);
g.emplace(g.begin(),3,4);
return 0;
}
|
如何在vector数组中删除元素
1
2
3
4
5
6
7
8
9
10
11
| #include<bits/stdc++.h>
int main(void)
{
vectot<int> g;
g.erase(g.beagin());
g.erase(g.end());
g.erase(g.begin(),g.begin()+5);
g.erase(g.begin,g.end);
return 0;
}
|
vector数组中的其他元素
1.resize(len)函数可以手动改变Vector数组长度给数组扩容
2.clear可以清空vector中的所有数组
3.empty函数返回一个bool值，可以用来判断数组是否为空
4.vector可以实现反向遍历
1
2
3
4
5
| for(auto it=g.rbegin();it!=g.rand();++it)
{
printf("%e",*it);
return 0;
}
|
是利用结构题按字典序排序
字符串函数的应用（基于P534）
题解
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
| #include<stdio.h>
#include<string.h>
char temp[1000];
int main()
{
char a[1110];
char b[111];
int n,m;
int l,r;
int k;
scanf("%d",&n);
scanf("%s",a);
for(int i=0;i<n;i++)
{
scanf("%d",&m);
if(m==1)
{
scanf("%s",b);
strcat(a,b);
printf("%s\n",a);
}
else if(m==2)
{
scanf("%d%d",&l,&r);
a[l+r]='\0';
strcpy(temp, &a[l]);
strcpy(a, temp);
printf("%s\n",a);
}
else if(m==3)
{
scanf("%d%s",&k,temp);
strcat(temp,&a[k]);
a[k]='\0';
strcat(a, temp);
printf("%s\n",a);
}
else if(m==4)
{
int flag=0;
char keep[1000]={0};
scanf("%s",temp);
for(int i=0;a[i]!='\0';i++)
{
if(a[i]==temp[0])
{
for(int j=0;j<strlen(temp);j++)
{
keep[j]=a[i+j];
}
if(strcmp(keep,temp)==0)
{
printf("%d\n",i);
flag++；
break;
}
}
}
if(!flag) printf("-1\n");
}
}
}
|
字符串函数的使用方法见CSDN:字符串函数
洛谷P1597：
C语言解法：
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<bits/stdc++.h>
using namespace std;
int main(){
int a=0,b=0,c=0;
char s[256];
cin>>s;
int len=strlen(s);
for(int i=0;i<len;i++){
if(s[i]=='a'){
if(s[i+3]=='a') a=a;
- if(s[i+3]=='b') a=b;
else if(s[i+3]=='c') a=c;
else a=s[i+3]-'0';
}
if(s[i]=='b'){
if(s[i+3]=='a') b=a;
else if(s[i+3]=='b') b=b;
else if(s[i+3]=='c') b=c;
else b=s[i+3]-'0';
}
if(s[i]=='c'){
if(s[i+3]=='a') c=a;
else if(s[i+3]=='b') c=b;
else if(s[i+3]=='c') c=c;
else c=s[i+3]-'0';
}
}
cout<<a<<" "<<b<<" "<<c;
return 0;
}
|
C语言解法：
比较两种题解我们可以看到C++的优势在于：
C++有更高效的赋值逻辑，可以直接利用数组索引进行赋值
基本语法知识点
布尔常量 bool
1
2
| bool vis[20];
if(!=vis[i])
|
链表
链表和数组的区别
快速访问：很少插入，删除 使用数组
正常访问：经常插入，删除 链表
比较杂的语法知识
底层const和顶层const
11.17未理解待补见const的应用
$\color{blue}{>洛谷P1312（重叠数boy，girl的个数）}$
$\color{blue} {boy是整类型（）中可以理解成bool常量如果是真则+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
| int aplusb(string a, string b, int *c)
{
int j1[505] = {0}, j2[505] = {0}, lena = a.length();
int lenb = b.length(), len = 0, jw = 0;
for(int i = 0; i < lena; i++) {
j1[i] = a[lena - i - 1] - '0';
}
for(int i = 0; i < lenb; i++) {
j2[i] = b[lenb - i - 1] - '0';
}
int i;
for(i = 0; i < max(lena, lenb); i++) {
c[i] = j1[i] + j2[i] + jw;
jw = c[i] / 10;
c[i] = c[i] % 10;
}
if(jw > 0) {
c[i] = jw;
len = i + 1;
} else {
len = i;
}
return len;
}
|
排序算法
归并排序
代码实现
动态视频
快速排序
快速排序
快速排序动态视频快速排序
排序算法基于洛谷（P1177）
题解：
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
|
void QuickSort(int array[], int low, int high) {
int i = low;
int j = high;
if(i >= j) {
return;
}
int temp = array[low];
while(i != j) {
while(array[j] >= temp && i < j) {
j--;
}
while(array[i] <= temp && i < j) {
i++;
}
if(i < j) {
swap(array[i], array[j]);
}
}
swap(array[low], array[i]);
QuickSort(array, low, i - 1);
QuickSort(array, i + 1, high);
}
|
快速排序优化版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void qs(int *a,int l,int r)
{
int m=a[(l+r)/2],i=l,j=r;
do{
while(a[i]<m) i++;
while(a[j]>m) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;
j--;
}
}while(i<=j);
if(l<j) qs(a,l,j);
if(r>i) qs(a,i,r);
}
|
P1177中的几种题解：
冒泡排序过于简单最终只能拿六十分
堆排序
堆排序笔记：
堆排序使用缺点：不稳定
时间复杂度：O（nlogn）
堆排序代码实现：
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
|
void DownAdjust(int a[],int k,int n)
{
int i=k,j=i*2;
while(j<=n)
{
if(j+1<=n&&a[j+1]>a[j])j++;
if(a[i]<a[k]){
swap(a[i],a[j]);
i=j;
j=i*2;
}
else{
break;}
}
}
void HeapSort(int a[],int n)
{
for(int i=n/2;i>=i;i--)
{
DownAdjust(a,j,n);
}
for(int i=n;i>=2;i--)
{
swap(a[1],a[i]);
DownAdjust(a,1,i-1);
}
}
|
**自学视频网址：堆排序
C++STLsort函数
**sort函数格式：sort（arr,arr+n,cmp）**首地址，未地址，和排序规则
第三个参数是排序条件,可以从大到小也可以从小到大
代码如下：
1
2
3
4
5
| int cmp(int a,int b)
{
return a>b
}
|
下面是利用结构题按字典序排序:
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
| struct student
{
string name="0";
int chinese=0;
int math=0;
int english=0;
int sum = 0;
};
student stu[1005];
bool cmp(student& s1, student& s2)
{
return s1.name < s2.name;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> stu[i].name >> stu[i].chinese >> stu[i].math >> stu[i].english;
stu[i].sum= stu[i].chinese + stu[i].math + stu[i].english;
}
sort(stu, stu+n,cmp);
return 0;
}
|
sort函数用字符串排序，洛谷P1012
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
string s[25];
bool cmp(string a,string b)
{
return a+b>b+a;
}
int main(void)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)cout<<s[i];
return 0;
}
|
用在结构体用sort代码，中引用Vector数组＋auto+const
基于P1104：
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 <bits/stdc++.h>
using namespace std;
struct Person {
string name;
int year;
int month;
int day;
int bian;
};
bool cmp(const Person& a, const Person& b) {
if (a.year != b.year) {
return a.year < b.year;
} else if (a.month != b.month) {
return a.month < b.month;
} else if(a.day!=b.day) {
return a.day < b.day;
}
else{
return a.bian>b.bian;
}
}
int main() {
int n;
cin >> n;
vector<Person> people(n);
for (int i = 0; i < n; i++) {
cin >> people[i].name >> people[i].year >> people[i].month >> people[i].day;
people[i].bian=i;
}
sort(people.begin(), people.end(), cmp);
for (const auto& person : people) {
cout << person.name << endl;
}
return 0;
}
|
二分算法/分治思想
DFS深度优先搜索
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
|
bool check(int x) {}
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
bool check(double x) {}
double bsearch_3(double l, double r)
{
const double eps = 1e-6;
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
|
这篇代码的语法知识点见上面的语法学习部分
*即结构在用sort进行排序时,字符串可以用字典序进行排序,排序的对应目标取决于排序条件中书写的参数
DFS的模板：
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
| void dfs(int u)
{
if(到达目的地)
{
}
for(int i=1;i<=枚举数；i++)
{
if(满足条件)
{
更新状态位；
dfs(step+1)
恢复状态位；
}
}
}
void dfs(int step,int flag)
{
if(step==k)
{
for(int i=0;i<k;i++)
{
cout<<setw(3)<<arr[i];
}
cout<<endl;
return ;
}
if(n-flag<k-step) return ;
for(int i=flag+1;i<=n;i++)
{
arr[step]=i;
dfs(step+1,i);
}
}
|
用递归去表示全排列算法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
45
46
47
48
| void dfs(int step)
{
if(step==n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=step+1;i<=n;i++)
{
a[step]=i;
check[i]=1;
dfs(step+1);
check[i]=0;
}
}
由两个函数我们可以发现DFS的核心是找到枚举的最大数量，理解怎样进行回溯，怎样搜索
``` C++
#include<bits/stdc++.h>
using namespace std;
int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
bool vis[20];
int b[20];
void dfs(int s,int t)
{
if(s==t)
for(int i=0;i<t;++i) cout<<b[i]<<" ";
{
cout<<endl;
return ;
}
}
for(int i=0;i<t;i++>)
{
if(!vis[i])
{
vis[i]=true;
b[s]=a[i];
dfs(s+1,t);
vis[i]=false;
}
}
|
1
2
3
4
5
6
7
8
| struct A
{
int a;
int b;
}p[2];
P[2]={{1,2},{2,3}};
|
DFS:
第八届蓝桥杯C++A组，迷宫题
DP动态规划
