
题目链接:http://bailian.openjudge.cn/practice/4103/ 总时间限制: 1000ms 内存限制: 65536kB 描述 有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:a. 每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;b. 走过的格子立即塌陷无法再走第二次;c. 只能向北、东、西三个方向走;请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。 输入 允许在方格上行走的步数n(n <= 20) 输出 计算出的方案数量 样例输入 2 样例输出 7 算法分析 参考来源:https://www.cnblogs.com/sjymj/p/5379221.html l[i]表示最后一步向左走到达第x个格,那么它上一步不能是向右边走,r[i]表示最后一步向右走到达第x个格,那么它上一步不能是向左边走,u[i]表示最后一步向上走到达第x个格;那么它上一步可以从左、下、右三个方向到达。 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,ans; 5 int l[30],r[30],u[30]; 6 int main() 7 { 8 cin>>n; 9 if (n==1) cout<<3; 10 else 11 { 12 l[1]=1; 13 r[1]=1; 14 u[1]=1; 15 for (int i=2;i<=n;i++) 16 { 17 l[i]=l[i-1]+u[i-1]; 18 r[i]=r[i-1]+u[i-1]; 19 u[i]=l[i-1]+r[i-1]+u[i-1]; 20 } 21 ans=l[n]+r[n]+u[n]; 22 cout<<ans<<endl; 23 } 24 return 0; 25 }
题目链接:http://codevs.cn/problem/2287/ 题目描述 Description 火车从始发站(称为第1站)开出,在始发站上车的人数为a,然后到达第2站,在第2站有人上、下车,但上、下车的人数相同,因此在第2站开出时(即在到达第3站之前)车上的人数保持为a人。从第3站起(包括第3站)上、下车的人数有一定的规律:上车的人数都是前两站上车人数之和,而下车人数等于上一站上车人数,一直到终点站的前一站(第n-1站),都满足此规律。现给出的条件是:共有N个车站,始发站上车的人数为a,最后一站下车的人数是m(全部下车)。试问从x站开出时车上的人数是多少?若无解输出“No answer.”(所有数据均在longint范围内) 输入描述 Input Description a,n,m和x 输出描述 Output Description x站开出时车上的人数 样例输入 Sample Input 1 6 7 3 样例输出 Sample Output 2 数据范围及提示 Data Size & Hint 无 算法分析: 假设第2站上车人数y,下车人数也是y。根据题目意思可以有如下表格: 观察发现上车、下车人数这两行里面a和x的系数分别独自形成斐波那契数列。 所以,定义结构体struct obj,含两个成员项p和q分别表示a和x的系数。 最后一个车站下车人数m等于第n-1个车站出发的人数。上表中有6a+7y=m,已知a即可求得y。若y为整数则有解,若y不为整数则无解。 若是有解则可以根据y计算第x个车站出发时的人数。具体参考代码: 1 #include <stdio.h> 2 #include <stdlib.h> 3 struct obj 4 { 5 int p,q; 6 }; 7 int main() 8 { 9 struct obj up[25],down[25],sum[25]; 10 int i,a,m,n,x; 11 int y,ans; 12 scanf("%d%d%d%d",&a,&n,&m,&x); 13 14 up[1].p=1; up[1].q=0; 15 up[2].p=0; up[2].q=1; 16 17 down[1].p=0; down[1].q=0; 18 down[2].p=0; down[2].q=1; 19 20 sum[1].p=1; sum[1].q=0; 21 sum[2].p=1; sum[2].q=0; 22 23 for(i=3;i<n;i++) 24 { 25 up[i].p=up[i-1].p+up[i-2].p; 26 up[i].q=up[i-1].q+up[i-2].q; 27 down[i].p=up[i-1].p; 28 down[i].q=up[i-1].q; 29 sum[i].p=sum[i-1].p+up[i].p-down[i].p; 30 sum[i].q=sum[i-1].q+up[i].q-down[i].q; 31 } 32 if((m-sum[n-1].p*a)%sum[n-1].q==0) 33 { 34 y=(m-sum[n-1].p*a)/sum[n-1].q; 35 ans=sum[x].p*a+sum[x].q*y; 36 printf("%d\n",ans); 37 } 38 else printf("No answer.\n"); 39 40 return 0; 41 }
同一个平面内有n(n<=500)条直线,已知其中p(n>=p>=2)条直线相交于同一点。则这n条直线最多能将平面分割成多少个不同的区域? 分析:观察发现原有的p条线把平面分为2p个区域。为了能够划分出尽可能多的区域,从第p+1条线开始,添加每条线时都应该使新加的这条线和先前所有线相交于新的点。(也就是说,除了最早的p条线共点外,没有其他线三线共点。) 另外,观察发现:按照上述方法添加直线时,假设当前平面有x条直线,添加一条线以后将新增加x+1个区域。所以只要累加每一次新增加的区域数即可。 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int main() 5 { 6 freopen("surface_data/surface1.in","r",stdin); 7 freopen("surface_data/surface1.txt","w",stdout); 8 int n,p; 9 int i,sum=0; 10 scanf("%d%d",&n,&p); 11 sum=p*2; 12 for(i=p+1;i<=n;i++) 13 { 14 sum=sum+i; 15 } 16 printf("%d\n",sum); 17 return 0; 18 }
【问题描述】如下图所示,一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房M开始爬到蜂房N,M<N,有多少种爬行路线? 【输入格式】 输入M,N的值。【输出格式】 爬行有多少种路线。【输入样例】bee.in 1 14【输出样例】bee.out 377 算法分析: 假设f(i)表示从m到达i的方法数目。则有: f(m)=1,f(m+1)=1. f(i)=f(i-1)+f(i-2),其中i>=m+2 光盘测试数据比较大,要用高精度数解决。 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include<string.h> 4 //高精度数操作函数 5 //高精度数a[]的a[0]存放位数,例如“357234567”存为int数组:“9357234567”。 6 #define maxN 1005 7 void add(int *a,int *b,int *c);//a+b -> c 8 void mov(int *from,int *to); //把from复制到to 9 void printOut(int *a); //输出高精度数a 10 11 int main() 12 { 13 /* 14 int a[maxN]={5,5,5,5,5,5}; 15 int b[maxN]={5,5,5,5,5,5}; 16 int c[maxN]={0}; 17 printOut(a); 18 printf(" + "); 19 printOut(b); 20 printf("="); 21 add(a,b,c); 22 printOut(c); 23 printf("\n");*/ 24 25 freopen("bee_data/BEE1.in","r",stdin); 26 freopen("bee_data/BEE1.txt","w",stdout); 27 int m,n,i,a[1005]={0},b[1005]={0},c[1005]={0}; 28 scanf("%d%d",&m,&n); 29 a[0]=1;a[1]=1; 30 b[0]=1;b[1]=1; 31 c[0]=1;c[1]=1; 32 for(i=m+2;i<=n;i++) 33 { 34 35 add(a,b,c); // c=a+b; 36 mov(b,a); // a=b; 37 mov(c,b); // b=c; 38 } 39 printOut(c); 40 printf("\n"); 41 return 0; 42 } 43 //高精度数操作函数 44 //高精度数a[]的a[0]存放位数,例如“357234567”存为int数组:“9357234567”。 45 void add(int *a,int *b,int *c) //a+b -> c 46 { 47 int i,j,k; 48 for(i=0;i<maxN;i++) c[i]=0; 49 50 for(i=a[0],j=b[0],k=1; i>=1&&j>=1; i--,j--,k++) 51 c[k]=a[i]+b[j]; 52 while(i>=1) { c[k]=a[i]; i--; k++; } 53 while(j>=1) { c[k]=b[j]; j--; k++; } 54 c[0]=k-1; 55 for(i=1;i<=c[0];i++) //进位 56 { 57 c[i+1]+=c[i]/10; 58 c[i]=c[i]%10; 59 } 60 if(c[i]!=0) c[0]++; //向更高位进位 61 for(i=1,j=c[0];i<j;i++,j--) 62 { k=c[i]; c[i]=c[j]; c[j]=k; } 63 } 64 void mov(int *from,int *to) //把from复制到to 65 { 66 int i; 67 68 for(i=0;i<=from[0];i++) 69 to[i]=from[i]; 70 } 71 void printOut(int *a) //输出高精度数a 72 { 73 int i; 74 for(i=1;i<=a[0];i++) 75 { 76 printf("%d",a[i]); 77 } 78 } 利用高精度数据解决
题目链接: http://www.joyoi.cn/problem/tyvj-1199 http://tyvj.cn/p/1199 题目限制 时间限制 内存限制 评测方式 题目来源 1000ms 131072KiB 标准比较器 Local 题目描述 给定一个信封,最多只允许粘贴N(N≤100)张邮票,我们现在有M(M≤100)种邮票,面值分别为:X1,X2……Xm(Xi≤255为正整数),并假设各种邮票都有足够多张。要求计算所能获得的邮资最大范围。即求最大值MAX,使1-MAX之间的每一个邮资都能得到。例如:N=4,有2种邮票,面值分别为1分,4分,于是可以得到1-10分和12分,13分,16分邮资,由于得不到11分和15分,所以邮资的最大范围max=10 输入格式 第一行为最多粘贴的邮票张数n。第二行为邮票种数m。以下m行各有一个数字表示邮票的面值。 本地测试的输入格式: 第一行:m,n的值,中间用一空格隔开。 第二行:A[1..m](面额),每个数中间用一空格隔开。 输出格式 仅一个数,最大的max的值。 算法分析: 从面额1开始,建立递推关系方程。比如:面额1,2,4只用1张邮票行了,面额3可以表示为面额1,2的邮票和1+1=2张邮票,面额5有两种表示方式min(面额1+面额4,面额2+面额3)邮票数目……照此类推,递推关系方程不难建立,以下是递推的一种方法: 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int main() 5 { 6 freopen("stamp_data/STAMP14.in","r",stdin); 7 freopen("stamp_data/STAMP14.txt","w",stdout); 8 int n,m,i,j,c[256]={0},a[31001]={0}; 9 int b1=1; 10 11 scanf("%d%d",&m,&n);//local test 12 //scanf("%d%d",&n,&m);//online judge 13 for(i=1;i<=m;i++) 14 { 15 scanf("%d",&c[i]); 16 if(c[i]==1) b1=0; 17 } 18 19 if(b1==1) printf("0\n"); 20 else 21 { 22 i=1; a[1]=1;//a[i]=x表示构造i这个值用x张邮票 23 do 24 { 25 i++; 26 for(j=1;j<=m;j++) 27 { 28 if( (i%c[j]==0)&&( (i/c[j]<a[i]) || (a[i]==0) )) 29 a[i]=i/c[j]; //判断它能否被题目给定面额整除 30 } 31 for(j=1;j<=i/2;j++) //寻找 1<= j <=i使得a[j]+a[i-j]值最小 32 if(a[j]+a[i-j]<a[i]) a[i]=a[j]+a[i-j]; 33 }while((a[i]<=n)&&(a[i]!=0)); 34 printf("%d\n",i-1); 35 } 36 return 0; 37 } 这种递推方法原理是:对于某种要求得到的面额,判断它能否被题目给定面额整除,再寻找(1<=j<=i),使A[j]+A[i-j]值最小,求出凑成某种面额最少邮票数。 这种递推方法虽然简单,由于1<=邮票面额<=255,1<=n<=100,因此MAX值最多可达到25500,25500次循环里必定还有嵌套循环,因此算法不加优化,很难在规定时间内得出最优值。这就需要递推的算法优化。 进一步优化 何不将用m种面额邮票作循环,建立递推关系式:A[i]=min(A[i-C[j]]+1),于是当取到极限值时,程序减少了约1.6*10^8次循环,递推优化作用不言而喻。 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int main() 5 { 6 freopen("stamp_data/STAMP0.in","r",stdin); 7 freopen("stamp_data/STAMP0.txt","w",stdout); 8 int x[256]={0},pieces[30001]={0}; 9 int n,m,i; 10 int maxX=0; 11 scanf("%d%d",&m,&n); //local test 12 //scanf("%d%d",&n,&m); //online judge 13 for(i=1;i<=m;i++) 14 scanf("%d",&x[i]); 15 do 16 { 17 maxX++; 18 for(i=1;i<=m;i++) 19 { 20 if(maxX-x[i]>=0) 21 { 22 if(pieces[maxX]==0) pieces[maxX]=pieces[maxX-x[i]]+1; 23 if(pieces[maxX]>pieces[maxX-x[i]]+1) pieces[maxX]=pieces[maxX-x[i]]+1; 24 } 25 } 26 if(pieces[maxX]==0 || pieces[maxX]>n) 27 { 28 printf("%d\n",maxX-1); 29 break; 30 } 31 }while(1); 32 return 0; 33 }