牛客练习赛64题解

  • 时间:
  • 浏览:
  • 来源:互联网

题目链接

A.怪盗-1412

题意:
n1m4k2有n个1,m个4,k个2
1412组成一个序列问最多能有多少子序列是1412
题解:
11112222111144摆成11…1122…2211…1144……的样子
使这样能使得每个数都有贡献
1根据和一样,两数差最小乘积最大可以知道平分1即可
四个位置个数相乘

#include<bits/stdc++.h>
using namespace std;
int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        long long n,m,k;
        scanf("%lld%lld%lld",&n,&m,&k);
        printf("%lld\n",(n/2)*m*k*(n-n/2));
    }
}

B.Dis2

题意:
2给一棵树,问每个点有多少和他距离为2的点
题解:
2对于每个点来说,距离为2的点,就是这个点的子节点的子节点
统计一下这个点相连的点,每个点的度数
但由于是双向边,需要去除自己的贡献
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll ans[maxn];
vector<int> g[maxn];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int u=1;u<=n;u++){
        ll ans=0;
        for(auto v:g[u]){
            if(v==u)continue;
            ans+=g[v].size()-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}


C.序列卷积之和

题意:
n给一个长度为n的数组
l=1nr=lni=lrj=iraiaj mod 1e9+7求\sum_{l=1}^n\sum_{r=l}^n\sum_{i=l}^r\sum_{j=i}^ra_i*a_j~mod~1e9+7
题解:
n<=2e5n<=2e5,很大
暴力求解就不用想了,考虑一下怎么样化简
自己举个例子感受一下,不要太多数
41234我这里举4个数,1,2,3,4
1然后先走前两个确定,结果是1
然后第一个不变,第二个累加区间加
11+12+22得到1*1+1*2+2*2
11+12+13+22+23+33再变一次1*1+1*2+1*3+2*2+2*3+3*3

11+12+13+14+22+23+24+33+34+441*1+1*2+1*3+1*4+2*2+2*3+2*4+3*3+3*4+4*4
1这样第一个累加为1的时候跑完了
我们可以化简一下
1(1+1+2+1+2+3+1+2+3+4)1*(1+1+2+1+2+3+1+2+3+4)
2(2+2+3+2+3+4)2*(2+2+3+2+3+4)
3(3+3+4)3*(3+3+4)
444*4
然后可以想象一下,或者大概再往后下一点就能发现
2第一个累加为2的时候,其实就是这式子里的后三个
3为3的时候是后两个
这规律就找到了
西我们只要把这些括号里的东西算出来和数相乘,最后求一下后缀的后缀就是答案了
ini+1括号里的可以用个数算,我们可以发现第i个数一共有n-i+1个
然后我们用后缀跑一下每个括号里每个数的个数乘对应的值
西sumi这样括号里的东西算出来了,假设是sum_i
i=1naisumi1\sum_{i=1}^na_i*sum_i就是第一个累加为1时候的结果
i=2naisumi2\sum_{i=2}^na_i*sum_i就是第一个累加为2时候的结果
1n所以这个时候我们就需要求一下后缀的后缀算出来第一个累加为1到n全部的和
便但其实有更简便的方法,我们直接记个数
iaisumii假设下标为i的a_i*sum_i我们用的次数应该是i次
i1n所以i从1到n直接将每个值乘他的贡献次数就是最终答案

如果你感觉这样的规律不好看出来
那你可以考虑,去掉两层内部的累加,用代码输出一下找一下规律
这个规律应该也很好看出,其实就是我在上面说的规律
但是会更加直观
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
ll Pow(ll a, ll b){
	ll ans = 1;
	while(b > 0){
		if(b & 1){
			ans = ans * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
ll a[maxn],s1[maxn];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=n;i;i--)
        s1[i]=(s1[i+1]+a[i]*(n-i+1)%mod)%mod;
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans=(ans+i*a[i]%mod*s1[i]%mod)%mod;;
    cout<<ans;
    return 0;
}


D.宝石装箱

题意:
nnn个宝石放进n个盒子
iai如果第i种宝石不能放到a_i盒子有多少种方案
mod 998244353mod~998244353
题解:
i如果是直接写,我们需要考虑对于第i种宝石
aia_i盒子是否已经被放了宝石,最后得出的会是两种情况
我们很难统计这两种情况
那就倒着写,先随意放,看看其中有多少不合法的方案
n!总方案很好求,就是n!
现在需要求的是不合法的方案
不合法的方案就是某个盒子放了不该放的宝石
i我们需要统计最后有用的就是i个盒子放了不该放的宝石的方案
ii但是恰好i个我们很难求出,我们可以用至少有i个盒子放了不该放的宝石
i如果是至少i个盒子,那么肯定有重复的方案
这时候就可以用的容斥原理了,奇数加偶数减,容斥原理就不多说
i现在开始开始说怎么求至少i个盒子放了不该放的
其实就是统计出哪几个位置,有几个不该放的宝石
不该放的宝石个数,就是这一个点的方案数
对于多个位置就是相乘起来
由于统计的是需要将所有宝石放入,对于其他宝石也需要进行放入
那么就是乘剩余没有选择的个数的阶乘,我们已经选择的是确定不合法的
使01+这一过程我们可以使用01背包+滚动数组实现
dp[j]=dp[j1]a[i]状态转移很简单,就是dp[j]=dp[j-1]*a[i]
求出来的是我们确定不合法的盒子数
然后剩下的就是把他乘上对应的阶乘形成完整方案,然后进行容斥去重即可
最后用总数减去这个算出来的数
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll fac[maxn],dp[maxn],a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;cin>>n;fac[0]=1;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        a[x]++;
        fac[i]=fac[i-1]*i%mod;
    }
    dp[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j>=0;j--)
            dp[j+1]=(dp[j+1]+dp[j]*a[i]%mod)%mod;
    ll ans=fac[n],res=0;
    for(int i=1,p=1;i<=n;i++,p=-p)
        res=(res+fac[n-i]*dp[i]*p%mod+mod)%mod;
    cout<<(ans-res+mod)%mod;
    return 0;
}

本文链接http://element-ui.cn/news/show-340087.aspx