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

杭州电子科技大学ACM集训队资料集 杭州电子科技大学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 1 杭州电子科技大学ACM集训队资料集 Acm比赛注意事项 1. 服务器不支持long double类型，最高支持到double(浮点型)和long long (长整型)，注意 double 比float 更适宜。 2. while语句中的(cin>>M>>N && M!=0 && N!=0)(注意是与还是或)上式也 可改写成(cin>>M>>N && (M || N)) 3. 在有些题目，特别是数据比较烦的时候，或者数据精度要求高的时候，可能 精度要求不够。。。 ,m=1; for(i=1; i<=k; 4. (引用其他人的)奇怪的事情多着呢.昨天我做2305时候 i++) m *= 2和 m = (1<>n && n!=-1) { ... } 则会出错，而应该 while(cin>>n && n > 0) { ... } 这是在zoj_1475中的一个陷阱。 16. 打开文件的语句别写错了,还有文件名小心郁闷死你.多注意点细节,不要频繁提交。 常用的词汇(如max,min)作为变量名在本地机上可以正常编译,但递交上17. 一些 去不一定能编译.更郁闷的是用了一些常用的词汇,编译也通过了,输出

答案

八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案

也是正确的,但就是wa.解决方案:单词前面加上一个字母,比如lmax,lmin 18. 当提交一直WA时,再仔细读一边题目,而不是一味的想特殊数据。 19. 关于比赛配合问题:1) 拿到题目一般是每人看几道题..也就是扫描一下输入输出什么的,简单讨论一下确定出一道最简单的让一个人去做,机子空着毕竟比较浪费...剩下两个人就可以把题目熟悉起来了...三个人讨论题目的话机子又空着了~~呵呵,一般两个人讨论就行了. 2) 开始地时候三个人分工好每人看几道题，第一时间找到最简单地题，然后一个人开始写程序，另外两个人开始讨论剩下的题目，按照难度/可能通过率/熟悉程度/决定下面做那些题目，然后在纸上写程序，调试. 3) 还有随时注意观察其他队的动态如果有的题目大多数队都通过了而自己还没有做的话，赶快做这个题目。或者是自己一个题目做了很久没有通过，而其他队也没有通过的话，很有可能就是数据有问题或者题目有陷阱，赶快换题目做。比赛不是比谁能做出难题，而是谁能做出更多的题目。 4 杭州电子科技大学ACM集训队资料集 Numbers和数学公式 一. Fibonacci Number 0, 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 Number 1, 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(对角线). 5 杭州电子科技大学ACM集训队资料集 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,2…n) // sigma求和 六. 杨式图表的个数 杨式图表(Young Tableau)是一个矩阵，它满足条件: 如果格子(i , j)没有元素，则它右边和上边的相邻格子也一定没有元素。 如果格子(i , j)有元素a[i,j]，则它右边和上边的相邻格子要么没有元素，要么比a[i,j] 大。 1 ~ n 所组成的杨式图表的个数由下式给出: a(1) = 1, a(2) = 2 a(n) = a(n-1) + (n-1) * a(n-2) (n>2) 6 杭州电子科技大学ACM集训队资料集 上图为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) ) 7 杭州电子科技大学ACM集训队资料集 数论模板 int gcd(int a, int b)//最大公约数 { if(b==0) return a; else return gcd(b, a%b); } //扩展的欧拉函数，返回放在x, y中 // d = gcd(a, b) 这里求得的x, y满足 d = ax + by int 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等于x0 int ans = n; for(int i=0; i规范

编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载