牛客算法周周练8 题解

今天状态不好啊，净是犯小错误qwq

A.小A买彩票

一道签到题。

注意到，概率=不亏的方案数/总方案数

而，总方案数= $4^n$ (每次从1,2,3,4中选一个，选n次)

那么，我们只需要计算的就是不亏的方案数了。

我们注意到，n很小，而且，最多可以获得的也才 $4*n$ 元(先不考虑支付的 $3*n$ 元)

那么，这个明显可以使用dp统计方案数。

我们设dp[i][j]，表示前i次抽奖中，不考虑支付的3*i元的情况下，获得j元的方案数。

那么我们只需要分当前中的是1元,2元,3元,4元四个情况考虑转移即可。

最后，我们直接统计获得的钱数不小于3*n的方案数之和即可。

复杂度: $O(n^2)$

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[31][121];
signed main(){
    int n;
    scanf("%lld",&n);
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=i;j<=i*4;++j){
            for(int k=1;k<=4;++k){
                if(j<k)break;
                dp[i][j]+=dp[i-1][j-k];
            }
        }
    }
    int tot=0;
    for(int i=3*n;i<=4*n;++i){
        tot+=dp[n][i];
    }
    int sum=pow(4,n);
    int D=__gcd(tot,sum);
    tot/=D,sum/=D;
    printf("%lld/%lld",tot,sum);
    return 0;
}

B.「金」点石成金

看到n这么小，而且每次的状态也就两种。。。直接爆搜即可。

需要注意的是，做减法的时候记得把差和0取最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=16;
#define int long long
int a[N],b[N],c[N],d[N],ans,n;
inline int max(int x,int y){
    return x>y?x:y;
}
inline void dfs(int now,int l,int r){
    if(now==n+1){
        ans=max(ans,l*r);
        return;
    }
    dfs(now+1,l+c[now],max(0,r-d[now]));
    dfs(now+1,max(0,l-b[now]),r+a[now]);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld%lld%lld",&a[i],&b[i],&c[i],&d[i]);
    }
    dfs(1,0,0);
    printf("%lld",ans);
    return 0;
}

C.小阳的贝壳

这是个挺套路的题目，他的第二个询问其实就已经提醒你怎么做了。

我们用一颗线段树维护一个差分数组即可。

对于区间修改，我们直接改成做差分数组的两次单点修改即可

对于询问差的最大值，我们直接找到区间最大值即可

至于询问gcd，我们先求出现在第l个数的真实的值(做个前缀和就行了)，然后和l+1-r的差分数组的gcd取gcd即可。

为啥正确呢？

因为，有如下定理:

$1.gcd(x,y)=gcd(x-y,y)$ [这个大家在学辗转相除或更相减损的应该都接触过]

$2.gcd(a_l....a_r)=gcd(gcd(a_l...a_{x}),gcd(a_{y}...a_r))(其中l<=x,y<=r并且[l,x]∪[y,r]=[l,r])$ (这个和最值的有点相似,这个的证法很多，个人推荐用分解质因数然后转化成区间最值的形式证明)

由第二个定理，我们不难得出:

$gcd(a_l...a_r)=gcd(a_l,a_l...a_{r-1},a_{r-1},a_r)=gcd(a_l,gcd(a_l,a_{l+1})...gcd(a_{r-1},a_r))$

然后由第一个定理，我们不难得出:

$gcd(a_l,gcd(a_l,a_{l+1})...gcd(a_{r-1},a_r))=gcd(a_l,(a_{l+1}-a_l)...(a_r-a_{r-1}))=gcd(a_l,b_{l+1}...b_r)$

于是，我们直接求出这个东西就行了。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
struct node{
    int w,g,s;
}t[N<<2];
int a[N];
inline int my_max(int x,int y){//绝对值最值
    return abs(x)>abs(y)?x:y;
}
inline void build(int now,int l,int r){
    if(l==r){
        t[now].w=t[now].g=t[now].s=(a[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(now<<1,l,mid),build(now<<1|1,mid+1,r);
    t[now].w=my_max(t[now<<1].w,t[now<<1|1].w);
    t[now].g=__gcd(t[now<<1].g,t[now<<1|1].g);
    t[now].s=t[now<<1].s+t[now<<1|1].s;
}
inline void insert(int now,int l,int r,int x,int y){
    if(l==r){
        t[now].w=t[now].g=t[now].s=(t[now].w+y);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        insert(now<<1,l,mid,x,y);
    }else{
        insert(now<<1|1,mid+1,r,x,y);
    }
    t[now].w=my_max(t[now<<1].w,t[now<<1|1].w);
    t[now].g=__gcd(t[now<<1].g,t[now<<1|1].g);
    t[now].s=t[now<<1].s+t[now<<1|1].s;
}
inline int find1(int now,int l,int r,int lc,int rc){//区间绝对值最值
    if(lc<=l&&r<=rc){
        return t[now].w;
    }
    int mid=(l+r)>>1,res=0;
    if(lc<=mid){
        res=my_max(res,find1(now<<1,l,mid,lc,rc));
    }
    if(rc>mid){
        res=my_max(res,find1(now<<1|1,mid+1,r,lc,rc));
    }
    return res;
}
inline int find2(int now,int l,int r,int lc,int rc){//区间gcd
    if(lc<=l&&r<=rc){
        return t[now].g;
    }
    int mid=(l+r)>>1,res=0;
    if(lc<=mid){
        res=__gcd(res,find2(now<<1,l,mid,lc,rc));
    }
    if(rc>mid){
        res=__gcd(res,find2(now<<1|1,mid+1,r,lc,rc));
    }
    return res;
}
inline int find3(int now,int l,int r,int lc,int rc){//区间和
    if(lc<=l&&r<=rc){
        return t[now].s;
    }
    int mid=(l+r)>>1,res=0;
    if(lc<=mid){
        res=(res+find3(now<<1,l,mid,lc,rc));
    }
    if(rc>mid){
        res=(res+find3(now<<1|1,mid+1,r,lc,rc));
    }
    return res;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=n;i;--i){
        a[i]-=a[i-1];
    }
    build(1,1,n);
    while(m--){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1){
            int x;
            scanf("%d",&x);
            insert(1,1,n,l,x);
            if(r<n){
                insert(1,1,n,r+1,-x);
            }
        }else if(opt==2){
            if(l==r){
                puts("0");
                continue;
            }
            printf("%d\n",abs(find1(1,1,n,l+1,r)));
        }else{
            if(l==r){
                printf("%d\n",find3(1,1,n,1,l));
            }else{
                printf("%d\n",abs(__gcd(find3(1,1,n,1,l),find2(1,1,n,l+1,r))));
            }
        }
    }
    return 0;
}

D.Forsaken喜欢字符串

读完题，我们发现，询问其实就是求，其余的字符串中，和当前字符串中所有长度为len的子串的匹配个数之和再乘len

注意到，n,q很大，所以我们肯定不能直接比较。

但是，我们发现k非常小。

于是，我们对所有的串求出他的所有子串，然后用一个map每个字符串的出现次数。

这样，在询问的时候，我们把第x个字符串的所有长度为y的子串处理出来，然后直接查询当前子串在map的出现次数就行了。

但是，因为子串不能和同一个字符串的子串匹配，所以，我们还要算出当前子串在第x个字符串的出现次数，然后答案减去这个出现次数即可（即，只和第x个字符串以外的字符串匹配）

(思路早想到了，但实现时换了好几种写法。。。今天真的状态布星啊qwq)

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+1;
int n,k;
char s[N][6];
map<string,int>sp,ep;
inline string get_string(int id,int x,int y){
    string now="";
    for(int i=1;i<=y;++i){
        now+=s[id][x+i-1];
    }
    return now;
}
signed main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i){
        scanf("%s",s[i]+1);
        for(int j=1;j<=k;++j){
            for(int p=1;p<=k-j+1;++p){
                ++sp[get_string(i,p,j)];
            }
        }
    }
    int q;
    scanf("%d",&q);
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        long long ans=0;
        ep.clear();
        for(int i=1;i<=k-y+1;++i){
            ++ep[get_string(x,i,y)];
        }
        for(int i=1;i<=k-y+1;++i){
            string now=get_string(x,i,y);
            ans+=sp[now]-ep[now];
        }
        printf("%lld\n",ans*y);
    }
    return 0;
}

E.Board

见过这个题，原题不是加任意数而是加1，不过其实是一样的。。。

我们首先分析，设 $x[i]$ 表示第i行加的数字之和， $y[i]$ 表示第i列加的数字之和,第i行第j列的数字为 $s(i,j)$ 。

那么，对于第i行第j列的数字，它现在的值即为 $x[i]+y[j]$ 。

于是，我们设被隐藏的数字是第a行第b列的那个，那么它的值即为 $x[a]+y[b]$

我们想办法把这个和构造出来。

我们随便再找两个数字c,d(c,d<=n),使得c!=a,d!=b

那么，我们就有:

$s(c,b)=x[c]+y[b]$

$s(a,d)=x[a]+y[d]$

$s(c,d)=x[c]+y[d]$

注意到， $s(c,b)+s(a,d)-s(c,d)=s(a,b)=x[a]+y[b]$

而，又因为只有第a行第b列的值是不确定的，所以，这三个数字的值是确定的。

所以，我们直接输出这个式子的值就行了

代码:

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001];
signed main(){
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            scanf("%d",&a[i][j]);
            if(a[i][j]==-1){
                x=i,y=j;
            }
        }
    }
    int k=1,t=1;
    if(y==k)++k;
    if(x==t)++t;
    printf("%d",a[x][k]+a[t][y]-a[t][k]);
    return 0;
}