NOIP要点

1. 关于开long long的事。

一般而言，只要涉及到加法的操作并且$a_i$足够大，那么就要开long long了。

而如果你使用了long long以及printf，记得printf要加%lld。

2. 关于读入加速。

不要使用ios::sync_with_stdio(false)，会出一些奇奇怪怪的bug。

快读的原理是先读入非数字字符如果发现-就当自己读到了负数，负数标记设$-1$（初始值$1$）。然后只要读入的还是数字，那么读入数字部分（初值$0$）乘上$10$加上读入的字符$-48$（-0）。

然后下边是fread板子：

#include <bits/stdc++.h>
using namespace std;
const int N=100001;
struct io{
	char op[N] , * s;
	//数组大小即读入数据量大小 
	io(){
		//一定注意在这里开文件 
		//使用fread时无法从console中输入，请使用文件读入 
		freopen( "test.in" , "r" , stdin );
		freopen( "test.out" , "w" , stdout );
		fread( s = op , 1 , 1 << 26 , stdin );
	}
	inline int read(){
		int u=0;
		while( * s<48 ) s++;
		while( * s>32 ) u=u*10+(*s++)-48;
		return u;
	}
} ip;
#define read ip.read
int main(){
	int a = read() ,b = read();
    printf("%d\n",a+b);
	return 0;
}

然后下边是快读板子（推荐NOIP用这个，因为代码比较短，而且也有效）：

inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}

3. 关于数组最大大小

首先是单个数组绝对不能开在任何函数内。能开全局变量的尽量全局变量。

然后是各个变量的大小（1B=8bit）：

接下来，若$1k=1000B,1M=1000k$，则对于一道128M空间的题目，我们最多开$125000000=1.25=times 10^9$字节的数组，等价于——

• 一个$10^8$字节的bool或char数组，或一个$10^4\times 4$的二维数组
• 一个$10^7$或最多三个$10^6$的int数组，或两个$(5\times 10^3)\times (5\times 10^3)$的二维数组
• 一个$10^6$的long long数组，或一个$(5\times 10^3)\times (5\times 10^3)$的二维数组

最后，一个数组最多能申请$4\times 10^8B$的空间。

并且如果一个函数没有递归内容，可以在函数定义前加上inline，比如inline int abs。

减少递归是省时间/空间的重要方法。

4. 关于图论的存边做法

• 如果题目有明示$n$比较小的（比如$n\le 100$），那么想都别想直接邻接矩阵（存边/遍历所有边/遍历从$n$开始的所有边/找到$a→b$的边的时间复杂度$1,n^2,n,1$，下同）
• 否则的话优先选择邻接表（$1,m,m,m$），然后选择边目录（$1,m,m,m$）。
• 如果要用到最小生成树的话优先选择边目录。

5. BFS时的要点

如果是对于每个点分别做SPFA注意每次BFS前先清空vis数组再将vis[s]设成$1$。

6. 内存的计算方法

如果看到空间限制$<120M$的，就要注意这里。

• 首先是对于每个数组，我们要乘上他的每一位大小（连乘）
• 然后再乘上一个这种类型所对的字节长度

比如int a[1001][1001]的话，它的大小就是$1001\times 1001\times 4\approx 4M$。

再比如bool a[19999][19999]，它的大小是$39996001 B=399M$。

再比如long long f[4][200001]，它的大小是$6400032 B=6M$。

对于内存比较少的题，这三个数组全部会MLE。

记住，你开了多少，这个内存就给你算多少！！！

7. 内存的一些优化方法

• 假如说一道题的数据范围$n\le 100001$，但是你只会$n\le 1001$的部分分，那你的邻接矩阵/耗的比较大的矩阵的大小就开到$1001$。

不要为了多出来的五分而丢了原来的部分分。

• 假如说DP的第$i$状态只能从第$i-1$步的所有状态推出来，那么可以考虑使用滚动数组优化，比如Luogu T142958。
• 在内存很紧的前提下，除非必须开long long，否则千万别开。用不上的话那多出来的空间就是浪费。
• 减少递归，没涉及到递归的函数要在开头加inline。