牛客小白月赛99（A~F）

本文主要是介绍牛客小白月赛99（A~F），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客小白月赛99

写在前面

这次的小白月赛题目出的挺好，很多算法知识都有涉及到，E题这种题型我还是第一次遇到，也是学到了一些有用的算法知识

A 材料打印

思路

签到题，考虑2种情况：

• 彩印比黑白更便宜，全部印彩印
• 黑白比彩印更便宜，黑白和彩印都选

code

void solve(){int a,b,c,d;cin >> a >> b >> c >> d;if(c>=d){cout << (a+b)*d << endl;return ;}cout << a*c+b*d << endl;return ;
}

B %%%

思路

观察样例不难发现，每次都取自身的一半
在操作过程中，若n可以被2整除，我们需要将n除以2后在减去1，反之，直接除以2即可

code

void solve(){int n;cin >> n;int cnt=0;while(n){if(n%2==0){n/=2;n--;} else n/=2;cnt++;}cout << cnt << endl;return ;
}

C 迷宫

思路

考点：搜索

这道题需要用到2次搜索（bfs或者dfs都行）

先从终点进行搜索，搜索上下左右四个方向，搜索到当前坐标为 ‘#’ ,则将这个坐标的行和列都进行标记(正向搜索需要用到)

然后我们再从起点进行搜索，每次都在 ‘.’ 的坐标进行搜索，如果当前行或者列被标记过，则说明可以用激光将这一行或者一列都清除掉，直接输出YES

如果搜索结束还未找到终点以及被标记的行或者列，那就输出NO

code

const int N=1e3+5;
int v[N][N],fx[N],fy[N];
char a[N][N];
int sx,sy,ex,ey;
int n,m,flag=0;
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
struct node{int x,y;
};
void bfs1(int x,int y){queue<node> q;q.push({x,y});v[x][y]=1;while(!q.empty()){int x=q.front().x,y=q.front().y;q.pop();if(a[x][y]=='S'){flag=1;return ;}for(int i=0;i<=3;++i){int tx=x+dx[i];int ty=y+dy[i];if(tx<1||ty<1||tx>n||ty>m) continue;if(a[tx][ty]=='#') fx[tx]=1,fy[ty]=1;if(a[tx][ty]=='#' || v[tx][ty]) continue;v[tx][ty]=1;q.push({tx,ty});}}
}
void bfs2(int x,int y){memset(v,0,sizeof v);queue<node> q;q.push({x,y});v[x][y]=1;while(!q.empty()){int x=q.front().x,y=q.front().y;q.pop();if(fx[x] || fy[y]){cout << "YES" << endl;exit(0);}for(int i=0;i<=3;++i){int tx=x+dx[i];int ty=y+dy[i];if(tx<1||ty<1||tx>n||ty>m) continue;if(a[tx][ty]=='#' || v[tx][ty]) continue;v[tx][ty]=1;q.push({tx,ty});}}
}
void solve(){cin >> n >> m;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){cin >> a[i][j];if(a[i][j]=='S') sx=i,sy=j;if(a[i][j]=='E') ex=i,ey=j;}bfs1(ex,ey);if(flag){cout << "YES" << endl;return ;}bfs2(sx,sy);cout << "NO" << endl;return ;
}

D 又是一年毕业季

思路

思维题，我们选择的拍照时间的因子中不能存在是某个人眨眼睛的时间
很显然我们就会想到素数，我们只需要找个最小的没有出现过的素数

由于n的范围在2e5，显然我们可以进行暴搜
先用筛法将素数找出来，接着遍历2e5+1个素数，找最小的没有出现过的素数就行了

code

const int N=1e7+5;
int prime[N],v[N];
void ola(){memset(v,true,sizeof v);v[1]=v[0]=false;int k=0;for(int i=2;i<=N;++i){if(v[i]){prime[++k]=i;}for(int j=1;prime[j]*i<=N;++j){v[prime[j]*i]=false;if(i%prime[j]==0) break; }}
}
void solve(){int n;cin >> n;map<int,int> m;for(int i=1;i<=n;++i){int x;cin >> x;m[x]=1;}for(int i=1;i<=2e5+1;++i){if(!m[prime[i]]){cout << prime[i] << endl;break;}}return ;
}

E 多米诺骨牌

思路

考点：区间合并(贪心)

区间合并的板子题，将这些骨牌按左边界，然后遍历这些骨牌，每次遍历都让计数器k++
如果上一个骨牌的右边界大于等于当前骨牌的左边界，则更新当前右边界为max(当前骨牌的右边界,原右边界)
反之，将计数器k存入数组里面，更新左边界为当前左边界，更新右边界为当前骨牌的右边界，k清零
最后将最后一个合并的骨牌存入到数组里

将数组进行降序排序，如果m大于等于数组的长度，直接输出n
反之，输出0~m-1 下标的数组总和

code

const int N=1e6+5;
vector<PII> a;
vector<int> res;
int n,m;
void merge(){sort(a.begin(),a.end());int k=0;int st=-2e9,ed=-2e9;for(auto u : a){k++;if(ed<u.fi){if(st!=-2e9) res.push_back(k);st=u.fi,ed=u.se;k=0;}else ed=max(ed,u.se);}if(st!=-2e9) res.push_back(k+1);
}
void solve(){cin >> n >> m;a.resize(n);res.clear();for(int i=0;i<n;++i){int x;cin >> x;a[i].se=x;} for(int i=0;i<n;++i){int x;cin >> x;a[i].fi=x;a[i].se+=a[i].fi;}merge();sort(res.begin(),res.end(),greater<int>());if(m>=res.size()){cout << n << endl;} else{int ans=0;for(int i=0;i<m;++i){ans+=res[i];}cout << ans << endl;}return ;
}

F 自爆机器人

思路

考点：背包DP

这题其实不难，难点在于如何将来回走动的时间抽象为完全背包的问题

先考虑无解的情况，如果 $n>t$ ,自然答案就为0
那么其他情况都是有解的，这个机器人最少也能对怪物造成n点伤害
那么剩下 $t-n$ 的时间该怎么算呢，我们在回头细看题目
这个机器人能在任意两堵墙之间来回走动，实际上我们只要让他在相邻的两堵墙之间来回走动即可

举个栗子：3 4 8
这个机器人可以选择在3 4进行移动，我们需要考虑来回，那么它所消耗的时间就为2*（4-3）=2
同理，我们也可以选择在3 8进行移动，它消耗的时间为2*5=10
但是我们选择3 8进行移动和3 4 + 4 8 进行移动所消耗的时间是相同的，因此我们只需要考虑相邻的两堵墙即可

由于它可以无限次进行移动，不难想到完全背包，来回移动消耗的时间既是重量也是价值
开一个f数组存它的价值，它的上限就为 $t-n$ ，我们只需要考虑 $f[t-n]$ 的最大价值即可

最后输出 $n+f[t-n]$

code

const int N=2e5+5;
int a[N],f[N];
void solve(){set<int> s;int n,m,t;cin >> n >> m >> t;for(int i=1;i<=m;++i) cin >> a[i];if(n>t){cout << 0 << endl;return ;}sort(a+1,a+1+m);int ans=t-n;for(int i=1;i<=ans;++i) f[i]=0;for(int i=1;i<m;++i){s.insert(2*(a[i+1]-a[i]));}for(auto x : s)for(int j=x;j<=ans;++j){f[j]=max(f[j],f[j-x]+x);}cout << n+f[ans] << endl;return ;
}

这篇关于牛客小白月赛99（A~F）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---