华山青竹
华山青竹_个人页
华山青竹
文章
543
问答
0
视频
0
个人介绍
一个喜欢玩代码的小青年呵呵呵
擅长的技术
-
发表了文章 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 }
-
发表了文章 2018-02-02
位数问题
【问题描述】 在所有的N位数中，有多少个数当中有偶数个数字3？ 由于结果可能很大，你只需要输出这个答案对12345取余的值。【输入格式】 读入一个数N【输出格式】 输出有多少个数中有偶数个数字3。【输入样例】 2【输出样例】 73【数据规模】 1<=N<=1000【样例说明】 在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个 算法分析： 方法一：排列组合(但需要运用动态规划)。 可以列出公式,在n个格子中放x个3(其中x为偶数,包括0)： 含义为在n个格子中取x个3,且不考虑第一位的特殊情况为 而第一位为0的情况是： 两者减下,就为答案。 算法二：递推 考虑这种题目,一般来说都是从第i-1位推导第i位,且当前位是取偶数还是取奇数的。 恍然大悟.可以用f[i][0]表示前i位取偶数个3有几种情况,f[i][1]表示前i位取奇数个3有几种情况。 则状态转移方程可以表示为:f[i][0]=f[i-1][0]*9+f[i-1][1]; f[i][1]=f[i-1][0]+f[i-1][1]*9; 边界条件:f[1][1]=1;f[1][0]=9; 1 【参考程序】 2 #include<iostream> 3 using namespace std; 4 int main() 5 { 6 int f[1001][2],n,i,x; 7 cin>>n; 8 f[1][1]=1;f[1][0]=9; 9 for(i=2;i<=n;i++) 10 { 11 x=f[1][0]; 12 if(i==n)x--; 13 f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345; 14 f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345; 15 } 16 cout<<f[n][0]; 17 return 0; 18 }
-
发表了文章 2018-02-02
昆虫繁殖
【问题描述】 科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。 每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)。 问过Z个月以后，共有成虫多少对？ 0=<X<=20,1<=Y<=20,X=<Z<=50【输入格式】 x,y,z的数值【输出格式】 过Z个月以后，共有成虫对数【输入样例】 1 2 8【输出样例】 37 1 #include<iostream> 2 using namespace std; 3 int main() 4 { //a[i]表示第i个月成虫对数；b[i]表示第i个月虫卵的的对数 5 long long a[101]={0},b[101]={0},i,j,x,y,z; 6 cin>>x>>y>>z; 7 for(i=1;i<=x;i++){a[i]=1;b[i]=0;} 8 for(i=x+1;i<=z+1;i++) //因为要统计到第z个月后，所以要for到z+1 9 { 10 b[i]=y*a[i-x]; 11 a[i]=a[i-1]+b[i-2]; 12 } 13 cout<<a[z+1]<<endl; 14 return 0; 15 }
-
发表了文章 2018-02-01
不定方程求解
题目链接：http://noi.openjudge.cn/ch0201/7650/ 总时间限制: 1000ms 内存限制: 65536kB 描述 给定正整数a，b，c。求不定方程 ax+by=c 关于未知数x和y的所有非负整数解组数。 输入 一行，包含三个正整数a，b，c，两个整数之间用单个空格隔开。每个数均不大于1000。 输出 一个整数，即不定方程的非负整数解组数。 样例输入 2 3 18 样例输出 4 来源 《奥数典型题举一反三（小学六年级）》 (ISBN 978-7-5445-2883-2) 第四章 第二讲 例1 1 #include <stdio.h> 2 int main(int argc, char *argv[]) 3 { 4 int a,b,c,x,y,count=0; 5 scanf("%d%d%d",&a,&b,&c); 6 for(x=0;x<=c/a;x++) 7 { 8 y=(c-a*x)/b; 9 if(a*x+y*b==c) count++; 10 } 11 printf("%d\n",count); 12 return 0; 13 } 备注：2017级全体同学贡献。
-
发表了文章 2018-01-31
子串计算
题目链接：http://noi.openjudge.cn/ch0201/2472/ 总时间限制: 1000ms 内存限制: 65536kB 描述 给出一个只包含0和1的字符串（长度在1到100之间），求其每一个子串出现的次数。 输入 一行，一个01字符串。 输出 对所有出现次数在1次以上的子串，输出该子串及出现次数，中间用单个空格隔开。按子串的字典序从小到大依次输出，每行一个。 样例输入 10101 样例输出 0 2 01 2 1 3 10 2 101 2 1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 5 struct obj 6 { 7 char str[105]; 8 int count; 9 }; 10 11 void fun(char temp[]); 12 int cmp(const void *a,const void *b); 13 14 struct obj b[60000]; 15 int indexOfBArr=0; //b[]的下标,indexOfBArr表示b[]真正使用的行数 16 17 int main(int argc, char *argv[]) 18 { 19 char a[105],temp[105]; 20 int i,j,len,k,t; 21 22 scanf("%s",a); 23 len=strlen(a); 24 25 //枚举所有子串 26 for(i=0;i<len;i++)//枚举子串的开始点 27 { 28 k=0; 29 for(j=i;j<len;j++)//枚举子串的结束点 30 { 31 temp[k]=a[j]; 32 k++; 33 temp[k]='\0'; 34 fun(temp);//扫描b[]的每一行对应的子串，检验是否已经保存temp[]这个子串。 35 } 36 } 37 38 qsort(b,indexOfBArr,sizeof(b[0]),cmp); 39 40 for(i=0;i<indexOfBArr;i++) 41 { 42 if(b[i].count>1) 43 printf("%s %d\n",b[i].str,b[i].count); 44 }/**/ 45 46 47 return 0; 48 } 49 void fun(char temp[])//扫描b[]的每一行对应的子串，检验是否已经保存temp[]这个子串。 50 { 51 int i; 52 if(indexOfBArr==0) { strcpy(b[0].str,temp); b[0].count=1; indexOfBArr++; return;} 53 for(i=0;i<indexOfBArr;i++) 54 { 55 if(strcmp(b[i].str,temp)==0) { b[i].count++; return; } 56 } 57 58 strcpy(b[indexOfBArr].str,temp); 59 b[indexOfBArr].count=1; 60 indexOfBArr++; 61 } 62 int cmp(const void *a,const void *b) 63 { 64 struct obj x,y; 65 x=*(struct obj *)a; 66 y=*(struct obj *)b; 67 return strcmp(x.str,y.str); 68 }
-
发表了文章 2018-01-31
白细胞计数
总时间限制: 1000ms 内存限制: 65536kB 题目链接：http://noi.openjudge.cn/ch0109/08/ 描述 医院采样了某临床病例治疗期间的白细胞数量样本n份，用于分析某种新抗生素对该病例的治疗效果。为了降低分析误差，要先从这n份样本中去除一个数值最大的 样本和一个数值最小的样本，然后将剩余n-2个有效样本的平均值作为分析指标。同时，为了观察该抗生素的疗效是否稳定，还要给出该平均值的误差，即所有有 效样本（即不包括已扣除的两个样本）与该平均值之差的绝对值的最大值。 现在请你编写程序，根据提供的n个样本值，计算出该病例的平均白细胞数量和对应的误差。 输入 输入的第一行是一个正整数n（2 < n <= 300），表明共有n个样本。以下共有n行，每行为一个浮点数，为对应的白细胞数量，其单位为10^9/L。数与数之间以一个空格分开。 输出 输出为两个浮点数，中间以一个空格分开。分别为平均白细胞数量和对应的误差，单位也是10^9/L。计算结果需保留到小数点后2位。 样例输入 5 12.0 13.0 11.0 9.0 10.0 样例输出 11.00 1.00 提示 为避免浮点精度误差过大，请使用double类型。 1 #include<stdio.h> 2 int main() 3 { 4 int n,i,maxIndex,minIndex; 5 double a[305],sum,avg; 6 double temp,maxDifferenceValue; 7 scanf("%d",&n); 8 scanf("%lf",&a[0]); 9 maxIndex=minIndex=0; 10 sum=a[0]; 11 for(i=1;i<n;i++) 12 { 13 scanf("%lf",&a[i]); 14 if(a[i]>a[maxIndex]) maxIndex=i; 15 if(a[i]<a[minIndex]) minIndex=i; 16 sum=sum+a[i]; 17 } 18 sum=sum-a[maxIndex]-a[minIndex]; 19 avg=sum/(n-2); 20 21 maxDifferenceValue=-1; 22 for(i=0;i<n;i++) 23 { 24 if(i!=maxIndex&&i!=minIndex) 25 { 26 temp=a[i]-avg; 27 temp=(temp>0?temp:-temp); 28 if(temp>maxDifferenceValue) maxDifferenceValue=temp; 29 } 30 } 31 printf("%.2lf %.2lf\n",avg,maxDifferenceValue); 32 return 0; 33 }
-
发表了文章 2018-01-29
头插法建立、输出单向链表的案例
1 #include<stdio.h> 2 #include<stdlib.h> 3 struct obj 4 { 5 int num; 6 struct obj *next; 7 }; 8 int main(int argc, char *argv[]) 9 { 10 int n,i,t; 11 struct obj *head=NULL,*temp=NULL,*p=NULL; 12 13 scanf("%d",&n); 14 for(i=0;i<n;i++) 15 { 16 scanf("%d",&t); 17 temp=(struct obj *)malloc(sizeof(struct obj)); 18 temp->num=t; 19 temp->next=NULL; 20 21 temp->next=head; 22 head=temp; 23 } 24 25 p=head; 26 while(p!=NULL) 27 { 28 printf("%d ",p->num); 29 p=p->next; 30 } 31 printf("\n"); 32 return 0; 33 }
-
发表了文章 2018-01-11
Lintcode 730 所有子集的和
已知： 给一整数 n, 我们需要求前n个自然数形成的集合的所有可能子集中所有元素的和。 示例： 给出 n = 2, 返回 6 可能的子集为 {{1}, {2}, {1, 2}}. 子集的元素和为 1 + 2 + 1 + 2 = 6 给出 n = 3, 返回 24 可能的子集为 {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} 子集的和为: 1 + 2 + 3 + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24 思路： 其实这更像是一个数学问题，而不是代码问题。以4为例子，取一个数，则取1的可能性为1种，取两个数字，则取1的可能性为3种，取三个数字，则取1的可能性为3种，取四个数字，可能性为1种，则1总共计算了 1+3+3+1 共8次, 其他三个数字也是8次。 所以，结合上面两个示例，很容易可以推的： 当已知n的值时，我们会取里面的每个数字2^(n-1)次 上述分析来源：http://blog.csdn.net/mio_bass/article/details/78797298 根据上述分析，求解的公式就是 公式解析：因为最后把所有子集的所有项累加的表达式里面，1~n的每一个数都有机会出现2^(n-1)次，所以求和表达式就变为： 最终变为上面第一个公式。 利用第一个公式求解就非常方便了。 补充： 对于“会取里面的每个数字2^(n-1)次”的另一种解析可以如下进行： 集合里面有1~n共n个元素。构造子集的时候，对每个元素而言都有取或不取两种选择，所以子集数目共有2^(n-1)个。 讨论这些子集：原集合的元素ai只有选和不选两种情况，故所有子集分两类：包含ai的子集和不包含ai的子集。每一类的子集个数都是2^(n-1)个。 所以最后面计算累加和的时候需要累加ai的次数是2^(n-1)次，也就是元素ai对累加和的贡献是ai*2^(n-1)。 每一个元素出现的次数都是2^(n-1)次，所以上述第二个公式即可推出来。 代码比较简单就不写了。 其他参考： http://blog.csdn.net/zhaohengchuan/article/details/78716365 http://blog.csdn.net/u010005161/article/details/52175525
-
发表了文章 2018-01-08
简单博弈论取石子
来源：https://www.cnblogs.com/thewaytomakemiracle/p/5018812.html 有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。 （一）巴什博弈（Bash Game，同余理论）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。 显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。 （二）威佐夫博弈（Wythoff Game，黄金分割）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。 这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有如下三条性质： 1。任何自然数都包含在一个且仅有一个奇异局势中。由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1> ak-1 。所以性质1。成立。 2。任意操作都可将奇异局势变为非奇异局势。 事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。 3。采用适当的方法，可以将非奇异局势变为奇异局势。假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）； 如果a = ak ，b > bk，那么，取走b - bk个物体，即变为奇异局势；如果 a = ak ， b < bk ,则同时从两堆中拿走 ak - ab - ak个物体,变为奇异局势（ ab - ak , ab - ak+ b - ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余的数量a - ak 即可； 如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k）,从第二堆里面拿走 b - bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b - aj即可。 从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。 那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，...,n 方括号表示取整函数)奇妙的是其中出现了黄金分割数（1+√5）/2 = 1。618..., 因此,由ak，bk组成的矩形近似为黄金矩形，由于2/（1+√5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[j（1+√5）/2]，那么a = aj，bj= aj + j，若不等于，那么a = aj+1，bj+1 = aj+1+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。 （三）尼姆博弈（Nim Game，异或理论）：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。 这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。 第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示这种运算。这种运算和一般加法不同的一点是1+1=0。先看（1，2，3）的按位模2加的结果： 1 =二进制012 =二进制103 =二进制11 （+）———————0 =二进制00 （注意不进位） 对于奇异局势（0，n，n）也一样，结果也是0。 任何奇异局势（a，b，c）都有a（+）b（+）c =0。如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b< c,我们只要将 c变为 a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要将c 变为a（+）b，只要从 c中减去 c-（a（+）b）即可。 例1。（14，21，39），14（+）21=27，39-27=12，所以从39中拿走12个物体即可达到奇异局势（14，21，27）。 例2。（55，81，121），55（+）81=102，121-102=19，所以从121中拿走19个物品就形成了奇异局势（55，81，102）。 例3。（29，45，58），29（+）45=48，58-48=10，从58中拿走10个，变为（29，45，48）。 例4。我们来实际进行一盘比赛看看： 甲:(7,8,9)->(1,8,9)奇异局势 乙:(1,8,9)->(1,8,4) 甲:(1,8,4)->(1,5,4)奇异局势 乙:(1,5,4)->(1,4,4) 甲:(1,4,4)->(0,4,4)奇异局势 乙:(0,4,4)->(0,4,2) 甲:(0.4,2)->(0,2,2)奇异局势 乙:(0,2,2)->(0,2,1) 甲:(0,2,1)->(0,1,1)奇异局势 乙:(0,1,1)->(0,1,0) 甲:(0,1,0)->(0,0,0)奇异局势 甲胜。
-
发表了文章 2018-01-07
分蛋糕
总时间限制: 1000ms 内存限制: 65536kB 描述 有一块矩形大蛋糕，长和宽分别是整数w 、h。现要将其切成m块小蛋糕，每个小蛋糕都必须是矩形、且长和宽均为整数。切蛋糕时，每次切一块蛋糕，将其分成两个矩形蛋糕。请计算：最后得到的m块小蛋糕中，最大的那块蛋糕的面积下限。 假设w= 4, h= 4, m= 4，则下面的切法可使得其中最大蛋糕块的面积最小。 假设w= 4, h= 4, m= 3，则下面的切法会使得其中最大蛋糕块的面积最小: 输入 共有多行，每行表示一个测试案例。每行是三个用空格分开的整数w, h, m ，其中1 ≤ w, h, m ≤ 20 ， m ≤ wh. 当 w = h = m = 0 时不需要处理，表示输入结束。 输出 每个测试案例的结果占一行，输出一个整数，表示最大蛋糕块的面积下限。 样例输入 4 4 4 4 4 3 0 0 0 样例输出 4 6 算法分析：直接枚举DP f[i][j][k]表示把i*j分成k块蛋糕时，最大的那块蛋糕的面积下限（最小值）。枚举横切竖切形成的新蛋糕即可 1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define N 25 5 #define INF 5005 6 int f[N][N][N];int w,h,m; 7 int main(){ 8 w=h=m=20; 9 for(int i=1;i<=w;i++){ 10 for(int j=1;j<=h;j++){ 11 f[i][j][1]=i*j; 12 for(int k=2;k<=m;k++){ 13 f[i][j][k]=INF; 14 for(int r=1;r<i;r++){ 15 f[i][j][k]=min(f[i][j][k],max(f[r][j][k-1],(i-r)*j)); 16 for(int p=1;p<k;p++) 17 f[i][j][k]=min(f[i][j][k],max(f[r][j][p],f[i-r][j][k-p])); 18 } 19 20 for(int c=1;c<j;c++){ 21 f[i][j][k]=min(f[i][j][k],max(f[i][c][k-1],(j-c)*i)); 22 for(int p=1;p<k;p++) 23 f[i][j][k]=min(f[i][j][k],max(f[i][c][p],f[i][j-c][k-p])); 24 } 25 } 26 } 27 } 28 while(scanf("%d%d%d",&w,&h,&m)&&(w||h||m)){ 29 printf("%d\n",f[w][h][m]);} 30 return 0; 31 } 来源：http://blog.csdn.net/qq_18455665/article/details/50512764
-
发表了文章 2018-01-07
[转]POJ3624 Charm Bracelet(典型01背包问题)
来源：https://www.cnblogs.com/jinglecjy/p/5674796.html 题目链接：http://bailian.openjudge.cn/practice/4131/ Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 32897 Accepted: 14587 Description Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880). Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings. Input * Line 1: Two space-separated integers: N and M* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di Output * Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints Sample Input 4 6 1 4 2 6 3 12 2 7 Sample Output 23 一、题目大意 有N个物品，分别有不同的重量Wi和价值Di，Bessie只能带走重量不超过M的物品，要是总价值最大，并输出总价值。 二、解题思路 典型的动态规划题目，用一个数组记录背包各个重量的最优解，不断地更新直到穷尽所有可能性。 状态更新公式：state[weight] = max{state[weight-W[i]]+D[i], state[weight]} 1 // 背包问题（动态规划） 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #define MAXN 3402 6 #define MAXM 12880 7 using namespace std; 8 9 int main(){ 10 int N, M, W[MAXN+5], D[MAXN+5], dp[MAXM+5]; 11 while(scanf("%d%d", &N, &M) != EOF){ 12 for(int i=0; i<N; i++){ 13 scanf("%d%d", &W[i], &D[i]); 14 } 15 memset(dp, 0, sizeof(dp)); 16 for(int i=0; i<N; i++){ 17 for(int left_w=M; left_w>=W[i]; left_w--){ 18 dp[left_w] = max(dp[left_w-W[i]]+D[i], dp[left_w]); 19 } 20 } 21 printf("%d\n", dp[M]); 22 } 23 24 return 0; 25 }
-
发表了文章 2018-01-01
将cmd中命令输出保存为TXT文本文件
转自：https://www.cnblogs.com/hongten/archive/2013/03/27/hongten_windows_cms.html 例如：将Ping命令的加长包输出到D盘的ping.txt文本文件。1、在D:目录下创建文本文件ping.txt（这步可以省略，偶尔提示无法创建文件时需要）2、在提示符下输入ping www.idoo.org.ru －t > D:ping.txt3、这时候发现D盘下面的ping.txt里面已经记录了所有的信息备注：只用“>”是覆盖现有的结果，每一个命令结果会覆盖现有的txt文件，如果要保存很多命令结果的话，就需要建立不同文件名的txt文件。那么有没有在一个更好的办法只用一个txt文件呢？答案是肯定的，要在同一个txt文件里面追加cmd命令结果，就要用“>>”替换“>” 就可以了. 看来以后，自己做了一下测试，下面是我个人测试的结果： 在执行命令： 1 ping www.baidu.com -t > c:\hongten\hongten.txt 首先我们要在c盘中建立hongten的文件夹....不然系统找不到的... 执行命令： 如果要关闭，直接在控制台按：Ctrl+c 即可....
-
发表了文章 2017-12-24
最佳加法表达式
最佳加法表达式 总时间限制: 1000ms 内存限制: 65536kB 描述 给定n个1到9的数字，要求在数字之间摆放m个加号(加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36 输入 有不超过15组数据每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=50)第二行是若干个数字。数字总数n不超过50,且 m <= n-1 输出 对每组数据，输出最小加法表达式的值 样例输入 2 123456 1 123456 4 12345 样例输出 102 579 15 提示 要用到高精度计算，即用数组来存放long long 都装不下的大整数，并用模拟列竖式的办法进行大整数的加法。 算法参考：http://www.cnblogs.com/quintessence/p/7206417.html 使用了高精度 http://www.cnblogs.com/Renyi-Fan/p/6970166.html 没有使用高精度，有详细分析 假定数字串长度是n，添完加号后,表达式的最后一个加号添加在第 i 个数字后面，那么整个表达式的最小值，就等于在前 i 个数字中插入 m – 1个加号所能形成的最小值，加上第 i + 1到第 n 个数字所组成的数的值（i从1开始算）。 设V(m,n)表示在n个数字中插入m个加号所能形成的表达式最小值，那么：if m = 0V(m,n) = n个数字构成的整数else if n < m + 1V(m,n) = ∞elseV(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m … n-1)Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操作复杂度是O(j-i+1)总时间复杂度：O(mn2) .（dp二维表已经加号的位置） 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int INF=0x3f3f3f3f; 7 const int N=1005; 8 int a[N],num[N][N],dp[N][N]; 9 //a[N]里面是存数字串 10 //num[i][j]表示数字串a[N]的第i位到第j位之间的数字串表示的数组 11 //dp[i][j]在i个数字中插入j个加号所能形成的表达式最小值 12 int main(){ 13 int n,m; 14 while(scanf("%d %d",&n,&m)){ 15 for(int i=1;i<=n;i++){ 16 scanf("%d",&a[i]); 17 } 18 //预处理,计算i到j数字串组成的数字 19 for(int i=1;i<=n;i++){ 20 num[i][i]=a[i];//只有一个数字 21 for(int j=i+1;j<=n;j++){ 22 num[i][j]=num[i][j-1]*10+a[j]; 23 } 24 } 25 memset(dp,0x3f,sizeof(dp)); 26 for(int i=1;i<=n;i++){ 27 dp[0][i]=num[1][i];//无加号时 28 } 29 //其实就是感觉在那个位置放不放加号 30 //这里n可以写在m前面。要加一个限制条件n>m，好麻烦，所以m在前且n=m+1 31 //这里k的取值范围就是m到n，k表示在第k个数后面插入加号 32 for(int i=1;i<=m;i++) 33 for(int j=i;j<=n;j++) 34 for(int k=i;k<=j;k++) 35 dp[i][j]=min(dp[i][j],dp[i-1][k]+num[k+1][j]); 36 cout<<dp[m][n]<<endl; 37 } 38 } 未使用高精度的代码 下面是使用了高精度数据结构的算法代码： 首先，由于 数据范围显然需要用到高精度，高精度的写法不再赘述。 dp[i][j]表示前i个数添加了j个加号得到的最小和。转移方程为 dp[i][j]=min(dp[x][j-1]+num[x+1][i]) 其中x>=j且x<i num[x+1][i]表示第x+1位到第i位组成的数。 1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <queue> 8 #include <set> 9 #include <map> 10 #include <list> 11 #include <vector> 12 #include <stack> 13 #define mp make_pair 14 //#define P make_pair 15 #define MIN(a,b) (a>b?b:a) 16 //#define MAX(a,b) (a>b?a:b) 17 typedef long long ll; 18 typedef unsigned long long ull; 19 const int MAX=1e2+5; 20 const int INF=1e8+5; 21 using namespace std; 22 //const int MOD=1e9+7; 23 typedef pair<ll,int> pii; 24 const double eps=0.00000001; 25 26 string add(string x,string y) 27 { 28 string re; 29 int jin=0; 30 for(int i=x.length()-1,j=y.length()-1;i>=0||j>=0;i--,j--) 31 { 32 re=" "+re; 33 re[0]=(i>=0?x[i]-'0':0)+(j>=0?y[j]-'0':0)+jin; 34 if(re[0]>=10) 35 jin=1,re[0]=(re[0]%10)+'0'; 36 else 37 jin=0,re[0]=re[0]+'0'; 38 } 39 if(jin) 40 re='1'+re; 41 return re; 42 } 43 string mins(string x,string y) 44 { 45 if(x.length()<y.length()) 46 return x; 47 else if(y.length()<x.length()) 48 return y; 49 else return x<y?x:y; 50 } 51 int m; 52 string x; 53 string dp[55][55]; 54 int main() 55 { 56 while(~scanf("%d",&m)) 57 { 58 cin>>x; 59 int len=x.length(); 60 x=" "+x; 61 for(int i=0;i<=len;i++) 62 dp[i][0]=x.substr(1,i); 63 for(int j=1;j<=m;j++) 64 for(int i=j+1;i<=len;i++) 65 for(int s=j;s<i;s++) 66 { 67 if(s==j) 68 dp[i][j]=add(dp[s][j-1],x.substr(s+1,i-s)); 69 else 70 dp[i][j]=mins(dp[i][j],add(dp[s][j-1],x.substr(s+1,i-s))); 71 } 72 cout<<dp[len][m]<<"\n"; 73 } 74 } 下面是自己写的原始高精度算法的代码，结果超时了。。。 1 #include <stdio.h> 2 #include<string.h> 3 4 #define MaxLength 91 5 int m,len,a[MaxLength]; 6 long long count=0; 7 8 void init(char str[],int a[]); 9 void add(int a[],int b[],int c[]); 10 int cmp(int a[],int b[]); 11 void fun(int m,int n,int min[]); 12 void num(int i,int j,int t[]); 13 void output(int minSum[]); 14 15 int main(int argc, char *argv[]) 16 { 17 freopen("003.txt","r",stdin); 18 freopen("003.out","w",stdout); 19 char str[MaxLength]; 20 int minSum[MaxLength]; 21 int i; 22 23 while(scanf("%d%s",&m,str)!=EOF) 24 { 25 init(str,a); 26 len=a[0]; 27 /*printf("%d\n",m); 28 for(i=1;i<=a[0];i++) printf("%d",a[i]); 29 printf("\n");*/ 30 for(i=1;i<MaxLength;i++) { minSum[i]=9; } 31 minSum[0]=MaxLength+4; 32 33 fun(m,len,minSum); 34 output(minSum); 35 } 36 37 /*char str1[20]="1",str2[20]="234"; 38 int aa[25],bb[25],cc[25]; 39 40 init(str1,aa); 41 init(str2,bb); 42 for(int i=0;i<=aa[0];i++) printf("%d",aa[i]);printf("\n"); 43 for(int i=0;i<=bb[0];i++) printf("%d",bb[i]);printf("\n"); 44 add(aa,bb,cc); 45 for(int i=0;i<=cc[0];i++) printf("%d",cc[i]);printf("\n");*/ 46 47 return 0; 48 } 49 50 /******************************************************************************/ 51 /*输入一个字符串str表示高精度正整数 52 将str转换成int数组存储在a[] 53 a[0]存储str代表的数字的位数 54 str正序存储在a[]中 55 */ 56 void init(char str[],int a[]) 57 { 58 int i; 59 //memset(a,0,sizeof(int)*MaxLength); 60 a[0]=strlen(str); 61 for(i=1;i<=a[0];i++) 62 a[i]=str[i-1]-'0'; 63 } 64 /******************************************************************************/ 65 void fun(int m,int n,int min[]) 66 { 67 int i,j,x[MaxLength]={0},y[MaxLength]={0},sum[MaxLength]; 68 //printf("m=%d n=%d\n",m,n); 69 if(m==0) 70 { 71 num(1,n,min); 72 } 73 else if(n<m+1) 74 { 75 for(i=1;i<MaxLength;i++) { min[i]=9;} 76 min[0]=MaxLength+2; 77 } 78 else 79 { 80 for(i=0;i<MaxLength;i++) min[i]=9; 81 min[0]=MaxLength+2; 82 83 for(i=m;i<n;i++) 84 { 85 fun(m-1,i,x); 86 num(i+1,n,y); 87 add(x,y,sum); 88 if(cmp(sum,min)==-1) 89 { for(j=0;j<=sum[0];j++) min[j]=sum[j]; } 90 } 91 } 92 } 93 /******************************************************************************/ 94 void num(int i,int j,int t[]) 95 { 96 count++; 97 //printf("%d\n",count); 98 99 int k; 100 t[0]=j-i+1; 101 for(k=1;i<=j;k++,i++) t[k]=a[i]; 102 } 103 /******************************************************************************/ 104 /* 输入高精度正整数a和b,计算c=a+b */ 105 void add(int a[],int b[],int c[]) 106 { 107 int x=0,i=a[0],j=b[0],k=1; 108 //memset(c,0,sizeof(int)*MaxLength); 109 //这个地方初始化的字节数的解释：c[]从主调函数传过来，c的元素个数未知。 110 //sizeof(c)只能测出一个元素的字节数，而不是整个数组的字节数 111 112 while(i>0&&j>0) 113 { 114 c[k]=a[i]+b[j]+x;//x表示加法的进位 115 x=c[k]/10; //新产生的进位 116 c[k]=c[k]%10; //只保留个位 117 k++; 118 i--; 119 j--; 120 } 121 while(i>0) 122 { 123 c[k]=a[i]+x; 124 x=c[k]/10; 125 c[k]=c[k]%10; 126 k++; 127 i--; 128 } 129 while(j>0) 130 { 131 c[k]=b[j]+x; 132 x=c[k]/10; 133 c[k]=c[k]%10; 134 k++; 135 j--; 136 } 137 c[k]=x; //可能有向更高位的进位 138 if(c[k]==0) k--; 139 c[0]=k; 140 141 for(i=1,j=c[0];i<j;i++,j--) 142 { 143 x=c[i]; c[i]=c[j]; c[j]=x; 144 } 145 } 146 /******************************************************************************/ 147 /* 比较a[]和b[]表示的两个高精度整数的大小，返回1表示a>b，0表示相等，-1表示a<b */ 148 int cmp(int a[],int b[]) 149 { 150 int i; 151 if(a[0]<b[0]) return -1; 152 else if(a[0]>b[0]) return 1; 153 else 154 { 155 i=1; 156 while(i<=a[0]&&a[i]==b[i]) i++; 157 if(i>a[0]) return 0; 158 else if(a[i]<b[i])return -1; 159 else return 1; 160 } 161 } 162 /******************************************************************************/ 163 void output(int minSum[]) 164 { 165 int i; 166 for(i=1;i<=minSum[0];i++) 167 { 168 printf("%d",minSum[i]); 169 } 170 printf("\n"); 171 } View Code
-
发表了文章 2017-11-08
洛谷 P1736 创意吃鱼法
题目描述 题目链接：https://www.luogu.org/problemnew/show/P1736 回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。 在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。 猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？ 输入输出格式 输入格式： 有多组输入数据，每组数据： 第一行有两个整数n和m（n,m≥1），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。 对于30%的数据，有n,m≤100 对于60%的数据，有n,m≤1000 对于100%的数据，有n,m≤2500 输出格式： 只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。 输入输出样例 输入样例#1： 4 6 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 输出样例#1：3 算法分析：来源：洛谷题解板块 https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1736 1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 6 int n,m,ans; 7 int a[2509][2509],f[2509][2509],s1[2509][2509],s2[2509][2509];//s1为横向，s2为纵向 8 9 int main() 10 { 11 cin>>n>>m; 12 //第一遍左上---->右下 13 for(int i=1;i<=n;i++) 14 for(int j=1;j<=m;j++) 15 { 16 scanf("%d",&a[i][j]); 17 if(!a[i][j]) 18 { 19 s1[i][j]=s1[i][j-1]+1; 20 s2[i][j]=s2[i-1][j]+1; 21 } 22 if(a[i][j]) 23 f[i][j]=min(f[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1; 24 ans=max(ans,f[i][j]); 25 } 26 27 //第二遍右上---->左下 28 memset(f,0,sizeof(f)); //数组置0 29 memset(s1,0,sizeof(s1)); 30 memset(s2,0,sizeof(s2)); 31 32 for(int i=1;i<=n;i++) 33 for(int j=m;j>=1;j--) 34 { 35 if(!a[i][j]) 36 { 37 s1[i][j]=s1[i][j+1]+1; 38 s2[i][j]=s2[i-1][j]+1; 39 } 40 if(a[i][j]) 41 f[i][j]=min(f[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1; 42 ans=max(ans,f[i][j]); 43 } 44 cout<<ans<<endl; 45 return 0; 46 } 类似参考题目： 洛谷 P1387 最大正方形 题解
-
发表了文章 2017-11-08
洛谷P1387 最大正方形
题目描述 题目链接：https://www.luogu.org/problemnew/show/P1387 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。 输入输出格式 输入格式： 输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1. 输出格式： 一个整数，最大正方形的边长 输入输出样例 输入样例#1： 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 输出样例#1： 2 算法解析： 来源：http://www.cnblogs.com/CXSheng/p/7801313.html 本题也可以参考洛谷题解 动态规划，求什么设什么。 设maxSize[i][j] = 以a[i][j]为右下角的最大正方形边长， 则maxSize[i][j] = k代表着a[i][j]左上方k*k区域内的数字都是1， 起初我想，如果a[i][j]是1，那么就可以把maxSize[i-1][j-1]代表的一大片矩形的边长扩大1. 即maxSize[i][j]= ① 0 ，a[i-1][j-1]==0 or 边界； ② maxSize[i-1][j-1]+1 , a[i-1][j-1]!=0； 但是!这是片面的，因为我忽略了a[i][j]正上方和正左方是否存在0的情况。 如图： 假设我们要求maxSize[i][j]对应着最右下角的红点， 浅蓝色的圈是maxSize[i-1][j-1]对结果的影响； 橙色的圈是a[i][j]正上方连续的1对结果的影响； 绿色的圈是a[i][j]正左方连续的1对结果的影响； 总图如下： 去三个值中最小的，记入maxSize[i][j] 综上可知，更新设定： 当a[i][j]为1时： 设maxSize[i][j] = 以a[i][j]为右下角的最大正方形边长， LeftNum1[i][j] = a[i][j]（不包括）正左边连续1的个数， UpNum1[i][j] = a[i][j]（不包括）正上方边连续1的个数， 于是maxSize[i][j] = min（maxSize[i-1][j-1]+1,leftNum1[i][j]+1,upNum1[i][j]+1） 注意边界情况即可。 1 #include<stdio.h> 2 #define MAXN 100 3 #define MAXM 100 4 int array[MAXN+1][MAXM+1]={0}; 5 int maxSize[MAXN+1][MAXM+1]={0}; 6 int leftNum1[MAXN+1][MAXM+1]={0}; 7 int upNum1[MAXN+1][MAXM+1]={0}; 8 int n,m; 9 int Figure(int tempN,int tempM) 10 { 11 if(tempN-1==0||tempM-1==0||array[tempN-1][tempM-1]==0) 12 return 1; 13 int min=maxSize[tempN-1][tempM-1]+1; 14 if(leftNum1[tempN][tempM]+1<min) 15 min=leftNum1[tempN][tempM]+1; 16 if(upNum1[tempN][tempM]+1<min) 17 min=upNum1[tempN][tempM]+1; 18 return min; 19 } 20 void tPrint() 21 { 22 /* int i,j; 23 printf("\n"); 24 for(i=1;i<=n;i++) 25 { 26 for(j=1;j<=m;j++) 27 //printf("%d ",[i][j]); 28 printf("%d ",upNum1[i][j]);//============== 29 printf("\n"); 30 } 31 printf("\n");*/ 32 } 33 int main() 34 { 35 int i,j; 36 scanf("%d%d",&n,&m); 37 int maxans=0; 38 for(i=1;i<=n;i++) 39 for(j=1;j<=m;j++) 40 scanf("%d",&array[i][j]); 41 for(i=1;i<=n;i++) 42 for(j=1;j<=m;j++) 43 { 44 if(j==1||array[i][j]==0) 45 leftNum1[i][j]=0; 46 else 47 { 48 if(array[i][j-1]==0) 49 leftNum1[i][j]=0; 50 else 51 leftNum1[i][j]=leftNum1[i][j-1]+1; 52 } 53 54 if(i==1||array[i][j]==0) 55 upNum1[i][j]=0; 56 else 57 { 58 if(array[i-1][j]==0) 59 upNum1[i][j]=0; 60 else 61 upNum1[i][j]=upNum1[i-1][j]+1; 62 } 63 } 64 for(i=1;i<=n;i++) 65 for(j=1;j<=m;j++) 66 { 67 maxSize[i][j]=Figure(i,j); 68 if(maxSize[i][j]>maxans) 69 maxans=maxSize[i][j]; 70 } 71 tPrint(); 72 printf("%d\n",maxans); 73 return 0; 74 } 类似参考题目： 洛谷P1736 创意吃鱼法 题解
-
发表了文章 2017-11-05
1078 最小生成树
链接：http://codevs.cn/problem/1078/ 题目描述 Description 农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。 每两个农场间的距离不会超过100000 输入描述 Input Description 第一行： 农场的个数，N（3<=N<=100）。 第二行..结尾: 接下来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们每行限制在80个字符以内，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为线路从第i个农场到它本身的距离在本题中没有意义。 输出描述 Output Description 只有一个输出，是连接到每个农场的光纤的最小长度和。 样例输入 Sample Input 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 样例输出 Sample Output 28 算法分析： 这道题是典型的最小生成树模板题。 1 #include<stdio.h> 2 #include<stdlib.h> 3 #define MAXV 100 4 #define INF 100005 5 void prim(int **edges,int n,int v); 6 int main(int argc, char *argv[]) 7 { 8 int N,**edges; 9 int i,j; 10 scanf("%d",&N); 11 edges=(int **)malloc(sizeof(int*)*N); 12 for(i=0;i<N;i++) 13 edges[i]=(int *)malloc(sizeof(int)*N); 14 for(i=0;i<N;i++) 15 for(j=0;j<N;j++) 16 scanf("%d",&edges[i][j]); 17 prim(edges,N,0); 18 return 0; 19 } 20 void prim(int **edges,int n,int v) 21 { 22 int total=0; 23 int lowcost[MAXV]; 24 // lowcost[k]=0标记k已经加入U.另外，lowcost[k]=w表示从最小生成树的点到达k节点的最短边是w 25 int min; 26 int closest[MAXV],i,j,k; //对于某个节点i∈V-U， closest[i]=v表示节点i借助某条边依附于处在U中的节点v。 27 for (i=0;i<n;i++) //给lowcost[]和closest[]置初值 28 { 29 lowcost[i]=edges[v][i]; 30 closest[i]=v; //closest[i]=v表示当前状态下到达i点的最合适的经过点是v 31 } 32 for (i=1;i<n;i++) //找出n-1个顶点 33 { 34 min=INF; 35 for (j=0;j<n;j++) //在(V-U)中找出离U最近的顶点k 36 if (lowcost[j]!=0 && lowcost[j]<min) 37 { 38 min=lowcost[j]; 39 k=j; //k记录最近顶点的编号 40 } 41 //printf(" 边(%d,%d)权为:%d\n",closest[k]+1,k+1,min); 42 total=total+min; 43 lowcost[k]=0; //标记k已经加入U 44 for (j=0;j<n;j++) //修改数组lowcost和closest 45 if (edges[k][j]!=0 && edges[k][j]<lowcost[j]) 46 { 47 lowcost[j]=edges[k][j]; 48 closest[j]=k; //closest[j]=k表示构造最小生成树过程中，当前状态下到达j节点最优的路径是经过k节点。 49 } 50 } 51 //printf("最小生成树权值之和：%d\n",total); 52 printf("%d\n",total); 53 }
-
发表了文章 2017-10-27
判断元素是否存在
题目链接：http://noi.openjudge.cn/ch0113/41/ 总时间限制: 1000ms 内存限制: 65536kB 描述 有一个集合M是这样生成的： (1) 已知 k 是集合 M 的元素； (2) 如果 y 是 M 的元素，那么， 2y+1 和 3y+1 都是 M 的元素； (3) 除了上述二种情况外，没有别的数能够成为 M 的一个元素。 问题：任意给定 k 和 x，请判断 x 是否是 M 的元素。这里的 k是无符号整数，x 不大于 100000， 如果是，则输出YES，否则，输出 NO 输入 输入整数 k 和 x, 逗号间隔。 输出 如果是，则输出 YES，否则，输出NO 样例输入 0,22 样例输出 YES 代码一：深搜 1 #include<cstdio> 2 int k,x; 3 int pd(int k,int x) 4 { 5 if(k>x) return 0; 6 else if(k==x) return 1; 7 return (pd(2*k+1,x)||pd(3*k+1,x)); 8 } 9 int main() 10 { 11 scanf("%d,%d",&k,&x); 12 if(pd(k,x)==1) printf("YES"); 13 else if(pd(k,x)==0) printf("NO"); 14 return 0; 15 } 下面是广搜算法代码，是错的代码： 1 #include <iostream> 2 #include<stdio.h> 3 #include<queue> 4 using namespace std; 5 int bfs(long long k,int x) 6 { 7 long long t1,t2,t3; 8 if(k==x) return 1; 9 else if(k>x) return -1; 10 11 queue<long long> q; 12 q.push(k); 13 14 while(!q.empty()) 15 { 16 //printf("%lld\n",q.front()); 17 t1=q.front(); q.pop(); 18 t2=t1*2+1; 19 t3=t1*3+1; 20 if(t2==x||t3==x) return 1; 21 else if(t2>x&&t3>x) return -1; 22 else 23 { 24 if(t2<x) q.push(t2); 25 if(t3<x) q.push(t3); 26 } 27 } 28 } 29 int main() 30 { 31 long long k; 32 int x; 33 freopen("r.txt","w",stdout); 34 scanf("%lld,%d",&k,&x); 35 printf("%lld %d\n",k,x); 36 int res=bfs(k,x); 37 if(res==1)printf("YES\n"); 38 else printf("NO\n"); 39 return 0; 40 } 广搜，不能AC 错误原因： 有可能会发生这样一个情况：比较大的数据先入队，然后超x了结果返回-1。其实后面还有小数据没有被测到。 可以按如下方式修改： 1 #include <iostream> 2 #include<stdio.h> 3 #include<queue> 4 using namespace std; 5 int bfs(long long k,int x) 6 { 7 long long t1,t2,t3; 8 if(k==x) return 1; 9 else if(k>x) return -1; 10 11 queue<long long> q; 12 q.push(k); 13 14 while(!q.empty()) 15 { 16 //printf("%lld\n",q.front()); 17 t1=q.front(); q.pop(); 18 t2=t1*2+1; 19 t3=t1*3+1; 20 if(t2==x||t3==x) return 1; 21 else 22 { 23 if(t2<x) q.push(t2); 24 if(t3<x) q.push(t3); 25 } 26 } 27 return -1; 28 } 29 int main() 30 { 31 long long k; 32 int x; 33 34 scanf("%lld,%d",&k,&x); 35 int res=bfs(k,x); 36 if(res==1)printf("YES\n"); 37 else printf("NO\n"); 38 return 0; 39 }
-
发表了文章 2017-10-21
1531 山峰 【栈的应用】
题目连接：http://codevs.cn/problem/1531/ 题目描述 Description Rocky山脉有n个山峰，一字排开，从西向东依次编号为1, 2, 3, ……, n。每个山峰的高度都是不一样的。编号为i的山峰高度为hi。 小修从西往东登山。每到一座山峰，她就回头观望自己走过的艰辛历程。在第i座山峰，她记录下自己回头能看到的山峰数si。 何谓“能看到”？如果在第i座山峰，存在j<k<i，hj<hk，那么第j座山峰就是不可见的。除了不可见的山峰，其余的山峰都是可见的。 回家之后，小修把所有的si加起来得到S作为她此次旅行快乐值。现在n座山峰的高度都提供给你了，你能计算出小修的快乐值吗？ 输入描述 Input Description 第一行一个整数n(n<=15000)。 第i+1(1<=i<=n)行是一个整数hi（hi<=109）。 输出描述 Output Description 仅一行：快乐值。 样例输入 Sample Input 5 2 1 3 5 9 样例输出 Sample Output 5 数据范围及提示 Data Size & Hint 说明：s1=0, s2=1, s3=2, s4=1, s5=1。 分析： 只用维护当前单调递减的山峰序列即可 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<stack> 5 using namespace std; 6 int n,a[15050],ans,s[15009],top=1; 7 int main() 8 { 9 scanf("%d",&n); 10 for(int i=1;i<=n;i++) 11 scanf("%d",&a[i]); 12 s[1]=a[1]; 13 for(int i=2;i<=n;i++) 14 { 15 ans+=top; 16 if(s[top]>a[i]) s[++top]=a[i]; 17 else { 18 while(s[top]<=a[i]&&top>=1) 19 { 20 top--; 21 } 22 s[++top]=a[i]; 23 } 24 } 25 printf("%d",ans); 26 return 0; 27 } 代码来源：http://www.cnblogs.com/suishiguang/p/6216847.html
-
发表了文章 2017-10-13
什么是P问题、NP问题和NPC问题
来源：http://www.matrix67.com/blog/archives/105 这或许是众多OIer最大的误区之一。 你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。接下来你可以看到，把NP问题当成是 NPC问题是一个多大的错误。 还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。 容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。 自然地，人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。有些问题甚至根本不可能找到一个正确的算法来，这称之为“不可解问题”(Undecidable Decision Problem)。The Halting Problem就是一个著名的不可解问题，在我的Blog上有过专门的介绍和证明。再比如，输出从1到n这n个数的全排列。不管你用什么方法，你的复杂度都是阶乘级，因为你总得用阶乘级的时间打印出结果来。有人说，这样的“问题”不是一个“正规”的问题，正规的问题是让程序解决一个问题，输出一个“YES”或“NO”（这被称为判定性问题），或者一个什么什么的最优值（这被称为最优化问题）。那么，根据这个定义，我也能举出一个不大可能会有多项式级算法的问题来：Hamilton回路。问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做Hamilton回路）。这个问题现在还没有找到多项式级的算法。事实上，这个问题就是我们后面要说的NPC问题。 下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。 接下来引入NP问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。比方说，我RP很好，在程序中需要枚举时，我可以一猜一个准。现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我RP很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题，即你猜到了解但是没用，因为你不能在多项式的时间里去验证它。下面我要举的例子是一个经典的例子，它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然，前面所说的Hamilton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样：试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有Hamilton回路”。 之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“NP问题”，实际上是在探讨NP问题与P类问题的关系。 很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中，把所有 NP问题划进另一个集合NP中，那么，显然有P属于NP。现在，所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP？通常所谓的“NP问题”，其实就一句话：证明或推翻P=NP。 NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问 题，好比物理学中的大统一和数学中的歌德巴赫猜想等。 目前为止这个问题还“啃不动”。但是，一个总的趋势、一个大方向是有的。人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在，使人们相信P≠NP。下文将花大量篇幅介绍NPC问题，你从中可以体会到NPC问题使P=NP变得多么不可思议。 为了说明NPC问题，我们先引入一个概念——约化(Reducibility，有的资料上叫“归约”)。 简单地说，一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem，旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。 “问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。 很显然，约化具有一项重要的性质：约化具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。这个道理非常简单，就不必阐述了。 现在再来说一下约化的标准概念就不难理解了：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B。 当然，我们所说的“可约化”是指的可“多项式地”约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。 好了，从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC 问题，也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。再次回到全文开头，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。此时，我的目的终于达到了，我已经把NP问题和NPC问题区别开了。到此为止，本文已经写了近5000字了，我佩服你还能看到这里来，同时也佩服一下自己能写到这里来。 NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了。 既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。 顺便讲一下NP-Hard问题。NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。 不要以为NPC问题是一纸空谈。NPC问题是存在的。确实有这么一个非常具体的问题属于NPC问题。下文即将介绍它。 下文即将介绍逻辑电路问题。这是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。 逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。 什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。看下面一例，不需要解释你马上就明白了。 ┌───┐ │ 输入1├─→┐ ┌──┐ └───┘ └─→┤ │ │ or ├→─┐ ┌───┐ ┌─→┤ │ │ ┌──┐ │ 输入2├─→┤ └──┘ └─→┤ │ & nbsp;└───┘ │ ┌─→┤AND ├──→输出 └────────┘┌→┤ │ ┌───┐ ┌──┐ │ └──┘ │ 输入3├─→┤ NOT├─→────┘ └───┘ └──┘ 这是个较简单的逻辑电路，当输入1、输入2、输入3分别为True、True、False或False、True、False时，输出为True。 有输出无论如何都不可能为True的逻辑电路吗？有。下面就是一个简单的例子。 ┌───┐ │输入1 ├→─┐ ┌──┐ └───┘ └─→┤ │ │AND ├─→┐ ┌─→┤ │ │ │ └──┘ │ ┌──┐ │ └→┤ │ ┌───┐ │ │AND ├─→输出 │输入2 ├→─┤ ┌──┐ ┌→┤ │ └───┘ └→┤NOT ├→──┘ └──┘ └──┘ 上面这个逻辑电路中，无论输入是什么，输出都是False。我们就说，这个逻辑电路不存在使输出为True的一组输入。 回到上文，给定一个逻辑电路，问是否存在一种输入使输出为True，这即逻辑电路问题。 逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。 有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来，Hamilton 回路成了NPC问题，TSP问题也成了NPC问题。现在被证明是NPC问题的有很多，任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说，正是因为NPC问题的存在，P=NP变得难以置信。P=NP问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。
-
发表了文章 2017-10-06
洛谷 P2335 [SDOI2005]位图
OJ检测链接：https://www.luogu.org/problem/show?pid=2335 题目描述 现在我们给出一个n*m的单色位图，且该图中至少含有一个白色的像素。我们用(i, j)来代表第i行第j列的像素，并且定义两点p1=(i1, j1)和p2=(i2, j2)之间的距离为： d(p1, p2)=|i1 - i2| + |j1 – j2| 任务： 请写一个程序： 从文本文件BIT.IN中读入该位图； 对于每个像素，计算出离该像素最近的白色像素与它的距离； 把结果输出到文本文件BIT.OUT中。 输入输出格式 输入格式： 在文本文件BIT.IN的第一行包括两个用空格分开的整数n和m，1<=n<=150，1<=m<=150。以下的n行每行包括一个长度为m的整数为零或一，在第i+1行的第j个字符如果为”1”，那么表示像素(i, j)为白的，否则为黑的。 输出格式： 在文本文件BIT.OUT中输出一个n*m的数表，其中的第i行的第j个数字为f(i, j)表示像素(i, j)到最近的白色像素的距离 输入输出样例 输入样例#1： 3 4 0 0 0 1 0 0 1 1 0 1 1 0 输出样例#1： 3 2 1 0 2 1 0 0 1 0 0 1 分析： 从每一个白点出发做广搜去计算该白点到其他黑点的最短距离并做更新和记录的操作。 1 #include <cstdio> 2 #include <iostream> 3 #include <queue> 4 5 using namespace std; 6 7 int n,m,map[200][200]={0},ans[200][200]; 8 int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; //上下左右瞎动 9 queue<int> p,q; 10 11 void bfs(int x,int y); 12 13 int main() 14 { 15 int i,j,k; 16 scanf("%d%d",&n,&m); 17 for(i=0;i<160;i++) //初始化ans数组 18 for(j=0;j<160;j++) 19 ans[i][j]=9999; 20 for(i=1;i<=n;i++) 21 for(j=1;j<=m;j++) 22 { 23 scanf("%d",&map[i][j]); //1为白，0为黑 24 if(map[i][j]==1) ans[i][j]=0; //记录白点的距离：0 25 } 26 for(i=1;i<=n;i++) //寻找白格子 27 for(j=1;j<=m;j++) 28 if(map[i][j]==1) 29 { 30 bfs(i,j); 31 } 32 for(i=1;i<=n;i++) 33 { 34 for(j=1;j<=m;j++) 35 printf("%d ",ans[i][j]); 36 printf("\n"); 37 } 38 return 0; 39 } 40 void bfs(int x,int y) 41 { 42 int b[200][200]={0}; 43 int i,tx,ty,txx,tyy; 44 b[x][y]=1; 45 p.push(x); 46 q.push(y); 47 while(!p.empty()) 48 { 49 tx=p.front(); 50 ty=q.front(); 51 p.pop(); 52 q.pop(); 53 for(i=0;i<4;i++) 54 { 55 txx=tx+dx[i]; 56 tyy=ty+dy[i]; 57 if(txx>0 && txx<=n && tyy>0 && tyy<=m && b[txx][tyy]==0 && map[txx][tyy]!=1&&(ans[tx][ty]+1<ans[txx][tyy])) //越界检查 && 来访检查 && 白格子检查 && 假如本次广搜的路径距离较短才需要把该点入队继续搜索 58 { 59 p.push(txx); 60 q.push(tyy); 61 b[txx][tyy]=1; 62 ans[txx][tyy]=ans[tx][ty]+1; 63 } 64 } 65 } 66 }
-
发表了文章 2017-10-04
矿藏估价
某个矿藏丰富的地区埋有不同价值的矿藏。Mr. Chen某日记起他在此处有一块领地，于是他很想知道自己的领地上到底包含价值多少的矿物。他在该地区的地图上画出了领地的边界，请你来为他做一个资产评估。 假定整个地区的地图为矩形。为了方便起见，我们把这个地区划分成若干单位正方形区域，每个区域以该处的矿藏价值标识。Mr. Chen划出的边界是一条封闭的曲线且不自交。边界经过的单位区域由于墨水的缘故，上面的矿藏价值标识变得不可辨认，保守估计，可认为价值为0。 输入：第一行为两个整数N, M (1<= N<=50，1<=M<=50)，表示地图有N行M列单位区域构成。接下来的N行为地图。每行有M个单位区域的标识，每个标识或者为一非负整数，表示该处矿藏价值；或者为‘*’，表示领地的边界经过这一单位区域。每两个单位区域的表示之间以至少一个空格隔开。 输出：一个整数，即领地范围内所有矿藏的价值之和。 输入样例5 6231 11 41 5 7 113 * * * 31 34* 81 65 23 * 21 * * * 7 120 4 2 89 6 3输出样例169 1、作图G=(V,E)。所有非边界的单位区域对应顶点集V中的一个顶点，V={vij | (i,j)非边界区域}。若两个非边界的单位区域相邻，则相应顶点之间有无向边。 2、扩充图G：先扩充V，在原有地图的外围加一圈顶点：v00, v01, …, v0,M+1，vN+1,0, vN+1,1, …, vN+1,M+1，v10, v20, …, vN0，v1,M+1, v2,M+1, …, vN,M+1。新顶点的矿藏价值为0。再相应扩充E，所有原来地图边缘顶点与这些新顶点连边。 设整个地图的矿藏总值为A，Mr.Chen领地(不含v00)中的矿藏价值为AS，剩下部分的矿藏价值为AT，则AS+AT=A。求S有两条途径： (a) 遍历不含v00的子图S，直接统计AS； (b) 遍历含v00的子图T，统计AT，由AS=A-AT求出AS，其中A可通过两重循环简单求得。 如果用(a)计划，必须需要先找到S中的一个顶点，然后开始遍历，要做到这一点比较困难。相比之下，如果用(b)计划，可直接从v00开始遍历，省去不少麻烦，所以我们用(b)计划。 种子染色法可以形象的理解为在图中抛下一颗种子(顶点v00)，一种颜色就朝着四面八方蔓延开来，填满所有可达区域。我们用队列q存储非Mr.Chen领地中待扩展单位区域的坐标，按照“先进先出”的顺序扩展这些单位区域，直至队列q空为止。此时，非Mr.Chen领地的区域全部被染色，矿藏总值A减去被染色区域内的矿藏价值即为问题的解。 设地图的行数为N，列数为M，地图为a，其中单位区域(r，c) 中的矿藏价值为a[r,c]。如果 (r,c)为边界，则a[r,c]=‘*’。写程序时也你可以用某个特殊的数代替‘*’，例如-1。 1 Readln(n，m)； /*输入地图信息*/ 2 for c←1 to n do 3 for r←1 to m do read(read(a[c,r])； 4 /*设边缘顶点的矿藏价值为0*/ 5 for c←0 to M+1 do{a[0,c]←0；a[N+1,c]←0 }； 6 for r←1 to N do {a[r,0]←0;a[r,M+1]←0}； 7 A←0； /*累计个地图的矿藏总值*/ 8 for r←1 to N do 9 for c←1 to M do if a[r,c] ‘*’ then A←A+a[r,c]； 10 (0,0)进入队列q； 11 while q队列非空do 12 { 取出q的队首坐标(r,c)； 13 SUB-Test(r-1,c)；SUB-Test(r+1,c)；/*依次处理(r,c)的4个相邻位置*/ 14 SUB-Test(r,c-1)；SUB-Test(r,c+1)； 15 q出队操作 }；/*while*/ 16 writeln(A)； 17 其中过程SUB-Test(r,c)判断区域(r,c)是否在地图外或为边界。如果不是，则入队，并从A中扣去该区域矿藏价值，同时置已访问标志”*”。 18 Proc SUB-Test(r,c：integer)； 19 { if(r0)and(c0)and(rN+1)and(cM+1)and(a[r,c]‘*’) 20 then{ (r,c)进入队列q；A←A-a[r,c]；a[r,c]←‘*’}/*then*/ 21 }/* SUB-Test */
-
发表了文章 2017-10-01
二分法小结
文章来源：http://www.cnblogs.com/hyl2000/p/5734908.html NOIP中二分应该是很简单的算法了，去年noip的day2-t1就是裸的二分，这里有两个例题 1、poj2456：Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000). His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?（大意就是说有一些牛和牛舍，我们要尽量使最近的两头牛之间的距离最大） 2、跳石头（noip2015-day2-t1）：每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？（简单来说就是使最小值最大） 这类问题有个明显的特征：使最小值最大或者使最大值最小。这个时候大概步骤就是先对读进来的数据进行排序（因为二分查找是在有序的数据上进行的）然后执行二分。其中二分里的check函数是最关键的部分，例如第一题中我们就是二分答案，然后在check中贪心的来安排牛的位置，看是否能够满足答案。而第二题也是二分答案，check中按我们求出的答案把不满足答案的石头撤掉，看是否能够满足答案。这就是check的大概思路：即检查是否能够满足答案。 二分中还有一个重要的细节：求最大值的最小值时mid=(l+r)/2，l=mid+1，r=mid；而查找最小值的最大值时mid=(l+r+1）/2，l=mid，r=mid-1。不然程序会陷入死循环，或者得不到正确答案。 最后一点就是实数二分的时候因为精度需要常常我们会让程序一直进行计算，然而由于计算时的精度误差，常常也会使程序效率低下或者死循环。一般来讲我们这时可以限制二分次数，一般60-70次即可满足精度需要，这样可以提高程序效率，避免TLE的情况出现。 最最后一点，这类问题数据量一般都非常大，记得用scanf读入，第一题我就因为用cin而TLE了，改成scanf之后马上就过了。。。。。
-
发表了文章 2017-10-01
Aggressive cows
总时间限制: 1000ms 内存限制: 65536kB 描述 Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance? 输入 * Line 1: Two space-separated integers: N and C* Lines 2..N+1: Line i+1 contains an integer stall location, xi 输出 * Line 1: One integer: the largest minimum distance 样例输入 5 3 1 2 8 4 9 样例输出 3 提示 OUTPUT DETAILS:FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.Huge input data,scanf is recommended. 来源 USACO 2005 February Gold 题目OJ链接：http://bailian.openjudge.cn/practice/2456/ 题目分析： （参考http://blog.csdn.net/wuxiushu/article/details/49158843） 题意要表达的是：把C头牛放到N个带有编号的隔间里，使得任意两头牛所在的隔间编号的最小差值最大。例如样例排完序后变成1 2 4 8 9，那么1位置放一头牛，4位置放一头牛，它们的差值为3；最后一头牛放在8或9位置都可以，和4位置的差值分别为4、5，和1位置的差值分别为7和8，不比3小，所以最大的最小值为3。 分析：这是一个最小值最大化的问题。先对隔间编号从小到大排序，则最大距离不会超过两端的两头牛之间的差值，最小值为0。所以我们可以通过二分枚举最小值来求。假设当前的最小值为x，如果判断出最小差值为x时可以放下C头牛，就先让x变大再判断；如果放不下，说明当前的x太大了，就先让x变小然后再进行判断。直到求出一个最大的x就是最终的答案。 本题的关键就在于讨论差值的大小。 1 #include<iostream> 2 #include<algorithm> 3 #include<stdio.h> 4 #include<string.h> 5 using namespace std; 6 const int MAX = 100010; 7 int a[MAX],n,m; 8 9 bool C(int d) 10 { 11 int t = a[0],count = 1; 12 for(int i = 1;i < n;i ++) 13 { 14 if(a[i] - t >= d) 15 { 16 count ++; 17 t=a[i]; 18 if(count >= m) 19 return true; 20 } 21 } 22 return false; 23 } 24 25 26 int solve() 27 { 28 int x = 0,y = a[n-1] - a[0]; 29 while(x <= y) 30 { 31 int mid=(x+y)/2; 32 if(C(mid)) 33 x=mid + 1; 34 else 35 y=mid - 1; 36 } 37 return x - 1; 38 } 39 40 41 int main() 42 { 43 while(~scanf("%d%d",&n,&m)) 44 { 45 for(int i = 0;i < n;i ++) 46 scanf("%d",&a[i]); 47 sort(a,a+n); 48 printf("%d\n",solve()); 49 } 50 return 0; 51 }
-
发表了文章 2017-09-24
POJ 2676 Sudoku (数独 DFS)
Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 14368 Accepted: 7102 Special Judge Description Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task. Input The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0. Output For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them. Sample Input 1 103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107 Sample Output 143628579 572139468 986754231 391542786 468917352 725863914 237481695 619275843 854396127 Source Southeastern Europe 2005 题目链接：http://poj.org/problem?id=2676 http://bailian.openjudge.cn/practice/2982/ 题目大意：就是数独咯，让你求解数独游戏，9乘9的矩阵要求每行每列和9个3*3的子矩阵内都出现数字1-9 题目分析：9乘9的矩阵，从第一个位置一直搜到最后一个位置，若当前位置有数字搜下一位置，否则枚举1-9并判断， 判断时当前行r = n/9当前列为c = n%9当前子矩阵的第一个元素位置为r / 3 * 3，c / 3 * 3 1 #include <cstdio> 2 char s[10]; 3 int num[9][9]; 4 bool flag; 5 6 bool ok(int n, int cur) 7 { 8 int r = n / 9; //当前行 9 int c = n % 9; //当前列 10 for(int j = 0; j < 9; j++) //枚举列 11 if (num[r][j] == cur) 12 return false; 13 for(int i = 0; i < 9; i++) //枚举行 14 if (num[i][c] == cur) 15 return false; 16 //得到当前所在的子矩阵的第一个元素位置 17 int x = r / 3 * 3; 18 int y = c / 3 * 3; 19 //枚举子矩阵中的元素 20 for(int i = x; i < x + 3; i++) 21 for(int j = y; j < y + 3; j++) 22 if (num[i][j] == cur) 23 return false; 24 return true; 25 } 26 27 void DFS(int n) 28 { 29 if(n > 80 || flag) 30 { 31 flag = true; 32 return; 33 } 34 if(num[n / 9][n % 9])//当前位置有数字直接搜索下一位 35 { 36 DFS(n + 1); 37 if(flag) 38 return; 39 } 40 else 41 { 42 for(int cur = 1; cur <= 9; cur++) //枚举数字 43 { 44 if(ok(n, cur)) //若ok则插入 45 { 46 num[n / 9][n % 9] = cur; 47 DFS(n + 1); 48 if(flag) 49 return; 50 num[n / 9][n % 9] = 0; //还原 51 } 52 } 53 } 54 } 55 56 int main() 57 { 58 int T; 59 scanf("%d", &T); 60 while(T--) 61 { 62 flag = false; 63 for(int i = 0; i < 9; i++) //得到数独矩阵 64 { 65 scanf("%s", s); 66 for(int j = 0; j < 9; j++) 67 num[i][j] = (s[j] - '0'); 68 } 69 DFS(0); //从第一位开始搜 70 for(int i = 0; i < 9; i++) 71 { 72 for(int j = 0; j < 9; j++) 73 printf("%d", num[i][j]); 74 printf("\n"); 75 } 76 } 77 } View Code 题解来源：http://blog.csdn.net/tc_to_top/article/details/43699047
-
发表了文章 2017-09-24
单词序列
题目链接 总时间限制: 1000ms 内存限制: 1024kB 描述 给出两个单词（开始单词和结束单词）以及一个词典。找出从开始单词转换到结束单词，所需要的最短转换序列。转换的规则如下： 1、每次只能改变一个字母 2、转换过程中出现的单词(除开始单词和结束单词)必须存在于词典中 例如： 开始单词为：hit 结束单词为：cog 词典为：[hot,dot,dog,lot,log,mot] 那么一种可能的最短变换是： hit -> hot -> dot -> dog -> cog, 所以返回的结果是序列的长度5； 注意： 1、如果不能找到这种变换，则输出0； 2、词典中所有单词长度一样； 3、所有的单词都由小写字母构成； 4、开始单词和结束单词可以不在词典中。 输入 共两行，第一行为开始单词和结束单词（两个单词不同），以空格分开。第二行为若干的单词（各不相同），以空格分隔开来，表示词典。单词长度不超过5,单词个数不超过30。 输出 输出转换序列的长度。 样例输入 hit cog hot dot dog lot log 样例输出 5 分析： http://www.cnblogs.com/bleopard/p/4066262.html http://blog.csdn.net/loi__dijiang/article/details/52812774 最朴素的BFS可过。主要是对于字符串的处理。 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 6 using namespace std; 7 8 struct Note 9 { 10 string sf; 11 int nus; 12 } d[31]; 13 14 string ks,es; 15 queue<int> q; 16 bool b[31],vis; 17 int length; 18 int sum=0; 19 20 int gs(string x,string y) 21 { 22 int sum=0; 23 for(int i=0;i<length;i++) if(x[i]!=y[i]) sum++; 24 return sum; 25 } 26 27 int main() 28 { 29 cin>>ks>>es; 30 length=ks.size(); 31 int i=1; 32 char ch; 33 d[i].sf=ks; 34 i=2; 35 while(cin>>d[i].sf) i++; 36 d[i].sf=es; 37 q.push(1); 38 while(!q.empty()) 39 { 40 int cur=q.front(); 41 q.pop(); 42 if(d[cur].sf==es) 43 { 44 printf("%d\n",d[cur].nus+1); 45 vis=1; 46 break; 47 } 48 for(int j=1;j<=i;j++) 49 { 50 if(gs(d[cur].sf,d[j].sf)==1&&!b[j]) 51 { 52 d[j].nus=d[cur].nus+1; 53 q.push(j); 54 b[j]=1; 55 } 56 } 57 } 58 if(!vis) printf("0\n"); 59 return 0; 60 }
-
发表了文章 2017-09-24
宠物小精灵之收服
题目链接 总时间限制: 1000ms 内存限制: 65536kB 描述 宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。 一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时，狩猎也宣告结束。 我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。 小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。 现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问，小智该如何选择收服哪些小精灵以达到他的目标呢？ 输入 输入数据的第一行包含三个整数：N(0 < N < 1000)，M(0 < M < 500)，K(0 < K < 100)，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。 输出 输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。 样例输入 样例输入1： 10 100 5 7 10 2 40 2 50 1 20 4 20 样例输入2： 10 100 5 8 110 12 10 20 10 5 200 1 110 样例输出 样例输出1： 3 30 样例输出2： 0 100 提示 对于样例输入1：小智选择：(7,10) (2,40) (1,20) 这样小智一共收服了3个小精灵，皮卡丘受到了70点伤害，剩余100-70=30点体力。所以输出3 30对于样例输入2：小智一个小精灵都没法收服，皮卡丘也不会收到任何伤害，所以输出0 100 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int n,m,k,ans,power; 6 int r[105],c[105],f[1005][505]; 7 int main(){ 8 scanf("%d%d%d",&n,&m,&k); 9 for (int i=1;i<=k;++i) 10 scanf("%d%d",&r[i],&c[i]); 11 for (int i=1;i<=k;++i) 12 for (int p=n;p>=r[i];--p) 13 for (int q=m;q>=c[i];--q) 14 f[p][q]=max(f[p][q],f[p-r[i]][q-c[i]]+1); 15 ans=0; power=m; 16 for (int i=1;i<=m;++i) 17 if (f[n][i]>ans){ 18 ans=f[n][i]; power=m-i; 19 } 20 printf("%d %d",ans,power); 21 } 分析： http://blog.csdn.net/c20190101zjx/article/details/52717370 http://www.cnblogs.com/yi-ye-zhi-qiu/p/7586532.html http://blog.csdn.net/clove_unique/article/details/50152305
-
发表了文章 2017-09-24
开餐馆
题目链接 总时间限制: 1000ms 内存限制: 65536kB 描述 北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, ... mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。 输入 标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ，表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行,第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000).第2行:n 个地点的位置m1 , m2, ... mn ( 1000000 > mi > 0 且为整数,升序排列)第3行:n 个地点的餐馆利润p1 , p2, ... pn ( 1000 > pi > 0 且为整数) 输出 对于每组测试数据可能的最大利润 样例输入 2 3 11 1 2 15 10 2 30 3 16 1 2 15 10 2 30 样例输出 40 30 分析：动态规划的题目，就是计算每个位置所能获得的最大利润，再求最大值 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N = 105; 7 int dp[N],m[N],p[N]; 8 9 int main() 10 { 11 int t,n,k; 12 cin >> t; 13 while(t--) 14 { 15 cin >> n >> k; 16 memset(dp,0,sizeof(dp)); 17 for(int i = 1;i <= n;i++) 18 scanf("%d",&m[i]); 19 for(int i = 1;i <= n;i++) 20 scanf("%d",&p[i]); 21 dp[1] = p[1]; 22 for(int i = 2;i <= n;i++) 23 { 24 dp[i] = p[i];//每个位置的初始利润 25 for(int j = 1;j < i;j++) 26 if(m[i] - m[j] > k) 27 dp[i] = max(dp[i],dp[j]+p[i]);//每个位置所能得到的最大利润 28 } 29 int maxn = 0; 30 for(int i = 1;i <= n;i++) 31 maxn = max(maxn,dp[i]); 32 printf("%d\n",maxn); 33 } 34 return 0; 35 } ps：这道题既然最后只开一家餐馆，为何需要考虑内部竞争呢……
-
发表了文章 2017-09-24
8467:鸣人的影分身
题目链接 总时间限制: 1000ms 内存限制: 65536kB 描述 在火影忍者的世界里，令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。 影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。 针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。 那么问题来了，假设鸣人的查克拉能量为M，他影分身的个数为N，那么制造影分身时有多少种（用K表示）不同的分配方法？（影分身可以被分配到0点查克拉能量） 输入 第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。 输出 对输入的每组数据M和N，用一行输出相应的K。 样例输入 1 7 3 样例输出 8 这道题跟放苹果这一题其实是一模一样的。放苹果这道题在很多地方都有评测，除了百炼，NOIOpenJudge也有。 本题的题目描述虽然增加了一个题目背景，但本质意思没有变，甚至题目的输入输出案例都没有变。 题解参考： http://www.cnblogs.com/huashanqingzhu/p/3801214.html http://www.cnblogs.com/huashanqingzhu/p/4036425.html 这里使用递归解决，其实也可以用动规解决。 1 #include <stdio.h> 2 int fun(int m,int n)//m个果放进n个盘 3 { 4 if(m<n) return fun(m,m); 5 else if(m==0||n==1) return 1; 6 else return fun(m,n-1)+fun(m-n,n); 7 } 8 int main(int argc, char *argv[]) 9 { 10 int T,M,N,k; 11 scanf("%d",&T); 12 for(;T>0;T--) 13 { 14 scanf("%d%d",&M,&N); 15 k=fun(M,N); 16 printf("%d\n",k); 17 } 18 return 0; 19 }
-
发表了文章 2017-09-24
4123:马走日
[题目链接] 总时间限制: 1000ms 内存限制: 1024kB 描述 马在中国象棋以日字形规则移动。 请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。 输入 第一行为整数T(T < 10)，表示测试数据组数。每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 10, n < 10) 输出 每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。 样例输入 1 5 4 0 0 样例输出 32 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int sx[8]={1,1,-1,-1,2,2,-2,-2}; 6 int sy[8]={2,-2,2,-2,1,-1,1,-1}; 7 int t,n,m,x,y,ans; 8 bool b[20][20]; 9 void dfs(int dep,int s,int t) 10 { 11 if(dep==n*m) 12 { ans++; return; } 13 for (int r=0;r<8;++r) 14 { 15 int x=s+sx[r]; int y=t+sy[r]; 16 if (!b[x][y]&&x>0&&y>0&&x<=n&&y<=m) 17 { 18 b[x][y]=true; 19 dfs(dep+1,x,y); 20 b[x][y]=false; 21 } 22 } 23 } 24 int main() 25 { 26 scanf("%d",&t); 27 while (t--) 28 { 29 scanf("%d%d",&n,&m); 30 scanf("%d%d",&x,&y); 31 ++x; ++y; 32 memset(b,0,sizeof(b)); 33 ans=0,b[x][y]=true; 34 dfs(1,x,y); 35 printf("%d\n",ans); 36 } 37 }
-
发表了文章 2017-09-23
大盗阿福
题目链接 总时间限制: 1000ms 内存限制: 65536kB 描述 阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。 作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？ 输入 输入的第一行是一个整数 T (T <= 50) ，表示一共有 T 组数据。接下来的每组数据，第一行是一个整数 N (1 <= N <= 100, 000) ，表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000 。 输出 对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。 样例输入 2 3 1 8 2 4 10 7 6 14 样例输出 8 24 提示 对于第一组样例，阿福选择第 2 家店铺行窃，获得的现金数量为 8 。对于第二组样例，阿福选择第 1 和 4 家店铺行窃，获得的现金数量为 10 + 14 = 24 。 题解：（来源） 状态表达：f[i] = 在前i家店中最多能盗到的钱数。 转移方程：f[i] = max(f[i-1],f[i-2]+val[i]) 状态数量：n 转移代价：O(1) 时间复杂度：O(n) 空间复杂度：O(n)或O(1) 上面的空间复杂度可以是O(1)是因为可以把当前状态只需要f[i-1],f[i-2]，这样就只要定义一个变量，不需要开数组了。 1 #include<cstdio> 2 int num[100001],f[100001]; 3 int main() 4 { 5 int t,i,n; 6 7 scanf("%d",&t); 8 while(t>0) 9 { 10 t--; 11 scanf("%d",&n); 12 for(i=0;i<n;i++)scanf("%d",&num[i]); 13 f[0]=num[0],f[1]=(num[0]>num[1]?num[0]:num[1]); 14 for(i=2;i<n;i++)f[i]=( f[i-1]>f[i-2]+num[i] ? f[i-1] : f[i-2]+num[i] ); 15 printf("%d\n",f[n-1]); 16 } 17 return 0; 18 }
-
发表了文章 2017-09-17
迷宫问题
题目连接： http://poj.org/problem?id=3414 http://bailian.openjudge.cn/practice/3151/ 总时间限制: 1000ms 内存限制: 65536kB 描述 You are given two pots, having the volume of A and B liters respectively. The following operations can be performed: FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap; DROP(i) empty the pot i to the drain; POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j). Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots. 输入 On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B). 输出 The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’. 样例输入 3 5 4 样例输出 6 FILL(2) POUR(2,1) DROP(1) POUR(2,1) FILL(2) POUR(2,1) 题目大意与题解：http://blog.csdn.net/freedomcheng/article/details/7385666 给出两个杯子容积，初始都为空杯子，给出目标水量，可以执行一些操作，分别是倒空一个杯子，倒满一个杯子，和将一个杯子的水倒到另一个中，问得到目标水量要进行至少多少次以及每次都是什么FILL（1）表示倒满1杯子，POUR（2，1）表示将2杯子里的水倒进1杯子中，DROP（1）表示倒空1杯子。本体为广度优先生成树，每次对六种操作进行广度搜索，用二维数组进行状态是否出现过的标记，并记录每次出现的节点的父节点，最后用递归进行输出。 POJ的题判与百炼的题判稍微不一样，下面是POJ的代码。 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 int a,b,c; 7 8 9 struct node 10 { 11 int aa;//a杯子里的水量 12 int bb;//b杯子里的水量 13 int parent;//父节点编号 14 int ope;//执行什么操作得到该节点 15 int level;//层次 16 node(int x,int y,int p,int o,int l):aa(x),bb(y),parent(p),ope(o),level(l){}//构造函数，为了方便返回该结构体变量 17 node(){}//有自定义构造函数的时候必须有一个默认构造函数 18 }; 19 20 21 node nod[1000000]; 22 bool fl[205][205]; 23 int stk[1000000]; 24 25 26 void output(int p) 27 { 28 int top=0; 29 stk[0]=p;//数组模拟栈实现递归 30 while(nod[stk[top]].parent!=-1) 31 { 32 top++; 33 stk[top]=nod[stk[top-1]].parent; 34 } 35 for(int i=top;i>=0;i--) 36 { 37 switch(nod[stk[i]].ope) 38 { 39 case 0: 40 { 41 printf("DROP(1)\n"); 42 } 43 break; 44 case 1: 45 { 46 printf("FILL(1)\n"); 47 } 48 break; 49 case 2: 50 { 51 printf("DROP(2)\n"); 52 } 53 break; 54 case 3: 55 { 56 printf("FILL(2)\n"); 57 } 58 break; 59 case 4: 60 { 61 printf("POUR(1,2)\n"); 62 } 63 break; 64 case 5: 65 { 66 printf("POUR(2,1)\n"); 67 } 68 break; 69 } 70 } 71 } 72 73 74 void f1(node& n) 75 { 76 n.aa=0; 77 } 78 void f2(node& n) 79 { 80 n.aa=a; 81 } 82 void f3(node& n) 83 { 84 n.bb=0; 85 } 86 void f4(node&n) 87 { 88 n.bb=b; 89 } 90 void f5(node&n) 91 { 92 if(b-n.bb<n.aa) 93 { 94 n.aa=n.aa-(b-n.bb); 95 n.bb=b; 96 } 97 else 98 { 99 n.bb+=n.aa; 100 n.aa=0; 101 } 102 } 103 void f6(node&n) 104 { 105 if(a-n.aa<n.bb) 106 { 107 n.bb=n.bb-(a-n.aa); 108 n.aa=a; 109 } 110 else 111 { 112 n.aa+=n.bb; 113 n.bb=0; 114 } 115 } 116 void(*fun[6])(node&n)={f1,f2,f3,f4,f5,f6};//函数指针数组，保存六个函数 117 118 119 int main() 120 { 121 while(~scanf("%d%d%d",&a,&b,&c)) 122 { 123 memset(fl,0,sizeof(fl));//标记数组，表示一种状态是否出现过 124 int front=0; 125 int tail=0; 126 nod[tail++]=node(0,0,-1,-1,0);//构造函数的用处 127 fl[0][0]=1; 128 int res; 129 int res_loc=-1; 130 while(front<tail) 131 { 132 node nd=nod[front++]; 133 if(nd.aa==c||nd.bb==c) 134 { 135 res=nd.level;//res记录得到结果时候的深度 136 res_loc=front-1;//表示得到的结果在数组中是第几个 137 break; 138 } 139 for(int i=0;i<6;i++)//进行六种操作，每次调用函数数组中的一个函数 140 { 141 node nt=nd; 142 fun[i](nt);//调用第i个函数 143 if(fl[nt.aa][nt.bb]==0) 144 { 145 fl[nt.aa][nt.bb]=1; 146 nod[tail++]=node(nt.aa,nt.bb,front-1,i,nt.level+1);//依然是构造函数的应用 147 } 148 } 149 } 150 if(res_loc==-1) 151 { 152 printf("impossible\n"); 153 continue; 154 } 155 printf("%d\n",res); 156 output(res_loc); 157 } 158 return 0; 159 } View Code
-
发表了文章 2017-09-10
鸣人和佐助
题目链接：http://bailian.openjudge.cn/practice/4115/ 总时间限制: 1000ms 内存限制: 65536kB 描述 佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？ 已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？ 输入 输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。 输出 输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。 样例输入 样例输入1 4 4 1 #@## **## ###+ **** 样例输入2 4 4 2 #@## **## ###+ **** 样例输出 样例输出1 6 样例输出2 4 1 #include <iostream> 2 #include <queue> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 struct point 8 { 9 int x, y, ckl, time; 10 point (int xx,int yy, int cc, int tt):x(xx), y(yy), ckl(cc), time(tt){}; 11 }; 12 13 int r,c,t; 14 int min_time = 1 << 30; 15 int dx[4] = {0, 0, 1, -1}; 16 int dy[4] = {1, -1, 0, 0}; 17 char mp[210][210]; 18 bool visited[210][210][11]; 19 20 int bfs(int x, int y, int ex, int ey, int t) 21 { 22 queue<point> q; 23 q.push(point(x, y, t, 0)); 24 while (!q.empty()) 25 { 26 point temp = q.front(); 27 q.pop(); 28 for (int i = 0; i < 4; i++) 29 { 30 int sx = temp.x + dx[i]; 31 int sy = temp.y + dy[i]; 32 if (sx == ex && sy == ey) 33 { 34 min_time = temp.time + 1; 35 return true; 36 } 37 if (mp[sx][sy] == '*') 38 { 39 if (sx >= 0 && sx < r && sy >= 0 && sy < c && !visited[sx][sy][temp.ckl]) 40 { 41 visited[sx][sy][temp.ckl] = true; 42 q.push(point(sx, sy, temp.ckl, temp.time + 1)); 43 } 44 } 45 if (mp[sx][sy] == '#') 46 { 47 if (sx >= 0 && sx < r && sy >= 0 && sy < c && !visited[sx][sy][temp.ckl - 1] && temp.ckl > 0) 48 { 49 visited[sx][sy][temp.ckl - 1] = true; 50 q.push(point(sx, sy, temp.ckl - 1, temp.time + 1)); 51 } 52 } 53 } 54 } 55 return false; 56 } 57 58 int main(){ 59 cin >> r >> c >> t; 60 int x, y, ex, ey; 61 memset(visited, 0, sizeof(visited)); 62 for (int i = 0; i < r; i++) 63 { 64 for (int j = 0; j < c; j++) 65 { 66 cin >> mp[i][j]; 67 if(mp[i][j] == '@') 68 { 69 x = i; 70 y = j; 71 mp[i][j] = '*'; 72 } 73 if(mp[i][j] == '+') 74 { 75 ex = i; 76 ey = j; 77 mp[i][j] = '*'; 78 } 79 } 80 } 81 if (bfs(x, y, ex, ey, t)) 82 cout << min_time << endl; 83 else 84 cout << "-1" <<endl; 85 } 参考： 分析http://www.cnblogs.com/huibixiaoxing/p/6537769.html 代码http://blog.csdn.net/u010524510/article/details/47148665
-
发表了文章 2017-09-09
和为给定数
总时间限制: 1000ms 内存限制: 65536kB 描述 给出若干个整数，询问其中是否有一对数的和等于给定的数。 输入 共三行：第一行是整数n(0 < n <= 100,000)，表示有n个整数。第二行是n个整数。整数的范围是在0到10^8之间。第三行是一个整数m（0 <= m <= 2^30)，表示需要得到的和。 输出 若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行No。 样例输入 4 2 5 1 4 6 样例输出 1 5 1 #include<stdio.h> 2 #include<stdlib.h> 3 int cmp(const void *a,const void *b) 4 { 5 return *(int *)a - *(int *)b; 6 } 7 int main(int argc, char *argv[]) 8 { 9 int n,a[100005],i,m; 10 int left,right; 11 12 scanf("%d",&n); 13 for(i=0;i<n;i++) 14 scanf("%d",&a[i]); 15 scanf("%d",&m); 16 qsort(a,n,sizeof(int),cmp); 17 left=0; 18 right=n-1; 19 while(left<right) 20 { 21 if(a[left]+a[right]<m) left++; 22 else if(a[left]+a[right]>m) right--; 23 else break; 24 } 25 if(left<right) printf("%d %d\n",a[left],a[right]); 26 else printf("No\n"); 27 return 0; 28 }
-
发表了文章 2017-09-03
棋盘问题 POJ 1321
总时间限制: 1000ms 内存限制: 65536kB 描述 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 输入 输入含有多组测试数据。每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n当为-1 -1时表示输入结束。随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 输出 对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。 样例输入 2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1 样例输出 2 1 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <iostream> 5 #include <algorithm> 6 #include <set> 7 #include <queue> 8 #include <stack> 9 10 using namespace std; 11 char map[10][10]; 12 int vis[10];//第i列是否放置了棋子 13 int cnt;//已放棋子的数目 14 int sum;//放置方法的总数 15 int n,k; 16 void dfs(int s) 17 { 18 int i; 19 if(cnt==k){//所有的棋子都放置好 20 sum++; 21 return ; 22 } 23 else{ 24 if(s>=n)//如果越界 25 return ;//返回 26 else{ 27 for(i=0;i<n;i++){//讲一个棋子尝试放在0-n-1列的某一行 28 if(map[s][i]=='#'&&!vis[i]){ 29 vis[i]=1;//标记该列已经放了棋子 30 cnt++;//棋子数+1 31 dfs(s+1);//继续搜索 32 cnt--;//经过一轮递归后num始终保持不变,因为没有放棋子 33 vis[i]=0;//在此处不放棋子 34 } 35 } 36 dfs(s+1);//进行剩下的k-1个棋子的遍历 37 } 38 } 39 } 40 int main() 41 { 42 int i; 43 while(~scanf("%d %d",&n,&k)){ 44 getchar(); 45 if(n==-1&&k==-1) break; 46 memset(vis,0,sizeof(vis)); 47 for(i=0;i<n;i++) 48 scanf("%s",map[i]); 49 cnt=sum=0; 50 dfs(0); 51 printf("%d\n",sum); 52 } 53 return 0; 54 } 参考： http://blog.csdn.net/u013486414/article/details/43878071
-
发表了文章 2017-09-03
A Knight's Journey
总时间限制: 1000ms 内存限制: 65536kB描述BackgroundThe knight is getting bored of seeing the same black and white squares again and again and has decided to make a journeyaround the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans? ProblemFind a path such that the knight visits every square once. The knight can start and end on any square of the board.输入The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .输出The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.If no such path exist, you should output impossible on a single line.样例输入31 12 34 3样例输出Scenario #1:A1 Scenario #2:impossible Scenario #3:A1B3C1A2B4C2A3B1C3A4B2C4来源TUD Programming Contest 2005, Darmstadt, Germany 大致题意：给出一个p行q列的国际棋盘，马可以从任意一个格子开始走，问马能否不重复的走完所有的棋盘。如果可以，输出按字典序排列最小的路径。打印路径时，列用大写字母表示（A表示第一列），行用阿拉伯数字表示（从1开始），先输出列，再输出行。 分析：如果马可以不重复的走完所有的棋盘，那么它一定可以走到A1这个格子。所以我们只需从A1这个格子开始搜索，就能保证字典序是小的；除了这个条件，我们还要控制好马每次移动的方向，控制方向时保证字典序最小（即按照下图中格子的序号搜索）。控制好这两个条件，直接从A1开始深搜就行了。 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int path[88][88], vis[88][88], p, q, cnt; 7 bool flag; 8 9 int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; 10 int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; 11 12 bool judge(int x, int y) 13 { 14 if(x >= 1 && x <= p && y >= 1 && y <= q && !vis[x][y] && !flag) 15 return true; 16 return false; 17 } 18 19 void DFS(int r, int c, int step) 20 { 21 path[step][0] = r; 22 path[step][1] = c; 23 if(step == p * q) 24 { 25 flag = true; 26 return ; 27 } 28 for(int i = 0; i < 8; i++) 29 { 30 int nx = r + dx[i]; 31 int ny = c + dy[i]; 32 if(judge(nx,ny)) 33 { 34 35 vis[nx][ny] = 1; 36 DFS(nx,ny,step+1); 37 vis[nx][ny] = 0; 38 } 39 } 40 } 41 42 int main() 43 { 44 int i, j, n, cas = 0; 45 scanf("%d",&n); 46 while(n--) 47 { 48 flag = 0; 49 scanf("%d%d",&p,&q); 50 memset(vis,0,sizeof(vis)); 51 vis[1][1] = 1; 52 DFS(1,1,1); 53 printf("Scenario #%d:\n",++cas); 54 if(flag) 55 { 56 for(i = 1; i <= p * q; i++) 57 printf("%c%d",path[i][1] - 1 + 'A',path[i][0]); 58 } 59 else 60 printf("impossible"); 61 printf("\n"); 62 if(n != 0) 63 printf("\n"); 64 } 65 return 0; 66 } 来源：http://blog.csdn.net/lyhvoyage/article/details/18355471
-
发表了文章 2017-09-03
红与黑
红与黑总时间限制: 1000ms 内存限制: 65536kB描述有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。输入包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下1）‘.’：黑色的瓷砖；2）‘#’：白色的瓷砖；3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。当在一行中读入的是两个零时，表示输入结束。输出对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。样例输入6 9....#......#..............................#@...#.#..#.0 0样例输出45 1 #include<iostream> 2 #include<stdio.h> 3 #include<queue> 4 using namespace std; 5 6 struct obj 7 { 8 int x,y; 9 }; 10 int w,h; 11 char a[22][22]; 12 queue<struct obj> q; 13 struct obj startPoint; 14 int count=0; 15 int dx[4]={-1,0,1, 0};//上右下左 16 int dy[4]={ 0,1,0,-1}; 17 18 void bfs(); 19 int main() 20 { 21 int i,j; 22 freopen("data.in","r",stdin); 23 while(scanf("%d%d",&w,&h)!=EOF) 24 { 25 getchar(); 26 //printf("%d %d\n",w,h); 27 if(w==0&&h==0) break; 28 for(i=0;i<h;i++) 29 { 30 for(j=0;j<w;j++) 31 { 32 scanf("%c",&a[i][j]); 33 //printf("%c",a[i][j]); 34 if(a[i][j]=='@') 35 { 36 startPoint.x=i; 37 startPoint.y=j; 38 } 39 } 40 getchar(); 41 //printf("\n"); 42 } 43 44 bfs(); 45 printf("%d\n",count); 46 } 47 return 0; 48 } 49 void bfs() 50 { 51 struct obj temp; 52 int xx,yy; 53 54 count=1; 55 q.push(startPoint); 56 while(!q.empty()) 57 { 58 for(int i=0;i<4;i++) 59 { 60 xx=q.front().x+dx[i]; 61 yy=q.front().y+dy[i]; 62 if(xx>=0&&xx<h&&yy>=0&&yy<w&&a[xx][yy]=='.') 63 { 64 a[xx][yy]='@'; 65 temp.x=xx; 66 temp.y=yy; 67 q.push(temp); 68 count++; 69 } 70 } 71 q.pop(); 72 } 73 }
-
发表了文章 2017-08-26
单词翻转
总时间限制: 1000ms 内存限制: 65536kB 描述 输入一个句子（一行），将句子中的每一个单词翻转后输出。 输入 只有一行，为一个字符串，不超过500个字符。单词之间以空格隔开。 输出 翻转每一个单词后的字符串，单词之间的空格需与原文一致。 样例输入 hello world 样例输出 olleh dlrow 1 #include <iostream> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 6 int main() 7 { 8 int i,j,k; 9 char s[505]; 10 int f; 11 gets(s); 12 //printf("%s\n",s); 13 14 i=0; 15 f=0; 16 while(s[i]!='\0') 17 { 18 if(s[i]==' ') 19 { 20 if(f==0) printf(" "); 21 else 22 { 23 //cout s[k] to s[j] 24 for(k=i-1;k>=j;k--) printf("%c",s[k]); 25 f=0; 26 printf(" "); 27 } 28 } 29 else 30 { 31 if(f==0) { j=i; f=1; } 32 } 33 i++; 34 } 35 for(k=i-1;k>=j;k--) printf("%c",s[k]); 36 printf("\n"); 37 return 0; 38 }
-
发表了文章 2017-08-26
codevs 1862 最长公共子序列（求最长公共子序列长度并统计最长公共子序列的个数）
题目描述 Description 字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij = yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。 对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。 输入描述 Input Description 第1行为第1个字符序列，都是大写字母组成，以”.”结束。长度小于5000。 第2行为第2个字符序列，都是大写字母组成，以”.”结束，长度小于5000。 输出描述 Output Description 第1行输出上述两个最长公共子序列的长度。 第2行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对100,000,000求余即可。 样例输入 Sample Input ABCBDAB.BACBBD. 样例输出 Sample Output 47 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 #define maxn 5010 7 #define MOD 100000000 8 char A[maxn],B[maxn],cur; 9 int f[2][maxn], g[2][maxn]; 10 11 int main() 12 { 13 scanf("%s%s", A + 1, B + 1); 14 int na = strlen(A + 1), nb = strlen(B + 1); 15 A[na--] = '\0'; B[nb--] = '\0'; 16 17 cur=0; 18 for(int i = 1; i <= nb; i++) g[0][i] = 1; 19 g[0][0] = g[1][0] = 1; 20 21 for(int i = 1; i <= na; i++) 22 { 23 cur ^= 1; 24 for(int j = 1; j <= nb; j++) 25 { 26 if(A[i] == B[j]) f[cur][j] =f[cur^1][j-1] + 1; 27 else f[cur][j] = max(f[cur^1][j], f[cur][j-1]); 28 29 g[cur][j] = 0; 30 if(f[cur][j] == f[cur^1][j]) g[cur][j] += g[cur^1][j]; 31 if(f[cur][j] == f[cur][j-1]) g[cur][j] += g[cur][j-1]; 32 if(f[cur][j] == f[cur^1][j] && f[cur][j] == f[cur][j-1] && f[cur^1][j-1] == f[cur][j]) 33 g[cur][j] -= g[cur^1][j-1]; 34 if(A[i] == B[j] && f[cur][j] == f[cur^1][j-1] + 1) g[cur][j] += g[cur^1][j-1]; 35 if(g[cur][j] > MOD) g[cur][j] %= MOD; 36 if(g[cur][j] < 0) g[cur][j] = (g[cur][j] % MOD) + MOD; 37 } 38 } 39 printf("%d\n%d\n", f[cur][nb], g[cur][nb]); 40 return 0; 41 } 参考1：http://blog.csdn.net/moep0/article/details/52760974 参考2：http://blog.csdn.net/litble/article/details/67640655 算法分析： 第一个问题可以参考最长公共子序列原题的题解。 第二个问题可以阅读参考1和参考2的分析和代码自己理解。 这里摘抄参考1里面的两段代码留存： 代码一：使用了滚动数组。 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <stack> 6 #include <vector> 7 #include <queue> 8 #include <cstring> 9 #include <string> 10 #include <map> 11 #include <set> 12 using namespace std; 13 14 const int BufferSize = 1 << 16; 15 char buffer[BufferSize], *Head, *Tail; 16 inline char Getchar() { 17 if(Head == Tail) { 18 int l = fread(buffer, 1, BufferSize, stdin); 19 Tail = (Head = buffer) + l; 20 } 21 return *Head++; 22 } 23 int read() { 24 int x = 0, f = 1; char c = Getchar(); 25 while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); } 26 while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); } 27 return x * f; 28 } 29 30 #define maxn 5010 31 #define MOD 100000000 32 char A[maxn], B[maxn], cur; 33 int f[2][maxn], g[2][maxn]; 34 35 int main() { 36 scanf("%s%s", A + 1, B + 1); 37 int na = strlen(A + 1), nb = strlen(B + 1); 38 A[na--] = '\0'; B[nb--] = '\0'; 39 40 for(int i = 1; i <= nb; i++) g[0][i] = 1; g[0][0] = g[1][0] = 1; 41 for(int i = 1; i <= na; i++) { 42 cur ^= 1; 43 for(int j = 1; j <= nb; j++) { 44 f[cur][j] = max(f[cur^1][j], f[cur][j-1]); 45 if(A[i] == B[j]) f[cur][j] = max(f[cur][j], f[cur^1][j-1] + 1); 46 g[cur][j] = 0; 47 if(f[cur][j] == f[cur^1][j]) g[cur][j] += g[cur^1][j]; 48 if(f[cur][j] == f[cur][j-1]) g[cur][j] += g[cur][j-1]; 49 if(f[cur][j] == f[cur^1][j] && f[cur][j] == f[cur][j-1] && f[cur^1][j-1] == f[cur][j]) g[cur][j] -= g[cur^1][j-1]; 50 if(A[i] == B[j] && f[cur][j] == f[cur^1][j-1] + 1) g[cur][j] += g[cur^1][j-1]; 51 if(g[cur][j] > MOD) g[cur][j] %= MOD; 52 if(g[cur][j] < 0) g[cur][j] = (g[cur][j] % MOD) + MOD; 53 } 54 } 55 56 printf("%d\n%d\n", f[cur][nb], g[cur][nb]); 57 58 return 0; 59 } View Code 代码二：不使用滚动数组，假如测试数据较小，可以AC。 1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #define mod 100000000 7 using namespace std; 8 string a,b; 9 int f[5005][5005],g[5005][5005]; 10 int main(){ 11 cin>>a>>b; 12 int l1=a.length()-1,l2=b.length()-1; 13 a=' '+a,b=' '+b; 14 for(int i=0;i<=l1;i++)g[i][0]=1; 15 for(int i=0;i<=l2;i++)g[0][i]=1; 16 for(int i=1;i<=l1;i++) 17 for(int j=1;j<=l2;j++) 18 { 19 if(a[i]==b[j]) 20 { 21 f[i][j]=f[i-1][j-1]+1; 22 g[i][j]=g[i-1][j-1]; 23 if(f[i][j]==f[i][j-1])g[i][j]=(g[i][j]+g[i][j-1])%mod; 24 if(f[i][j]==f[i-1][j])g[i][j]=(g[i][j]+g[i-1][j])%mod; 25 } 26 else 27 { 28 f[i][j]=max(f[i-1][j],f[i][j-1]); 29 if(f[i][j]==f[i-1][j])g[i][j]=(g[i][j]+g[i-1][j])%mod; 30 if(f[i][j]==f[i][j-1])g[i][j]=(g[i][j]+g[i][j-1])%mod; 31 if(f[i][j]==f[i-1][j-1])g[i][j]-=g[i-1][j-1],g[i][j]=(g[i][j]+mod)%mod; 32 } 33 } 34 cout<<f[l1][l2]<<endl<<g[l1][l2]%mod; 35 return 0; 36 } View Code
-
发表了文章 2017-08-24
最长公共子序列(POJ1458)
题目链接：http://poj.org/problem?id=1458 题目大意：给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。 输入有若干行，每行是两个字符串。对每一行输入的两个字符串，输出最长公共子串的长度。 Sample Inputabcfbc abfcabprogramming contest abcd mnp Sample Output420 算法分析 参考1：北大郭炜老师mooc课程参考2：http://blog.csdn.net/u013480600/article/details/40741333 参考3：http://blog.csdn.net/lz161530245/article/details/76943991 输入两个串s1,s2,设MaxLen(i,j)表示:s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0开始算）MaxLen(i,j) 就是本题的“状态”假定 len1 = strlen(s1),len2 = strlen(s2）那么题目就是要求 MaxLen(len1,len2) 显然：MaxLen(n,0) = 0 ( n= 0…len1）MaxLen(0,n) = 0 ( n=0…len2）递推公式：if(s1[i-1] == s2[j-1]) //s1的最左边字符是s1[0] MaxLen(i,j) = MaxLen(i-1,j-1) + 1;else MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );时间复杂度O(mn),其中m,n是两个字串长度。 关于证明，可以阅读参考2和参考3的证明过程。大概过程记录如下： 我们用Ax表示序列A的连续前x项构成的子序列，即Ax= a1,a2,……ax, By= b1,b2,……by, 我们用LCS(x, y)表示它们的最长公共子序列长度，那原问题等价于求LCS(m,n)。为了方便我们用L(x, y)表示Ax和By的一个最长公共子序列。 让我们来看看如何求LCS(x, y)。我们令x表示子序列,考虑最后一项 第（1）种情况：Ax ＝ By 那么它们L(Ax, By)的最后一项一定是这个元素！ 为什么呢？为了方便，我们令t=Ax=By, 我们用反证法：假设L(x,y)最后一项不是t， 则要么L(x,y)为空序列（别忘了这个），要么L(x,y)的最后一项是Aa＝Bb ≠ t, 且显然有a<x,b<y。无论是哪种情况我们都可以把t接到这个L(x,y)后面,从而得到一个更长的公共子序列。矛盾！ 如果我们从序列Ax中删掉最后一项ax得到Ax-1,从序列By中也删掉最后一项by得到By-1，(多说一句角标为0时，认为子序列是空序列)，则我们从L(x,y)也删掉最后一项t得到的序列是L(x – 1, y - 1)。为什么呢？和上面的道理相同，如果得到的序列不是L(x - 1, y - 1)，则它一定比L(x - 1, y - 1)短，那么它后面接上元素t得到的子序列L(x,y)也比L(x - 1, y - 1)接上元素t得到的子序列短，这与L(x, y)是最长公共子序列矛盾。 因此L(x,y)=L(x-1,y-1)最后接上元素t，也就是说： LCS(Ax, By) = LCS(x - 1, y - 1) + 1 第（2）种情况：Ax ≠ By 仍然设t=L(Ax,By)的最后一个字符,或者L(Ax,By)是空序列（这时t是未定义值不等于任何值）。 则t≠Ax和t≠By至少有一个成立，因为t不能同时等于两个不同的值嘛！ （2.1） 如果t≠Ax，则有L(x,y)=L(x-1,y)，因为根本没Ax的事嘛。 也就是说：LCS(x,y) = LCS(x – 1, y) （2.2） 如果t≠By,同理有L(x,y)= L(x,y-1)。 也就是说：LCS(x,y) = LCS(x, y – 1) 可是，我们事先并不知道t，由定义，我们取最大的一个，因此这种情况下,有LCS(x,y)=max(LCS(x–1,y),LCS(x,y–1))。 看看目前我们已经得到了什么结论： LCS(x,y) = (1) LCS(x - 1,y - 1) + 1 如果Ax ＝ By (2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By 这是一个显然的递推式，光有递推可不行，初值是什么呢？ 显然，一个空序列和任何序列的最长公共子序列都是空序列！所以我们有: LCS(x,y) = (1) LCS(x - 1,y - 1) + 1 如果Ax ＝ By (2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By (3) 0 如果x=0或者y=0 到此我们求出了计算最长公共子序列长度的递推公式。我们实际上计算了一个(n + 1)行(m + 1)列的表格（行是0..n，列是0..m)，也就这个二维度数组LCS(n,m)。 证明过程 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 char sz1[5005]; 5 char sz2[5005]; 6 int maxLen[5005][5005]; 7 int main() 8 { 9 while( cin >> sz1 >> sz2 ) 10 { 11 int length1 = strlen( sz1); 12 int length2 = strlen( sz2); 13 int nTmp; 14 int i,j; 15 for( i = 0;i <= length1; i ++ ) maxLen[i][0] = 0; 16 for( j = 0;j <= length2; j ++ ) maxLen[0][j] = 0; 17 for( i = 1;i <= length1;i ++ ) 18 { 19 for( j = 1; j <= length2; j ++ ) 20 { 21 if( sz1[i-1] == sz2[j-1] ) 22 maxLen[i][j] = maxLen[i-1][j-1] + 1; 23 else 24 maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]); 25 } 26 } 27 cout << maxLen[length1][length2] << endl; 28 } 29 return 0; 30 } 上面的题目并没有要求输出最长的公共子序列。假如要输出最长公共子序列，可以阅读参考3的代码：（也可以暂时跳过，本文末尾有代码实现。） 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 int LCSLength(char* str1, char* str2, int **b) 5 { 6 int i,j,length1,length2,len; 7 length1 = strlen(str1); 8 length2 = strlen(str2); 9 10 //双指针的方法申请动态二维数组 11 int **c = new int*[length1+1]; //共有length1+1行 12 for(i = 0; i < length1+1; i++) 13 c[i] = new int[length2+1];//共有length2+1列 14 15 for(i = 0; i < length1+1; i++) 16 c[i][0]=0; //第0列都初始化为0 17 for(j = 0; j < length2+1; j++) 18 c[0][j]=0; //第0行都初始化为0 19 20 for(i = 1; i < length1+1; i++) 21 { 22 for(j = 1; j < length2+1; j++) 23 { 24 if(str1[i-1]==str2[j-1])//由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-1个元素 25 { 26 c[i][j]=c[i-1][j-1]+1; 27 b[i][j]=0; //输出公共子串时的搜索方向 28 } 29 else if(c[i-1][j]>c[i][j-1]) 30 { 31 c[i][j]=c[i-1][j]; 32 b[i][j]=1; 33 } 34 else 35 { 36 c[i][j]=c[i][j-1]; 37 b[i][j]=-1; 38 } 39 } 40 } 41 /* 42 for(i= 0; i < length1+1; i++) 43 { 44 for(j = 0; j < length2+1; j++) 45 printf("%d ",c[i][j]); 46 printf("\n"); 47 } 48 */ 49 len=c[length1][length2]; 50 for(i = 0; i < length1+1; i++) //释放动态申请的二维数组 51 delete[] c[i]; 52 delete[] c; 53 return len; 54 } 55 void PrintLCS(int **b, char *str1, int i, int j) 56 { 57 if(i==0 || j==0) 58 return ; 59 if(b[i][j]==0) 60 { 61 PrintLCS(b, str1, i-1, j-1);//从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串 62 printf("%c",str1[i-1]);//c[][]的第i行元素对应str1的第i-1个元素 63 } 64 else if(b[i][j]==1) 65 PrintLCS(b, str1, i-1, j); 66 else 67 PrintLCS(b, str1, i, j-1); 68 } 69 70 int main(void) 71 { 72 char str1[100],str2[100]; 73 int i,length1,length2,len; 74 printf("请输入第一个字符串："); 75 gets(str1); 76 printf("请输入第二个字符串："); 77 gets(str2); 78 length1 = strlen(str1); 79 length2 = strlen(str2); 80 //双指针的方法申请动态二维数组 81 int **b = new int*[length1+1]; 82 for(i= 0; i < length1+1; i++) 83 b[i] = new int[length2+1]; 84 len=LCSLength(str1,str2,b); 85 printf("最长公共子序列的长度为：%d\n",len); 86 printf("最长公共子序列为："); 87 PrintLCS(b,str1,length1,length2); 88 printf("\n"); 89 for(i = 0; i < length1+1; i++)//释放动态申请的二维数组 90 delete[] b[i]; 91 delete[] b; 92 system("pause"); 93 return 0; 94 } 求最长公共子序列长度并输出最长公共子序列 查找并输出最长公共子序列也可以参考https://wenku.baidu.com/view/7e96c94f2b160b4e767fcfc9.html 空间上的优化： 观察上面算法中的关键代码： for( i = 1;i <= length1;i ++ ) { for( j = 1; j <= length2; j ++ ) { if( sz1[i-1] == sz2[j-1] ) maxLen[i][j] = maxLen[i-1][j-1] + 1; else maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]); } } 可以发现，计算maxLen数组第i行时用到的只有第i行与第i-1行。我们的目的是要计算maxLen[length1][length2]，所以，可以考虑只保存两行即可，也就是使用滚动数组只保存两行。 代码如下：（参考来源） cur表示当前需要求的那一行的下标。 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 char sz1[5005]; 5 char sz2[5005]; 6 int maxLen[2][5005]; 7 int main() 8 { 9 int i,j,length1,length2,cur=0; 10 11 while( cin >> sz1 >> sz2 ) 12 { 13 length1 = strlen( sz1); 14 length2 = strlen( sz2); 15 for( i=0;i<2; i++ ) maxLen[i][0]=0; 16 for( j=0;j<=length2;j++ ) maxLen[0][j]=0; 17 cur=0; 18 19 for( i = 1;i <= length1;i ++ ) 20 { 21 cur ^= 1; 22 for( j = 1; j <= length2; j ++ ) 23 { 24 if( sz1[i-1] == sz2[j-1] ) 25 maxLen[cur][j] = maxLen[cur^1][j-1] + 1; 26 else 27 maxLen[cur][j] = max(maxLen[cur][j-1],maxLen[cur^1][j]); 28 } 29 } 30 cout << maxLen[cur][length2] << endl; 31 } 32 return 0; 33 } View Code 下面修改一下代码寻找出一个最长公共子序列。 上面经过空间优化后，也只是寻找到了最长公共子序列的长度，那么如何得到一个最长公共子序列而仅仅不是简单的长度呢？其实我们离真正的答案只有一步之遥！ 参考上图，我们建立一个二维数组ans[][]，在寻找最长公共子序列的长度时用ans[i][j]记录LCS（i，j）是如何来的（从左边、上边或是从左上），ans[i][j]等于1，2，3分别表示： L(x,y) = L(x, y – 1) L(x,y)= L(x – 1, y) L(x,y) = L(x,- 1 y- 1)末尾接上Ax 当ans[i][j]等于3时字符串1的第i个字符（或字符串2的第j个字符，其实两者相同）肯定是最长公共子序列的一部分，要保留到temp[ ]中。所以从ans[][]右下角逆推即可求出temp[ ]，然后逆序输出temp[]即可。代码如下： 1 //51Nod动态规划教程例题 求最长公共子序列的长度并输出一个最长公共子序列 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5 #define maxN 5005 6 char sz1[maxN]; 7 char sz2[maxN]; 8 int maxLen[2][maxN]; 9 char ans[maxN][maxN]={0}; 10 11 void printLCS(int len1,int len2);//输出一个最长公共子序列 12 int main() 13 { 14 int i,j,length1,length2,cur=0; 15 freopen("poj1458.in","r",stdin); 16 while( cin >> sz1 >> sz2 ) 17 { 18 memset(ans,0,sizeof(char)*maxN*maxN); 19 length1 = strlen( sz1); 20 length2 = strlen( sz2); 21 for( i=0;i<2; i++ ) maxLen[i][0]=0; 22 for( j=0;j<=length2;j++ ) maxLen[0][j]=0; 23 cur=0; 24 25 for( i = 1;i <= length1;i ++ ) 26 { 27 cur ^= 1; 28 for( j = 1; j <= length2; j ++ ) 29 { 30 if( sz1[i-1] == sz2[j-1] ) 31 { 32 maxLen[cur][j] = maxLen[cur^1][j-1] + 1; 33 ans[i][j]=3; 34 } 35 else 36 { 37 //maxLen[cur][j] = max(maxLen[cur][j-1],maxLen[cur^1][j]); 38 if(maxLen[cur][j-1]>maxLen[cur^1][j]) 39 { 40 maxLen[cur][j]=maxLen[cur][j-1]; 41 ans[i][j]=1; 42 } 43 else 44 { 45 maxLen[cur][j]=maxLen[cur^1][j]; 46 ans[i][j]=2; 47 } 48 } 49 } 50 } 51 cout << maxLen[cur][length2] << endl; 52 if(maxLen[cur][length2]>0) printLCS(length1,length2); 53 } 54 return 0; 55 } 56 void printLCS(int len1,int len2)//输出一个最长公共子序列 57 { 58 char temp[maxN]; 59 int i=len1,j=len2,k=0; 60 while(ans[i][j]!=0) 61 { 62 if(ans[i][j]==3) { temp[k++]=sz1[i-1]; i--;j--; } 63 else if(ans[i][j]==1) 64 { 65 j--; 66 } 67 else if(ans[i][j]==2) 68 { 69 i--; 70 } 71 } 72 for(k--;k>=0;k--) printf("%c",temp[k]); 73 printf("\n"); 74 }
-
发表了文章 2017-08-22
编程填空：左边i位取反
总时间限制: 1000ms 内存限制: 1024kB描述写出函数中缺失的部分，使得函数返回值为一个整数,该整数的左边i位是n的左边i位取反，其余位和n相同请使用【一行代码】补全bitManipulation3函数使得程序能达到上述的功能 1 #include <iostream> 2 using namespace std; 3 4 int bitManipulation3(int n, int i) { 5 // 在此处补充你的代码 6 } 7 8 int main() { 9 int t, n, i; 10 cin >> t; 11 while (t--) { 12 cin >> n >> i; 13 cout << bitManipulation3(n, i) << endl; 14 } 15 return 0; 16 } 输入 第一行是整数 t，表示测试组数。每组测试数据包含一行，是两个整数 n 和 i (1<=i<=32)。输出对每组输入数据，输出整型变量n中左边i位取反的结果。样例输入10 32样例输出-1提示注意i从1开始 1 #include <iostream> 2 using namespace std; 3 4 int bitManipulation3(int n, int i) { 5 // 在此处补充你的代码 6 7 return i==32 ? (~n) : ( (((1<<i)-1)<<(32-i))^n ); 8 } 9 10 int main() { 11 int t, n, i; 12 cin >> t; 13 while (t--) { 14 cin >> n >> i; 15 cout << bitManipulation3(n, i) << endl; 16 } 17 return 0; 18 }
-
发表了文章 2017-08-22
编程填空：第i位取反
总时间限制: 1000ms 内存限制: 1024kB描述写出函数中缺失的部分，使得函数返回值为一个整数,该整数的第i位是n的第i位取反，其余位和n相同 请使用【一行代码】补全bitManipulation2函数使得程序能达到上述的功能 1 #include <iostream> 2 using namespace std; 3 4 int bitManipulation2(int n, int i) { 5 // 在此处补充你的代码 6 } 7 8 int main() { 9 int t, n, i; 10 cin >> t; 11 while (t--) { 12 cin >> n >> i; 13 cout << bitManipulation2(n, i) << endl; 14 } 15 return 0; 16 } 输入 第一行是整数 t，表示测试组数。每组测试数据包含一行，是两个整数 n 和 i (0<=i<=31)。输出输出整型变量n中的第i位取反的结果样例输入11 0样例输出0提示二进制的最右边是第0位 1 #include <iostream> 2 using namespace std; 3 4 int bitManipulation2(int n, int i) { 5 // 在此处补充你的代码 6 return n^(1<<i); 7 } 8 9 int main() { 10 int t, n, i; 11 cin >> t; 12 while (t--) { 13 cin >> n >> i; 14 cout << bitManipulation2(n, i) << endl; 15 } 16 return 0; 17 }
-
发表了文章 2017-08-22
编程填空：第i位替换
总时间限制: 1000ms 内存限制: 1024kB 描述 写出函数中缺失的部分，使得函数返回值为一个整数,该整数的第i位和m的第i位相同，其他位和n相同。 请使用【一行代码】补全bitManipulation1函数使得程序能达到上述的功能 #include <iostream> using namespace std; int bitManipulation1(int n, int m, int i) { // 在此处补充你的代码 } int main() { int n, m, i, t; cin >> t; while (t--) { cin >> n >> m >> i; cout << bitManipulation1(n, m, i) << endl; } return 0; } 输入 第一行是整数 t，表示测试组数。每组测试数据包含一行，是三个整数 n, m 和 i (0<=i<=31) 输出 对每组输入数据，每行输出整型变量n变化后的结果 样例输入 1 1 2 1 样例输出 3 提示 二进制的最右边是第0位 1 #include <iostream> 2 using namespace std; 3 4 int bitManipulation1(int n, int m, int i) { 5 // 在此处补充你的代码 6 return ((m>>i)&1)==1 ? (n|(1<<i)) : (n&(~(1<<i))); 7 } 8 9 int main() { 10 int n, m, i, t; 11 freopen("in (4).txt","r",stdin); 12 cin >> t; 13 while (t--) { 14 cin >> n >> m >> i; 15 cout << bitManipulation1(n, m, i) << endl; 16 } 17 return 0; 18 }
-
发表了文章 2017-08-11
poj 2192 Zipper
题目链接：http://poj.org/problem?id=2192 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 18658 Accepted: 6651 Description Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order. For example, consider forming "tcraete" from "cat" and "tree": String A: cat String B: tree String C: tcraete As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree": String A: cat String B: tree String C: catrtee Finally, notice that it is impossible to form "cttaree" from "cat" and "tree". Input The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line. For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive. Output For each data set, print: Data set n: yes if the third string can be formed from the first two, or Data set n: no if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example. Sample Input 3 cat tree tcraete cat tree catrtee cat tree cttaree Sample Output Data set 1: yes Data set 2: yes Data set 3: no Source Pacific Northwest 2004 题目大意： 给出两串，从两个串取出字符重新组合，看能否组成第三个串。要求：从第一个串取出的字符在第三个串中的顺序不变，第二个串取出的字符在第三个串中的顺序也不变。 算法分析： 此题深搜和DP都能解决： 深搜的话需要几个强有力剪枝条件 1、 第三个串最后一个字符要么是串1的最后一个字符，要么是串2的最后一个字符 2、 按照串1的顺序对串3进行搜索，若不匹配则该字符必是串2的下一个字符。 参考来源：http://www.cnblogs.com/yu-chao/archive/2012/02/26/2369052.html 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 char first[202],second[202],third[402],Left[401]; 6 int sign[402]; 7 bool flag; 8 int check() 9 { 10 int i,count=0; 11 int k=strlen(third); 12 for(i=0;i<k;i++) 13 if(!sign[i]) Left[count++]=third[i]; 14 Left[count]='\0'; 15 if(strcmp(Left,second)==0) return 1; 16 return 0; 17 } 18 int dfs(int f,int s,int t) 19 { 20 if(f>=strlen(first)) 21 { 22 if(check()) flag=true; 23 return 0; 24 } 25 if(flag) return 0; 26 if(first[f]==third[s]) 27 { 28 sign[s]=1; 29 if(s<strlen(third)) dfs(f+1,s+1,t); 30 sign[s]=0; 31 } 32 else 33 { 34 if(third[s]!=second[t]) return 0;//剪枝2 35 } 36 if(!flag && s<strlen(third)) dfs(f,s+1,t+1); 37 return 0; 38 } 39 int main() 40 { 41 int len1,len2,len3,Case,count=0; 42 scanf("%d",&Case); 43 while(Case--) 44 { 45 count++; 46 flag=false; 47 scanf("%s %s %s",first,second,third); 48 memset(sign,0,sizeof(sign)); 49 50 len1=strlen(first); 51 len2=strlen(second); 52 len3=strlen(third); 53 54 if(len1+len2!=len3) 55 { 56 printf("Data set %d: no\n",count); 57 continue; 58 } 59 if(third[len3-1]!=first[len1-1] && third[len3-1]!=second[len2-1])// 剪枝1 60 { 61 printf("Data set %d: no\n",count); 62 continue; 63 } 64 dfs(0,0,0); 65 if(flag) 66 printf("Data set %d: yes\n",count); 67 else 68 printf("Data set %d: no\n",count); 69 } 70 return 0; 71 } View Code 动规算法：（参考来源） 最优子结构分析：如上例，如果A、B可以组成C，那么，C最后一个字母，必定是 A 或 B 的最后一个字母组成。 C去除除最后一位，就变成是否可以求出 A-1和B 或者 A与B-1 与 是否可以构成 C-1。。。 状态转移方程： 用f[i][j] 表示 A前 i 位 和B 前j 位是否可以组成 C的前i+j位 dp[i][j]= (dp[i-1][j]&&(a[i]==c[i+j]))||(dp[i][j-1]&&(b[j]==c[i+j])) 1 #include<stdio.h> 2 #include<string.h> 3 4 char a[201],b[201],c[402]; 5 int la,lb,lc; 6 int dp[201][201]; 7 8 int main() 9 { 10 int ncase; 11 scanf("%d",&ncase); 12 for(int n=1; n<=ncase; n++) { 13 14 a[0]='p'; 15 b[0]='p'; 16 c[0]='p'; 17 18 scanf("%s%s%s",a+1,b+1,c+1); 19 20 la=strlen(a); 21 lb=strlen(b); 22 lc=strlen(c); 23 24 la-=1; 25 lb-=1; 26 27 //处理边界 28 for (int i=1; i<=la; i++) 29 if (a[i]==c[i]) dp[i][0]=1; 30 31 for (int i=1; i<=lb; i++) 32 if (b[i]==c[i]) dp[0][i]=1; 33 //DP 34 for (int i=1; i<=la; i++) 35 for (int j=1; j<=lb; j++) 36 dp[i][j]= (dp[i-1][j]&&(a[i]==c[i+j]))||(dp[i][j-1]&&(b[j]==c[i+j])); 37 38 printf("Data set %d: ",n); 39 if (dp[la][lb]==1) printf("yes\n"); 40 else printf("no\n"); 41 42 } 43 } 虽然代码简洁明了易理解，但是个人感觉下面的代码更准确一些。 来源：http://www.cnblogs.com/yu-chao/archive/2012/02/26/2369052.html 若用DP来作先定义res[i][j]=1表示串1前i个字符和串2的前j个字符能组成串3的前i+j个字符，res[i][j]=0则不能。 状态转移方程如下： Res[i][j]= (third[i+j]==first[i] && res[i-1][j]==1) ||(third[i+j]==second[j]&&res[i][j-1]==1) 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 char first[201],second[201],third[401]; 6 int res[201][201]; 7 int init(int n,int m) 8 { 9 int i; 10 for(i=1;i<=m;i++) 11 if(second[i]==third[i]) res[0][i]=1; 12 else break; 13 for(i=1;i<=n;i++) 14 if(first[i]==third[i]) res[i][0]=1; 15 else break; 16 return 0; 17 } 18 int dp(int n,int m) 19 { 20 int i,j; 21 for(i=1;i<=n;i++) 22 for(j=1;j<=m;j++) 23 { 24 if(third[i+j]==first[i] && res[i-1][j]) res[i][j]=1; 25 if(third[i+j]==second[j] && res[i][j-1]) res[i][j]=1; 26 } 27 if(res[n][m]) return 1; 28 return 0; 29 } 30 int main() 31 { 32 int n,len1,len2,count=0;; 33 scanf("%d",&n); 34 while(n--) 35 { 36 count++; 37 scanf("%s %s %s",first+1,second+1,third+1); 38 len1=strlen(first+1); 39 len2=strlen(second+1); 40 memset(res,0,sizeof(res)); 41 init(len1,len2); 42 43 if(dp(len1,len2)) 44 printf("Data set %d: yes\n",count); 45 else 46 printf("Data set %d: no\n",count); 47 } 48 return 0; 49 } View Code
-
发表了文章 2017-08-11
3:拦截导弹
题目链接：http://cxsjsxmooc.openjudge.cn/2017t2summerw5/3/ 总时间限制: 1000ms 内存限制: 65536kB 描述 某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。 输入 输入有两行，第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。 输出 输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。 样例输入 8 300 207 155 300 299 170 158 65 样例输出 6 来源 医学部计算概论2006期末考试题 算法分析： 这个题目其实跟最长上升子序列问题类似，只是这里寻找的是最长不上升子序列的长度。 假设用maxLen[k]表示以a[k]做为“终点”的最长不上升子序列的长度，那么： 初始状态： maxLen [1] = 1maxLen[k]= max { maxLen [i]： 1<=i < k 且 a[i ]>= a[k]且 k≠1 } + 1若找不到这样的i,则maxLen[k] = 1 maxLen[k]的值，就是在a[k]左边，“终点”数值大于或等于a[k] ，且长度最大的那个不上升子序列的长度再加1。因为a[k]左边任何“终点”大于或等于a[k]的子序列，加上a[k]后就能形成一个更长的不上升子序列 。 1 #include <stdio.h> 2 #define maxN 5005 3 int main(int argc, char *argv[]) 4 { 5 int i,j; 6 int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长不上升子序列的长度 7 int max; 8 9 scanf("%d",&n); 10 for(i=0;i<n;i++) { scanf("%d",&a[i]); maxLen[i]=1; } 11 12 for(i=1;i<n;i++)//枚举所有子序列的终点 13 { 14 for(j=0;j<i;j++)//枚举以a[i]做终点的子序列中a[i]的前缀元素 15 { 16 if(a[j]>=a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列 17 { 18 maxLen[i]=(maxLen[j]+1>maxLen[i]?maxLen[j]+1:maxLen[i]); 19 } 20 } 21 } 22 max=maxLen[0]; 23 for(i=1;i<n;i++) 24 if(maxLen[i]>max) max=maxLen[i]; 25 printf("%d\n",max); 26 return 0; 27 } 注意：不要想着把数组翻转过来然后寻找最长上升子序列哈哈哈，题目说了，不能够先拦截后面的导弹。
-
发表了文章 2017-08-09
codevs 1576 最长严格上升子序列
题目链接：http://codevs.cn/problem/1576/ 题目描述 Description 给一个数组a1, a2 ... an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。 输出长度即可。 输入描述 Input Description 第一行，一个整数N。 第二行 ，N个整数（N < = 5000） 输出描述 Output Description 输出K的极大值，即最长不下降子序列的长度 样例输入 Sample Input 5 9 3 6 2 7 样例输出 Sample Output 3 数据范围及提示 Data Size & Hint 【样例解释】 最长不下降子序列为3,6,7 解题思路 参考：北大郭炜老师 1.找子问题：“求以ak（ k=1, 2, 3…N）为终点的最长上升子序列的长度”一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。 2. 确定状态子问题只和一个变量-- 数字的位置相关。因此序列中数的位置k 就是“状态”，而状态 k 对应的“值”，就是以a[k]做为“终点”的最长上升子序列的长度。状态一共有N个。 3. 找出状态转移方程 maxLen [k]表示以a[k]做为“终点”的最长上升子序列的长度那么：初始状态： maxLen [1] = 1maxLen[k]= max { maxLen [i]： 1<=i < k 且 a[i ]< a[k]且 k≠1 } + 1若找不到这样的i,则maxLen[k] = 1 maxLen[k]的值，就是在a[k]左边，“终点”数值小于a[k] ，且长度最大的那个上升子序列的长度再加1。因为a[k]左边任何“终点”小于a[k]的子序列，加上a[k]后就能形成一个更长的上升子序列 。 1 #include <stdio.h> 2 #define maxN 5005 3 int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度 4 int main(int argc, char *argv[]) 5 { 6 int i,j; 7 scanf("%d",&n); 8 for(i=0;i<n;i++) { scanf("%d",&a[i]); maxLen[i]=1; } 9 10 for(i=1;i<n;i++)//枚举所有子序列的终点 11 { 12 for(j=0;j<i;j++)//枚举以a[i]做终点的子序列中a[i]的前缀元素 13 { 14 if(a[j]<a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列 15 { 16 maxLen[i]=(maxLen[j]+1>maxLen[i]?maxLen[j]+1:maxLen[i]); 17 } 18 } 19 } 20 printf("%d\n",maxLen[n-1]); 21 return 0; 22 } 上面的代码写错了，抱歉。更正如下： 1 #include <stdio.h> 2 #define maxN 5005 3 int main(int argc, char *argv[]) 4 { 5 int i,j,t; 6 int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度 7 int max; 8 9 scanf("%d",&n); 10 for(i=0;i<n;i++) { scanf("%d",&a[i]); maxLen[i]=1; } 11 for(i=1;i<n;i++)//枚举所有子序列的终点 12 { 13 for(j=0;j<i;j++)//枚举以a[i]做终点的子序列中a[i]的前缀元素 14 { 15 if(a[j]<a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列 16 { 17 maxLen[i]=(maxLen[j]+1>maxLen[i]?maxLen[j]+1:maxLen[i]); 18 } 19 } 20 } 21 max=maxLen[0]; 22 for(i=1;i<n;i++) 23 if(maxLen[i]>max) max=maxLen[i]; 24 printf("%d\n",max); 25 return 0; 26 } 思考题 ： 如何改进程序，使之能够输出最长上升子序列 ？ 思路：新增pre[ ]，其中pre[k]=x表示在a[ ]序列构成的若干个上升子序列中，a[k[的前驱是a[x]。一开始pre[ ]全部初始化为-1表示一开始所有元素的前驱都是自己本身。在循环求解maxLen[i]的同时，更新pre[i]。最后在扫描出maxLen[ ]最大值为maxLen[i]以后，从pre[i]往前推即可。假如要顺序输出该最长上升子序列，可以把逆推pre[ ]的过程保存再输出。 参考代码： 1 #include<stdio.h> 2 #include<string.h> 3 #define maxN 5005 4 int main(int argc, char *argv[]) 5 { 6 int i,j,t; 7 int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度 8 int max; 9 int pre[maxN]; 10 int c[maxN],maxIndex; 11 12 memset(pre,-1,sizeof(pre)); 13 14 scanf("%d",&n); 15 for(i=0;i<n;i++) { scanf("%d",&a[i]); maxLen[i]=1; } 16 17 for(i=1;i<n;i++)//枚举所有子序列的终点 18 { 19 for(j=0;j<i;j++)//枚举以a[i]做终点的子序列中a[i]的前缀元素 20 { 21 if(a[j]<a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列 22 { 23 if(maxLen[j]+1>maxLen[i]) 24 { 25 maxLen[i]=maxLen[j]+1; 26 pre[i]=j; 27 } 28 } 29 } 30 } 31 max=maxLen[0]; 32 for(i=1;i<n;i++) 33 if(maxLen[i]>max) { max=maxLen[i]; maxIndex=i; } 34 printf("%d\n",max); 35 36 j=0; 37 c[j++]=a[maxIndex]; 38 while(pre[maxIndex]!=-1) 39 { 40 maxIndex=pre[maxIndex]; 41 c[j++]=a[maxIndex]; 42 } 43 for(i=j-1;i>=0;i--) 44 { 45 printf("%d ",c[i]); 46 } 47 printf("\n"); 48 return 0; 49 } View Code
-
发表了文章 2017-08-09
3299 有序数组合并求第K大问题
题目描述 Description 给出两个有序数组A和B（从小到大有序），合并两个有序数组后新数组c也有序，询问c数组中第k大的数 假设不计入输入输出复杂度，你能否给出一个O(logN)的方法？ 输入描述 Input Description 第一行输入三个整数n、m和k 第二行输入n个用空格隔开的整数表示数组A 第三行输入m个用空格隔开的整数表示数组B 输入保证A和B数组非递减 输出描述 Output Description 合并两个数组之后的第k大的数 样例输入 Sample Input 2 3 4 1 2 1 1 5 样例输出 Sample Output 2 数据范围及提示 Data Size & Hint 1<=n,m<=1000000 1<=k <=n+m 算法一：O（m+n+k） 做类似于归并排序的合并，但是没有使用额外的空间。 1 #include <stdio.h> 2 long long n,m,k,a[1000005],b[1000005]; 3 long long findKthSMallest() 4 { 5 int ai=0,bi=0; 6 while(k>0) 7 { 8 if(ai<n&&bi<m) 9 { 10 if(a[ai]<=b[bi]) 11 { 12 if(k==0) return a[ai]; 13 ai++; 14 } 15 else if(b[bi]<=a[ai]) 16 { 17 if(k==0) return b[bi]; 18 bi++; 19 } 20 } 21 else if(ai<n&&bi==m) 22 { 23 if(k==0) return a[ai]; 24 ai++; 25 } 26 else if(ai==n&&bi<m) 27 { 28 if(k==0) return b[bi]; 29 bi++; 30 } 31 else return -1; 32 33 k--; 34 } 35 } 36 int main(int argc, char *argv[]) 37 { 38 int i; 39 scanf("%d%d%d",&n,&m,&k); 40 for(i=0;i<n;i++) scanf("%d",&a[i]); 41 for(i=0;i<m;i++) scanf("%d",&b[i]); 42 printf("%d\n",findKthSMallest()); 43 return 0; 44 } View Code 下面的代码是同样的思路，但是代码比较简洁易懂： 1 #include <stdio.h> 2 int n,m,k,a[1000005],b[1000005]; 3 int findKthSMallest(int a[],int n,int b[],int m,int k) 4 { 5 int a_offset = 0, b_offset = 0; 6 if(n+m<k) return -1; 7 8 while(true) 9 { 10 if(a_offset<n) 11 { 12 while (b_offset == m || a_offset<n&&a[a_offset] <= b[b_offset]) 13 { 14 if(a_offset+1 + b_offset == k) return a[a_offset]; 15 a_offset++; 16 } 17 } 18 if(b_offset<m) 19 { 20 while (a_offset == n || b_offset<m&&a[a_offset] >= b[b_offset]) 21 { 22 if (a_offset + b_offset+1 == k) return b[b_offset]; 23 b_offset++; 24 } 25 } 26 } 27 } 28 int main(int argc, char *argv[]) 29 { 30 int i; 31 scanf("%d%d%d",&n,&m,&k); 32 for(i=0;i<n;i++) scanf("%d",&a[i]); 33 for(i=0;i<m;i++) scanf("%d",&b[i]); 34 printf("%d\n",findKthSMallest(a,n,b,m,k)); 35 return 0; 36 } 第二段代码参考自：在线疯狂的博客，原文代码有误，已经修正。 第三种写法：省一些空间，b[ ]并没有提前完整输入。 1 #include <stdio.h> 2 int n,m,k,a[1000005]; 3 int main(int argc, char *argv[]) 4 { 5 int i,j,bTemp,kIndex,kValue=0,f; 6 scanf("%d%d%d",&n,&m,&k); 7 for(i=0;i<n;i++) scanf("%d",&a[i]); 8 9 i=0,kIndex=0,f=0; 10 for(j=0;j<m||i<n;j++) // i是a[]的下标，j是b[]的下标 11 { 12 //for的语句条件和这里的if条件是防止b[]扫描完了却未曾寻找到第k个数. 13 //这个时候需要继续循环，在a[]中寻找，但是不再输入 14 if(j<m) scanf("%d",&bTemp); 15 16 while(i<n||j<m) 17 { 18 if(j==m||i<n&&a[i]<=bTemp) 19 { 20 kIndex++; 21 kValue=a[i++]; 22 if(kIndex==k) { f=1; break; } 23 } 24 else 25 { 26 kIndex++; 27 kValue=bTemp; 28 if(kIndex==k) f=1; 29 break; 30 } 31 } 32 if(f==1) break; 33 } 34 printf("%d\n",kValue); 35 return 0; 36 } View Code 算法二：时间复杂度O（log（n+m））。当然，假如考虑输入，那时间复杂度仍然是O（n+m） 代码来源：http://www.cnblogs.com/swanspouse/p/5285015.html 代码解析： 传统解法，最直观的解法是O(m+n)。直接merge两个数组，然后求第K大的数字。 如果想要时间复杂度将为O(log(m+n))。我们可以考虑从K入手。如果我们每次能够删除一个一定在第K个元素之前的元素，那么我们需要进行K次，但是如果每次我们都删除一半呢？由于两个数组都是有序的，我们应该充分利用这个信息。 假设A B 两数组的元素都大于K/2，我们将A B两数组的第K/2个元素进行比较。比较的结果有三种情况。 A[K/2] == B[K/2] A[K/2] > B[K/2] A[K/2] <= B[K/2] 如果 A[K/2] < B[K/2] 意味着 A[0] 到 A[K/2] 肯定在A∪B的前k个元素中。因此我们可以放心删除A数组的这个k/2个元素。同理A[K/2] > B[K/2]。 如果 A[K/2] == B[K/2] 说明已经找到了第K个元素，直接返回A[K/2]或者B[K/2]。 1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4 int a[1000005],b[1000005]; 5 int find_kth(int A[],int m, int B[], int n, int k) 6 { 7 if(m > n ) return find_kth(B, n, A, m, k); 8 if( m == 0) return B[k-1]; 9 if( k == 1) return min(A[0], B[0]); 10 11 int ia = min(k /2, m); 12 int ib = k -ia; 13 if( A[ia-1] < B[ib -1]) 14 return find_kth(A +ia, m -ia, B, n, k -ia); 15 else if( A[ia-1] > B[ib-1]) 16 return find_kth(A, m, B +ib, n -ib, k -ib); 17 else 18 return A[ia-1]; 19 } 20 int main(int argc, char *argv[]) 21 { 22 int i,n,m,k; 23 int ans; 24 scanf("%d%d%d",&n,&m,&k); 25 for(i=0;i<n;i++) scanf("%d",&a[i]); 26 for(i=0;i<m;i++) scanf("%d",&b[i]); 27 ans=find_kth(a,n,b,m,k); 28 printf("%d\n",ans); 29 return 0; 30 } 说明 注意其中的递归终止条件。 将求第K大元素的问题划分成为子问题，不断的对问题进行缩小，采取递归的方式求解。 此问题可以进行拓展，比如求两有序数组的中位数。
暂无更多信息
-
发表了文章
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-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计算概论-排队游戏【这个用到了栈的思想】
滑动查看更多
暂无更多信息
暂无更多信息