题解 | #牛客小白月赛 61 #
补完一套月赛，此图为证
说明
题目链接
赛中我就做出A，B两题，结果后来一直卡E。实际上这套题C、E并不是代码不好写，C就是bfs的板子，E就是推个式子，但是因为细节很多，很容易注意不到。
D、F算是压轴题，难度大概能对标cf div2的D甚至是E吧，远远不是出题人所说的对标cf div2的A~C难度。
D是一个模拟，根本想不到要用队列，就算想到了，也不会想到金币有可能爆long long而不能在这时接着加（和游戏里面差不多）。而且模拟的过程细节结果过多，只能说出题人想防小白AK那真是没办法~
F是双指针+差分，这个题主要是读完题之后很难联想到要用差分这个算法，因为你难以想到这m个约束对应于m个条件。
A 超市里扫货
直接按题意模拟。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int v[maxn];
int main()
{
int n,V;
cin>>n>>V;
for(int i=1;i<=n;i++)cin>>v[i];
long long ans=1,sum=0;
for(int i=1;i<=n;i++){
if(sum+v[i]<=V)sum+=v[i];
else sum=v[i],ans++;
}
cout<<ans<<endl;
return 0;
}
B 柜台结账
仍然是模拟，只是细节有点多。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
bool pd(string s){
bool flag=true;
for(int i=0;i<s.length();i++){
if(s[i]-'0'){
flag=false;
break;
}
}
return flag;
}
int pd5(string s){
int ans;
if(s[0]-'0'==5){
bool flag=true;
for(int i=1;i<s.length();i++){
if(s[i]-'0'){
flag=false;ans=1;break;
}
}
if(flag==true){
ans=3;
}
}
else if(s[0]-'0'>5){
ans=1;
}
else{
ans=2;
}
return ans;
}
int main()
{
string a1,a2;
cin>>a1>>a2;
if(pd5(a2)==1){
cout<<"Happy birthday to MFGG"<<endl;
}
else if(pd5(a2)==2){
if(!pd(a2))cout<<"Happy birthday to YXGG"<<endl;
else cout<<"PLMM"<<endl;
}
else {
if((a1[a1.length()-1]-'0')&1){
cout<<"Happy birthday to MFGG"<<endl;
}
else{
if(!pd(a2))cout<<"Happy birthday to YXGG"<<endl;
else cout<<"PLMM"<<endl;
}
}
return 0;
}
C 小喵觅食
这个题用不了dfs，因为dfs不能直接求出每个点的最短距离。但是bfs可以，因为可以在bfs的每一层利用dp的思想将层数状态转移。
先bfs求每个点以小猫为起点的单源最短路，再bfs求每个点以PLMM为起点的单源最短路，然后凡是满足条件的点都要算一遍最短路之和。注意，千万不能意淫，因为你不是计算机！每个满足约束的点都要算一遍其最短距离。
#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int n,m,r1,r2;
const int maxn=1e3+5;
char s[maxn][maxn];
struct node{
int x,y;
};
queue<node> q;
int cx,cy,px,py;
bool vis[maxn][maxn];
int disc[maxn][maxn],disp[maxn][maxn],dis[maxn][maxn];
void bfs(int sx, int sy){
node now;
now.x=sx;
now.y=sy;
q.push(now);
dis[sx][sy]=0;
vis[sx][sy]=1;
while(!q.empty()){
node next;
now = q.front();
q.pop();
for(int i=0;i<4;i++){
next.x=now.x+dir[i][0];
next.y=now.y+dir[i][1];
if(next.x>=1&&next.y>=1&&next.x<=n&&next.y<=m){
if(s[next.x][next.y]!='*'&&!vis[next.x][next.y]){
vis[next.x][next.y]=1;
dis[next.x][next.y]=dis[now.x][now.y]+1;
q.push(next);
}
}
}
}
}
int main(){
cin>>n>>m;
cin>>r1>>r2;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf(" %c",&s[i][j]);
if(s[i][j]=='P')px=i,py=j;
if(s[i][j]=='M')cx=i,cy=j;
}
}
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
bfs(cx,cy);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)disc[i][j]=dis[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(disc[i][j]==0)disc[i][j]=1e9;
}
}
disc[cx][cy]=0;
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
bfs(px,py);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)disp[i][j]=dis[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(disp[i][j]==0)disp[i][j]=1e9;
}
}
disp[px][py]=0;
int ans=1e9;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(abs(cx-i)+abs(cy-j)<=r2){
if(disp[i][j]<=r1){
ans=min(ans,disp[i][j]+disc[i][j]);
}
}
}
}
if(ans==1e9)ans=-1;
cout<<ans<<endl;
return 0;
}
D 石油大亨
这个代码以我现在一个cf绿名的码力写不出来，估摸着起码得蓝名才能写出这。这个代码是出题人的，但是注释是我自己加的，让我写我写不出来，等我上了蓝名再回来自己写一遍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e5+5;
const ll linf = 0x3f3f3f3f3f3f3f3f;
//即4557430888798830600，4.557×10^18
//long long最大9223372036854775807，9.223×10^18
int n, ec, et, p; ll s;
int t[M];
void work()
{
scanf("%d %d %d %d %lld", &n, &ec, &et, &p, &s);
for (int i = 1; i <= n; ++i) scanf("%d", &t[i]);
if (s < ec) {printf("-1\n");return;}
//如果初始金额小于造一名工程师的金额，就不可能实现
//那么下面的就是一开始的钱至少够造一个工程师
queue<ll> q; //存储工程师占领油田的时间
ll cur_time = 0;//当前时间为0
for (int i = 1, oil_cnt = 0; i <= n; ++i) {//第i个油田，占领油田数一开始为0
ll next_time;//下一次可以开始训练工程师的最小时间点
if(i==1)next_time=0;//如果从第1个油田算起，那就是现在就可以开始训练
else next_time=cur_time+et;//如果不是第一个油田，那就是当前时间点+et秒训练时间
//当前工程师占领油田的时间点，在下一次可以开始训练工程师的最小时间点及以前
while (!q.empty() && q.front() <= next_time) { //计算从当前到next_time的金额收益
//如果金额没爆long long,才接着收钱，否则就不收了，不然爆了没法存
//虽然linf不是long long最大值，但大于这个值再存金币也没有意义
//之所以不设置long long最大值，还是为了大得适当，防止意外溢出
if(s < linf) s += oil_cnt * (q.front() - cur_time) * p;
//当前的油田数乘p金额是一秒的；
//经历的时间是下一名工程师占领油田的时间点-当前工程师占领油田的时间点
//因为在这一段时间油田数是固定的
cur_time = q.front();//更新当前工程师占领油田的时间点
q.pop();//因为已经用了，所以弹出队列
oil_cnt++;//占领的油田数加1，因为更新一次当前时间，就被占领一个油田
}
if (cur_time < next_time) {
//如果当前工程师占领油田的时间点，小于可以训练下一名工程师的最小时间点
if(s < linf) s += oil_cnt * (next_time - cur_time) * p;
//当前的油田数乘p金额是一秒的；
//经历的时间是可以训练下一名工程师的最小时间点-当前工程师占领油田的时间点
cur_time = next_time;//更新当前时间点为可以训练下一名工程师的最小时间点
}
if (s < ec) {
//如果当前金额不足以训练一名工程师
while (!q.empty() && s + oil_cnt * (q.front() - cur_time) * p < ec) {
//如果当前工程师占领油田时，金额不足以训练下一名工程师
s += oil_cnt * (q.front() - cur_time) * p;//先把这段时间的钱加上
cur_time = q.front();//先更新当前时间
q.pop();//当前工程师占领油田的时间点已经用过了，因此弹出队列
oil_cnt++;//占领的油田数加1
}
//金额不足，需要等待
ll wait_time = (ec - s + (ll)oil_cnt * p - 1) / (oil_cnt * p);
//需要等待wait_time的时间
//还需要金额ec-s，
s += oil_cnt * wait_time * p;//加上等待时间内生产的钱
cur_time += wait_time;//更新当前时间
}
s -= ec;//更新当前金额
q.push(cur_time + et + t[i]);//工程师占领油田的时间点等于
//当前时间点+et秒训练时间+工程师去油田的时间
//注意，每次循环结束后才加入队列
//因此最后一次循环的cur_time+et+t[n]就是答案
}
printf("%lld\n", cur_time + et + t[n]);
}
int main()
{
work();
return 0;
}
E 排队
就是分三类，正序数，负序数，零序数。有对称性知正序数和负序数数量相同，那么求出全排列，再减去零序数的数量，最后除2就是逆序数的数量。
零序数的数量用排列组合求。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=1e5+10;
const ll mod=1e9+7;
ll cnt[N],a[N],j[N];
ll js(ll x){
if(x!=0){
return x*(x-1)/2;
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll n;cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
cnt[a[i]]++;
}
ll sum=n*(n-1)/2;
for(int i=0;i<N;i++)
{
sum-=js(cnt[i]);
}
sum%=mod;
for(int i=3;i<=n;i++)
{
sum*=i;
sum%=mod;
}
if(n==1)sum/=2;
cout<<sum<<endl;
return 0;
}
F 选座椅
由于区间连续，所以用双指针控制区间长度，不断尺取。如果长度区间[L,R]满足m个条件，则长度区间[L,R+1]也满足，以此类推。那么就可以看出可以用差分来对一段连续区间进行加操作。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
const int mod=1e9+7;
int n,m;
vector<int> v[maxn];
int cnt[maxn],deta[maxn],fac[maxn];
void add(int id, int &now){
for(auto u:v[id]){
cnt[u]++;
if(cnt[u]==1)now++;
}
}
void del(int id, int &now){
for(auto u:v[id]){
cnt[u]--;
if(cnt[u]==0)now--;
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=3;i++){
for(int j=1;j<=m;j++){
int u;
cin>>u;
v[u].push_back(j);
}
}
int now=0;
memset(deta,0,sizeof(deta));
for(int i=1,j=1;i<=n;i++){
while(j<=n&&now<m)add(j,now),j++;
//j多加1是为了下一次add
if(now==m){
int L=(j-1)-i+1;
int R=n-i+1;
deta[L]++;
deta[R+1]--;
}
del(i,now);
if(i==j)j++;
}
fac[0]=fac[1]=1;
for(int i=2;i<=n;i++){
fac[i]=fac[i-1]*i%mod;
}
for(int i=1;i<=n;i++){
deta[i]=deta[i]+deta[i-1]%mod;
cout<<deta[i]*fac[i]%mod<<" ";
}
return 0;
}
小结
这套题难度比牛客小白月赛1难了不少，很多结论如果不熟练那就直接无了。但是多学多练，总有一天我终将成为你。
投递中国石化等公司10个岗位 >
Momenta公司福利 286人发布