牛客小白月赛45

写在前面

周五来打一打好久没打的小白月赛，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*i的x都能够取满？除了一个特例：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;
}