NOIP / ACM 选手必知的编程技巧及常用C++模板
前言
平时做题或者比赛掌握一些有用的技巧会方便我们调试，使程序可读性更强，另外模板也比较省时，所以我就从网上整理了一下。
重载运算符
重载运算符是通过对运算符的重新定义，使得其支持特定数据类型的运算操作。
有的时候，我们构造了一种新的数据类型（高精度数，矩阵），当然可以将数据类型的运算操作用函数的形式写出来。但采用重载运算符的方式，可以让程序更为自然。
当然，重载运算符在语法上也有一些要求：
重载运算符的一般形式为返回值类型 operator 运算符(参数,…)
在结构体内部重载运算符时，括号内的参数会少一个（事实上，另外一个参数是this指针，即指向当前参数的指针（这个不重要啦，你只需要知道就好）），也就是说，两元运算符只需要1个参数。（在结构体外部定义时，两元运算符还是需要2个参数）
其他要求就和普通函数的要求差不多了。
#include <stdio.h>
struct pair_num//一个二元组类型
{
int x,y;
pair_num operator +(pair_num a)const //不加const会CE
{
pair_num res;
res.x=x+a.x;//x事实上是this.x
res.y=y+a.y;
return res;
}
pair_num operator -(pair_num a)const
{
pair_num res;
res.x=x-a.x;
res.y=y-a.y;
return res;
}
bool operator <(pair_num a)const //sort,set等数据结构需要使用小于号
{
return x<a.x||(x==a.x&&y<a.y);
}
}a,b,res;
pair_num operator *(pair_num a,pair_num b)//在结构体外部定义时，不要加const
{
pair_num res;
res.x=a.x*b.x;
res.y=a.y*b.y;
return res;
}
int main()
{
scanf("%d%d",&a.x,&a.y);
scanf("%d%d",&b.x,&b.y);
res=a+b;
printf("%d %d\n",res.x,res.y);
res=a-b;
printf("%d %d\n",res.x,res.y);
res=a*b;
printf("%d %d\n",res.x,res.y);
return 0;
}
namespace的用法
在C++程序中，我们往往会加上using namespace std;这一行语句，那么它是干嘛的呢？
事实上，C++引入了一个叫做名字空间(namespace)的机制。引入这个机制的目的，是为了解决程序中变量/函数名重复的问题。
举个栗子：我写了一个solve()函数，另外一个人也写了一个solve()函数，如果把这两个函数放在一个程序里面，就会出现函数重名的问题。这时，我可以把我的solve()函数放在namespace code1中，把另外一个人的solve()放在namespace code2当中，然后，通过code1::solve();语句就可以调用我写的solve()函数，code2::solve()可以调用另外一个人的solve()函数。
写成代码大概是这样的：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
long long n,m,a[100005],p[100005],aw[100005],atk[100005];
namespace one_game
{
//其实namespace里也可以声明变量
//这个例子还没有体现出namespace的强大
//不过我们几乎不写工程代码，所以也无所谓了，这只是个例子
void solve()
{
for(int y=0;;y++)
if((a[1]+p[1]*y)%atk[1]==0)
{
cout<<(a[1]+p[1]*y)/atk[1]<<endl;
return;
}
}
}
namespace p_1
{
void solve()
{
if(atk[1]==1)//solve 1-2
{
sort(a+1,a+n+1);
cout<<a[n]<<endl;
return;
}
else if(m==1)//solve 3-4
{
long long k=atk[1],kt=ceil(a[1]*1.0/k);
for(int i=2;i<=n;i++)
k=aw[i-1],kt=max(kt,(long long)ceil(a[i]*1.0/k));
cout<<k<<endl;
}
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(a,0,sizeof(a));
memset(p,0,sizeof(p));
memset(aw,0,sizeof(aw));
memset(atk,0,sizeof(atk));
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>p[i];
for(int i=1;i<=n;i++)
cin>>aw[i];
for(int i=1;i<=m;i++)
cin>>atk[i];
if(n==1&&m==1)one_game::solve();//solve 8-13
else if(p[1]==1)p_1::solve();//solve 1-4 or 14-15
else cout<<-1<<endl;
}
return 0;
}
事实上，C++标准库把所有的函数都放在了namespace std当中，所以我们调用这些函数的时候，应该采用std::xxx的形式来调用标准库中的函数。当然，在加入using namespace std;一行后，就可以省略std::了，我们就可以偷懒了。（其实using namespace std;在工程上不推荐使用，但各位OIer们平时使用也没有什么问题）
当然，我们在比赛的时候，可以通过使用namespace来使我们的程序结构更加规整。比较常见的用法就是针对每个子任务（诸如上面的屠龙勇士），各写一个namespace，在其中定义我们解决该子任务所需要的变量与函数，这样各个子任务间互不干扰，方便了我们这些蒟蒻们骗分，也降低了正解爆炸的分数损失。
善用标识符进行调试
我们在本地测试的时候，往往要加入一些调试语句。要提交到OJ的时候，就要把他们全部删除，有些麻烦。
我们可以通过定义标识符的方式来进行本地调试。
大致的程序框架是这样的：
#define DEBUG
#ifdef DEBUG
//do something
#endif
// or
#ifndef DEBUG
//do something
#endif#ifdef会检查程序中是否有通过#define定义的对应标识符，如果有定义，就会执行下面的内容，#ifndef恰恰相反，会在没有定义相应标识符的情况下执行后面的语句。
我们提交程序的时候，只需要将#define DEBUG一行注释掉即可。
当然，我们也可以不在程序中定义标识符，而是通过-DDEBUG的编译选项在编译的时候定义DEBUG标识符。这样就可以在提交的时候不用修改程序了。
对拍
有的时候我们写了一份代码，但是不知道它是不是正确的。这时候就可以用对拍的方法来进行检验或调试。
什么是对拍呢？具体而言，就是通过对比两个程序的输出来检验程序的正确性。你可以将自己程序的输出与其他程序（打的暴力或者其他dalao的标程）的输出进行对比，从而判断自己的程序是否正确。
当然，我们不能自己比对两段程序的输出，所以我们需要通过批处理的方法来实现对拍的自动化。
具体而言，我们需要一个数据生成器，两个要进行对拍的程序。
每次运行一次数据生成器，将生成的数据写入输入文件，通过重定向的方法使两个程序读入数据，并将输出写入指定文件，利用Windows下的fc命令比对文件（Linux下为diff命令），从而检验程序的正确性。
如果发现程序出错，可以直接利用刚刚生成的数据进行调试啦。
对拍程序的大致框架如下：
#include <stdio.h>
#include <stdlib.h>
int main()
{
//For Windows
//对拍时不开文件输入输出
//当然，这段程序也可以改写成批处理的形式
while(1)
{
system("gen > test.in");//数据生成器将生成数据写入输入文件
system("test1.exe < test.in > a.out")//获取程序1输出
system("test2.exe < test.in > b.out")//获取程序2输出
if(system("fc a.out b.out"))
{
//该行语句比对输入输出
//fc返回0时表示输出一致，否则表示有不同处
system("pause")//方便查看不同处
return 0;
//该输入数据已经存放在test.in文件中，可以直接利用进行调试
}
}
}
写数据生成器的几个小提示
在使用rand()前，别忘了调用srand(time(NULL))来重置随机数种子。（不重置的话，每次调用rand()只会得到一套随机数）
rand()的生成随机数范围在Windows下为 [0,32767] ，在Linux下为 [0,2^{31}-1] ，所以如果数据过大，最好手写一个随机数生成器。
小技巧：
打的代码最好不要删除，用//注释掉是一个更好的主意，说不定以后要用。
输出64位整数时请记得使用%lld！（当然也可以使用cin/cout来解决这个问题，别忘了加上ios::sync_with_stdio(false);防止IO耗时过久）
别忘了算内存，有可能你不小心多输了一个0就MLE了。（一般情况下，256M内存的话，int数组最多可以开到 5 * 10^7 ）
模板
#include<bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1 | 1
#define ffr(i,x,y) for(int i=(x),_en=(y);i<=_en;i++)
#define rff(i,x,y) for(int i=(x),_en=(y);i>=_en;i--)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
const int maxn=1005,inf=1<<29,mod=1000000007;
const double pi=acos(-1.0);
bool sf(int &x){return scanf("%d",&x)==1;}
bool sf(ll &x){return scanf("%I64d",&x)==1;}
bool sf(double &x){return scanf("%lf",&x)==1;}
bool sf(char &x){return scanf("%c",&x)==1;}
bool sf(char *x){return scanf("%s",x)==1;}
bool sf(string &x){return cin>>x;}
template<class T>inline void sf2(T&num){
num=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
num*=f;
}
void pf(int x,int op){op==0?printf("%d",x):printf("%d%c",x,op==1?' ':'\n');}
void pf(ll x,int op){op==0?printf("%I64d",x):printf("%I64d%c",x,op==1?' ':'\n');}
void pf(char x,int op){op==0?printf("%c",x):printf("%c%c",x,op==1?' ':'\n');}
void pf(char *x,int op){op==0?printf("%s",x):printf("%s%c",x,op==1?' ':'\n');}
void pf(string x,int op){op==0?cout<<x:cout<<x<<(op==1?' ':'\n');}
inline int gcd(int x,int y){if(!x)return y;return gcd(y%x,x);}
inline int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=(ll)x*x%p)if(k&1)res=(ll)res*x%p;return res;}
int n,m,k;
int dp[maxn][maxn],a[maxn][maxn];
int dir[][2]={{0,1},{-1,0},{0,-1},{1,0},{-1,1},{-1,-1},{1,-1},{1,1}};
int main()
{
return 0;
}解释
对于代码段：
#include<bits/stdc++.h>
bits/stdc++.h这个头文件，号称是包含所有C++头文件的头文件，只能说666666，不过有些OJ可能不支持哦，正规比赛最好老老实实地一个个头文件敲吧。
对于代码段：
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1 | 1
这两个宏定义是为了计算树里面左右儿子节点。在线段树里用的比较多，比如当前节点维护的是[l,r]，令m=(l+r)/2，那么左儿子维护的是[l,m]，右儿子维护[m+1,r]。
对于代码段：
#define ffr(i,x,y) for(int i=(x),_en=(y);i<=_en;i++)
#define rff(i,x,y) for(int i=(x),_en=(y);i>=_en;i--)
#define clr(f,z) memset(f,z,sizeof(f))
有木有觉得写for循环很累，从现在起，比如你要写for(int i=0;i<=10;i++) 只需要写成ffr(i,0,10)就可以了，是不是省了不少力？
rff刚好是个倒序循环。
对于ACM，经常要多组输入，那很多时候，变量啊，数组啊就要清空初始化，那就要用memset，代码贼长，现在，有了这个宏定义，比如要把数组a（不管几维都可以）清空，那就可以clr(a,0)或者clr(a,-1)，贼方便，同时要注意，z的值只能是0或者-1哦，这是因为memset这个函数只能把数组每个元素搞成0或者-1，因为0的二进制补码表示是全0,-1的二进制补码表示是全1，重置起来方便嘛。那如果你要重置成某个特定的别的值，就要么就自己循环重置，要么就用C++里的fill函数。
代码段：
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
就是定义各种类型的缩写，有些类型太长了，写起来都不太愿意，而且DEV又没有什么代码自动补全。
比较常用的就是long long，比如之前定义这个类型要long long a=1;现在只要ll a=1;就行了，贼方便。接下来看代码段：
const int maxn=1005,inf=1<<29,mod=1000000007;
const double pi=acos(-1.0);
定义了一些常用的常量，比如用来表示数组的最大值的maxn,无穷大inf，还有表示模的mod，以及π的精确表示pi。
接下来的代码段：
bool sf(int &x){return scanf("%d",&x)==1;}
bool sf(ll &x){return scanf("%I64d",&x)==1;}
bool sf(double &x){return scanf("%lf",&x)==1;}
bool sf(char &x){return scanf("%c",&x)==1;}
bool sf(char *x){return scanf("%s",x)==1;}
bool sf(string &x){return cin>>x;}
利用函数重载把常见的一些数据类型进行了读取。函数传的是引用，返回值代表有没有数据读入，这在多组输入中有用。
然后接下来的代码段：
template<class T>inline void sf2(T&num){
num=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
num*=f;
}
这是个读入函数，优点是比前面的读入快，特别是输入数据量比较大的时候就能体现出它的价值了，可以叫它“读入外挂”。利用模板template来接受任何类型的参数，当然函数内的实现决定了，这只对整数有用。
接下来的代码段：
void pf(int x,int op){op==0?printf("%d",x):printf("%d%c",x,op==1?' ':'\n');}
void pf(ll x,int op){op==0?printf("%I64d",x):printf("%I64d%c",x,op==1?' ':'\n');}
void pf(char x,int op){op==0?printf("%c",x):printf("%c%c",x,op==1?' ':'\n');}
void pf(char *x,int op){op==0?printf("%s",x):printf("%s%c",x,op==1?' ':'\n');}
void pf(string x,int op){op==0?cout<<x:cout<<x<<(op==1?' ':'\n');}
利用函数重载实现各种各样的常用输出。
op是控制输出变量后面跟的是什么，0代表什么都不跟，1代表跟空格，2代表跟换行。
接下来的代码段：
inline int gcd(int x,int y){if(!x)return y;return gcd(y%x,x);}
inline int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=(ll)x*x%p)if(k&1)res=(ll)res*x%p;return res;}
gcd函数用来求两个数的最大公约数，power用来求快速幂x^k%p。这两个函数在数论中经常用到。
接下来的代码段：
int n,m,k;
int dp[maxn][maxn],a[maxn][maxn];
int dir[][2]={{0,1},{-1,0},{0,-1},{1,0},{-1,1},{-1,-1},{1,-1},{1,1}};
n,m,k是常用的变量，dp,a是常用数组，dir是常用方向数组。在搜索里面用得比较多，用来向相邻的八个方向扩散。
来源
洛谷日报#86
你迎哥哥 https://blog.csdn.net/u013615904/article/details/80310016
上一篇： Vue2数据双向绑定原理
下一篇： Vue2的数据劫持,Vue3的数据劫持