【牛客练习赛64】前四题题解

A

知识点：贪心、乘法原理
思路：如果是给定的字符串，那么dp求解即可。但这道题只给了1、2、4的数量。显然111...1144...44111...11222...22这样是最优的，且两个1的连续子串长度之差尽可能小。
最终输出 $(n/2)*(n/2+n\%2)*m*k$ 即可。

#include<bits/stdc++.h>;
using namespace std;
#define ll long long
const int mod = 1e9+7;

int main(){
    ll t;
    cin>>t;
    while(t--){
        ll n,m,k;
        cin>>n>>m>>k;
        ll a=n/2,b=n-a;
        cout<<a*b*m*k<<endl;
    }
}

B

知识点：图论
思路：统计所有点的度数，那么每个点距离为 $2$ 的数量为它的邻点的度数之和减去邻点的个数。

#include<bits/stdc++.h>;
using namespace std;
#define ll long long
const int mod = 1e9+7;
int dp[222222];
vector<int>g[222222];
int main(){
    ll n,i,j,k;
    cin>>n;
    for(i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
        dp[x]++;
        dp[y]++;
    }
    for(i=1;i<=n;i++){
        ll sum=0;
        for(j=0;j<g[i].size();j++){
            sum+=dp[g[i][j]]-1;
        }
        cout<<sum<<endl;
    }
}

C

知识点：dp
思路：这道题其实就是求所有子区间的区间内部两两乘积之和。
我们先把问题分解，假设 $dp[i]$ 为前 $i$ 个数的最终答案，那么 $dp[i+1]$ 比 $dp[i]$ 多了哪些区间呢？答案是 $(1,i),(2,i)...(i,i)$ 这些。
那么我们可以先转换一下思路，设 $dp2[i]$ 为 $(1,i),(2,i)...(i,i)$ 这些区间内部的两两乘积之和，这些区间里的乘积可以分为两类，含 $a[i]$ 的和不含 $a[i]$ 的。
含 $a[i]$ 的部分，有 $1$ 个 $a[1]*a[i]$ , $2$ 个 $a[2]*a[i]$ , ... $i$ 个 $a[i]*a[i]$ 。这些部分可以前缀和预处理搞定。
不含 $a[i]$ 的部分，可以看成为 $(1,i-1),(2,i-1)...(i-1,i-1)$ 这些区间内部的两两乘积之和,正好是dp2[i-1]。
那么这道题就做出来了。
（当时推的时候思路没这么清晰，把 $a[i]*a[i]$ 单独拿出来了，繁琐了很多）。

#include<bits/stdc++.h>;
using namespace std;
#define ll long long
const int mod = 1e9+7;
ll dp[200202],dp2[200020],sum[200020],dpp[200020];
ll a[200202];
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int main(){
    ll n,i,j,k;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        dp2[i]=dp2[i-1]+sum[i];
        sum[i]%=mod;
        dp2[i]%=mod;
    }
    dpp[1]=a[1]*a[1];
    for(i=2;i<=n;i++){
        dpp[i]=dpp[i-1]+(sum[i-1]*i%mod-dp2[i-1]+mod)*a[i]%mod+(i)*a[i]%mod*a[i]%mod;
        dpp[i]%=mod;
    }
    //for(i=1;i<=n;i++)cout<<sum[i]<<" "<<dpp[i]<<endl;
    for(i=1;i<=n;i++)
    dp[1]=a[1]*a[1];
    for(i=2;i<=n;i++){
       // cout<<(sum[i-1]*i%mod-dp2[i-1]+mod)%mod<<endl;
        dp[i]=dp[i-1]+a[i]*a[i]%mod*i%mod+(sum[i-1]*i%mod-dp2[i-1]+mod)*a[i]%mod+dpp[i-1];
        dp[i]%=mod;
    }
    cout<<dp[n];
}

D

知识点：dp、容斥原理
思路：这道题直接正向求不太好求，可以反向思维：一共有 $n!$ 个排列，把所有不合法的情况减去，就是合法的情况。
不合法的情况可以这样去求：
先用一个桶来统计每个位置的不合法的宝石数量（ $0$ 可以跳过不统计）,记为 $t[m]$ 。
首先有1个位置不合法的总方案共有 $(n-1)!*\sum_{i=1}^mt[i]$
2个位置不合法的总方案共有 $(n-2)!*\sum_{i=1}^m\sum_{j=i+1}^mt[i]*t[j]$
3个位置不合法的总方案共有 $(n-3)!*\sum_{i=1}^m\sum_{j=i+1}^m\sum_{k=j+1}^mt[i]*t[j]*t[k]$
问题就是如何求里面的和式了。这个可以用二维dp解决，设 $dp[i][j]$ 为前 $j$ 个数里，取 $i$ 个数乘积之和，那么有： $dp[i][j]=dp[i][j-1]+dp[i-1][j-1]*a[j]$
求完了这些之后，我们可以用 $n!$ 减去1个位置不合法的方案数，那么2个位置不合法的情况被多减了一次，需要加回来，3个位置不合法的情况又被加多了，再减掉。。以此类推，最终求出来的就是合法方案的总数。
注意这道题 $n$ 范围是8000， $O(n^2)$ 的时间复杂度可以过，但空间复杂度不行，所以只能开滚动数组进行dp（我就是第一发开的二维数组导致mle一次QAQ）

#include<bits/stdc++.h>;
using namespace std;
#define ll long long
const int mod = 998244353;
ll jc[200020];
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    power(x,mod-2);
}
ll a[20002],t[20002],b[20002],dp[3][8002];
int main(){
    ll n,i,j=1,k;
    cin>>n;
    ll tt=1;
    jc[0]=1;
    for(i=1;i<=n;i++)jc[i]=tt=tt*i%mod;
    for(i=0;i<n;i++)cin>>a[i],t[a[i]]++;
    int jud=-1,temp=n;
    for(i=1;i<=n;i++){
        if(t[i])b[j++]=t[i];
    }
    j--;

    //for(i=1;i<=j;i++)cout<<dp[i][j]<<endl;
    ll res=jc[n];
    for(i=1;i<=j;i++){
        if(i==1){
            for(k=1;k<=j;k++){
                dp[1][k]=(dp[1][k-1]+b[k])%mod;
            }
        }
        else{
            for(k=1;k<=j;k++){
                dp[0][k]=dp[1][k];
            }
            for(k=1;k<=j;k++){
                dp[1][k]=(dp[1][k-1]+dp[0][k-1]*b[k])%mod;
            }
        }
        res+=jud*jc[n-i]*dp[1][j]%mod,jud*=-1;
        res=(res+mod)%mod;
     //   cout<<res<<endl;
    }
    cout<<res;
}