首页 > 代码库 > 20150102练习
20150102练习
第一题：给定nm的矩阵，每个格子内有一个数值，要求从第一行到第n行的没一个格子都能到的路线上最大值的最小值。
思路：一开始写了一个裸裸的深搜，但是tle了（当时自己以为不会。。。）。后来听说二分答案，然后就有了一点思路。可以找到所有数值中的最大值和最小值，然后对于mid为标准，比mid小的格子可以走，比mid大的不可以，然后从一头进行floodfill，如果能到另一头，就把范围缩小，一直到l>=r-1，然后输出答案。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int p[1001][1001]={0},dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},m,n,t;bool map[1001][1001]={false},visit[1001][1001]={false},ff=false;void dfs(int x,int y){ int i,j,xx,yy; if (visit[x][y]) return; visit[x][y]=true; if (x==n) { t=m; ff=true; return; } for (i=0;i<=3;++i) { xx=x+dx[i]; yy=y+dy[i]; if (xx>0&&xx<=n&&yy>0&&yy<=m&&map[xx][yy]) { dfs(xx,yy); if (ff) return; } }}int main(){ freopen("murder.in","r",stdin); freopen("murder.out","w",stdout); int i,j,minn,maxn=0,mid,ans; scanf("%d%d",&n,&m); minn=2100000000; for (i=1;i<=n;++i) for (j=1;j<=m;++j) { scanf("%d",&p[i][j]); if (p[i][j]>maxn) maxn=p[i][j]; if (p[i][j]<minn) minn=p[i][j]; map[i][j]=true; } while(minn<maxn-1) { mid=(minn+maxn)/2; memset(visit,false,sizeof(visit)); for (i=1;i<=n;++i) for (j=1;j<=m;++j) { if (p[i][j]<=mid) map[i][j]=true; else map[i][j]=false; } t=0; ff=false; dfs(1,1); if (t<m) minn=mid; else ans=maxn=mid; } printf("%d\n",ans); fclose(stdin); fclose(stdout);}
这里有一点问题，就是要注意return，否则可能re。。。
第二题：给定一些文件的路径，不同的层之间用/隔开，最后输出一个清晰的文件夹形式的目录。
思路：很裸的字符串操作，放到树里面，但因为结点很少，所以不需要什么高级的优化就可以。很简单，不过有些细节问题要注意，不能出错。调了好久。。。读入的时候边分离文件名边从树里找到相对应的路径，从父亲往孩子一层层找就可以了，如果这个父亲没有这个孩子，就把它加进去，然后继续。输出的时候对一个结点的孩子排一下序，然后递归输出就可以了。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;struct use{ int fa,son[16]={0},len; char ch[10];}tree[760000],na;char ss[1000];int comp(struct use x,struct use y){ int i,l; l=min(x.len,y.len); for (i=0;i<l;++i) { if (x.ch[i]<y.ch[i]) return -1; if (x.ch[i]>y.ch[i]) return 1; } if (x.len>l) return 1; if (y.len>l) return -1; return 0;}void dfs(int i,int ceng){ int j,k,t; for (j=1;j<=5*(ceng-1);++j) { if (j%5==1) printf("|"); else printf(" "); } if (ceng>0) printf("|----"); for (j=0;j<tree[i].len;++j) printf("%c",tree[i].ch[j]); printf("\n"); if (tree[i].son[0]==0) return; for (j=1;j<=tree[i].son[0]-1;++j) for (k=tree[i].son[0]-1;k>=j;--k) { if (comp(tree[tree[i].son[k]],tree[tree[i].son[k+1]])>0) { t=tree[i].son[k];tree[i].son[k]=tree[i].son[k+1];tree[i].son[k+1]=t; } } for (j=1;j<=tree[i].son[0];++j) dfs(tree[i].son[j],ceng+1);}int main(){ freopen("file.in","r",stdin); freopen("file.out","w",stdout); int n,i,j,k,l,t,ln,top=0; bool f=false; scanf("%d",&n); for (i=1;i<=n;++i) { scanf("%s%*c",&ss); l=strlen(ss); t=0;j=0; while(j<l) { ln=0; while(ss[j]!=‘/‘&&j<l) { na.ch[ln]=ss[j];++ln;++j; } ++j; na.len=ln;f=false; for (k=1;k<=tree[t].son[0];++k) { if (comp(tree[tree[t].son[k]],na)==0) { t=tree[t].son[k]; f=true; break; } } if (!f) { ++top;tree[top].fa=t;tree[top].len=ln; for (k=0;k<ln;++k) tree[top].ch[k]=na.ch[k]; ++tree[t].son[0]; tree[t].son[tree[t].son[0]]=top; t=top; } } } dfs(1,0); fclose(stdin); fclose(stdout);}
第三题：有n个函数，每一个函数有一个效果值，这n个函数是环形排列的，然后要求从n个函数中选出m个不相邻的函数使其效果值之和最大。
思路：这个题在测试的时候直接放弃了，想写一个深搜，结果十分钟赤裸裸的写渣了。下午先用了dp，结果第一次只写对了几个点。后来看了dada的思路，明白了一些，换了循环顺序，先循环取几个数，然后从能取的数的位置用二维数组更新到这个位置上取多少个数的值，因为是环形的，所以要做两遍（一遍是1~n-1，一遍是2~n），然后取较大值输出。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int f[5001][5001],a[5001]={0},n,m;int work(int l,int r){ int i,j; memset(f,128,sizeof(f)); for (i=l;i<=n;++i) f[i][1]=max(f[i-1][1],a[i]); for (i=2;i<=m;++i) for (j=l+(i-1)*2;j<=r;++j) f[j][i]=max(f[j-1][i],f[j-2][i-1]+a[j]); return f[r][m];}int main(){ freopen("compile.in","r",stdin); freopen("compile.out","w",stdout); int i,j; scanf("%d%d",&n,&m); for (i=1;i<=n;++i) scanf("%d",&a[i]); if (m>n/2) printf("Error!\n"); else printf("%d\n",max(work(1,n-1),work(2,n))); fclose(stdin); fclose(stdout);}
20150102练习
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。