牛客算法周周练8题解

A - 小A买彩票
题意:
买一张彩票需要元，可能得到元，问连续买n张彩票不亏损的概率是多少，要求以最简分数表示概率
思路：
用表示买了张彩票得到元的方案数，显然总的方案数为
那么很显然状态转移方程为:
最后，由于要最简分数，分子分母必须同时除上二者的

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath> 
 using namespace std;
 typedef long long ll;
 ll dp[32][125];
 int main()
 {
     int n;
     scanf("%d",&n);
     memset(dp,0,sizeof(dp));
     if(n==0){
         cout<<"1/1";
         return 0;
     }
    if(n==1){
        cout<<"1/2";
        return 0;
    }
    ll x=0,y=1;
    for(int i=1;i<=n;i++) y*=4;
    dp[1][1]=dp[1][2]=dp[1][3]=dp[1][4]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=120;j++){
            if(j-1>0&&j>=i) dp[i][j]+=dp[i-1][j-1];
            if(j-2>0&&j-1>=i) dp[i][j]+=dp[i-1][j-2];
            if(j-3>0&&j-2>=i) dp[i][j]+=dp[i-1][j-3];
            if(j-4>0&&j-3>=i) dp[i][j]+=dp[i-1][j-4];
            if(i==n&&j>=n*3) x+=dp[i][j];
        }
    }
    ll k=__gcd(x,y);
    x/=k,y/=k;
    cout<<x<<"/"<<y; 
     return 0;
 }

B -「金」点石成金
题意:
次操作，你可以选择增加点财富，减少点法力，或者增加点法力，减少点财富(如果财富或法力小于时，则变为)，求最后法力*财富的最大值

思路：
由于最大为15，我们可以暴力枚举每种情况，因此可以使用,但是我选择了二进制枚举的做法
枚举到中的每一个数，如果该数二进制表示中第位为则表示该次进行第一种操作，否则表示进行第二次操作
每次模拟得到最后的值，并记录最大值即可

#include<iostream>
#include<algorithm>
 using namespace std;
 typedef long long ll;
 const int maxn=1e6+10;
 struct node{
    ll a,b,c,d;
 }arr[maxn];
 int main()
 {
    int n;
    scanf("%d",&n);
    ll x,y,ans=0;
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld%lld",&arr[i].a,&arr[i].b,&arr[i].c,&arr[i].d);
    for(int i=0;i<(1<<n);i++){
        ll x=0,y=0;
        for(int j=0;j<n;j++){
            if((i>>j)&1==1){
                x+=arr[j+1].a;
                y=max(0ll,y-arr[j+1].b);
            }
            else{
                y+=arr[j+1].c;
                x=max(0ll,x-arr[j+1].d);
            }
        }
        ans=max(ans,x*y);
    }
    cout<<ans;
    return 0;
 }

C - 小阳的贝壳(线段树维护差分数组)
题意：
给一个序列，进行三种操作
操作. 区间所有数加上
操作. 求区间中所有相邻的数的最大差值
操作. 求区间中所有数的最大公因数
思路：
对于本题，我们不应该维护普通数组，而应该维护一个差分数组
对于差分数组，如果将原数组的区间加上等同于在差分数组的位置加上,并且在处减去，因此操作一就变成了简单的单点修改了
但是，对于操作二三我们需要维护什么信息呢？
首先，差分数组本身保存的就是原数组中相邻两数的差值，因此对操作二我们只要维护差分数组绝对值的最大值即可
其次，根据辗转相除的定义，会有如下性质
因此一个区间的就等于原数组中区间第一个数与差分数组中的其他数的，所以我们还需要维护差分数组的区间
至于区间第一个数如何求，根据定义求一个查分数组的前缀和即可,因此我们还需要维护一个查分数组的区间和

#include<iostream>
#include<algorithm>
#include<cmath>
#define ls rt<<1
#define rs rt<<1|1
 using namespace std;
 const int maxn=1e5+10;
 struct node{
     int sum,mx,gcd;//差分区间和，区间最大值，区间GCD 
 }t[maxn<<2];
 int a[maxn],b[maxn]; //原数组，差分数组 
 void push_up(int rt)
 {
     t[rt].sum=t[ls].sum+t[rs].sum;
     t[rt].mx=max(t[ls].mx,t[rs].mx);
     t[rt].gcd=__gcd(t[ls].gcd,t[rs].gcd);
 }
 void build(int l,int r,int rt)
 {
     if(l==r){
         t[rt].sum=b[l];
         t[rt].gcd=t[rt].mx=abs(b[l]);
         return;
     }
    int mid=(l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    push_up(rt);
 }
 void update(int l,int r,int rt,int pos)
 {
     if(l==r){
         t[rt].sum=b[l];
         t[rt].gcd=t[rt].mx=abs(b[l]);
         return;
     }
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,ls,pos);
    else update(mid+1,r,rs,pos);
    push_up(rt);
 }
 int query_sum(int l,int r,int rt,int L,int R)
 {
     if(l>=L&&r<=R) return t[rt].sum;
     int mid=(l+r)>>1;
     int ans=0;
     if(L<=mid) ans+=query_sum(l,mid,ls,L,R);
    if(R>mid) ans+=query_sum(mid+1,r,rs,L,R);
    return ans;
 }
 int query_max(int l,int r,int rt,int L,int R){
     if(l>=L&&r<=R) return t[rt].mx;
     int mid=(l+r)>>1;
     int ans=0;
     if(L<=mid) ans=max(ans,query_max(l,mid,ls,L,R));
    if(R>mid) ans=max(ans,query_max(mid+1,r,rs,L,R));
    return ans;
 }
 int query_gcd(int l,int r,int rt,int L,int R){
     if(l>=L&&r<=R) return t[rt].gcd;
     int mid=(l+r)>>1;
     int ans=0;
     if(L<=mid) ans=__gcd(ans,query_gcd(l,mid,ls,L,R));
    if(R>mid) ans=__gcd(ans,query_gcd(mid+1,r,rs,L,R));
    return ans;
 }
 int main()
 {
     int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
    build(1,n,1); 
    for(int i=1;i<=m;i++){
        int op,l,r,x;
        scanf("%d",&op);
        if(op==1){
            cin>>l>>r>>x;
            b[l]+=x;
            b[r+1]-=x;
            update(1,n,1,l);
            update(1,n,1,r+1);    
        }
        else if(op==2){
            cin>>l>>r;
            cout<<query_max(1,n,1,l+1,r)<<endl;
        }
        else if(op==3){
            cin>>l>>r;
            int t=query_sum(1,n,1,1,l);
            if(l==r) cout<<t<<endl;
            else cout<<__gcd(t,query_gcd(1,n,1,l+1,r))<<endl;
        }
    }
    return 0;

D - Forsaken喜欢字符串
题意:
给个长度为字符串，然后给出询问，每次询问选定一个字符串，让你计算在所有其他字符串中相同子串个数再乘上长度
思路：
由于字符串长度最长只为，那么子串的种类数也最多为，所以我们可以建立个
然后我们直接遍历每个子串，利用可以直接找到所有字符串中与自己相同的字符串个数，再减去本字符串中相同的子串个数乘上长度就为答案

#include<iostream>
#include<algorithm>
#include<map>
 using namespace std;
 const int maxn=5e4+10;
 typedef long long ll;
 map<string,int> m1,m2,m3,m4,m5;
 string s[maxn];
 int main()
 {
     int n,k,m,x,len;
     cin>>n>>k;
     for(int i=1;i<=n;i++)
         cin>>s[i];
     for(int i=1;i<=n;i++){
         for(int l=1;l<=k;l++){
             for(int j=0;j+l-1<k;j++){
                 string s1=s[i].substr(j,l);
                 if(l==1) m1[s1]++;
                 else if(l==2) m2[s1]++;
                 else if(l==3) m3[s1]++;
                 else if(l==4) m4[s1]++;
                 else if(l==5) m5[s1]++;
             }
         }
     }
     cin>>m;
     for(int i=1;i<=m;i++){
         cin>>x>>len;
         int ans=0;
         for(int j=0;j+len-1<k;j++){
             int num=0;
             string s1=s[x].substr(j,len);
             for(int l=0;l+len-1<k;l++){
                 string s2=s[x].substr(l,len);
                 if(s2==s1) num++;
             }
             if(len==1) ans+=len*(m1[s1]-num);
            else if(len==2) ans+=len*(m2[s1]-num); 
            else if(len==3) ans+=len*(m3[s1]-num); 
            else if(len==4) ans+=len*(m4[s1]-num); 
            else if(len==5) ans+=len*(m5[s1]-num); 
         }
        cout<<ans<<endl;
     }
     return 0;
  } 

E - Board
题意:
给一个全为的矩阵，每次将矩阵的某一行或某一列全部加上,进行若干次操作后，会得到一个新的矩阵，将矩阵中的某一个位置遮去，求该位置的值
思路：
直接遍历每一行与每一列，并且每个元素减去一行(或一列)的最小值(含有的行与列不进行此操作)
最后的答案就为所在行与列数字的和

#include<iostream>
#include<algorithm>
 using namespace std;
 const int maxn=1005;
 int a[maxn][maxn];
 int 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;
             }
         }
     }
    for(int i=1;i<=n;i++){
        if(i==x) continue;
        int mi=100000;
        for(int j=1;j<=n;j++)
            mi=min(mi,a[i][j]);
        for(int j=1;j<=n;j++)
            a[i][j]-=mi;
    }
    for(int j=1;j<=n;j++){
        if(j==y) continue;
        int mi=100000;
        for(int i=1;i<=n;i++)
            mi=min(mi,a[i][j]);
        for(int i=1;i<=n;i++)
            a[i][j]-=mi;
    }
    cout<<max(a[x-1][y],a[x+1][y])+max(a[x][y-1],a[x][y+1]);
    return 0; 
 }