牛客小白月赛28题解
A:牛牛和牛可乐的赌约
简单题，我们还是正难则反，概率减一下全赢的概率就可以了。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int P=1e9+7;
LL qpow(LL x,LL y){LL res=1;for(;y;y>>=1,x=x*x%P)if(y&1)res=res*x%P;return res;}
int main(){
int T;scanf("%d",&T);
while(T--){
int n,m;scanf("%d%d",&n,&m);
printf("%d\n",(P+1-qpow(qpow(n,P-2),m))%P);
}
return 0;
}B:牛牛和牛可乐的赌约2
我们可以写一个对抗搜索的dp，然后打一个表就可以发现规律，所以说呢，这道题也算是一个结论题，我们只需要判断他们的余数是否相同就可以。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
int T;scanf("%d",&T);
while(T--){
int n,m;scanf("%d%d",&n,&m);
puts((n%3-m%3+3)%3==0?"awsl":"yyds");
}
return 0;
}
C:单词记忆方法
一道模拟题，我们只需要观察串出现的方式，然后我们用个递归不断往下算就可以了。
这题不递归应该要用手工栈类似的方法写，可能会比较麻烦，还是建议大家用递归写吧！
注意要开long long
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
char str[N];int n,st[N],tp,R[N];
LL calc(int l,int r){
LL res=0;
for(int i=l,j;i<=r;i++){
LL x,num;
if(str[i]=='('){
x=calc(i+1,R[i]-1);i=R[i];
if(i+1<=n&&isdigit(str[i+1])){
num=0;j=i+1;
while(j<=n&&isdigit(str[j]))num=num*10+str[j]-'0',j++;
i=j-1;
}else num=1;
}else{
x=str[i]-'A'+1;
if(i+1<=n&&isdigit(str[i+1])){
num=0;j=i+1;
while(j<=n&&isdigit(str[j]))num=num*10+str[j]-'0',j++;
i=j-1;
}else num=1;
}
res+=x*num;
}
return res;
}
int main(){
scanf("%s",str+1);n=strlen(str+1);
for(int i=1,x;i<=n;i++)if(str[i]=='(')st[++tp]=i;else if(str[i]==')')x=st[tp],R[x]=i,tp--;
printf("%lld\n",calc(1,n));
return 0;
}D:位运算之谜
考虑进位之间的关系，我们发现满足条件的情况就是相减以后满足条件的。
还有一种你也可以和B题一样写个暴力然后打表找找规律，两种方法都可以。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
int T;scanf("%d",&T);
while(T--){
LL x,y;scanf("%lld%lld",&x,&y);
if(x<(y<<1)||(((x-y)&y)!=y))puts("-1");else printf("%lld\n",y^(x-y));
}
return 0;
}E:会当凌绝顶，一览众山小
一道很裸的数据结构题，码完就ac了
发现操作都是单点修改，然后麻烦的就是我们如何找到那个修改的点，这需要我们二分然后在线段树上查最值。
然后我们在每个节点上维护一个当前max和min，以及max和min出现的位置。
剩下的我们就需要二分，这题主要还是有很多码的细节需要大家注意，边界情况一定要小心。
代码：
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+5,Inf=2e9;
struct node{int x,h;}a[N];
int n,b[N],p[N],h[N],len;
void chkmi(pii &x,pii y){if(y.first<x.first)x=y;}
void chkma(pii &x,pii y){if(y.first>x.first)x=y;}
namespace seg{
pii mi[N<<2],ma[N<<2];
void update(int rt){
if(mi[rt<<1].first<=mi[rt<<1|1].first)mi[rt]=mi[rt<<1];else mi[rt]=mi[rt<<1|1];
if(ma[rt<<1].first>=ma[rt<<1|1].first)ma[rt]=ma[rt<<1];else ma[rt]=ma[rt<<1|1];
}
void build(int rt,int l,int r){
if(l==r){mi[rt]=ma[rt]=pii(h[l],l);return;}
int mid=(l+r)>>1;
build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
update(rt);
}
void change(int rt,int l,int r,int x){
if(l==r){mi[rt]=ma[rt]=pii(h[x],x);return;}
int mid=(l+r)>>1;
(x<=mid)?change(rt<<1,l,mid,x):change(rt<<1|1,mid+1,r,x);
update(rt);
}
pii askmi(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R)return mi[rt];
int mid=(l+r)>>1;pii res=pii(Inf,Inf);
if(L<=mid)chkmi(res,askmi(rt<<1,l,mid,L,R));
if(R>mid)chkmi(res,askmi(rt<<1|1,mid+1,r,L,R));
return res;
}
pii askma(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R)return ma[rt];
int mid=(l+r)>>1;pii res=pii(-Inf,-Inf);
if(L<=mid)chkma(res,askma(rt<<1,l,mid,L,R));
if(R>mid)chkma(res,askma(rt<<1|1,mid+1,r,L,R));
return res;
}
}
void change(int x){
if(x==1)return;
if(h[x-1]>h[x]){h[x-1]=h[x];seg::change(1,1,n,x-1);return;}
int now=x-1;
for(int i=20,t;~i;i--){
t=now-(1<<i);
if(t>=1&&seg::askma(1,1,n,t,x-1).first<=h[x])now=t;
}
if(now>1)h[now-1]=h[x],seg::change(1,1,n,now-1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].h),b[++len]=a[i].x;
sort(b+1,b+len+1);len=unique(b+1,b+len+1)-b-1;
for(int i=1;i<=n;i++)p[i]=lower_bound(b+1,b+len+1,a[i].x)-b,h[p[i]]=a[i].h;
seg::build(1,1,n);
for(int i=1,x,pos,rma;i<=n;i++){
x=p[i];change(x);
if(x==n)continue;
rma=seg::askma(1,1,n,x+1,n).first;
if(rma>h[x])continue;
pos=seg::askmi(1,1,n,x+1,n).second;
h[pos]=h[x];seg::change(1,1,n,pos);
}
for(int i=1;i<=n;i++)printf("%d%c",h[p[i]]," \n"[i==n]);
return 0;
}
F:牛牛的健身运动
容易发现题目要求我们求的东西是一个凸壳，我们对于凸壳的题目可以使用三分算法找到那个我们要求的点。
然后我们在三分的内部求一个最小值和次小值就可以。
注意这题的数剧范围有很大的迷惑性。n可以出到100000以上的。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+5;
const LL Inf=2e18;
struct node{int x,y;}a[N];
int n,m;LL val[N],mi,mi2,ans=-Inf;
LL calc(int x){
for(int i=1;i<=n;i++)val[i]=(LL)a[i].x*x+a[i].y;
LL mi=Inf,mi2=Inf;
for(int i=1;i<=n;i++)if(val[i]<mi)mi2=mi,mi=val[i];else if(val[i]<mi2)mi2=val[i];
return mi+mi2;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
int l=1,r=m;
while(l+50<r){
int mid=l+(r-l)/3,mid2=r-(r-l)/3;
if(calc(mid)<calc(mid2))l=mid;else r=mid2;
}
for(int i=l;i<=r;i++)ans=max(ans,calc(i));
printf("%lld\n",ans);
return 0;
}G:牛牛和字符串的日常
要求O(n)求匹配的问题，通常和kmp和exkmp有关，这题显然是一个和next数组有关的。
我们求出母串的nxt数组，然后对于接下来的每个串都不断匹配，然后对于匹配到的位置取个max。
注意也可以用其他带log的字符串算法维护，但是这题带log可能不太能通过，所以作者写的是kmp。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m,nxt[N],ans;char str[N],s[N];
int main(){
scanf("%s",str+1);n=strlen(str+1);
for(int i=2,j=0;i<=n;i++){
while(j&&str[i]!=str[j+1])j=nxt[j];
if(str[i]==str[j+1])j++;
nxt[i]=j;
}
int T;scanf("%d",&T);
while(T--){
scanf("%s",s+1);m=strlen(s+1);
int res=0;
for(int i=1,j=0;i<=m;i++){
while(j&&s[i]!=str[j+1])j=nxt[j];
if(s[i]==str[j+1])j++;
res=max(res,j);
}
ans+=res;
}
printf("%d\n",ans);
return 0;
}
H:上学要迟到了
建图的思路比较清晰，我们相邻的两站彼此连边，相同的公交站之间单项连边，然后跑一个dij。
代码：
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=1e5+5,Inf=2e9;
int n,m,s,t,T,a[N],b[N],lst[N],dis[N];bool vis[N];
vector<pii>adj[N];
priority_queue<pii>q;
void adde(int u,int v,int w){adj[u].pb(pii(v,w));}
int main(){
scanf("%d%d%d%d%d",&n,&m,&s,&t,&T);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=n;i;i--){
if(lst[a[i]])adde(i,lst[a[i]],b[a[i]]);
lst[a[i]]=i;
}
for(int i=1;i<n;i++)adde(i,i+1,T),adde(i+1,i,T);
for(int i=1;i<=n;i++)dis[i]=Inf;
q.push(pii(0,s));dis[s]=0;
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u])continue;vis[u]=true;
for(auto edg:adj[u]){
int v=edg.first,w=edg.second;
if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,q.push(pii(-dis[v],v));
}
}
printf("%d\n",dis[t]);
return 0;
}
I:迷宫
好像因为是bool数组，我们暴力dp的数组都开的下，但是作者考试的时候写了个滚动数组，然后这样的空间就会变成O(np)的级别的，p代表的是模数。
因为我们考虑滚动数组中我们把步数滚动，因为同一步数的最多只有O(n)级别的，我们类似于利用bfs的思想，对于一步内的所有点考虑完再接着考虑，可以成功压缩空间。
注意：这个按步数的思想是解决许多网格图的关键套路，可以简化空间。
代码：
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=105,P=1e4+7;
int n,m,a[N][N],id[N][N],ans;bool dp[2][N<<1][P];
vector<pii>v[N<<1];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]),a[i][j]%=P,v[i+j].pb(pii(i,j)),id[i][j]=v[i+j].size()-1;
dp[0][0][a[1][1]]=true;
for(int i=3,now,lst;i<=n+m;i++){
now=i&1;lst=now^1;
for(auto t:v[i]){
int x=t.first,y=t.second;
for(int md=0;md<P;md++){
if(x>1)dp[now][id[x][y]][(md+a[x][y])%P]|=dp[lst][id[x-1][y]][md];
if(y>1)dp[now][id[x][y]][(md+a[x][y])%P]|=dp[lst][id[x][y-1]][md];
}
}
memset(dp[lst],false,sizeof(dp[lst]));
}
for(int i=0;i<P;i++)if(dp[(n+m)&1][id[n][m]][i])ans++;
printf("%d\n",ans);
return 0;
}J:树上行走
相同类型的点之间可以随便走，我们把相邻的并且类型相同的连接，会有很多连通快，我们对于所有的连通块的大小取个max就是答案！用并查集维护即可。
代码：
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+5;
int n,fa[N],siz[N],type[N],ma;vector<int>Ans;
int find(int u){return fa[u]==u?u:fa[u]=find(fa[u]);}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&type[i]),fa[i]=i,siz[i]=1;
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
if(type[u]!=type[v])continue;
if(find(u)!=find(v))siz[fa[v]]+=siz[fa[u]],fa[fa[u]]=fa[v];
}
for(int i=1;i<=n;i++)ma=max(ma,siz[i]);
for(int i=1;i<=n;i++)if(siz[find(i)]==ma)Ans.pb(i);
printf("%d\n",(int)Ans.size());
for(auto x:Ans)printf("%d ",x);puts("");
return 0;
}
查看24道真题和解析
