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

: 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); } 15. 题目中描述：“A negative value for n indicates the end of input. ” Sample Input 1 2 3 -1 如果在读题目的时候不注意，而根据sample input作判断，输入的时候用： while(cin>>n && n!=-1) { ... } 则会出错，而应该 while(cin>>n && n > 0) { ... } 这是在zoj_1475中的一个陷阱。 16. 打开文件的语句别写错了,还有文件名小心郁闷死你.多注意点细节,不要频繁提交。 17. 一些常用的词汇(如max,min)作为变量名在本地机上可以正常编译,但递交上去不一定能编译.更郁闷的是用了一些常用的词汇,编译也通过了,输出答案也是正确的,但就是wa.解决方案:单词前面加上一个字母,比如lmax,lmin 18. 当提交一直WA时,再仔细读一边题目,而不是一味的想特殊数据。 19. 关于比赛配合问题：1) 拿到题目一般是每人看几道题..也就是扫描一下输入输出什么的,简单讨论一下确定出一道最简单的让一个人去做,机子空着毕竟比较浪费...剩下两个人就可以把题目熟悉起来了...三个人讨论题目的话机子又空着了~~呵呵,一般两个人讨论就行了. 2) 开始地时候三个人分工好每人看几道题，第一时间找到最简单地题，然后一个人开始写程序，另外两个人开始讨论剩下的题目，按照难度/可能通过率/熟悉程度/决定下面做那些题目，然后在纸上写程序，调试. 3) 还有随时注意观察其他队的动态如果有的题目大多数队都通过了而自己还没有做的话，赶快做这个题目。或者是自己一个题目做了很久没有通过，而其他队也没有通过的话，很有可能就是数据有问题或者题目有陷阱，赶快换题目做。比赛不是比谁能做出难题，而是谁能做出更多的题目。 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(对角线). 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) 上图为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; 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 #include #include const bool SafeFirst=false; //一般当同时使用了两个或两个以上大数运算时应设置为true;设置安全优先还是效率优先.若效率优先(false),一定要保证传入到函数中的数据都是规格的大数,否则可能出错.效率差常数倍,一般是1倍,要看具体数据,数据越小,而lmax开得越大,差距越大.一般建议用true const int nw=8; //jz中0的个数,nw<=8 const int jz=100000000; //配置进制,只能是10^nw const int lmax=100000; //大数数组开的大小,(lmax-1)*nw为大数的位数 void jia(const int a[],const int b[],int c[]) //大数a[]加大数b[],结果存在c[]中 { int i,top; top=a[0]>b[0]?a[0]:b[0]; if (SafeFirst) //在false情况下,如果传入的c[]非规格的,不能保证返回的c[]规格 { memset(c,0,sizeof(int)*lmax); }else { c[top+1]=0; } for (i=1;i<=top;i++) { c[i]+=a[i]+b[i]; if (c[i]>=jz) { c[i]-=jz; c[i+1]++; } } if (c[top+1]>0) c[0]=top+1; else c[0]=top; } void jia2(int a[],const int b[]) //对大数a[]累加另一大数b[] { int i,top; if (SafeFirst) memset(a+a[0]+1,0,sizeof(int)*(lmax-a[0]-1)); top=a[0]>b[0]?a[0]:b[0]; for (i=1;i<=b[0];i++) { a[i]+=b[i]; if (a[i]>=jz) { a[i]-=jz; a[i+1]++; } } if (a[top+1]>0) a[0]=top+1; else a[0]=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)*(a[0]+1)); t=c[1]+b; c[1]=t%jz; i=1; while (t>=jz) { t/=jz; t+=c[i+1]; c[i+1]=t%jz; i++; } if (c[0]=jz) { t/=jz; t+=a[i+1]; a[i+1]=t%jz; i++; } if (a[0]=b[] { int i,jw; if (SafeFirst) //若为false,不能保证传出的c[]是规格的 { memset(c,0,sizeof(int)*lmax); } jw=0; for (i=1;i<=b[0];i++) { if (a[i]-jw>=b[i]) { c[i]=a[i]-jw-b[i]; jw=0; } else { c[i]=a[i]+jz-jw-b[i]; jw=1; } } for (i=b[0]+1;i<=a[0];i++) { if (a[i]-jw>=0) { c[i]=a[i]-jw; jw=0; }else { c[i]=a[i]+jz-jw; jw=1; } } i=a[0]; while (c[i]==0) i--; if (i>0) c[0]=i; else c[0]=1; } void jian2(int a[],const int b[]) //a[]-=b[];a[]>b[] { int i; if (SafeFirst) memset(&a[a[0]+1],0,sizeof(int)*(lmax-a[0]-1)); for (i=1;i<=b[0];i++) { a[i]-=b[i]; if (a[i]<0) { a[i]+=jz; a[i+1]--; } } while (a[i]<0 && i0) a[0]=i; else a[0]=1; } void jian3(const int a[],const int b,int c[]) //a[]>=b { int i; memcpy(c,a,sizeof(int)*(a[0]+1)); if (SafeFirst) memset(&c[c[0]+1],0,sizeof(int)*(lmax-a[0]-1)); c[1]-=b; i=1; while (c[i]<0) { c[i+1]+=c[i]/jz; c[i]%=jz; if (c[i]<0) { c[i+1]--; c[i]+=jz; } i++; } i=c[0]; while (c[i]==0) i--; if (i>0) c[0]=i; else c[0]=1; } void jian4(int a[],const int b) { int i; a[1]-=b; i=1; while (a[i]<0) { a[i+1]+=a[i]/jz; a[i]%=jz; if (a[i]<0) { a[i+1]--; a[i]+=jz; } i++; } i=a[0]; while (a[i]==0) i--; if (i>0) a[0]=i; else a[0]=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<=a[0];i++) { up=0; for (j=1;j<=b[0];j++) { k=i+j-1; t=(__int64)a[i]*b[j]+up; c[k]+=t%jz; up=t/jz; while (c[k]>=jz) { c[k+1]++; c[k]-=jz; } } if (up>0) { c[i+b[0]]+=up; } } i=a[0]+b[0]; while (c[i]==0) i--; if (i>0) c[0]=i; else c[0]=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<=a[0];i++) { t=(__int64)a[i]*b+up; c[i]=t%jz; up=t/jz; } c[i]+=up; while (c[i]>=jz) { c[i+1]=c[i]/jz; c[i]%=jz; i++; } if (c[i]==0) i--; if (i>0) c[0]=i; else c[0]=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<=a[0];i++) { t=a[i]; for (j=1;j<=nw;j++) { p++; b[p]=t%10; t/=10; } } while (b[p]==0) p--; if (p>0) b[0]=p; else b[0]=1; } void chglth(const int a[],int b[]) { int i,j,top; memset(b,0,sizeof(int)*lmax); for (i=1;i<=a[0];i+=nw) { b[0]++; top=i+nw-1; if (top>a[0]) top=a[0]; for (j=top;j>=i;j--) { b[b[0]]=b[b[0]]*10+a[j]; } } } void chu(int a[],const int b[],int c[]) //c[]=a[]%b[],a[]/=b[];a[]>=0 && b[]>0; { int *a1=new int[nw*lmax],*b1=new int[nw*lmax],*c1=new int[nw*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=a1[0];i>=b1[0];i--) { if (i=1;j--) if (a1[i+j-b1[0]]b1[j]) { ok=true; break; } lcount=0; while (ok) { for (j=1;j<=b1[0];j++) { a1[i+j-b1[0]]-=b1[j]; if (a1[i+j-b1[0]]<0) { a1[i+j-b1[0]]+=10; a1[i+j-b1[0]+1]--; } } lcount++; for (j=b1[0];j>=1;j--) if (a1[i+j-b1[0]]b1[j]) { ok=true; break; } } c1[i-b1[0]+1]=lcount; } i=a1[0]; while (c1[i]==0) i--; if (i>0) c1[0]=i; else c1[0]=1; i=b1[0]; while (a1[i]==0) i--; if (i>0) a1[0]=i; else a1[0]=1; for (i=1;i<=a1[0];i++) if (a1[i]>9) { a1[i+1]+=a1[i]/10; a1[i]%=10; } while (a1[i]>9) { a1[i+1]=a1[i]/10; a1[i]%=10; i++; } if (a1[i]==0) i--; if (i>0) a1[0]=i; else a1[0]=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[]%b[] { memcpy(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=c[0];i>=1;i--) { if (i0) a[0]=i; else a[0]=1; i=1; while (c[i]>=jz) { c[i+1]=c[i]/jz; c[i]%=jz; i++; } if (c[i]==0) i--; if (i>0) c[0]=i; else c[0]=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 (t1<0) t1=0; for (j=t1;j<=i;j++) t=t*10+s[j]-'0'; a[0]++; a[a[0]]=t; } } void output(const int c[]) //大数输出 { int i,w,j,n; printf("%d",c[c[0]]); for (i=c[0]-1;i>0;i--) { n=c[i]; w=0; while (n>0) { w++; n/=10; } for (j=0;j0) printf("%d",c[i]); } printf("\n"); } void jiecheng(int n=-1) { int begin,i,cost,*t=new int[lmax],*a=new int[lmax]; memset(t,0,sizeof(t)*lmax); memset(a,0,sizeof(a)*lmax); if (n<0) scanf("%d",&n); begin=time(0); a[0]=1; a[1]=1; for (i=2;i<=n;i++) { for (int j=1;j<=a[0];j++) t[j]=a[j]; t[0]=a[0]; chen2(t,i,a); } cost=time(0)-begin; output(a); printf("Cost time : %d\n",cost); delete []t; delete []a; } void chenfang(const int a[],int n,int c[]) //求a[]的n次方 { int i,*b=new int[lmax]; 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 a[lmax]={0},b[lmax]={0},n; char s[nw*lmax]; while (scanf("%s",s)!=EOF) { scanf("%d",&n); chgstn(s,a); chenfang(a,n,b); output(b); } } void examinejia() { int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i; char s[nw*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 a[lmax]={0},c[lmax]={0},n,i; char s[nw*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 a[lmax],b,c[lmax],n,i; char s[lmax*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 a[lmax],b,n,i; char s[lmax*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 a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i; char s[nw*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 a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i; char s[nw*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 a[lmax],b,c[lmax],n,i; char s[lmax*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 a[lmax],b,n,i; char s[lmax*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 a[lmax],b[lmax],c[lmax]; char s[lmax*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 a[lmax],b[lmax],c[lmax],d[lmax]; char s[lmax*nw]; while (scanf("%s",s)!=EOF) { chgstn(s,a); scanf("%s",s); chgstn(s,b); chu2(a,b,c,d); output(c); output(d); } } void examinechu4() { int a[lmax],c[lmax],d[lmax],b; char s[nw*lmax]; while (scanf("%s%d",s,&b)!=EOF) { chgstn(s,a); chu4(a,b,c,d); output(c); output(d); } } int main() { // 以下用来检测各函数的正确性 jiecheng(); // examinechenfang(); // examinejia(); // examinejia2(); // examinejia3(); // examinejia4(); // examinejian(); // examinejian2(); // examinejian3(); // examinejian4(); // examinechu(); // examinechu2(); // examinechu4(); return 0; } 取模.cpp int div(char *A,int B) { int I; int C = 0; int Alen=strlen(A); for (I = 0; I #include #include #include #include #include using namespace std; typedef double TYPE; #define Abs(x) (((x)>0)?(x):(-(x))) #define Sgn(x) (((x)<0)?(-1):(1)) #define Max(a,b) (((a)>(b))?(a):(b)) #define Min(a,b) (((a)<(b))?(a):(b)) #define Epsilon 1e-10 #define Infinity 1e+10 #define Pi 3.14159265358979323846 TYPE Deg2Rad(TYPE deg) { return (deg * Pi / 180.0); } TYPE Rad2Deg(TYPE rad) { return (rad * 180.0 / Pi); } TYPE Sin(TYPE deg) { return sin(Deg2Rad(deg)); } TYPE Cos(TYPE deg) { return cos(Deg2Rad(deg)); } TYP