A,小A买彩票

题意

小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。 0≤n≤30

输入描述

一行一个整数N，为小A购买的彩票数量

输出描述

输出一个最简分数a/b，表示小A不亏本的概率。
若概率为1，则输出1/1，概率为0，则输出0/1。

解析

首先他要能不亏本，那么买一张的时候要买到3或者4，两张的时候要总和超过6，可以是33，34，43，44，24，42，这么多种情况，所以我们就不仅仅是考虑每一张都超过3，如果出现了一张1，来两张4就好了，所以我们考虑使用dp，来递推最多的可能性，之前都没有写过博客来讲一下dp，主要也是梳理一下自己对dp的认识

关于dp

我对dp的认识主要是像背包问题这种，这个物体放进去还是不放.

就像我现在背包已经装满了，装了i个物体，总质量为j，现在我要考虑是否要装第i+1个物体，如果没装满并且能装下，自然是直接装进去更好，那么如果装满了呢

我们用dp数组保存了每一种情况的最优解，也就是说假设我现在有2个物体a,b，a质量为1,价格为1，b质量为2，价格为2

我们先不管背包能装多少，首先可以得到dp[0][0]=0,也就是背包为空的时候,现在我们往后推我们dp数组为dp[1][1]也就是说之装一个物品，质量为1的时候显然只装一个a是最优解，然后我们递推，dp[1][2],也就是我们现在可以装的质量为2，还是只能装一个物体，如果我们不装物品b，那么dp[1][2]=dp[1][1]等于1，如果我们装物品2，那么我们就要在背包里腾出空间，拿出一个物品，然后装下物品2，dp[1][2]=dp[0][0]+2，这里就可以看到明显腾出空间再放入b更优，这样子一直往后推，当推到质量为我们所求的最大值的时候，得到的就一定是我们要的最优解。

好，梳理完了，我们来看现在这一题，我现在买了n张彩票，我现在要不亏本，那么我们最少就要中奖的总额达到3n，那么我们只要像前面一样，dp过去，然后在最后得到dp数组之和，将dp[n][3n]到dp[n][4*n]全部加起来就好了。

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll dp[32][150];
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
int main(void){
    ios::sync_with_stdio(false);
    memset(dp,0,sizeof(dp));
    int n;
    cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n*4;++j){
            if(j>=1)
                dp[i][j]+=dp[i-1][j-1];
            if(j>=2)
                dp[i][j]+=dp[i-1][j-2];
            if(j>=3)
                dp[i][j]+=dp[i-1][j-3];
            if(j>=4)
                dp[i][j]+=dp[i-1][j-4];
        }
    }
    ll a=0;
    for(int i=3*n;i<=121;++i){      //3*n为成本
        a+=dp[n][i];
    }
    ll b=pow(4,n);
    ll c=a/gcd(a,b);
    ll d=b/gcd(a,b);
    cout<<c<<"/"<<d<<endl;
    return 0;
}

B，[金]点石成金

题意

赛时提示：魔法值和财富值初始为0

帕秋莉掌握了一种金属性魔法
她决定去捡一些石头，施展点石成金魔法

帕秋莉将捡到的n块石头排成一排，并决定将一些石头点为黄金

对于第i块石头，如果将其变为黄金，会增加ai的财富，消耗bi的魔法（需要说明的是，就算魔法值不够，也可以操作，操作后魔法值归零）

否则，帕秋莉将会回复ci的魔法，但减少di的财富（财富值同理，可以无限制减少）

帕秋莉想知道，按照1-n的顺序以此操作每块石头，如何决策，可以使自己最后的收益值最大
只需要输出最大收益
收益值=财富值*魔法值

（提示：数值不会变为负数，即任何时候，如果数值小于了0，它会立即变为0）

输入描述

第一行一个整数n
接下来n行，每行四个数，分别代表对应石头的a,b,c,d值

输出描述

一个整数表示答案
这个题目我都不想写。。。。。。直接暴力dfs，处理一点细节就可以直接冲！！！

上图水文章

图片说明

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
typedef long long ll;
ll a[N], b[N], c[N], d[N];
int n;
ll dfs(int number, ll money, ll mofa){
    if(number == n + 1){
        return money * mofa;
    }
    ll temp = mofa - b[number];
    ll res = dfs(number + 1, money + a[number], temp < 0 ? 0 : temp);
    temp = money - d[number];
    res = max(res, dfs(number + 1, temp < 0 ? 0 : temp, mofa + c[number]));
    return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
    }
    ll res = dfs(1, 0, 0);
    printf("%lld\n", res);
    return 0;
}

C.小阳的贝壳

题意

小阳手中一共有 n 个贝壳，每个贝壳都有颜色，且初始第 i 个贝壳的颜色为 $col_i$。现在小阳有 3 种操作：

1 l r x：给 [l,r][l,r] 区间里所有贝壳的颜色值加上 xx 。

2 l r：询问 [l,r][l,r] 区间里所有相邻贝壳颜色值的差（取绝对值）的最大值（若 l = rl=r 输出 0）。

3 l r ：询问 [l,r][l,r] 区间里所有贝壳颜色值的最大公约数。

输入描述

第一行输入两个正整数 n,mn,m，分别表示贝壳个数和操作个数。
第二行输入 n个数 $col_i$ ，表示每个贝壳的初始颜色。
第三到第 m + 2 行，每行第一个数为 opt，表示操作编号。接下来的输入的变量与操作编号对应。

输出描述

共 m 行，对于每个询问（操作 2 和操作 3）输出对应的结果。

解析

线段树，俺不会隔壁大佬的代码大佬的博客

代码

#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喜欢字符串

待补

E.Board

题意

恬恬有一个nx n的数组。她在用这个数组玩游戏：
开始时，数组中每一个元素都是0。
恬恬会做某些操作。在一次操作中，她可以将某一行的所有元素同时加上一个值，也可以将某一列的所有元素同时加上一个值。
在几次操作后，一个元素被隐藏了。你能帮助她回忆隐藏的数是几吗？

输入描述

第一行一个整数n（1≤ n≤ 1000）。
接下来n行每行n个整数表示数组a。
第(i+1)行的第j个元素表示aij（aij=-1或0≤ aij ≤ 10000）。-1表示隐藏的元素。

输出描述

仅一个整数表示答案。

解析

这个题目就是每次我可以个一行或者一列都加上一，然后我现在隐藏了一个点的值，让你根据别的点的值来求出这个点，主要是考察思维，我上图理解一下就好了

图片说明

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN=1005;
int s[MAXN][MAXN];
int main(void){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int a,b;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin>>s[i][j];
            if(s[i][j]==-1)
                a=i,b=j;
        }
    }
    int ans=0;
    if(a==0||b==0)cout<<s[a][n-1]+s[n-1][b]-s[n-1][n-1];
    else cout<<s[a][0]+s[0][b]-s[0][0];
    return 0;
}

完结撒花，又写（水）完了一篇长博客

牛客算法周周练8

A,小A买彩票

题意

输入描述

输出描述

解析

关于dp

代码

B，[金]点石成金

题意

输入描述

输出描述

代码

C.小阳的贝壳

题意

输入描述

输出描述

解析

代码

D.Forsaken喜欢字符串

E.Board

题意

输入描述

输出描述

解析

代码