ACM程序设计基础

ACM程序设计基础判题•线上判题系统（OJ，OnlineJudge）–POJ–ZOJ–…•线下判题系统–PC2判题结果•ACAccepted•WAWrongAnswer•TLETimeLimitedExceed•MLEMemoryLimitedExceed•PEPresentationError•CECompilationError•RTERun-timeErrorPC2•RTE经常被误报为TLE或者contactstaff•没有内存限制（4G）•PE不可以自动判断比赛排名方法•回答正确的题数越多的越靠前；•回答正确的题数相同，则小分越小的越靠前；•小分等于每个答对题目的小分和，每个答对的题目的小分=第一次答对的使用时间（分钟）+20*本题错误提交的次数。•对于已经正确的题目再次提交，但答案如果错误也会算作一次错误的提交，答案如果正确则这次提交不计算在内。避免编译错误•使用标准函数，不要使用非ANSI标准函数•除非组委会说明，否则不要使用文件输入输出（OJ一般都不容许）•不要使用conio.h忘记算法的最优化•比赛时不要去寻找最优的算法•第一个想到的，可以AC的算法是最好的算法•AC了的题目不要去想再优化题目都长一样高！•题目不分难易，分值都是一样，所以先做容易的，小分越小，排名越前•查看排名，可以发现其他人做了什么，题目的相对难易程度，有没有陷阱。仔细读题，谋定后动•出题的人都是邪恶的！•请仔细读题，看错题目无论怎么做都不会对的，花5分钟仔细读题比错一次罚20分钟强！•细节决定成败！让代码简单明了•想怎么精简代码的时间比写这些代码用的时间长！•能不用指针就不要用•请将复杂的符合语句变成等价的若干条简单语句•避免条件表达式？：•不要使用名字相近的变量名，所有的变量名都不一样。•时间永远比空间珍贵！让代码简单明了•避免使用动态的内存分配•STL（StandardTempleteLibrary）会简化代码，但不要滥用•不要混用C和C++的输入和输出•大的数组请定义为全局的•递归程序请注意递归层数•数据精度问题•严格按输出的格式输出，不要多打一个字符比赛所需的能力•一门熟练的编程语言•分辨题目所属类型的能力•掌握算法的能力•分析算法的能力•算法实现的能力•Teamwork•超强的心理•良好的比赛策略你不是超人！•Teamworkismostimportant!•良好的沟通能力–能正确而清晰的叙述自己的想法–能快速地理解他人的想法•比赛是三个人的！找到自己的位置•找清楚自己的定位，强化自己的专长•搞清楚自己的实力，确定实际的目标•为这个目标定下正确的策略•不要希望奇迹的发生输入输出•知道输入数据组数nscanf(“%d”,&n);whlie(n--){这里处理每一组输入.然后直接按格式输出,没必要开数组存储答案。注意初始化。}•cinn;while(n--){}输入输出•没有数据总数,以EOF结束可能用的几个函数:scanf():while(scanf(%d)!=EOF){处理每一组数据,并输出.}•while(cinn){•}•getchar():读入一个字符whlie((ch=getchar())!=EOF){}•while(cinch){}•gets():读入一行while(gets(buf)!=NULL){}用getchar注意读入换行符.•cin读字符串时遇到空白符（空格，换行等）结束charstr[BUFFER];while(cinstr){}getline读字符串时遇到换行符结束,用于读一整行charstr[BUFFER];while(cin.getline(str,BUFFER)){}stringstr;while(getline(cin,str)){}输入输出•以0或-1结束的输入.while(scanf(%d,&n),n!=0){}输入输出•cin,cout没有使用缓冲区，速度比scanf，printf慢，如果有huge的数据可能会TLE•putchar/getchar比printf/scnaf快•不要混合使用cin，cout和scanf，printf，putchar，getchar。•不要输出多余的空格和空行qsort•一、对int类型数组排序intnum[100];Sample:intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}qsort(num,100,sizeof(num[0]),cmp);•二、对char类型数组排序（同int类型）charword[100];Sample:intcmp(constvoid*a,constvoid*b){return*(char*)a-*(char*)b;}qsort(word,100,sizeof(word[0]),cmp);•三、对double类型数组排序（特别要注意）doublein[100];intcmp(constvoid*a,constvoid*b){return*(double*)a*(double*)b?1:-1;}qsort(in,100,sizeof(in[0]),cmp)；•四、对结构体一级排序structIn{doubledata;intother;}s[100]//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写intcmp(constvoid*a,constvoid*b){return((structIn*)a)-data-((structIn*)b)-data;}qsort(s,100,sizeof(s[0]),cmp);•五、对结构体structIn{intx;inty;}s[100];//按照x从小到大排序，当x相等时按照y从大到小排序intcmp(constvoid*a,constvoid*b){structIn*c=(In*)a;structIn*d=(In*)b;if(c-x!=d-x)returnc-x-d-x;elsereturnd-y-c-y;}qsort(s,100,sizeof(s[0]),cmp);•六、对字符串进行排序structIn{intdata;charstr[100];}s[100];//按照结构体中字符串str的字典顺序排序intcmp(constvoid*a,constvoid*b){returnstrcmp(((In*)a)-str,((In*)b)-str);}qsort(s,100,sizeof(s[0]),cmp);algorithm•#includealgorithm•usingnamespacestd;常用函数•binary_search•nth_element•sort•stable_sort•unique•next_permutation•prev_permutation•make_heap•sort_heap