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