竞赛常识

博主： RearWaves
发布时间：2023 年 05 月 01 日
358 次浏览
2 条评论
3479字数
分类：算法设计

# 比赛常用技巧及库函数

> **特别声明:** 本博客是我在学习[acwing网站](https://www.acwing.com/)中的算法课程中所记录的笔记, 部分资源来源于网络, 如果有侵权,请及时联系作者删除相关的部分.
> 
> 如果有错误可以私信作者(qq:**1351798781**)进行更改, 非常感谢.
> 
> 欢迎够买[正版ACwing课程](https://www.acwing.com/activity)(不是广告, ACwing没有打钱).

## 1 头文件

### 万能头

```c++
#include <bits/stdc++.h>
```

### 常用头

```c++
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
```

### 数据结构

```c++
#include <queue>
```

### 常用定义

```c++
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
```

## 2 快速读/快速写

### 快读

```c++
template<typename T> inline T read() {
	T x = 0;
	bool flag = 0;
	char ch = getchar();
	while (ch < '0' || ch>'9')
		flag |= (ch == '-'), ch = getchar();
	while (ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return flag ? -x : x;
}
```

### 快写

```c++
template<typename T> inline T write(T x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
```

### 使用方法

```c++
int / ll / __int128 a = read<int / ll / __int128>()
write<int / ll / __int128>(a);
```

## 3 火车头

### 优化

```c++
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
```

### C++加速

```c++
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    ......
}
```

# 算法正确性检验

## 对拍

对拍就是当你写完一个代码, 你想要验证它是否是正确的,  但是单单手造样例或者看题目上的样例往往不一定能发现错误, 而且十分繁琐. 所以我们可以依靠强大的计算机来帮助我们检验程序的正确性.

接下来来讲一下对拍是如何实现的. 我们以a+b问题为例:

首先std是我们写的程序(可能有错误).

```c++
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	if (a % 20 == 0) a++;
	cout << a + b;
	return 0;
}
```

然后我们再写一个程序bs, 一般是暴搜等暴力程序, 但一定要确保这个程序是没有错误的.

```c++
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	int ans = 0;
	while (a--) ans++;
	while (b--) ans++;
	cout << ans;
	return 0;
}
```

我们再写一个数据生成器data, 利用系统里的随机数来生成随机数据.

```c++
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
	srand(time(0));
	rand();
	printf("%d %d\n", rand(), rand());
	return 0;
}
```

最后我们写一个程序“对拍”.

```c++
#include <cstdio>
#include <cstdlib>
using namespace std;
int main() {
	for (int i = 1; i < 100; i++) {
		// 把随机数据生成器生成树数据导入到in.txt里
		system("data.exe > in.txt");
		// 把in.txt里的数据导入到我们写的更优的但是可能有错误的那个std程序
		// 然后把std程序的结果导入到out.txt里
		system("std.exe < in.txt > out.txt");
		// 我们再按照同样的方式把那个暴力程序跑一边 存储结果到ans.txt
		system("bs.exe < in.txt > ans.txt");
		// 比对out.txt和ans.txt这两个输出数据是否相同
		if (system("fc out.txt ans.txt"))
			return 1;	//异常返回, 程序就会自动停止告诉你出现了错误
	}
	return 0;
}
```

然后我们就发现 我们的a+b程序出现了问题: 暴力程序算出的正确答案是39268, 而我们写的程序得出的答案是39269 比正确答案多了1. 然后我们再回到我们的那个文件夹里瞅一瞅.

# 骗分技巧

## 猜测答案

无解情况:

```c++
printf("-1");
```

测试数据包含样例.

听天由命:

```c++
#include<stdlib.h>
#include<time.h>
//以上两个头文件必须加
srand(time(NULL));	//输出随机数前执行次语句
printf("%d", rand() % X);	//输出0~X-1的随机整数
```

## 得分技巧

写暴力.

打表找规律: 先暴力算出来, 然后放在答案数组里面提交.

## 贪心的算法

想不到DP, 用贪心拿到部分分数.

一般ACM或者笔试题的时间限制是1秒或2秒.
在这种情况下, C++代码中的操作次数控制在 107∼108107∼108 为最佳.

下面给出在不同数据范围下, 代码的时间复杂度和算法该如何选择:

1. $n≤30$, 指数级别, dfs+剪枝, 状态压缩dp
2. $n≤100 => O(n^3)$, floyd, dp, 高斯消元
3. $n≤1000 => O(n^2), O(n^2logn)$, dp, 二分, 朴素版Dijkstra、朴素版Prim、Bellman-Ford
4. $n≤10000 => O(n∗\sqrt{n})$, 块状链表、分块、莫队
5. $n≤100000 => O(nlogn)$ => 各种sort, 线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
6. $n≤1000000 => O(n)$, 以及常数较小的 O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集, kmp、AC自动机, 常数比较小的 O(nlogn) 的做法: sort、树状数组、heap、dijkstra、spfa
7. $n≤10000000 => O(n)$, 双指针扫描、kmp、AC自动机、线性筛素数
8. $n≤10^9 => O(\sqrt{n})$, 判断质数
9. $n≤10^{18} => O(logn)$, 最大公约数, 快速幂, 数位DP
10. $n≤10^{1000} => O((logn)^2)$, 高精度加减乘除
11. $n≤10^{100000} => O(logk×loglogk)$, k表示位数, 高精度加减、FFT/NTT

## 注意事项

大模拟,计算几何,数据结构一定最后写.

字符串处理:

```c++
#include<sstream>
using namespace std;
int main() {
	stringstream ssin;	//从字符串中读取任何类型
	sscanf(str.c_str(), "%04d%02d", &year, &month);;
	sprintf(str, "%04d%02d", year, month);
	string s;
	s.substr(4, 3);	//返回s从4开始长度为3的子串
	s.substr(4);	//返回s从4开始到最后的子串
	strstr();	//O(n)的kmp
    s.find("yxc");	//O(n^2)级别的查找
    stoi();		//string to int
    stoll();	//string to long long
    stof();		//string to float
    stod();		//string to double
    atoi();atoll();atof();		//char str[N] to...
	return 0;
}
```

```c++
isdigit('a');	//判断一个字母是不是数字
tolower();toupper();
s.c_str();	//string变成字符数组, 返回指针
```

常见优化:

```c++
inline		//非递归函数加
register
```

运行错误: 数组越界,函数递归次数太多.

# 第七章 时空复杂度分析

C++语言1秒可以计算$10^7 - 10^8$次.

**下面给出在不同数据范围下, 代码的时间复杂度和算法该如何选择: **

1. $n≤30$, 指数级别, dfs+剪枝, 状态压缩dp
2. $n≤100 \to O(n^3)$, floyd, dp, 高斯消元
3. $n≤1000 \to O(n^2), O(n^2logn)$, dp, 二分, 朴素版Dijkstra、朴素版Prim、Bellman-Ford
4. $n≤10000 \to O(n∗\sqrt{n})$, 块状链表、分块、莫队
5. $n≤100000 \to O(nlogn)$,各种sort, 线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
6. $n≤1000000 \to O(n)$, 以及常数较小的 O(nlogn) 算法: 单调队列、 hash、双指针扫描、并查集, kmp、AC自动机, 常数比较小的 O(nlogn) 的做法: sort、树状数组、heap、dijkstra、spfa
7. $n≤10000000 \to O(n)$, 双指针扫描、kmp、AC自动机、线性筛素数
8. $n≤10^9 \to O(\sqrt{n})$, 判断质数
9. $n≤10^{18} \to O(logn)$, 最大公约数, 快速幂, 数位DP
10. $n≤10^{1000} \to O((logn)^2)$, 高精度加减乘除
11. $n≤10^{100000} \to O(logk×loglogk)$, k表示位数, 高精度加减、FFT/NTT

## 时间复杂度分析

1. 纯循环
2. 递归:主定理

不过, 并非所有递推关系式都可应用主定理. 该定理的推广形式包括Akra-Bazzi定理.

假设有递推关系式 $T(n)=a T\left(\frac{n}{b}\right)+f(n)$ , 其中 $n$ 为问题规模,  $a$ 为递推的子问题数量,  $\frac{n}{b}$ 为每个子问题的规模 (假设每个子问题的规模基本一样),  $f(n)$ 为递推以外进行的计算工作.

$a \geq 1$ , $b>1$ 为常数,  f(n) 为函数,  T(n) 为非负整数. 则有以下结果 (分类讨论):

- 若 $f(n)=O\left(n^{\log _{b} a-\varepsilon}\right), \varepsilon>0$, 那么 $T(n)=\Theta\left(n^{\log _{b} a}\right)$;
- 若 $f(n)=\Theta\left(n^{\log _{b} a}\right)$, 那么 $T(n)=\Theta\left(n^{\log _{b} a} \log n\right)$;
- 若 $f(n)=\Omega\left(n^{\log _{b} a+\varepsilon}\right), \varepsilon>0$, 且对于某个常数 $c<1$ 和所有充分大的 $n$ 有 $a f\left(\frac{n}{b}\right) \leq c f(n)$, 那么  $(n)=\Theta(f(n))$.

## 空间复杂度分析

1 Byte = 8 bit; 1 KB = 1024 Byte; 1 MB = 1024 × 1024 Byte.

int 4 Byte; char 1 Byte; double, long long 8 Byte; bool 1 Byte.

64 MB = 2^26 Byte = 1.6e7 int.

递归也是需要空间的, 快排: O(logn)

最后修改：2023 年 05 月 01 日

如果觉得我的文章对你有用，请随意赞赏

2 条评论

igbbiexfym
October 4th, 2024 at 09:07 pm

想想你的文章写的特别好https://www.ea55.com/

回复
oinuopwbvd
October 1st, 2024 at 08:42 pm

想想你的文章写的特别好https://www.237fa.com/

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

贪心讲解
评论数： 6
搜索初步
评论数： 5
图论初步
评论数： 4
欢迎使用 Typecho
评论数： 2
比赛常用技巧及库函数
评论数： 2

dvlafvodtu
看的我热血沸腾啊www.jiwenlaw.com
usukxmmttv
不错不错，我喜欢看 www.jiwenlaw.com
dcyfmsthoa
想想你的文章写的特别好www.jiwenlaw.com
jbbnknwfgc
想想你的文章写的特别好https://www.ea55.com/
igbbiexfym
想想你的文章写的特别好https://www.ea55.com/

比赛常用技巧及库函数
评论数： 2
图论初步
评论数： 4
欢迎使用 Typecho
评论数： 2
基础算法初步
评论数： 0
竞赛常识
评论数： 2

竞赛常识

RearWaves • 2023 年 05 月 01 日

# 比赛常用技巧及库函数

## 1 头文件

### 万能头

```c++
#include <bits/stdc++.h>
```

### 常用头

```c++
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
```

### 数据结构

```c++
#include <queue>
```

### 常用定义

```c++
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
```

## 2 快速读/快速写

### 快读

### 快写

```c++
template<typename T> inline T write(T x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
```

### 使用方法

```c++
int / ll / __int128 a = read<int / ll / __int128>()
write<int / ll / __int128>(a);
```

## 3 火车头

### 优化

```c++
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
```

### C++加速

```c++
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    ......
}
```

# 算法正确性检验

## 对拍

接下来来讲一下对拍是如何实现的. 我们以a+b问题为例:

首先std是我们写的程序(可能有错误).

```c++
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	if (a % 20 == 0) a++;
	cout << a + b;
	return 0;
}
```

然后我们再写一个程序bs, 一般是暴搜等暴力程序, 但一定要确保这个程序是没有错误的.

```c++
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	int ans = 0;
	while (a--) ans++;
	while (b--) ans++;
	cout << ans;
	return 0;
}
```

我们再写一个数据生成器data, 利用系统里的随机数来生成随机数据.

```c++
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
	srand(time(0));
	rand();
	printf("%d %d\n", rand(), rand());
	return 0;
}
```

最后我们写一个程序“对拍”.

# 骗分技巧

## 猜测答案

无解情况:

```c++
printf("-1");
```

测试数据包含样例.

听天由命:

```c++
#include<stdlib.h>
#include<time.h>
//以上两个头文件必须加
srand(time(NULL));	//输出随机数前执行次语句
printf("%d", rand() % X);	//输出0~X-1的随机整数
```

## 得分技巧

写暴力.

打表找规律: 先暴力算出来, 然后放在答案数组里面提交.

## 贪心的算法

想不到DP, 用贪心拿到部分分数.

一般ACM或者笔试题的时间限制是1秒或2秒.
在这种情况下, C++代码中的操作次数控制在 107∼108107∼108 为最佳.

下面给出在不同数据范围下, 代码的时间复杂度和算法该如何选择:

## 注意事项

大模拟,计算几何,数据结构一定最后写.

字符串处理:

```c++
isdigit('a');	//判断一个字母是不是数字
tolower();toupper();
s.c_str();	//string变成字符数组, 返回指针
```

常见优化:

```c++
inline		//非递归函数加
register
```

运行错误: 数组越界,函数递归次数太多.

# 第七章 时空复杂度分析

C++语言1秒可以计算$10^7 - 10^8$次.

**下面给出在不同数据范围下, 代码的时间复杂度和算法该如何选择: **

## 时间复杂度分析

1. 纯循环
2. 递归:主定理

不过, 并非所有递推关系式都可应用主定理. 该定理的推广形式包括Akra-Bazzi定理.

$a \geq 1$ , $b>1$ 为常数,  f(n) 为函数,  T(n) 为非负整数. 则有以下结果 (分类讨论):

## 空间复杂度分析

1 Byte = 8 bit; 1 KB = 1024 Byte; 1 MB = 1024 × 1024 Byte.

int 4 Byte; char 1 Byte; double, long long 8 Byte; bool 1 Byte.

64 MB = 2^26 Byte = 1.6e7 int.

递归也是需要空间的, 快排: O(logn)

2 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

竞赛常识

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款