牛客练习赛64 A~C

比赛链接：https://ac.nowcoder.com/acm/contest/5633
A：https://ac.nowcoder.com/acm/contest/5633/A
题意：给你n，m，k个1，2，4。要你对这些数字进行排序，使得排序后的这串数字中有mx个“1412”子串，求mx的最大值。
思路：不难想，这串数字必定会是形如111( $图片说明$ 个）……444……111( $n2$ 个)……222这样的（n1+n2=n)，也就是2一定在最后，4一定夹在两组1之间，1被分为两组，那么此时的子串数就是n1 * k * n2 * m。要想这个值最大，也就变成，在n一定的情况下，求n1*n2的最大值，很容易知道这个最大值是 $图片说明$ *( $图片说明$ +(n&1))。至此代码也就写出来了

//author CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    ll t;
    cin>>t;//t组数据
    while(t--)
    {
        ll n,m,k;
        cin>>n>>m>>k;
        if(n<2||m<1||k<1)//那种数量本身就不够的，特判一下
        {
            cout<<0<<endl;
            continue;
        }
        if(n&1)//n为奇数
        {
            cout<<(n/2)*((n/2)+1)*m*k<<endl;
            continue; 
        }
        else//n为偶数
        {
            cout<<(n/2)*(n/2)*m*k<<endl;
        }
    }
     return 0;
}

B:https://ac.nowcoder.com/acm/contest/5633/B
题意：给你一颗树，问你对于每个点有多少个点和它的距离是2。
思路：对于每个点，如果它连接了不止一个点，那么这些点之间的距离就是2。很容易想到它们是不会重复的。至此代码也就可以写出来了。

//author CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=2e5+7;
const double pi=acos(-1);
using namespace std;
vector<int > e[maxn];
ll ans[maxn]={0};
int main()
{
    //ios::sync_with_stdio(false);
     ll n;
     cin>>n;
     ll a,b;
     for(int i=0;i<n-1;i++)
     {
         cin>>a>>b;
         e[a].push_back(b);
         e[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(e[i].size()>1)//如果这个点连接的点数大于1
        {
            for(size_t j=0;j<e[i].size();j++)
            {
                ans[e[i][j]]+=e[i].size()-1;//记得减去自己
            }
        }
    }
     for(int i=1;i<=n;i++)
     {
         cout<<ans[i]<<endl;
     }
    return 0;
}

C：https://ac.nowcoder.com/acm/contest/5633/C
题意：给你一个数组，要你计算 $图片说明$ 。
思路：一上来肯定不明白这个这个式子的意义，但你明白它是两个数相乘然后求和，那么我们打个表来看看每对数字都乘几次

ll b[maxn][maxn];//代表ai和aj乘了几次。
for(int l=1;l<=n;l++)
    {
        for(int r=l;r<=n;r++)
        {
            for(int i=l;i<=r;i++)
            {
                for(int j=i;j<=r;j++)
                {
                    b[i][j]++;
                }
            }
        }
    }

看一下样例：
图片说明

这一下子，我们就从O(n^4)优化到O(n^2),当然依旧不够。
还需要再次降低。
我们可以先把O(n^2)的核心部分写出来。
至于（n-j+1)这个系数怎么来的，你可以看看上面的图，超级直观有没有！

    for (int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            ans+=i*a[i]*a[j]*(n-j+1);//这里是优化点
            ans%=mod;
        }
    }

仔细观察，我们会发现其实我们要的是 $图片说明$ ,那么很容易就发现 $图片说明$ 每次都要从i到n，那么这里就可以用前缀和来降低一下复杂度。至此代码也就写出来了，但是要注意，因为它不停的在取模，很可能后面的前缀和比前面的前缀和小，但是后面肯定比前面大啊！所以在求两个前缀和的差的时候要补上一个mod来避免取负数模，使得差值一定是正数。

//author CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=2e5+7;
const double pi=acos(-1);
using namespace std;
ll a[maxn]={0};
ll sum[maxn]={0};
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    ll ans=0;
    sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    for(int i=1;i<=n;i++)
    {
        sum[i]=(sum[i-1]+(a[i]*(n-i+1)%mod))%mod;//维护前缀和。
    }

    for(int i = 1; i <= n; i++)
    {
        ans+=(((i*a[i])%mod)*((sum[n]-sum[i-1]+mod)%mod))%mod;//记得加一个mod。
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

写在最后：
C题一步一步的把复杂度从O(n^4)降到O（n)超级有成就感，感谢@Kur1su大佬的帮助！大佬的B题写的也超级棒，让不会树学的我也能写出来了。