算法竞赛偷分技巧

读取第k位：a>>k&1读取第k位并取反：心a>>k&1将第k位清0：a&=(1<< k)将第k位置1：a|=1<< k将第k位取反：a^=1<< k将第k1~k2位反转：a^=((1<< (k2-k1+1))-1)<< k2是否恰好只有一个true:!(x&(x-1))&&x判断是否有两个相邻的true:X>>1&X是否有三个相邻的txue:X>>1&X>>2&X

char c[100000]; //尽量避免“用多少开多少”，要留出少量空闲，以免数组越界 int x[300]={0}; //注意变量赋初值，除非循环变量、临时变量，尽量赋为零 l=strlen(c);

//将多次用到的表达式、函数存在变量中，避免重复计算 if(tt==l)

//首先解决“平凡问题4”，也是易出错的问题，尽量特殊处理 避免无效枚举 在外层循环过程中判断可能性 尤其是反复调用函数，会增加不必要的时 间开销。所以，一些简单的功能尽量在一个函数或主程序内完成，不要使用过多的函数；

涉 及全局的变量不要在函数调用时由接口给出，再返回值，尽量使用全局变量 盲目开大数组、高维数组，程序运行起来动辄 20M， 是完全没有必要的。尤其是盲目开高维数组，还会造成时间复杂度的升高 （1）INT（long）类型占 4 字节 （2）Long long int 或 int64 类型占 8 字节 （3）一个 int a[1000000]的数组占 4M，通常空间限制为 64M 时，最多开 15 个这样的 数组。若要开规模为 10000000 的 int 数组，占用达到 40M，一定只允许一个。 （4）一个 int a1000的二维数组同样占 4M。一个 int a2000的二维数组占 16M，最多开 3 个。二维数组最多允许 30003000 的规模，且只有一个。 （5）在使用空间时，一定要留出 10M 左右的空闲空间，不要将允许空间挤满，在大内 存程序调试时可以使用工具查看内存实际占用情况，不要铤而走险打“擦边球”。 不可能只有一个数组占用内存，要综合考虑整个程序。 （6）如果是允许 256M 内存，一维数组最多到 510^7，即 int a[50000000]，如果两个最多到 310^7。二维数组最多开到 int a7500，或两个 5000*5000 的数组。 这里的计算都考虑了余量，不能紧逼上限，以免发生意外。

（1）将二维带参变量的数组用结构体一维数组代替 （2）使用滚动数组，将无用的空间及时释放 （3）高精度运算尽量在原数基础上运算 （4）搜索时在原来状态基础上修改，少引入中间状态、临时状态 （5）队列使用循环队列，采用“MOD 队列长”的办法解决，不要只有 begin, end 两个 指针，造成使用过的空间浪费。尤其是广度优先搜索中注意。 （6）少使用链表等非线性结构，减少定位域的个数 在避免数组越界方面，尽量遵守这些规则：

（1）数组规模比测试数据的最大规模略大，如 n=10000 的试题，数组可以开到 10005 （2）尤其是 C 语言，减少 0 位的使用（高精度运算除外），从 1 使用到 n，符合自然思 考习惯，便于输入输出，不易出现数组元素正负 1 的问题，并以 0 位置为“哨兵”， 放上 0 或者特殊标记，既不会在状态转移时出现数组越界，又避免了初始位置的 特殊讨论，何乐而不为？ （3）在定义数组时为今后的编程提供方便，减少特殊情况数，而不是到具体处理时再 解决边界问题、特殊处理问题，这样既浪费时间又容易出错

降低编程复杂度，这里给出笔者的几条经验：

（1）减少使用指针，尽量使用数组 （2）保持程序逻辑清楚，变量名、函数名明确 （3）定义常量，将最大规模、MAXINT、数学常数等用#define 或 const 预定义。 （4）注意缩进，层次清晰 （5）对于复杂的分类问题，将各种类别表示在数组中，使用循环进行统一判断，而不 是分别判断处理。例如走棋盘类问题中四个方向的处理，表达式处理中的不同运 算符，搜索问题中的相似选择支，模拟类问题中的数据读入、不同操作符数学模 型的转化，字符串处理中的功能相似的符号，都应该在数组中进行归类处理，这 样程序的可移植性增强，可以快速添加、删除、修改类别，便于调试时对不同类别同时修改，还不容易出错

模块化思想 （1）将程序的各大功能板块，如输入、运算、输出分开编写。 （2）每一个部分解决一个问题，不要“眉毛胡子一把抓”，尽量保持各个部分之间的独 立性，尤其是变量不要反复引用，平行的中间变量尽量不要重叠，在程序段的开 始时注意初始化（尤其是最大最小值之类）。 （3）将一些成型的、经典的算法在考前练习熟练，考试时直接用函数写出来，不需要 再多考虑、调试。包括排序、并查集、基本数学算法等，在本文“应该学习的内 容”中有所介绍。 （4）这里要指出，模块化不是将一些较小的、反复用到的函数单独拿出来，因为这样 虽然逻辑清晰，但损失了时间复杂度，可以使用 Ctrl+C 的办法解决，反正源代码 的长度是没有限制的

int t,i,l1,l2,s1,s2,s3;//变量名简单清楚，易于编程 多组测试数据的问题注意初值，可以在循环内定义变量 l1=a[0]>b[0]?a[0]-b[0]:b[0]-a[0];//采用问号表达式，避免函数调用 l2=a[1]>b[1]?a[1]-b[1]:b[1]-a[1];//预处理一些常用的取值 s1=l1>l2?l1:l2;//抓住特殊性 if(l1==0&&l2= =0)//先进行特殊情况处理，避免边界错误