牛客小白月赛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 超市里扫货

直接按题意模拟。

#includeusing 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<
B 柜台结账

仍然是模拟,只是细节有点多。

#includeusing namespace std;
const int maxn = 1e5 + 5;
bool pd(string s){bool flag=true;
    for(int i=0;iif(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;iif(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"<if(!pd(a2))cout<<"Happy birthday to YXGG"<if((a1[a1.length()-1]-'0')&1){cout<<"Happy birthday to MFGG"<if(!pd(a2))cout<<"Happy birthday to YXGG"<
C 小喵觅食

这个题用不了dfs,因为dfs不能直接求出每个点的最短距离。但是bfs可以,因为可以在bfs的每一层利用dp的思想将层数状态转移。

先bfs求每个点以小猫为起点的单源最短路,再bfs求每个点以PLMM为起点的单源最短路,然后凡是满足条件的点都要算一遍最短路之和。注意,千万不能意淫,因为你不是计算机!每个满足约束的点都要算一遍其最短距离。

#includeusing 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;
};
queueq;
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<
D 石油大亨

这个代码以我现在一个cf绿名的码力写不出来,估摸着起码得蓝名才能写出这。这个代码是出题人的,但是注释是我自己加的,让我写我写不出来,等我上了蓝名再回来自己写一遍。

#includeusing 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;}
	//如果初始金额小于造一名工程师的金额,就不可能实现
	//那么下面的就是一开始的钱至少够造一个工程师
	queueq; //存储工程师占领油田的时间
	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就是逆序数的数量。

零序数的数量用排列组合求。

#includeusing 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;icin>>a[i];
		cnt[a[i]]++;
	}
	ll sum=n*(n-1)/2;
	for(int i=0;isum-=js(cnt[i]);
	}
	sum%=mod;
	for(int i=3;i<=n;i++)
	{sum*=i;
		sum%=mod;
	}
	if(n==1)sum/=2;
	cout<
F 选座椅

由于区间连续,所以用双指针控制区间长度,不断尺取。如果长度区间[L,R]满足m个条件,则长度区间[L,R+1]也满足,以此类推。那么就可以看出可以用差分来对一段连续区间进行加操作。

#includeusing namespace std;
#define int long long
const int maxn=1e5+5;
const int mod=1e9+7;
int n,m;
vectorv[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&&nowint 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<
小结

这套题难度比牛客小白月赛1难了不少,很多结论如果不熟练那就直接无了。但是多学多练,总有一天我终将成为你。
终将成为你

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享名称:牛客小白月赛61题解-创新互联
分享路径:http://scyanting.com/article/joocd.html