牛客练习赛64

怪盗

链接：https://ac.nowcoder.com/acm/contest/5633/A

题目描述

一个长度为n+m+k包含n个数字1，m个数字2和k个数字4的数组，最多可能有多少个子序列1412？如果一个序列是数组的子序列，当且仅当这个序列可以由数组删去任意个元素，再将数组中的剩余元素按顺序排列而成

solusion

有一个数学规律，相同周长的矩形，正方形面积最大，因此我们可以将1分成两个最接近 整数相加，2和4都只取一个，因此2放在前半1后，4放在后半1后，所求答案就是 ，并且a+b=n
如果n为偶数 a=b=n/2；
如果n为奇数 a=n/2+1;b=n/2;

#include <bits/stdc++.h>
using namespace std;
long long n,m,k,t;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        long long s=0;
        if(n%2==0)
            s=(n/2)*(n/2)*m*k;
        else
            s=(n/2+1)*(n/2)*m*k;
        cout<<s<<endl;
    }
}

B-Dis

链接：https://ac.nowcoder.com/acm/contest/5633/B

题目描述

给出一颗n{n}n个点n−1{n-1}n−1条边的树，点的编号为1,2,...,n−1,n{1,2,...,n-1,n}1,2,...,n−1,n，对于每个点i(1<=i<=n){i(1<=i<=n)}i(1<=i<=n)，输出与点i{i}i距离为2{2}2的点的个数。 两个点的距离定义为两个点最短路径上的边的条数。

solusion

先将边用vector存储起来，在对每一个点进行遍历，如果e[i][j]!=i说明没对遍历的那个点进行重复相加，然后再对e[i]中的每个点计算其长度，相加并减去无向图反向的边

#include<bits/stdc++.h>
using namespace std;
int n,u,v,s;
vector<int> e[200005];
int main()
{
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        s=0;
        for(int j=0;j<e[i].size();j++)
        {
            if(e[i][j]!=i)
            s=s+e[e[i][j]].size()-1;
        }
        cout<<s<<endl;
    }
}

C-序列卷积之和

链接：https://ac.nowcoder.com/acm/contest/5633/C

题目描述

给出一个长度为n的数组a1,a2,...,an，计算并输出。

solusion

本题需要找规律
拿示例1
n=4;
a[]={6,7,8,9}
sum[]={6,13,21,30}
ss[]={6,19,40,70}
s1=a1 * (a1+a1+a2+a1+a2+a3+a1+a2+a3+a4)
s2=a2 * (a2+a2+a3+a2+a3+a4)
s3=a3 * (a3+a3+a4)
s4=a4 * a4
通过倒着求
pre=a4
s=a4 * pre+a3 *(pre+2a3) +a2 * (pre+2a3+3a2)+a1 *(pre+2a3+3a2+4a1)

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[200005],sum[200005],ss[200005];
const int mod=1e9+7;
long long s=0,pre=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        sum[i]=(sum[i-1]+a[i])%mod;
        ss[i]=(ss[i-1]+sum[i])%mod;
    }
    for(int i=1;i<=n;i++)
    {
        pre=(a[i]*ss[n-i+1]%mod+pre)%mod;
    }
    for(int i=1;i<=n;i++)
    {
        s=(s+pre)%mod;
        pre=(pre-a[i]*ss[n-i+1]%mod+mod)%mod;
        cout<<pre<<endl;
    }
    cout<<s;
}