BestCoder Round #42

本文主要是介绍BestCoder Round #42，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一次打bc，也是我第一次打这种比赛，做出来三道不过system test时挂掉一道。原来比赛是这么的好玩。。。总的来说，还是有很多收获的

首先我感觉，我的手速还是有了那么一点提升的

A题水题代码略

B题变形二分

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAX 100010
using namespace std;int n,m,shoot;struct node{int id,value,shooted;bool operator<(node other)const{if(value<other.value)return 1;else if(value>other.value)return 0;else{if(id<other.id)return 1;elsereturn 0;}}
}bird[MAX];int bsearch(int high){int front=0,rear=n-1;if(high<bird[0].value||high>bird[n-1].value)return -1;int mid;while(front<rear){mid=(front+rear)/2;if(bird[mid].value<high)front=mid+1;else if(bird[mid].value>high)rear=mid;else if(bird[mid].value==high){if(bird[mid].shooted==0)rear=mid;else if(bird[mid].shooted==1)front=mid+1;}}if(bird[rear].value==high&&bird[rear].shooted==0){bird[rear].shooted=1;return bird[rear].id;}elsereturn -1;
}int main(){while(scanf("%d %d",&n,&m)!=EOF){for(int i=0;i<n;i++){scanf("%d",&bird[i].value);bird[i].id=i+1,bird[i].shooted=0;}sort(bird,bird+n);//for(int i=0;i<n;i++)//	cout<<bird[i].id<<' '<<bird[i].value<<endl;for(int i=0;i<m;i++){scanf("%d",&shoot);printf("%d\n",bsearch(shoot));;}}return 0;
}

C题让我收获最大，首先第一遍写的时候忽略了or just leave it alone. 这一句，导致一直wa,后来发现了这点，交上去tle，仔细检查后发现，dfs的时候，存在多余遍历，改了之后又是wa,再仔细检查，发现原来是受最开始的思路影响，初始化的时候有问题，这样才暂时ac，可最后system test的时候我傻眼了，又是tle,最后百思不得其解，发现只剩下一种可能性：记忆化搜索比递推慢，于是赛后又写了发递推才最终ac，才发现递推能比记忆化快这么多，以后还是能递推就递推吧。真是一波三折锕。。。

记忆化 tle代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX 101
using namespace std;int n,m,k,vectors[2][2]={{0,1},{1,0}};
int grid[MAX][MAX],dp[MAX][MAX][MAX];void init(){memset(dp,0,sizeof(dp));dp[n][m][0]=1;if(grid[n][m]<=k)dp[n][m][grid[n][m]]=1;
}void dfs(int a,int b,int c){if(a==n&&b==m){return ;}int x,y;for(int i=0;i<2;i++){x=a+vectors[i][0],y=b+vectors[i][1];if(x>=1&&x<=n&&y>=1&&y<=m){if(dp[x][y][c]==0)dfs(x,y,c);if(dp[x][y][c]==1){dp[a][b][c]=1;goto a;}if(c-grid[a][b]>=0){if(dp[x][y][c-grid[a][b]]==0)dfs(x,y,c-grid[a][b]);if(dp[x][y][c-grid[a][b]]==1){dp[a][b][c]=1;goto a;}}}}
a:{}
}int main(){while(cin>>n>>m>>k){for(int i=1;i<=n;i++){			for(int j=1;j<=m;j++){scanf("%d",&grid[i][j]);}}init();for(int i=k;i>=0;i--){dfs(1,1,i);if(dp[1][1][i]==1){cout<<i<<endl;goto next;		}}
next:{}	}return 0;
}

递推ac代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAX 102
using namespace std;int n,m,k,dp[MAX][MAX][MAX];
int s[MAX][MAX];void init(){memset(dp,0,sizeof(dp));
}int main(){while(scanf("%d %d %d",&n,&m,&k)!=EOF){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)scanf("%d",&s[i][j]);}init();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int t=0;t<=k;t++){dp[i][j][t]=max(dp[i][j-1][t],dp[i-1][j][t]);if(t-s[i][j]>=0)dp[i][j][t]=max(dp[i][j-1][t-s[i][j]]+s[i][j],max(dp[i-1][j][t-s[i][j]]+s[i][j],dp[i][j][t]));}}}int ans=0;for(int i=k;i>=0;i--)ans=max(ans,dp[n][m][i]);printf("%d\n",ans);}return 0;
}

这篇关于BestCoder Round #42的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---