文章目录
- 知识点
- 解题集
知识点
基础程序设计技巧
万能头文件
#include<bits/stdc++.h>
while执行多次输入
while (~scanf("%d", &n)) {}
循环退出
break是指直接跳出本层循环continue是指结束本次循环，但不跳出本层循环，进入下一次循环。
scanf，printf & cin, cout
cin, cout输入数据达到1e6或1e7后会变慢，则
改为scanf，printf
int 初定义
int类型的表示范围（-231～231-1），
有一种比int更大的类型，称为**long long**，它的表示范围是-263～263-1，比-1019～-1019略窄。
n太大（n≤1012），超过了int类型的表示范围，输入输出的时候用 %lld，如：scanf("%lld",&a);printf("%lld",a);
注意：C++中的cout无法输出 __int64类型变量的值。#求c(n,m)=n!/(m!*(n-m)!)
#define int long long
//加上这一行有时候程序过不了，则
#define ll long long
开数组一般大小：
const int N = 1e6 + 10;
int a[N];
布尔型（bool）
布尔型（bool）变量的值只有 真 （true) 和假 （false）。
应用：
①布尔型变量可用于逻辑表达式，也就是“或”“与”“非”之类的逻辑运算和大于小于之类的关系运算，逻辑表达式运算结果为真或为假。
②bool可用于定义函数类型为布尔型，函数里可以有 return TRUE; return FALSE 之类的语句。
③布尔型运算结果常用于条件语句：
if (逻辑表达式){如果是 true 执行这里；}
else{如果是 false 执行这里；}
④bool输出：只有0为假，其他都为真
基本数据类型取值范围
| type | size | 数值范围 |
|---|---|---|
| 无值型void | 0byte | 无值域 |
| 布尔型bool | 1 byte | true false |
| 有符号短整型short[int] / signed short[int] | 2 byte | -32768~32767 |
| 无符号短整型unsigned short[int] | 2byte | 0~65535 |
| 有符号整型int / signed[int] | 4 byte | -2147483648~2147483647 |
| 无符号整型unsigned[int] | 4 byte | 0~4294967295 |
| 有符号长整型long[int] / signed long[int] | 4 byte | -2147483648~2147483647 |
| 无符号长整型unsigned long[int] | 4 byte | 0~4294967295 |
| long long | 8 byte | 0~18446744073709552000 |
| 有符号字符型charlsignedchar | 1 byte | -128~127 |
| 无符号字符型unsigned char | 1 byte | 0~255 |
| 宽字符型wchar_t(unsigned short.) | 2byte | 0~65535 |
| 单精度浮点型float | 4 byte | 3.4e-38 - 3.4e+38 |
| 双精度浮点型double | 8 byte | 1.7e-308~1.7e+308 |
| long double | 8 byte |
文件输入输出操作
使用文件最简单的方法是使用输入输出重定向，只需要在main函数的入口处加入以下两条语句：freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
它将使得scanf从文件input.txt读入，printf写入文件output.txt.
浮点数陷阱
#include <stdio.h>
int main()
{
double i;
for(i=0;i!=10;i+=0.1)
printf("%.1lf\n",i);
return 0;
}
说明对于i可以达到10.0，但永远不会与10相等，所以for循环是一个死循环。
对于float和dobule类型的数据不能直接用 ==和!=来比较大小，即不要测试精确的浮点型数值，需要用精度比较，来测试一个可接受的数值范围。如：
for(i=0;fabs(10-i)>1e-5;i+=0.1)
C++中的输入输出
1）输入输出流：
头文件：#include <iostream> 头文件iostream包含了对输入输出流的定义#include<cstdio> (c++) == #include<stdio.h> (c)#include<cmath> (c++) == #include<math.h> (c)using namespace std 使用名字空间stdcin是输入流istream类对象，>>是提取运算符，存到a,b中cout是输出流ostream类的对象，<<是插入运算符，按顺序输出，endl为换行
析取器（>>）从流中输入数据
插入器（<<）向流中输出数据
#include <iostream> //头文件iostream包含了对输入输出流的定义
using namespace std; //使用名字空间std
int main(){
int a,b;
while(cin>>a>>b)
//cin是输入流istream类对象，>>是提取运算符，存到a,b中
cout<<a+b<<endl;
//cout是输出流ostream类的对象，<<是插入运算符，按顺序输出，endl为换行
return 0;
}
2）输入输出文件流：#include <fstream>fstream类，它是从iostream类派生的，用来支持对磁盘文件的输入输出。ifstream fin("aplusb.in");输入文件流，从硬盘到内存ofstream fout("aplusb.out");输出文件流，从内存到硬盘
#include <fstream> //fstream类，它是从iostream类派生的，用来支持对磁盘文件的输入输出。
using namespace std;
ifstream fin("aplusb.in"); //输入文件流，从硬盘到内存
ofstream fout("aplusb.out"); //输出文件流，从内存到硬盘
int main(){
int a, b;
while(fin>>a>>b) //析取器（>>）从流中输入数据
fout<<a+b<< "\n"; //插入器（<<）向流中输出数据
return 0;
}
如果想再次使用cin和cout，是否要逐个把程序中的所有fin和fout替换为cin和cout
不用这么麻烦，只需要把fin和fout的声明语句去掉，并加上这样两行即可：#define fin cin#define fout cout
递归
1、递归调用
2、递归出口
案例1：设计一个求阶乘的递归函数
1）形式化，写成一个函数，参数只有一个
令f(n) = n!
2）分解问题，尾递归，把n拿出来，子问题变成（n - 1）！
3）找到相似性，得到递推式
n!= (n - 1)!*n
f(n) = f(n - 1) * n
4）递归出口
n > n - 1 > n - 2 > n - 3 > … > 0
案例2：设计一个求解汉诺塔的递归函数
1）形式化，写成一个函数，参数有4个
//把n给盘子从a柱移到c柱，借助中间柱b
void hanoi(int n, char a, char b, char c);
2）分解问题，尾递归，把最大的盘子n拿出来，分解成n号盘子和上面的n - 1个盘子
3）找到相似性，得到递推式
//1）上面的n-1个盘子从a柱移到中间柱b，借助c
hanoi(n - 1, a, c, b);
//2）最大的盘子n从a柱移动到c柱
printf("move %d# from %c to %c\n", n, a, c);
//3）上面从n-1个盘子从b柱到c柱
hanoi(n - 1, b, a, c);
4）递归出口
n > n - 1 > n - 2 > n - 3 > … > 0
完整代码：
#include<bits/stdc++.h>
using namespace std;
void hanoi(int n, char a, char b, char c);
int main() {
int n;
while (cin >> n) {
hanoi(n, 'A', 'B', 'C');
}
return 0;
}
//把n给盘子从a柱移到c柱，借助中间柱b
void hanoi(int n, char a, char b, char c) {
if (n == 0) return ;
//1）上面的n-1个盘子从a柱移到中间柱b，借助c
hanoi(n - 1, a, c, b);
//2）最大的盘子n从a柱移动到c柱
printf("move %d# from %c to %c\n", n, a, c);
//3）上面从n-1个盘子从b柱到c柱
hanoi(n - 1, b, a, c);
}
案例3：字符串逆序
1）形式化，写成一个函数，参数有1个
//字符串s逆序
void reverse(char *s);
2）分解问题，尾递归，把第一个字符s[0]拿出来，分成2部分首字符s[0]和剩余的字符串（起始地址是s + 1）
3）找到相似性，得到递推式
//1）把第一个字符放到后面
char ts[2] = { s[0] };
strcat(s + 1, ts);
4）递归出口
n > n - 1 > n - 2 > n - 3 > … > 0
案例4：x星球
1）形式化，写成一个函数，参数有1个
//字符串s逆序
void reverse(char* s);
2）分解问题，有两种选择
（1）车队开进检查站，f(a - 1, b + 1)
（2）检查站开出1辆车，f(a, b - 1)
3）找到相似性，得到递推式
f(a, b) = f(a - 1, b + 1) + f(a, b - 1);
4）递归出口
n > n - 1 > n - 2 > n - 3 > … > 0
完整代码
#include<bits/stdc++.h>
using namespace std;
int f(int, int);
int main() {
int n;
while (cin >> n) {
cout << f(n, 0) << endl;
}
return 0;
}
//出站次序，车队有a辆车，检查站有b辆车
int f(int a, int b) {
if (a == 0) {
return 1;
}
if (b == 0) {
return f(a-1,1);
}
return f(a - 1, b + 1) + f(a, b - 1);
}
指针
& ：取地址符 & 用于获取变量的内存地址。它可以被用于任何数据类型的变量，包括基本数据类型（如整型、浮点型等）和复合数据类型（如数组、结构体等）。*为解引用符，解引用操作是指通过指针访问存储在其指向地址上的值。
#include<bits/stdc++.h>
using namespace std;
int main() {
int a = 10;
scanf("%d",&a); //& 为取地址符
cout << *(&a) << endl; //* 为解引用符，取出地址中的值
return 0;
}
int main() {
int a = 10;
int* pa = &a;
*pa = 11;
cout << *pa << endl; //11
cout << a << endl; //11
return 0;
}
sort()基本使用方法
sort()的定义
sort()函数可以对给定区间所有元素进行排序。
它有三个参数sort(begin, end, cmp):begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，cmp参数为排序准则，cmp参数可以不写，默认从小到大进行排序。
返回值：无
时间复杂度：O(nlogn)
排序范围：[first,last)
int main() {
int a[10] = { 10,9,8,7,6,5,4,3,2,1 };
sort(a + 0, a + 2 + 1,cmp); //排序前三位
for(int i = 0;i < 10;i++)
cout << a[i] << endl;
return 0;
}
bool控制cmp自定义排序：
bool cmp(int e1, int e2) { //int 对应 int a[10]
return e1 > e2; //降序为true不交换，升序为false交换
}
结构体排序
sort()也可以对结构体进行排序，
比如我们定义一个结构体含有学生的姓名和成绩的结构体Student，
然后我们按照每个学生的成绩从高到底进行排序。首先我们将结构体定义为：
struct Student {
string name;
int score;
};
根据排序要求我们可以将排序准则函数写为：
bool cmp_score(Student x, Student y) {
return x.score > y.score;
}
完整代码：
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct Student {
string name;
int score;
Student() {}
Student(string n, int s) :name(n), score(s) {}
};
bool cmp_score(Student x, Student y) {
return x.score > y.score;
}
int main() {
Student stu[3];
string n;
int s;
for (int i = 0; i < 3; i++) {
cin >> n >> s;
stu[i] = Student(n, s);
}
sort(stu, stu + 3, cmp_score);
for (int i = 0; i < 3; i++) {
cout << stu[i].name << " " << stu[i].score << endl;
}
return 0;
}
[#B3827[NICA #2] 高考组题](#B3827[NICA #2] 高考组题)
STL
STL是C语言标准中的重要组成部分
以模板类和函数的形式提供数据结构和算法优化STL大致分为3类，容器，算法，迭代器STL的主要组成部分
容器：用于存储数据集合的通用类模板，包括序列容器（如vector、list、deque）、关联容器（如set、multiset、map、multimap）和容器适配器（如stack、queue、priority_queue）。
算法：用于对容器中的元素进行各种操作的通用函数模板，例如排序、搜索、复制等。
迭代器：实现STL算法与容器交互所需的通用指针
vector动态数组
在 C++ 中，vector 是一个模板类，用于存储一个动态数组, 运行时根据需要改变数组大小
vector <数据类型> 变量名；
e.g. vector a; 默认初始化，a为空
e.g. vector b(a); 用a定义b
e.g. vector a(100); a有100个值为0的元素
开辟空间后可以直接访问a[0]…a[99]，没有用()开辟则无法访问，会溢出
多维数组
定义多维数组，例如定义一个二维数组 : vector<int> a[MAXN];
它的第一维大小是固定的MAXN，第二维是动态的。
用这个方式，可以实现图的邻接表存储。
vector语法
| 功能 | 例子 | 说明 |
|---|---|---|
| 赋值 | a.push_back(100); | 在尾部添加元素 |
| 元素个数 | int size = a.size(); | 元素个数 |
| 是否为空 | bool isEmpty = a.empty(); | 是否为空 |
| 打印 | cout << a[0] << endl; | 打印第一个元素 |
| 中间插入 | a.insert(a.begin() + i, k); | 在第i个元素前面插入k |
| 尾部插入 | a.push_back(8); | 尾部插入为8的元素 |
| 尾部插入 | a.insert(a.end(), 10, 5); | 尾部插入10个值为5的元素 |
| 删除尾部 | a.pop_back(); | 删除尾部元素 |
| 删除区间 | a.erase(a.begin() + i, a.begin() + j); | 删除区间[i, j - 1]的元素 |
| 删除元素 | a.erase(a.begin() + 2); | 删除第3个元素 |
| 调整大小 | a.resize(n); | 数组大小变为n |
| 清空 | a.clear(); | |
| 翻转 | reverse(a.begin(), a.end()); | 用函数reverse翻转数组 |
| 排序 | sort(a.begin(), a.end()); | 用函数sort排序，从小到大 |
样例代码
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> a;
vector <int> a(100); //a设置100个值为0的元素
//开辟空间后可以直接访问a[0]...a[99]，没有用（）开辟则无法访问 会溢出
a.push_back(8);
a.push_back(7);
cout << a.size();//元素个数
cout << *a.begin();//a[0],a.begin()迭代器类似于指针，要用解引用符
cout << *(a.end()-1);//a.end()指向最后元素的后一位
return 0;
}
迭代器&&循环遍历
迭代器Iterator是一种设计模式，在编程语言中用于访问容器的元素，而不需要暴露集合的内部表现方式。
迭代器提供了一种统一的方式来遍历不同类型的集合，使得代码更加灵活和可复用。
使用*操作符可以解压或展开迭代器或可迭代对象Iterable，将其内容依次提取出来。
vector<int>::iterator it;
for(it=a.begin(); it != a.end();it++){}
cout << *it; //解引用符解迭代器
for (auto it = a.begin(); it != a.end(); it++){}
cout << *it; //解引用符解迭代器
auto语法
auto的定义
【auto】(自动识别类型)
在C++中，auto关键字是一个类型说明符，用于自动推导变量的类型。
这意味着编译器会根据变量的初始化表达式自动确定变量的类型，从而使得代码更加简洁，
特别是当处理复杂类型时。auto关键字是在C++11标准中引入的，之后被广泛应用于现代C++编程中。
auto的语法
规则1：声明为auto（不是auto&）的变量，忽视掉初始化表达式的顶层const。即对有const的普通类型(int 、double等)忽视const，对常量指针（顶层const）变为普通指针，对指向常量（底层const）的常量指针（顶层cosnt）变为指向常量的指针（底层const）。
规则2：声明为auto& 的变量，保持初始化表达式的顶层const或 volatile 属性。
规则3：若希望 auto推导的是顶层const，加上const，即const auto。
参考资料
- [更喜欢用这个]
auto会拷贝一份容器内的veckor,在修改x时不会改变原容器当中的vector值，只会改变拷贝的vector。x为元素可直接使用
for(auto x : a){}
cout << x;
- 当需要对原数据进行同步修改时，就需要添加
&，即vector的引用，会在改变x的同时修改vector。
for (auto& x : vector){}
- [不常用]
const(常类型)，不能作为左值&(引用)，不拷贝，不申请新空间，
会对原vector修改当我们不希望拷贝原vector(拷贝需要申请新的空间)，同时不愿意随意改变原vector，那么我们可以使用for(constauto & x:vector)，这样我们可以很方便的在不拷贝的情况下读取vector，同时不会修改vector。一般用在只读操作。
for (const auto& x : vector)
auto在编程时真正的用途
1、代替冗长复杂的变量声明vector<int>::iterator it = v.begin(); 直接用auto代替 auto it = v.begin();
2、定义模板参数时，用于声明依赖模板参数的变量
template <typename _Tx, typename _Ty>
void Multiply(_Tx x, _Ty y) {
auto v = x + y;
std::cout << v;
}
使用reverse反向排列算法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> v(10);
for (int i = 0; i < 10; i++)
{
v[i] = i;
}
reverse(v.begin(), v.end());
vector<int>::iterator it;
for (it = v.begin(); it != v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
stack栈
栈的定义
栈Stack是一种线性数据结构，其特点是只允许在一端进行插入和删除操作；
这一端被称为栈顶top，相对地，把另一端称为栈底bottom；
这种数据结构遵循后进先出LIFO, Last In First Out的原则。
栈的语法
| 例子 | 说明 |
|---|---|
| stack< Type >s; | 定义栈，Type为数据类型，如int，foatchar等 |
| s.push(item); | 把item放到栈顶 |
| s.top(); | 返回栈顶的元素，但不会删除 |
| s.pop(); | 删除栈顶的元素，但不会返回 |
| s.size(); | 返回栈中元素的个数 |
| s.empty(); | 检查栈是否为空，如果为空返回true.否则返回false |
爆栈问题
栈需要用空间存储，存进栈的数组太大，那么总数会超过系统为栈分配的空间，就会爆栈，即栈溢出。
解决办法有两种 :
(1)在程序中调大系统的栈。依赖于系统和编译器。
(2)手工写栈。
P1427 小鱼的数字游戏
题目描述
小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字
a
i
a_i
ai（长度不一定，以
0
0
0 结束），记住了然后反着念出来（表示结束的数字
0
0
0 就不要念出来了）。这对小鱼的那点记忆力来说实在是太难了，你也不想想小鱼的整个脑袋才多大，其中一部分还是好吃的肉！所以请你帮小鱼编程解决这个问题。
输入格式
一行内输入一串整数，以
0
0
0 结束，以空格间隔。
输出格式
一行内倒着输出这一串整数，以空格间隔。
样例 #1
样例输入 #1
3 65 23 5 34 1 30 0
样例输出 #1
30 1 34 5 23 65 3
提示
数据规模与约定
对于
100
100\ %
100 的数据，保证
0
≤
a
i
≤
2
31
−
1
0 \leq a_i \leq 2 ^ {31} - 1
0≤ai≤231−1，数字个数不超过
100
100
100。
#include<bits/stdc++.h>
using namespace std;
int main() {
stack<int> s;
int x;
while (cin >> x&&x!=0) {
s.push(x);
}
while (!s.empty())
{
cout << s.top() << " ";
s.pop();
}
return 0;
}
解题集
闰年判断
if ((m%4==0&&m%100!=0)||m%400==0)
找完全平方数
int main() {
for (int a 1; a <= 9; a++) {
for (int b = 0; b <= 9; b++) {
int n = a * 1100 + b * 11;
double x = sqrt(n);
if (fabs(x - (int)x) < 1e-6) { //完全平方数 用0.000001判断
printf("%d %.0f\n", n, x);}}}}
可以用 对比0.000001 来判断是否为 整数!!!
阶乘之和（末6位）
输入n，计算S=1!+2!+3!+…+n!的末6位（不含前导0）。n≤106。这里，n!表示前n个正整数之积。
样例输入
10
样例输出
37913
完整代码
#include<bits/stdc++.h> //万能头文件
const int M = 1e6;
int main() {
int n;
while (~scanf("%d", &n)) { //可执行多次输入
long long s = 0, f = 1;
for (int i = 1; i <= n; i++) {
f = f * i % M; //i!
s = (s + f) % M; //阶乘和
}
printf("%lld %lld\n", n, s);
}
}
若逐个计算，则会发生乘法溢出，所以：
要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在每步计算之后对n 取余，结果不变。
求c(n,m)=n!/(m!*(n-m)!)
#include<bits/stdc++.h>
typedef unsigned long long ull; //ll 2^63-1>>unsigned 2^64-1 变大一倍
//求阶乘
ull f(int);
int main() {
int n, m;
while (~scanf("%d %d", &n,&m)) {
int x = f(n) / (f(m) * f(n - m));
printf("c(%d,%d) = %d\n", x);
}
return 0;
}
ull f(int n) {
int x = 1;
for (int i = 1; i <= n; i++){
x *= i;
}
return x;
}
孪生素数
#include<cstdio>
#include<iostream> //输入输出流
using namespace std; //使用名字空间std
//判断x是否素数
bool isPrime(int x);
int main() {
int m;
while (cin >> m) //cin是输入流istream类对象，>>是提取运算符，存到m中
{
//从大到小枚举
for (int i = m; i >= 5; i--)
{
if (isPrime(i) && isPrime(i - 2)) {
//cout是输出流ostream类的对象，<<是插入运算符，按顺序输出小的、空格、大的、换行，endl是换行
cout << i - 2 << " " << i << endl; break;
}
}
}
return 0;
}
素数判断可以使用“试除法”：
//函数定义，素数判断
bool isPrime(int x) {
if (x < 2)
{
return false;
}
//试除法
for (int i = 2; i <= x/i; i++)
{
if (x % i == 0) {
return false;
}
}
return true;
}
苹果和虫子
Description
小 B 喜欢吃苹果。她现在有