牛客小白月赛45

写在前面

rank
周五来打一打好久没打的小白月赛,rk94还说的过去吧,这一次也涨大分,经过寒假训练营的我分都不知道掉哪去了...
来说说比赛,刚开始看题发现A基本上没人过?就是那种0/88这种通过率,索性开B,然后B结论一直不确定,实际上早就猜出来了,但是还想着打暴力调试一下,浪费了不少时间,求稳嘛,然后再去做A,A有一个小坑,前两题是用Python过的,几行hhh。
然后C是有一个地方,开始还考虑到了,但是后面才想到hhh,D是搞了好久,想复杂了,也不是,就是还是模棱两可吧做这种括号匹配问题,也是1wa,只需要改一个条件就好了;E的话是一个树形DP,调了一会,最近做了好多树形DP诶,不记得改哪了哈哈哈
AB就不多说啦
题目链接我都不放了,直接放一个比赛链接:牛客小白月赛45

C-山楂(贪心)

题意

给出8个数字$a_i$代表山楂个数,对于第i级,可以用3或4个合成第i+1级的一个,最大是9级就不往下合成了,每次合成会加x*i分,x代表花费的个数,i是等级,求最后最大的得分是多少
比如a[1]=12,可以分成4个3(3+3+3+3)来每次合成一个(1+1+1+1),最后a[2]+=4,然后积分加上3*1 * 4

思路

我们不难想到这是一个递推,慢慢贪心贪过去,但是假如此时有a[i]个,那么我改怎么样能够达到积分最大并且下一个a[i+1]也能得到更多呢?
这个问题仔细想想发现,当个数小于3的时候(1,2),肯定是不行的,积分也无法增加;当个数大于等于3的时候,就可以进行加积分和升级,那么可以发现到7=3+4,11=3+3+4,20=3+3+3+3+4+4,要确保3更多,因为这样个数也多,比如刚才写的20,就是能升级6个,但是如果20=4+4+4+4+4,那么只能升级5个,这肯定不符合我们的贪心思想。
那么这样看来是不是所有的数都能够全部升级,也就是x*ix都能够取满?除了一个特例5
对于5来说需要特判,5只能分为一个4(贪心,4>3),但是用取模的方法不需要考虑到,是一样的

代码

我的代码:

inline void Case_Test()
{
    for (int i=1;i<=8;i++)
        cin>>a[i];
    for (int i=1;i<=8;i++)
    {
        int num=a[i];
        if (num<=2) continue;
        a[i+1]+=num/3;//能分多少个3
        if (num==5) ans+=4*i;//special judge five
        else ans+=num*i;//全加
    }
    cout<<ans;
}

伍教练的代码(取模):

for(int i=1;i<=n;i++)
{
    int num=a[i]/3;
    a[i+1]+=num;
    ans+=num*3*i;
    a[i]=a[i]%3;
    if(a[i]<=num)
        ans+=a[i]*i;
    else
        if(num==0)
            continue;
        else
            ans+=i;
}

D-切糕(括号匹配/组合数学)

题意

给出一个只含'('和')'的子串,将其切成若干个每个都合法的序列,请问这种不同的组合有多少个?
比如(())(),你只能要么不砍,要么只看中间一刀分成()() , (),这样子就是答案两种
不同:每一刀砍的地方不一样就算不同

思路

这个题思路很快,但是代码实现起来一开始想得很复杂,所以浪费了很多时间。实际上就是要将这个子串分成很多不能再分解的合法子串(),(()),((()))...然后就像变成了ABCD这样的,然后问你可以分成多少种不同的,比如ABCD四个,那么中间有3个空A_B_C_D,也就是我们所学的——插板法/隔板法,每一种空隙都有2种,所以是2的(cnt-1)次幂,cnt代表的是有多少个不能再分割的合法子串。
记得注意,哪怕有一个地方不是合法的,那么整个就不合法

总结:
我们对于括号匹配的问题,很多情况下用一个cnt来计数,如果出现了'(',那么cnt++;如果出现了')',那么cnt--。
这样的好处就是,如果出现了0,那么就代表这是一个合法匹配,比如(()),你会发现cnt是这样变化的:0->1->2->1->0,所以这是个合法的。
但是要注意,如果cnt出现的负数,那么代表这个时候出现的')'不是前面的'('能匹配的,所以肯定不合法。

思路相通之后,代码就很好写了,记得记得用快速幂。

代码

inline void Case_Test()
{
    cin>>st;
    n=st.length();
    for (int i=0;i<n;i++)
    {
        if (st[i]=='(')
            cnt++;
        else
        {
            cnt--;
            if (cnt<0) {cout<<-1;return;}
            if (cnt==0)
                k++;//个数++
        }
    }
    if (cnt!=0) cout<<-1;
    else cout<<qpow(2,k-1,mod);//插板法
}

E-筑巢(树形DP)

题意

给你一棵树,这个树每个点有点权,每个边有边权,让你选出一个非连通块(最小是一个点),不能选一个点和一条边,因为你选择了那条边,那么这条边的另外一个点也是属于连通块的。权值有正有负

思路

树形DP,大致就是先往下再网上来dp,维护一个值,这个值在我代码里面是f[x],表示的是以当前节点(一定要包括当前节点,目的保证联通)往下的连通块的最大权值,那么贪心的时候就是对于每一个子结点的f[y],我们加上边权w来判断是否大于0,根据贪心的思想,大于0肯定是需要的。
最后统计一下所有的f[i]取最大值,为什么直接是f[1]呢?
万一第一个结点旁边的权全是小于0很大的,而且答案是很深下的一个小结点呢?仔细想想

代码

int ans=-inf;//注意!!我这里一开始是ans,也就是ans=0,但是万一权值全是负的?所以我还是会输出0
//我这里wa了好久!!一直在调试哪里错了!!
inline void dfs(int x,int pre)
{
    int tmp=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to,w=edge[i].w;
        if (y==pre) continue;
        dfs(y,x);
        if (f[y]+w>0) tmp+=f[y]+w;
        //如果f[y]+w,y代表子结点,w代表这个x到y的边权,如果这个时候>0那么就可以通过贪心来贪
    }
    f[x]=tmp+a[x];//维护f[x],f[x]代表的是从x节点(包括x)往下的最大权值
    //最后加上a[x]是自己的点权
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) {cin>>a[i];ans=Max(ans,a[i]);}
    for (int i=1;i<n;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);add(v,u,w);
    }
    dfs(1,-1);
    for (int i=1;i<=n;i++) ans=Max(ans,f[i]);//为什么要统计最大的
    cout<<ans;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注