牛客练习赛64 题解

一.总结

后面开始打的，很多题都不是正解，都是歪门邪道/奇淫技巧，看了官方题解才恍然大悟，这里给大家介绍一下跟正解不同的黑科技做法。

二.题解

A. 怪盗-1412

一开始再由于子序列的问题，想了想第一个例子觉得不可能只是504，所以觉得自己读错题了，只能反着从样例读题。

很明显第一个例子是 6 ，7 ， 8 ，答案是 504 。
因为1412中的4和2都是单一的，所以必须会相乘并成为答案的一部分，所以我尝试用504/7/8，求出9，不难联想到9是3*3，正好是6的一半。

所以答案的式子就有了： $a*(a-a/2)*b*c$

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=2e3+5;
const int mod=1e9+7;

int main(){
    ll p; cin>>p;
    while(p--){
        ll a,b,c; cin>>a>>b>>c;
        cout<<a/2*(a-a/2)*b*c<<endl;
    }
    return 0;
}

B.Dis2

题意讲的很清楚，但是我的脑子没那么好，没有联想到直接累加跟 i 点相连的点的度-1 .

我的做法是 i 点距离为 2 有三种：

比如说 i 点的深度为 $d[i]$ ,那么只要 $d[i]-2>=1$ 就肯定存在一个点距离 i 点为 2.
还有一种就是 i 点的儿子的儿子个数累加和.
最后就是 i 点的父亲结点的儿子个数-1（i点本身）。

所以我用 cnt数组维护儿子个数，ans数组维护儿子的儿子个数和，具体可以看代码。

代码：

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=2e3+5;
const int mod=1e9+7;

vector<ll>g[manx];
ll cnt[manx],ans[manx],f[manx],d[manx];
ll ma;

void dfs(ll u,ll pre){
    d[u]=d[pre]+1; f[u]=pre;
    for(auto v: g[u]){
        if(v==pre) continue;
        cnt[u]++;
        dfs(v,u);
        ans[u]+=cnt[v];
    }
}

int main(){
    ll n; cin>>n;
    for(int i=1;i<n;i++){
        ll u,v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        ll x=ans[i];
     //   cout<<i<<" "<<x<<" "<<ans[i]<<" "<<d[i]<<endl;
        if(d[i]-2>=1) x++;
        x+=max(cnt[f[i]]-1,0ll);
        cout<<x<<endl;
    }
    return 0;
}

C.序列卷积之和

黑科技之打表找规律。
不难发现是个上三角矩阵且存在规律，以第一个样例可以打出下表:
4 3 2 1
0 6 4 2
0 0 6 3
0 0 0 4
所以我们可以预处理一下后缀和，然后 $O(n)$ 求出答案。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=2e3+5;
const int mod=1e9+7;

ll mps[N][N];
ll a[manx],b[manx],suf[manx];

int main(){
    ll n; cin>>n; ll ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    /*
    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++)
                    mps[i][j]++,ans+=a[i]*a[j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<mps[i][j]<<" ";
        cout<<endl;
    }
    代码实际输出：4 3 2 1 
    0 6 4 2 
    0 0 6 3 
    0 0 0 4 
    1988你期望的输出：1988
    */
    for(int i=n,j=1;i>=1;i--,j++) suf[i]=suf[i+1]+a[i]*j;
    ll sb=(1+n)*n/2;
    for(int i=1,j=1;i<=n;i++,j++){
        ans=(ans+(suf[i]%mod*j%mod*a[i]%mod)%mod)%mod;
    }
    cout<<ans;
    return 0;
}

D. 宝石装箱

类似于背包？
此类计数题着手点可以从所有方案-不合法方案来得到合法的方案。
考虑用 $dp[i][j]$ 维护前 i 个箱子至少放了 j 个不合法的宝石的方案数。
但是由于内存的关系，需要滚动数组优化，可以进行类似于背包的操作
因为第 i 个箱子至少放了 j 个不合法宝石是用前面一个状态(dp[j-1]) 推出
所以在枚举放不合法宝石的时候逆序枚举就可以实现内存优化
然后合法宝石的排列是 $(n-i)!$ ，不合法宝石的排列是 $dp[i]*a[i]$
因为是至少放了 x 个不合法宝石，所以肯定存在重复的方案，就需要进行容斥
偶数加，奇数减！

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define mod 1e9+7
#define mo 998244353
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=8e3+5;

ll a[N],dp[N],f[N];

int main(){
    ll n,x; cin>>n; 
    f[0]=dp[0]=1;
    for(int i=1;i<=n;i++) cin>>x,a[x]++,f[i]=f[i-1]*i%mo;
    for(int i=1;i<=n;i++)
        for(int j=i;j>=1;j--)
            dp[j]=(dp[j]+dp[j-1]*a[i])%mo;
    ll ans=0;
    for(int i=0;i<=n;i++){
        if(i&1) ans+=mo-(dp[i]*f[n-i]%mo);
        else ans+=(dp[i]*f[n-i]%mo);
        ans%=mo;
    }
    cout<<ans;
    return 0;
}