华山青竹
TA的个人档案
个人介绍
一个喜欢玩代码的小青年呵呵呵
擅长的技术
- 高分内容
- 最新动态
- 文章
- 问答
-
发表了文章 2018-02-04
4103:踩方格
题目链接：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 }
-
发表了文章 2018-02-03
2287 火车站
题目链接：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 }
-
发表了文章 2018-02-03
平面分割问题
同一个平面内有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 }
-
发表了文章 2018-02-03
蜜蜂路线
【问题描述】如下图所示，一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房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 } 利用高精度数据解决
-
发表了文章 2018-02-03
邮票问题
题目链接： 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 }
滑动查看更多
暂无更多信息
-
发表了文章
2013-11-28
OpenJudge计算概论-异常细胞检测
-
发表了文章
2013-11-28
OpenJudge计算概论-找出第k大的数
-
发表了文章
2013-11-28
OpenJudge计算概论-找和为K的两个元素
-
发表了文章
2013-11-28
OpenJudge计算概论-整数的个数
-
发表了文章
2013-11-28
OpenJudge计算概论-自整除数
-
发表了文章
2013-11-28
OpenJudge计算概论-最大奇数与最小偶数之差的绝对值
-
发表了文章
2013-11-28
OpenJudge计算概论-最长单词2
-
发表了文章
2013-11-28
OpenJudge计算概论-最高的分数
-
发表了文章
2013-11-29
OpenJudge数据结构与算法-计算点的距离并排序
-
发表了文章
2013-11-30
OpenJudge计算概论-循环移动
-
发表了文章
2013-11-30
OpenJudge计算概论-中位数
-
发表了文章
2013-11-30
OpenJudge计算概论-校门外的树
-
发表了文章
2013-11-30
OpenJudge计算概论-寻找下标
-
发表了文章
2013-12-02
已知二叉树的中序和前序序列(或后序)求解树
-
发表了文章
2013-12-03
OpenJudge计算概论-Tomorrow never knows【输入日期计算下一天的日期】
-
发表了文章
2013-12-03
OpenJudge计算概论-扩号匹配问题【这个用到了栈的思想】
-
发表了文章
2013-12-03
OpenJudge计算概论-流感传染【这个题用二维数组】
-
发表了文章
2013-12-03
OpenJudge计算概论-排队游戏【这个用到了栈的思想】
-
发表了文章
2013-12-03
OpenJudge计算概论-四大湖
-
发表了文章
2013-12-03
九度OJ题目1387斐波那契数列
滑动查看更多
暂无更多信息