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

杭州电子科技大学ACM集训队资料集杭州电子科技大学ACM集训队资料集2005.11Contents一 Acm比赛注意事项 02二 Numbers和数学公式 05三 数论模板 . 08四 大数类 . 10五 计算几何模板 . 14六 经典算法和源码 . 271128_求矩形面积和_线段树 . 27匈牙利算法1525 . 31最大子段和 . 32字典树 . 351203_kruscal . 371203_prim . 40Dijkstra . 43Bellmanford . 45七 线性规划.67八 高斯消元.69九 图论相关算法.74十 三角函数表.84Acm比赛注意事项1. 服务器不支持long double类型，最高支持到double（浮点型）和long long（长整型），注意 double 比float 更适宜。2. while语句中的(cinMN & M!=0 & N!=0)（注意是与还是或）上式也可改写成(cinMN & (M | N)3. 在有些题目，特别是数据比较烦的时候，或者数据精度要求高的时候，可能精度要求不够。4. （引用其他人的）奇怪的事情多着呢.昨天我做2305时候,m=1; for(i=1; i=k; i+) m *= 2和 m = (1k);本来是一样的.但是前面提交就AC,后面一个就一直的WA。（以上为原文，不过我觉得左移和乘2是有所不同的，乘2符号位不会变，但是，左移式连同符号位一起左移，空位补零，那正数左移后就可能变成负数了）。5. &可表示取地址符，也可以表示为对某个变量的引用。注意函数是传值，还是传地址的。6. abs的参数是整型，而不是浮点型。 7. 有些题目看上去好象用什么经典的算法，但如果你把题目看清楚，也许会有更简单的算法或者完全不同的思路，我刚开始就把他当作dp去做，可后来发现简单的循环就可以了。8. 关于cin和getline，cin后面不读入回车符，导致在输入流中还保存有，在下次读入getline的时候，getline就读入的是回车符，而不是我门要读的东西。1925考虑的就是这点。9. 当用cin TLE的时候试试scanf10. 当发现一个题目里面出现的数据跟16有关时,想想是否可以通过位运算解决(1219, 1639)11. 一定要注意结果是否会是long long类型12. .输入是一整行的字符串。 如1392 如果你用char a 200 来保存， cin.getline( a, 200 ); 如果你用string str;来保存的： Code: getline( cin , str );13. 一个Input Block对应一个Output Block，Output Block之间有空行。 如1152 int Case = 0; if ( Case+ ) cout endl; . cout x endl; 14. 一个一行中输入不定个数字的输入处理方法: char input501; int blankCount; int blankPos501; int i, j, s; cin.getline(input, 500); blankCount = 0; blankPos0 = 0; j = strlen(input); for (i = 0; i j; + i) if (inputi = ) blankCount +; blankPosblankCount = i; for (i = 0; i n & n!=-1) . 则会出错，而应该while(cinn & n 0) . 这是在zoj_1475中的一个陷阱。16. 打开文件的语句别写错了,还有文件名小心郁闷死你.多注意点细节,不要频繁提交。17. 一些常用的词汇(如max,min)作为变量名在本地机上可以正常编译,但递交上去不一定能编译.更郁闷的是用了一些常用的词汇,编译也通过了,输出答案也是正确的,但就是wa.解决方案:单词前面加上一个字母,比如lmax,lmin18. 当提交一直WA时,再仔细读一边题目,而不是一味的想特殊数据。19. 关于比赛配合问题：1) 拿到题目一般是每人看几道题.也就是扫描一下输入输出什么的,简单讨论一下确定出一道最简单的让一个人去做,机子空着毕竟比较浪费.剩下两个人就可以把题目熟悉起来了.三个人讨论题目的话机子又空着了呵呵,一般两个人讨论就行了. 2) 开始地时候三个人分工好每人看几道题，第一时间找到最简单地题，然后一个人开始写程序，另外两个人开始讨论剩下的题目，按照难度/可能通过率/熟悉程度/决定下面做那些题目，然后在纸上写程序，调试. 3) 还有随时注意观察其他队的动态如果有的题目大多数队都通过了而自己还没有做的话，赶快做这个题目。或者是自己一个题目做了很久没有通过，而其他队也没有通过的话，很有可能就是数据有问题或者题目有陷阱，赶快换题目做。比赛不是比谁能做出难题，而是谁能做出更多的题目。Numbers和数学公式一. Fibonacci Number0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 二. Lucas Number (特殊的Fibonacci Number ) 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 , . 三. Catalan Number1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 计算公式: C(2n, n) / (n + 1)应用:1. 将 n + 2 边形沿弦切割成 n个三角形的不同切割数 2. n +个数相乘,给每两个元素加上括号的不同方法数 eg: n = 2: (1 (2 3) , (1 2) 3) n = 3: (1 (2 (3 4), (1 (2 3) 4) , (1 2) (3 4), (1 (2 3) 4), (1 2) 3) 4) 3. the number of rooted, trivalent trees with n + 1 nodes eg: n = 2 n = 3 4. the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal(对角线). eg: n = 2 n = 3 5. 结点数为 n 的二叉树的不同构造数.四. striling number(斯特灵数)1, 3 , 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563 构造法: n个有标号的球放到m 个无标号的盒子中，要求无一为空，其不同的方案数 记作: s(n,m)s(0,0) = 0, s(n,k)=0 (n1,m=1) 五. bell number (和striling number 相似)1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975，定义: N元集合的所有划分数称为Bell数，记做Bn，根据第二类Stirling数的意义，我们可以很容易的得到：Bn=sigma(S(n,k) (k=1,2n) / sigma求和六. 杨式图表的个数 杨式图表（Young Tableau）是一个矩阵，它满足条件：如果格子（i , j）没有元素，则它右边和上边的相邻格子也一定没有元素。如果格子（i , j）有元素ai,j，则它右边和上边的相邻格子要么没有元素，要么比ai,j 大。 1 n 所组成的杨式图表的个数由下式给出：a(1) = 1, a(2) = 2a(n) = a(n-1) + (n-1) * a(n-2) (n2) 上图为n = 3 的 杨式图表七 钩子公式对于给定形状，不同的杨式图表的个数为n! 除以每个格子的钩子长度加1的积。其中，钩子长度定义为该格子右边的格子数和它上面的格子数子和。八. 三角形内切圆半径 s=(a+b+c)/2九. 三角形外接圆半径 r =(a*b*c)/(4*s) 其中s为三角形面积。十. 圆內接四边形面积公式圆內接四边形，其四边边长分別为a,b,c,d 。令 s=(a+b+c+d) / 2，则四边行面积为 sqrt( (s-a)*(s-b)*(s-c)*(s-d) )数论模板int gcd(int a, int b)/最大公约数if(b=0)return a;elsereturn gcd(b, a%b);/扩展的欧拉函数，返回放在x, y中/ d = gcd(a, b) 这里求得的x, y满足 d = ax + byint extend_euclid(int a,int b,int &x,int &y) int t,d; if (b=0) x=1;y=0;return a; d=extend_euclid(b,a %b,x,y); t=x; x=y; y=t-a/b*y; return d;/求解同余方程ax=b(mod n)void linear_solve(int a, int b, int n)int d, x, y;d = extend_euclid(a, n, x, y);/调用扩展的欧拉函数if(b%d=0)int e = (x*(b/d)%n;/e等于x0int ans = n;for(int i=0; id; i+)ans = (e+i*(n/d)%n;cout ans endl;/有d个解，在这里输出，根据题目要求，可以保存之/类的操作elsecout no solution endl;/无解的情况/筛选法构造素数表const int M = 1000;bool markM;/true : prime numbervoid prime()int i, j;memset(mark, true, sizeof(mark);mark0 = mark1 = false;for(i=2; i=sqrt(M); i+)if(marki)for(j=i*i; jM; j+=i)markj = false;/判断是否是素数bool is_prime(int u)if(u=0|u=1) return false;if(u=2) return true;if(u%2=0) return false;for(int i=3; i=sqrt(u); i+=2)if(u%i=0) return false;return true;大数类/*Code by weigangli 2005-11-2；可在10-100000000范围内配置进制；可配置安全优先活效率优先，主要针对不规范初始化引起的一些错误，一般情况下建议以安全优先的模式运行；效率测试：测试平台：普通笔记本测试环境：XP SP2编译器：VC+测试项目：计算10000!测试结果：1.安全优先模式，10进制，耗时15秒 2.效率优先模式，10进制，耗时13秒 3.安全优先模式，100000000进制，耗时2秒 4.效率优先模式，100000000进制，耗时2秒结果分析：安全优先或效率优先对效率的影响不大，而使用较高的进制对效率的影响相对明显；为了使用方便jia,.,jia4,jian,.,jian4,chen,.,chen4基本上都独立实现,因而有较多的冗余代码；*/#include #include #include const bool SafeFirst=false;/一般当同时使用了两个或两个以上大数运算时应设置为true;设置安全优先还是效率优先.若效率优先(false),一定要保证传入到函数中的数据都是规格的大数,否则可能出错.效率差常数倍,一般是1倍,要看具体数据,数据越小,而lmax开得越大,差距越大.一般建议用trueconst int nw=8;/jz中0的个数,nwb0?a0:b0;if (SafeFirst)/在false情况下,如果传入的c非规格的,不能保证返回的c规格memset(c,0,sizeof(int)*lmax);elsectop+1=0;for (i=1;i=jz)ci-=jz;ci+1+;if (ctop+10)c0=top+1;elsec0=top;void jia2(int a,const int b)/对大数a累加另一大数bint i,top;if (SafeFirst)memset(a+a0+1,0,sizeof(int)*(lmax-a0-1);top=a0b0?a0:b0;for (i=1;i=jz)ai-=jz;ai+1+;if (atop+10)a0=top+1;elsea0=top;void jia3(const int a,const int b,int c)/大数a加上小数b,存在c中int i;unsigned int t;if (SafeFirst) memset(c,0,sizeof(int)*lmax);memcpy(c,a,sizeof(int)*(a0+1);t=c1+b;c1=t%jz;i=1;while (t=jz)t/=jz;t+=ci+1;ci+1=t%jz;i+;if (c0=jz)t/=jz;t+=ai+1;ai+1=t%jz;i+;if (a0=bint i,jw;if (SafeFirst)/若为false,不能保证传出的c是规格的memset(c,0,sizeof(int)*lmax);jw=0;for (i=1;i=bi)ci=ai-jw-bi;jw=0;elseci=ai+jz-jw-bi;jw=1;for (i=b0+1;i=0)ci=ai-jw;jw=0;elseci=ai+jz-jw;jw=1;i=a0;while (ci=0) i-;if (i0) c0=i;elsec0=1;void jian2(int a,const int b) /a-=b;abint i;if (SafeFirst) memset(&aa0+1,0,sizeof(int)*(lmax-a0-1);for (i=1;i=b0;i+)ai-=bi;if (ai0)ai+=jz;ai+1-;while (ai0 & i0) a0=i;else a0=1;void jian3(const int a,const int b,int c)/a=bint i;memcpy(c,a,sizeof(int)*(a0+1);if (SafeFirst) memset(&cc0+1,0,sizeof(int)*(lmax-a0-1);c1-=b;i=1;while (ci0)ci+1+=ci/jz;ci%=jz;if (ci0) c0=i;elsec0=1;void jian4(int a,const int b)int i;a1-=b;i=1;while (ai0)ai+1+=ai/jz;ai%=jz;if (ai0) a0=i;elsea0=1;/*/inline void chen(const int a,const int b,int c)/大数乘大数_int64 t=0;int up=0,i,j,k;if (SafeFirst)memset(c,0,sizeof(int)*lmax);for (i=1;i=a0;i+)up=0;for (j=1;j=jz)ck+1+;ck-=jz;if (up0)ci+b0+=up;i=a0+b0;while (ci=0) i-;if (i0) c0=i;elsec0=1;inline void chen2(const int a,const int b,int c)/大数乘小数_int64 t;int up=0,i;if (SafeFirst)memset(c,0,sizeof(int)*lmax);for (i=1;i=jz)ci+1=ci/jz;ci%=jz;i+;if (ci=0) i-;if (i0) c0=i;elsec0=1;/*/void chghtl(const int a,int b)int t,i,j,p=0;memset(b,0,sizeof(int)*nw*lmax);for (i=1;i=a0;i+)t=ai;for (j=1;j0) b0=p;else b0=1;void chglth(const int a,int b)int i,j,top;memset(b,0,sizeof(int)*lmax);for (i=1;ia0) top=a0;for (j=top;j=i;j-)bb0=bb0*10+aj;void chu(int a,const int b,int c)/c=a%b,a/=b;a=0 & b0;int *a1=new intnw*lmax,*b1=new intnw*lmax,*c1=new intnw*lmax,i,j,lcount;bool ok;memset(a1,0,sizeof(int)*nw*lmax);memset(b1,0,sizeof(int)*nw*lmax);memset(c1,0,sizeof(int)*nw*lmax);chghtl(a,a1);chghtl(b,b1);for (i=a10;i=b10;i-)if (i=1;j-)if (a1i+j-b10b1j)ok=true;break;lcount=0;while (ok)for (j=1;j=b10;j+)a1i+j-b10-=b1j;if (a1i+j-b10=1;j-)if (a1i+j-b10b1j)ok=true;break;c1i-b10+1=lcount;i=a10;while (c1i=0) i-;if (i0) c10=i;elsec10=1;i=b10;while (a1i=0) i-;if (i0) a10=i;elsea10=1;for (i=1;i9)a1i+1+=a1i/10;a1i%=10;while (a1i9)a1i+1=a1i/10;a1i%=10;i+;if (a1i=0) i-;if (i0) a10=i;elsea10=1;chglth(a1,c);chglth(c1,a);delete a1;delete b1;delete c1;void chu2(const int a,const int b,int c, int d)/c=a/b;d=a%bmemcpy(c,a,sizeof(int)*lmax);chu(c,b,d);void chu3(int a,const int b,int c)/c=a%b; a/=b;_int64 t;int i;memcpy(c,a,sizeof(int)*lmax);for (i=c0;i=1;i-)if (i0) a0=i;elsea0=1;i=1;while (ci=jz)ci+1=ci/jz;ci%=jz;i+;if (ci=0) i-;if (i0) c0=i;elsec0=1;void chu4(const int a,const int b,int c,int d)/c=a/b; d=a%b;memcpy(c,a,sizeof(int)*lmax);chu3(c,b,d);/*/void chgstn(const char s,int a)/字符串转大数int i,t1,l,j,t;memset(a,0,sizeof(a);l=strlen(s);for (i=l-1;i=0;i-=nw)t=0;t1=i-nw+1;if (t10) t1=0;for (j=t1;j0;i-)n=ci;w=0;while (n0)w+;n/=10;for (j=0;j0) printf(%d,ci);printf(n);void jiecheng(int n=-1)int begin,i,cost,*t=new intlmax,*a=new intlmax;memset(t,0,sizeof(t)*lmax);memset(a,0,sizeof(a)*lmax);if (n0)scanf(%d,&n);begin=time(0);a0=1;a1=1;for (i=2;i=n;i+)for (int j=1;j=a0;j+)tj=aj;t0=a0;chen2(t,i,a);cost=time(0)-begin;output(a);printf(Cost time : %dn,cost);delete t;delete a;void chenfang(const int a,int n,int c)/求a的n次方int i,*b=new intlmax;memcpy(b,a,sizeof(int)*lmax);memcpy(c,a,sizeof(int)*lmax);for (i=2;i=n;i+)chen(b,a,c);memcpy(b,c,sizeof(int)*lmax);delete b;void examinechenfang()/检测chenfang()的正确性int almax=0,blmax=0,n;char snw*lmax;while (scanf(%s,s)!=EOF)scanf(%d,&n);chgstn(s,a);chenfang(a,n,b);output(b);void examinejia()int almax=0,blmax=0,clmax=0,n,i;char snw*lmax;while (scanf(%s,s)!=EOF)scanf(%d,&n);chgstn(s,a);memset(c,0,sizeof(c);for (i=1;i=n;i+)memcpy(b,c,sizeof(int)*lmax);jia(a,b,c);output(c);void examinejia2()int almax=0,clmax=0,n,i;char snw*lmax;while (scanf(%s,s)!=EOF)scanf(%d,&n);chgstn(s,a);memset(c,0,sizeof(c);for (i=1;i=n;i+)jia2(c,a);output(c);void examinejia3()int almax,b,clmax,n,i;char slmax*nw;while (scanf(%s%d%d,s,&b,&n)/memset(c,0,sizeof(c);chgstn(s,a);for (i=1;i=n;i+)jia3(a,b,c);memcpy(a,c,sizeof(int)*lmax);output(c);void examinejia4()int almax,b,n,i;char slmax*nw;while (scanf(%s%d%d,s,&b,&n)chgstn(s,a);for (i=1;i=n;i+)jia4(a,b);output(a);void examinejian()int almax=0,blmax=0,clmax=0,n,i;char snw*lmax;while (scanf(%s,s)!=EOF)scanf(%d,&n);chgstn(s,a);memset(c,0,sizeof(c);for (i=1;i=n;i+)memcpy(b,c,sizeof(int)*lmax);jia(a,b,c);output(c);for (i=1;i=n;i+)memcpy(b,c,sizeof(c);jian(b,a,c);output(c);void examinejian2()int almax=0,blmax=0,clmax=0,n,i;char snw*lmax;while (scanf(%s,s)!=EOF)scanf(%d,&n);chgstn(s,a);memset(c,0,sizeof(c);for (i=1;i=n;i+)memcpy(b,c,sizeof(int)*lmax);jia(a,b,c);output(c);for (i=1;i=n;i+)jian2(c,a);output(c);void examinejian3()int almax,b,clmax,n,i;char slmax*nw;while (scanf(%s%d%d,s,&b,&n)/memset(c,0,sizeof(c);chgstn(s,a);for (i=1;i=n;i+)jia3(a,b,c);memcpy(a,c,sizeof(int)*lmax);output(a);for (i=1;i=n;i+)jian3(a,b,c);memcpy(a,c,sizeof(int)*lmax);output(a);void examinejian4()int almax,b,n,i;char slmax*nw;while (scanf(%s%d%d,s,&b,&n)chgstn(s,a);for (i=1;i=n;i+)jia4(a,b);output(a);for (i=1;i=n;i+)jian4(a,b);output(a);void examinechu()int almax,blmax,clmax;char slmax*nw;while (scanf(%s,s)chgstn(s,a);scanf(%s,s);chgstn(s,b);chu(a,b,c);output(a);output(c);void examinechu2()int almax,blmax,clmax,dlmax;char slmax*nw;while (scanf(%s,s)!=EOF)chgstn(s,a);scanf(%s,s);chgstn(s,b);chu2(a,b,c,d);ou