杭州电子科技大学ACM集训队资料集.doc

杭州电子科技大学ACM集训队资料集 PAGE PAGE 1 杭州电子科技大学ACM集训队资料集 2005.11 Contents 一 Acm比赛注意事项 …………………………………………… 02 二 Numbers和数学公式 ………………………………………… 05 三 数论模板 ……………………………………………………….. 08 四 大数类 ………………………………………………………….. 10 五 计算几何模板 ………………………………………………….. 14 六 经典算法和源码 ……………………………………………….. 27 1128_求矩形面积和_线段树 ………………….. 27 匈牙利算法1525 ……………………………….. 31 最大子段和 ……………………………………... 32 字典树 …………………………………………... 35 1203_kruscal …………………………………... 37 1203_prim ………………………………………. 40 Dijkstra ………………………………………….. 43 Bellman—ford ………………………………….. 45 七 线性规划67 八 高斯消元69 九 图论相关算法74 十 三角函数表84 Acm比赛注意事项 服务器不支持long double类型，最高支持到double（浮点型）和long long（长整型），注意 double 比float 更适宜。 while语句中的(cinMN M!=0 N!=0)（注意是与还是或）上式也可改写成(cinMN (M || N)) 在有些题目，特别是数据比较烦的时候，或者数据精度要求高的时候，可能精度要求不够。。。 （引用其他人的）奇怪的事情多着呢.昨天我做2305时候,m=1; for(i=1; i=k; i++) m *= 2和 m = (1k);本来是一样的.但是前面提交就AC,后面一个就一直的WA。（以上为原文，不过我觉得左移和乘2是有所不同的，乘2符号位不会变，但是，左移式连同符号位一起左移，空位补零，那正数左移后就可能变成负数了）。 可表示取地址符，也可以表示为对某个变量的引用。注意函数是传值，还是传地址的。 abs的参数是整型，而不是浮点型。 有些题目看上去好象用什么经典的算法，但如果你把题目看清楚，也许会有更简单的算法或者完全不同的思路，我刚开始就把他当作dp去做，可后来发现简单的循环就可以了。 关于cin和getline，cin后面不读入回车符，导致在输入流中还保存有，在下次读入getline的时候，getline就读入的是回车符，而不是我门要读的东西。1925考虑的就是这点。 当用cin TLE的时候试试scanf 当发现一个题目里面出现的数据跟16有关时,想想是否可以通过位运算解决(1219, 1639) 一定要注意结果是否会是long long类型 .输入是一整行的字符串。 如1392 如果你用char a[ 200 ]来保存， cin.getline( a, 200 ); 如果你用string str;来保存的： Code: getline( cin , str ); 一个Input Block对应一个Output Block，Output Block之间有空行。 如1152 int Case = 0; {  if ( Case++ ) cout endl;  ...  cout x endl; } 一个一行中输入不定个数字的输入处理方法: char input[501]; int blankCount; int blankPos[501]; int i, j, s; cin.getline(input, 500); blankCount = 0; blankPos[0] = 0; j = strlen(input); for (i = 0; i j; ++ i) { if (input[i] == ) {  blankCount ++; blankPos[blankCount] = i; } } for (i = 0; i = blankCount; ++ i) { sscanf(input + blankPos[i], %d, s);  printf(%d\n, s); } 题目中描述：“A negative valu