技巧方法

1.一般用C语言节约空间，要用C++库函数或STL时才用C++;
cout、cin和printf、scanf最好不要混用。
大数据输入输出时最好不要用cin、cout，防止超时。

2.有时候int型不够用，可以用long long或__int64型(两个下划线__)。
介于 -2^63 ( -9,223,372,036,854,775,808) 到2^63-1(+9,223,372,036,854,775,807 )之间的整数
printf("%I64d",a); //__int64 一般VC编译器使用
printf("%lld",a); //long long 一般g++编译器使用

3纯字符串用puts()输出。
数据大时最好用scanf()、printf()减少时间。
先用scanf()，再用gets()会读入回车。所以在中间加一个getchar();
scanf("%c%c",&c1,&c2)会读入空格；建议用%s读取字符串，取第一个字符。

4.读到文件的结尾，程序自动结束
while( ( scanf(“%d”,&a) ) != -1 )
while( ( scanf(“%d”,&a) ) != EOF)
while( ( scanf(“%d”,&a) ) == 1 )
while( ~( scanf(“%d”,&a) )  )
读到一个0时，程序结束
while( scanf(“%d”,&a) ,a)
读到多个0时，程序结束
while( scanf(“%d%d%d”,&a,&b,&c),a+b+c ) //a,b,c非负
while( scanf(“%d%d%d”,&a,&b,&c),a|b|c )

5.数组定义int a[10]={0};可以对其全部元素赋值为0；
数组太大不要这样，防止CE。
全局变量，静态变量自动初始化为0；

6.有很多数学题是有规律的，直接推公式或用递归、循环。

7. 圆周率=acos(-1.0)
自然对数=exp(1.0)

8. 如果要乘或除2^n,用位移运算速度快。a>>n;a<<n;

9.定义数组时，数组大小最好比告诉的最大范围大一点。
字符数组大小必须比字符串最大长度大1。
处理字符数组时不要忘了在最后加'/0'或者0。





11.将乘法转换成加法减少时间
log(a*b)=log(a)+log(b)
将乘法转换成除法防止溢出
a/(b*c)=a/b/c

12.排序要求不高时可以用C++的STL模板函数sort(),stable_sort()
int a[n]={...};
sort(a,a+n);
bool cmp(int m,int n)
{return m>n;
}
sort(a,a+n,cmp);

13.有的题数据范围小但是计算量大可以用打表法
先把结果算出来保存在数组里，要用时直接取出来。

14.浮点数比较时最好控制精度
#define eps 1e-6
fabs(a-b)<eps

15.有些字符串与整型的转换函数是非标准的
可以使用sscanf()和sprintf()代替
sscanf(s,"%d",&n);//从字符串s中读入整数n
sprintf(s,"%d",n);//将n转换为字符串s

freopen(“1.txt”,”r”,stdin);
freopen(“1.txt”,”w”,stdout);

#define max 0x0ffffff;
#define min -0x0ffffff;

如果要乘或除2^n,用位移运算速度快。a>>n;a<<n; 如：求n^m 时间复杂度log(m)
int calc(int n,int m){
int re=1;
while(m){
if(m&1)
re*=n;
n*=n;
m>>=1;
}
return re;
}

习惯使用三目运算符
int max(int a,int b){return a>b?a:b;}
int ***(int m,int n){return n?***(n,m%n):m;}
int abs(int a){return a<0?-a:a;}

16. 大概的计算自己程序的时间的方法：引入头文件：#include<time.h> 
    主函数末尾添加上一句cout<<(double)clock()/CLOCKS_PER_SEC;
但是输入必需重定向，不然会计算输入数据等待时间。

17. runtimeerror 一般这种错误都是下标越界或者是未赋值的变量就直接使用这两种情况，一定要好好排查，不仔细一般找不出来。另外还有在函数内开了一个比较大的数组，使堆栈耗尽所以出错。

浮点数a和b比较大小的时候定义如下：
a = b ? fabs(a – b) < EPS; a < b ? b – a > EPS; a <= b ? b – a > -EPS

别顺手把 -- 写成 ++

int max(int a,int b)
{
    return a>b?a:b;
    //右边为错误样例!!!      a > b? return a: return b;  
}




while (scanf("%d%d", &n, &m), n + m)

1边读边存(适用于求X[m]-X[n] )

士兵杀敌（一）

描述

南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。

小工是南将军手下的军师，南将军现在想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。

注意，南将军可能会问很多次问题。

核心点:

9 for(int i=1;i<=N;++i)

10 {

11 scanf("%d",&sum[i]);

12 sum[i]+=sum[i-1];

13 }

2多情况考虑(尤为输入,输出)

1输入时:

如鸡兔同笼鸡0兔0之类的边界问题

2输出时:

模拟分数加减法

1/8+3/8

1/4-1/2

1/3-1/3

要考虑结果为1 -1 0分子小于0分子%分母==0等多种情况

3可以将二叉树看做一位数组

但如果要判断位置(该行的第几个)则要减去2^row

见猴子下落问题NYOJ 64

4判断字符串中字符频率

1用HASH (如只有小写时HASH[ ch-’a’ ] )

2用SORT (尤其是判断频率最高or最低两者)

见NYOJ62笨小熊

5几乎所有用到贪心算法来解决的题目都用到了sort()

6递归分治O(NlogN)

范围表示，程序用到了左闭右开来表示一个区间，好处是在处理“数组分割”时比较自然：区间[x,y]被分割成[x,m)和(m,y]，不需要再任何地方加减1。另外，空区间表示[x,x)，要比[x,x-1]要顺眼得多。

7m=x+(y-x)/2不被写成m=(x+y)/2，的原因，在数学上他们是相等的，但是在计算机中却有差别。运算符‘/’的“取整”是朝着零方向取整的，而不是向下取整，也就是说5/2=2,-5/2=-2。我们用x+(y-x)/2来确保分界点总是靠近区间起点。这在本题中并不是必要的，但是在二分查找中，却是相当重要的技巧。注：摘自《算法竞赛入门经典》。

7矩形之间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模。如果矩形Ｘ可以嵌套在矩形Ｙ里面，我们就从Ｘ到Ｙ连一条有向边。这个有向图是无环的，也就是说他是一个ＤＡＧ，这样，我们的任务就是求DAG上的最长路径。

8打表法是个好方法

9注意开数组的时候最好开的必要题目要求要大点。

最好在int main外面开数组(在外面定义防止栈溢出)

10技巧while(~scanf("%d",&n))

11再给一个字符串数组赋值的时候，到最后没有给字符串加‘\0’。导致atof()函数没有转化正确。

12做ACM的题目，就是要充分利用题目给出的条件(本题一明确指出输入的只有三个字符)。选择最优算法，而不是最通用的算法。

13至于那个判断条件，一般是if (t % 2 == 1)。

但也可以简化为if (t % 2)

14在寻找最小值的时候不需要记录它的值，只要记录下它的下标就可以。

15 const double eps = 1e-8;

16预处理思想

17文件结束符EOF的值是-1而不是0，所以while(scanf(…)!=0)常常会因为死循环而造成TLE，这个必须牢记。

变量初始化放在循环外(错误)，是一个典型的ACM初级错误

数组越界还能在提交后收到Runtime Error的信息反馈，而运算中的数据溢出则往往只能收到Wrong Answer的错误提示，所以这种错误往往容易被误导成算法问题；数组下标越界是最常见的Runtime Error，

关键就是程序未能及时接收回车符，而误将回车当作下一组数据的首字母，你可以通过添加一句getchar();轻松解决该问题。

题目并没有保证数据是递增的，但人往往有思维定势，而很多题目的设计就是针对这一点！

总结：ACM编程中，使用很大的数组是很常见的做法，但如果超大的数组被定义成局部变量，则很容易出现Runtime Error，解决办法也很简单：定义成全局变量即可。原因是局部变量分配在栈（较小），全局变量分配在堆（较大）；

样本是整数，不等于全部是整数！

原文链接: https://www.cnblogs.com/wwjyt/p/3182920.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍