牛客练习赛64 题解

A：怪盗-1412
题目描述
一个长度为n+m+k包含n个数字1，m个数字{2}2和{k}k个数字4的数组，最多可能有多少个子序列1412？
如果一个序列是数组的子序列，当且仅当这个序列可以由数组删去任意个元素，再将数组中的剩余元素按顺序排列而成。
思路
将序列排列成111444441111222222,这样可以得到最大化的子序列数量，答案为

m*k*(n/2)*(n/2+(n&1))

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

void solve(){
    ll n,m,k;cin>>n>>m>>k;
    cout<<m*k*(n/2)*(n/2+(n&1));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

B：Dis2
题目描述
给出一颗n个点n−1条边的树，点的编号为1,2,...,n−1,n，对于每个点i(1<=i<=n)，输出与点i距离为2的点的个数。
思路
两个点的距离定义为两个点最短路径上的边的条数。
与每个点距离为1的点为这个点的度数。对于每个点u，枚举和它有边相连的点v，点v对点u的贡献为与点v距离为1的点的个数减去1
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
vector<int>v[N];
void solve(){
    int n;cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y;cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(int i=1;i<=n;i++){
        int ans=0;
        for(int j:v[i]){
            ans+=v[j].size();
        }
        cout<<ans-v[i].size()<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

C：序列卷积之和
直接推出公式比较困难，打表找一下规律

容易知道，记录一下 后缀即可
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll sum[N],a[N];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        a[i]=x;
        sum[i]+=(sum[i-1]+x*(n-i+1));
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=(sum[n]-sum[i-1])%mod*i%mod*a[i];
        ans%=mod;
    }
    cout<<ans%mod;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

D：宝石装箱
题目描述
n颗宝石装进n个箱子使得每个箱子中都有一颗宝石。第i颗宝石不能装入第a[i]
个箱子。求合法的装箱方案对{998244353}998244353取模。
思路
两种装箱方案不同当且仅当两种方案中存在一颗编号相同的宝石装在不同编号的箱子中。

设g(x)表示选出x个箱子装不合法的宝石的方案数。求g（x）时采用滚动数组优化空间，其实就是个01背包每个可选可不选，即：

至少有x箱子不合法为：

根据容斥定理即可计算出答案(奇加偶减）
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e4+5;
const ll mod = 998244353;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll f[N],dp[N];
int n,a[N];
void solve(){
    f[0]=f[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;a[x]++;
    }
    dp[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j>=0;j--)
            (dp[j+1]+=dp[j]*a[i])%=mod;
    ll ans=0;
    for(int i=0,p=1;i<=n;i++,p*=-1)
        ans=(ans+p*dp[i]*f[n-i]%mod)%mod;
    ans=(ans+mod)%mod;
    cout<<ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}