C++竞赛优化技巧与考场实用技巧

标签：实用技巧 10 int 复杂度 C++ 考场使用优化 define

在洛谷观看更加简约哦~：一键直达

距离 2024 CSP/NOIP 已经不远了，在这里，我便分享一下我总结出来的竞赛优化技巧

时间优化

算法/数据结构优化

在处理一些问题，我们可以采用更高效的算法/数据结构来代替低效的算法/数据结构。

例如，你需要多次求一段区间的和时，一般会采用循环直接累加，那么时间复杂度就是 O(N) 。但是如果你采用线段树来解决这个问题，那么时间复杂度就可以降到 O(logN) ，这是质的转变。

再举一个平常的例子，排序，最开始大家学的都是冒泡排序，插入排序。这些排序的时间复杂度为 O(N^2) 。而大家熟知的快排平均时间复杂度为 O(NlogN) 极端情况下为 O(N^2) 。再如桶排序，一般时间复杂度为 O(N)极端情况下时间复杂度为 O(NlogN) $。可以直观的发现不同算法的时间复杂度差异。

除此之外还有查找操作，哈希表比线性搜索更快;频繁插入和删除元素，链表更好等，这里就不再展开了。

输入输出优化

输入优化

在c++中拥有非常多的输入方式，而一般我们使用的输入输出语句，由于设计与安全上的原因，时间复杂度可能会偏高，一般来说，当输入的数据个数超过 $ 10^6 $ 时，如果使用 cin/scanf 语句就会有超时的风险，这时我们可以采用以下方法:

方法1

使用 cin/cout 语句时，我们可以使用以下语句来关闭流同步，加快输入输出速度。

ios::sync_with_stdio(0);
cin.tie(0);

方法2

在 C++ 中读入字符的效率是高于读入整型变量的，所以可以采用读入字符的方式来读入整数。代码如下：

int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

输出优化

与快读一样，也是将整数拆解为字符的形式输出，代码如下：

void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

输出的优化除了快写优化以外，还有一点非常重要，那便是换行方式，一般初学者会使用 endl 来进行换行，但是 endl 效率较低，遇到输出数量大的问题时容易超时，一般我们使用 C语言中的 “\n” 进行换行，用法如下：

cout<<"星月666"<<"\n";
cout<<"星月999\n";
printf("星月awa\n");

其他

namespace FastIO
{
	#define FS 100000
	#define Tp template<typename Ty>
	#define Ts template<typename Ty,typename... Ar>
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	#define D isdigit(oc=tc())
	int ff,OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}struct IO_Cl {~IO_Cl() {clear();}}CL;
	Tp void read(Ty& x) {x=0,ff=1;while(!D) ff=oc^'-'?1:-1;while(x=(x<<3)+(x<<1)+(oc&15),D);x*=ff;}
	Ts void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp void write(Ty x) {while(OS[++OT]=x%10+48,x/=10);while(OT) pc(OS[OT--]);}
	Tp void writeln(Ty x) {write(x),pc('\n');} 
	#undef D
}using namespace FastIO;

//使用示例：read(n,m), read(a[i]), writeln(ans)

机房大佬发的，需要配合 freopen 使用，自己本地编译时无法使用，一般可以在最后加。直接当成函数使用即可，有知道原理的大佬可以私信解释一下(我太菜了)

缓存优化

图的存贮

如果需要保存第 i i i 条边的多个信息时，使用结构体优于使用多个数组存贮，具体使用如下:

//较快
struct node{
	int u,v,w;
}a[100005];
//较慢
const int N=1e5+5;
int u[N],v[N],w[N];

分块离线

对于分块查询等问题，可以将每次查询头尾的块内查询离线下来，可以显著提升程序运行效率。

常数优化

通常来说，乘法慢于加减法,位运算与加减法差不多，除法则远慢于乘法。

STL优化

结论（摘自进阶篇)

STL中通常只有数据结构需要担心性能，sort 等函数性能一般非常优秀，只要不遇到特(du)殊(liu)的数据一般没事，而数据结构，在开启了 O 2 O2 O2 优化后性能有显著提升。
list 性能很差，而且不能满足竞赛中的各种需要，推荐手写链表。
deque 和基于其的 stack,queue 性能较差，如果数据量大尽量避免使用，可使用固定大小的数组替代。
set,map 功能强大，但新能一般，可以使用离散化等离线技巧代替。
unordered_map 比 map 好，但不是很快，可以手写哈希表来代替，可大幅度改善性能。

时间优化总结

实践出真知，刷题量成就大牛。

空间优化

算法

减少 dfs 的使用，dfs使用时会调用栈，占用额外的内存。

数据结构

使用合适的数据结构可以大幅度减小空间的浪费。例如使用哈希表不仅可以节省时间还可以节省空间。

遇到一些数据范围很大，但是数据分布很散的题目，可以使用离散化来减小空间的浪费

其他

尽量减少临时变量的创建，多次利用可利用的临时变量

实用技巧

对拍

随机数据生成

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10000000
int main()
{
	//freopen(".in","r",stdin);
	freopen("data.out","w",stdout);
	mt19937 Rand(time(0));//生成随机种子 在random头文件中 
	cout<<Rand() %MAXN<<" "<<Rand()% MAXN;
	return 0;
}

文件比对（windows)

1.打开 cmd (Win+R 输入 cmd 即可打开)

2.输入 cd /d (文件夹目录地址例:C:\Users\qzez\Desktop\)这是桌面地址

具体格式： cd /d C:\Users\qzez\Desktop\ 即可切换到桌面

3.比较：fc 文件名1 文件名2

如果提示无法打开 - 找不到此类文件或文件夹

请检查以下是否打开了文件扩展名。

文件比对（Linux)

1.打开 bash (不会请百度)

2.输入 cd 目录名 (与windows相同)

3.比较：diff 文件1 文件2

考场注意事项

1.进入考场先试机！否则如果没关还原保护的话，关机就爆零两行泪了！

2.比赛时遇到多组数据一定要记得清零。

3.比赛结束前10分钟不要写代码了，检查一下 freopen 。

4.先看一遍题目，~~防止错过总司令~~，然后先把所有暴力分拿下，不仅时为了最后没时间最准备，也为对拍做了准备。

5.试机结束以后，先把快读，线段树等模板打好，防止比赛时心急遗忘。

6.检查电脑上有无计算器，Excel,画图等实用软件。

7.如果使用了 #define int long long 别忘了看一下 scanf 和 printf 里面有没有改为 lld ！本人吃过亏…

误区

众所周知，CCF的评测机如今已经开启了 O2 优化，所以以前的一些优化，在打开了 O2 优化之后，可以不再使用

-尽量不要使用 intline ,因为其通常会被忽略,有时甚至会降低程序效率，如果你想要强制内联，推荐使用 #define 。

-尽量不要使用 register,在 C++11 其已经被废弃，在 C++17 中，其已经被禁止。

没有必要将 x * 10 写为 (x << 3) + (x << 1)。
对于整数来说，没有必要将 i++ 写为 ++i。
没有必要可以规避高维数组（空间允许的情况下)

总结

编程是练出来的，不是听/看出来的，大家要多刷题，多练习，多比赛增加实战经验。

祝大家 CSP/NOIP 2024 RP++。

本文因为时间仓促，有许多细节之处尚未完善，请诸位OIER踊跃提出，帮助本文更加完善！

本文有很多内容参考了洛谷出品的深入浅出进阶篇，推荐大家看一看，书中内容更加丰富。

参考 & 鸣谢:

深入浅出进阶篇(洛谷教研组出品)

Csdn文献资料

星月工作室洛谷团队全体成员

yummy提出格式修改建议

lzm0107提出生成随机数据代码的建议

标签：实用技巧,10,int,复杂度,C++,考场,使用,优化,define
From： https://blog.csdn.net/daihaoweikevin/article/details/140470181