牛客算法入门课练习赛2题解
A.古老的牛市，遗迹的天梯
题目描述
牛市，一个拥有悠久历史的城市，2333年考古学家在牛市发现了一个神秘的遗迹，这些勇敢而智慧的古队员准备进入这个遗迹，但要进入这个遗迹就需要通过一段天梯。而登上天梯必须要按照它要求的方法，否则就无法登上。它要求的方法为：
可以直接登上比当前位置高1个单位高度的天梯。
可以从当前阶梯往下退一级天梯（第一级天梯除外）。
在连续退k步后，跳跃一次，跳跃的高度不超过2^k。比如说你现在位于第i级天梯，且之前从第i+k级天梯退下来，此时你可以跳到高度不超过(当前高度+ 2^k)的任何一级天梯。每一次跳跃只算一次移动哦！
开始的时候考古小队在第一级天梯。请你计算出最少的移动步数以登上最高一级天梯。
为何考古搞得跟游戏历险一样？牛市一定是一个魔性的城市！
输入描述:
第1行：一个整数N，表示天梯级数。
第2行：N个整数，依次为每层天梯梯的高度，保证递增。
题解
设f[i]为到达第i个阶梯所需要的最少步数，可以从一下状态转移来：
第一个方程就是直接跳，第二个中的j表示从第j的阶梯跳到第i个阶梯，k表示从j后退k步，按照题意来就行了
时间复杂度为O(n^3)，是可以通
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define iter set<int>::iterator
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5+5;
const ll mod = 1e18+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};
ll qpow(ll x,ll y){
ll ans=1,t=x;
while(y>0){
if(y&1)ans*=t,ans%=mod;
t*=t,t%=mod;
y>>=1;
}
return ans%mod;
}
int a[201],dp[201];
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
memset(dp,INF,sizeof(dp));
dp[1]=0;
for(int i=1;i<=n;i++){
for(int j=i-1;j>0;j--){
for(int k=j;k>0;k--){
int x=j-k;
if(qpow(2,x)+a[k]>=a[i])dp[i]=min(dp[i],dp[j]+x+1);
}
}
}
if(dp[n]==INF)dp[n]=-1;
cout<<dp[n];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
//int t;cin>>t;
//while(t--)solve(),cout<<'\n';
solve();
return 0;
}B.几乎毁灭牛市的流星雨
题解
看起来是dp，其实就是模拟一下，每一次向四周走一步，看看能不能到达安全区（bfs），到达就输出答案，如果走不动了，就是不可能了，棋盘范围设置305就好
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const int N = 5e4+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[8][2]={-1,0,1,0,0,-1,0,1,1,1,1,-1,-1,1,-1,-1};
ll qpow(ll x,ll y){
ll ans=1,t=x;
while(y>0){
if(y&1)ans*=t,ans%=mod;
t*=t,t%=mod;
y>>=1;
}
return ans%mod;
}
struct node{
int x,y,t;
}a[N];
bool cmp(node x,node y){return x.t<y.t;};
int dp[305][305],v[305][305];
int cnt=1;
void solve(){
int m;cin>>m;
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=m;i++){
cin>>a[i].x>>a[i].y>>a[i].t;
v[a[i].x][a[i].y]=1;
for(int j=0;j<4;j++){
int x=a[i].x+dir[j][0];
int y=a[i].y+dir[j][1];
if(x>-1&&x<305&&y>-1&&y<305)v[x][y]=1;
}
}
sort(a+1,a+1+m,cmp);
for(int i=0;i<=1005;i++){
while(cnt<=m&&i==a[cnt].t){
dp[a[cnt].x][a[cnt].y]=INF;
for(int j=0;j<4;j++){
int x=a[cnt].x+dir[j][0];
int y=a[cnt].y+dir[j][1];
if(x>-1&&x<305&&y>-1&&y<305)dp[x][y]=INF;
}
cnt++;
}
vector<pii>vv;
for(int j=0;j<305;j++){
for(int k=0;k<305;k++){
if(dp[j][k]!=INF&&dp[j][k]!=-1){
if(!v[j][k]){cout<<dp[j][k];return;}
else vv.push_back(pii(j,k));
}
}
}
if(vv.size()==0){cout<<-1;return;}
for(auto jj:vv){
int j=jj.fi,k=jj.se;
for(int ii=0;ii<4;ii++){
int x=j+dir[ii][0];
int y=k+dir[ii][1];
if(x>-1&&x<305&&y>-1&&y<305&&dp[x][y]==-1)dp[x][y]=i+1;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
//int t;cin>>t;
//while(t--)solve(),cout<<endl;
solve();
return 0;
}
C.迁徙过程中的河流
题目描述
牛市的幸存的先民在流星雨之后就忍痛离开了这片土地，选择迁徙，在迁徙的途中，他们需要渡过一条河。因为牛市的树木在流星雨中被严重破坏，所以他们只造出了一艘小船，船太小了，一次只能乘坐两人。
牛市的先民们每个人划船的速度都不尽相同，所以每个人都有一个渡河时间T，为了保证船的平衡，当穿上有两个人的时候，需要他们按照慢的那个人的速度划船，也就是说船到达对岸的时间等于船上渡河时间长的那个人的时间。
现在已知N个人的渡河时间T，请问最少要花费多少时间，才能使所有人都过河。
输入描述
输入文件第一行为先民的人数N(N≤100000)，以下有N行，每行一个整数为每个人的渡河时间。
题解
过河就两种方法
假设有4个人过河（T1<T2<T3<T4）
1.让用时最短的T1来回渡船，总时间为T2+T1+T3+T1+T2
2.1和2过河，1回来，3和4过河，2回来，1和2过河
用时T2+T1+T4+T2+T1
每次根据时间决定过河方法就好
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[8][2]={-1,0,1,0,0,-1,0,1,1,1,1,-1,-1,1,-1,-1};
ll qpow(ll x,ll y){
ll ans=1,t=x;
while(y>0){
if(y&1)ans*=t,ans%=mod;
t*=t,t%=mod;
y>>=1;
}
return ans%mod;
}
int n,t[N],ans;
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>t[i];
sort(t+1,t+n+1);
while(n>=4){
if(t[1]+t[n-1]>2*t[2])
ans+=2*t[2]+t[1]+t[n];
else
ans+=2*t[1]+t[n]+t[n-1];
n-=2;
}
if(n==3)ans+=t[1]+t[2]+t[3];
if(n==2)ans+=t[2];
if(n==1)ans+=t[1];
cout<<ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
//int t;cin>>t;
//while(t--)solve(),cout<<endl;
solve();
return 0;
}
E.牛牛的旅游纪念品
题目描述
牛牛在牛市的旅游纪念商店里面挑花了眼，于是简单粗暴的牛牛决定——买最受欢迎的就好了。
但是牛牛的背包有限，他只能在商店的n个物品里面带m个回去，不然就装不下了。
并且牛牛希望买到的纪念品不要太相似，所以导购小姐姐帮助牛牛把纪念品全部排成了一行，牛牛只需要让选出来要买的m个物品中任意两个的位置差都大于等于k就行了。
现在告诉你这n个物品排成一行之后的受欢迎程度（可能是负数），求牛牛带回去的m个物品的最大欢迎度之和。
输入描述:
第一行三个数n,m,k
接下来一行,有n个整数,是n个物品按顺序的受欢迎程度。
题解
设dp[i][j]表示前 i 个数中取 j 个数所能得到的最大值
那么就可以得dp方程
如果i-k>0,那么 就是取或不取
如果j==1,那么
初始全部-INF
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[8][2]={-1,0,1,0,0,-1,0,1,1,1,1,-1,-1,1,-1,-1};
ll qpow(ll x,ll y){
ll ans=1,t=x;
while(y>0){
if(y&1)ans*=t,ans%=mod;
t*=t,t%=mod;
y>>=1;
}
return ans%mod;
}
int dp[10001][101],a[10001];
void solve(){
memset(dp,-INF,sizeof(dp));
int n,m,k;cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>a[i];
dp[0][0]=0;
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
dp[i][j]=dp[i-1][j];
if(j==1)dp[i][j]=max(dp[i][j],a[i]);
if(i-k>=0)dp[i][j]=max(dp[i][j],dp[i-k][j-1]+a[i]);
}
}
cout<<dp[n][m];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
//int t;cin>>t;
//while(t--)solve(),cout<<endl;
solve();
return 0;
}
开发本科够了，早准备早投递
投递牛客等公司10个岗位 >
