欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP / ACM 选手必知的编程技巧及常用C++模板

程序员文章站 2022-07-02 20:28:35
...

前言

      平时做题或者比赛掌握一些有用的技巧会方便我们调试,使程序可读性更强,另外模板也比较省时,所以我就从网上整理了一下。

 

重载运算符

重载运算符是通过对运算符的重新定义,使得其支持特定数据类型的运算操作。

有的时候,我们构造了一种新的数据类型(高精度数,矩阵),当然可以将数据类型的运算操作用函数的形式写出来。但采用重载运算符的方式,可以让程序更为自然。

当然,重载运算符在语法上也有一些要求:

重载运算符的一般形式为返回值类型 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 

 

 

相关标签: 技巧