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; }