牛客练习赛64_牛客博客

A、怪盗-1412

思路：对于单次出现的元素比如'4'，'2'，放在一起可以让序列1412的数量尽可能多，即被重复计算的次数多。
而对于出现两次的元素'1'，分别设为 $x_1,x_2$ 考虑均值不等式 $\frac{x_1+x_2}{2}\geq\sqrt{x_1x_2}$ ， $x_1+x_2$ 等于n，所以很明显，如果要 $x_1x_2$ 最大，就应该使 $x_1$ 和 $x_2$ 尽可能平均分配。
以样例1为例，合理的排布应当是：111444444441112222222。
转述自某位大佬 $\Rightarrow$ 传送门，大佬太强了。
Code：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
ll t,n,m,k; 
int main() {
    js;
    cin>>t;
    while(t--) {
        cin>>n>>m>>k;
        ll zuo=n/2;
        ll you=n-zuo;
        cout<<zuo*m*you*k<<endl;
    }
}

B、Dis2

思路：每个点的答案ans[v]就是它父亲的边的数量size[u]-1，减一就除了自己那条边，其它的边u的另外一个端点都是和v距离为2的点。
Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
int head[maxn],Next[maxn<<1],to[maxn<<1],tot;
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
ll ans[maxn],size[maxn];
void dfs(int u,int fa) {
    ans[fa]+=size[u]-1;
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i];
        if(v==fa) continue;
        ans[v]+=size[u]-1;
        dfs(v,u);
    }
}
int main() {
    int n,u,v;
    read(n);
    for(int i=2;i<=n;++i) {
        read(u),read(v);
        ++size[u],++size[v];
        add(u,v),add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i) printf("%lld\n",ans[i]);
}

C、序列卷积之和

思路：打表找规律，找出每个乘积的系数
打表代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
ll b[1000][1000];
int main() {
    int n;
    while(read(n),1) {
        memset(b,0,sizeof b);
        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)
        ++b[i][j];
        for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j) if(b[i][j]) {
            printf("b[%d][%d]=%lld\n",i,j,b[i][j]);
        }
    }
}

图片说明
以n==5为例进行化简可得：

$a_1(5a_1+4a_2+3a_3+2a_4+1a_5)+$

= = $a_2*2(4a_2+3a_3+2a_4+1a_5)+$

== = ===== $a_3*3(3a_3+2a_4+1a_5)+$

= = ============ $a_4*4(2a_4+1a_5)+$

===== ==================== $a_51a_5$
等于号是为了对齐的，很明显是前缀和（后缀和也行），这么明显的规律我就不写方程了。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5,mod=1e9+7;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
ll a[maxn];
ll b[maxn];
int main() {
    int n;
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = n; i ; --i) b[i] = (b[i + 1] + a[i] * (n - i + 1) % mod) % mod;
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        (ans += a[i] * i % mod * b[i] % mod) %= mod;
    printf("%lld\n",ans);
    return 0;
}

D、宝石装箱

知识点：dp、滚动数组、容斥原理
思路：反向递推，不直接求有多少符合的方案，而是先求出不符合要求的方案数，然后用总的方案数 $n!$ 去它就是最终结果。摘自大佬的题解 $\Rightarrow$ 神崎兰子。

1. $dp[k]$ 对应的二维dp是 $dp[i][k]$ ，表示前k个可能放错宝石的箱子（可能有些箱子没有限制，也就是不可能会放错，就不用考虑它）至少放错了i个的方案数。
2.很显然 $dp[i][k]=dp[i-1][k]+dp[i-1][k-1]*b[i]$ ，对应的一维就是 $dp[k]=dp[k]+dp[k-1]*b[i]$ ， $b[k]$ 表示有多少个宝石不能放到第k个箱子里,乘 $b[i]$ 表示第i个宝箱放错了宝石。
3.求完了这些之后，我们可以用 $n!$ 减去1个位置不合法的方案数，那么2个位置不合法的情况被多减了一次，需要加回来，3个位置不合法的情况又被加多了，再减掉。。以此类推，最终求出来的就是合法方案的总数（就是奇减偶加，常见的容斥系数）。
4.因为2个位置不合法（比如a和b）的情况在a不合法和b不合法的统计中都被减了一次，相当于被减多了。
Code：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
#define ll long long
const int mod = 998244353;
ll jc[8005];
ll a[8005],t[8005],b[8005],dp[8005];
int main(){
    ll n,i,j=0,k;
    cin>>n;
    ll tt=1;
    jc[0]=1;
    for(i=1;i<=n;i++)jc[i]=jc[i-1]*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];
    }
    ll res=jc[n];
    dp[0]=1;
    for(i=1;i<=j;i++)
    for(k=i;k;--k){
        dp[k]=(dp[k]+dp[k-1]*b[i])%mod;
    }
    for(i=1;i<=j;++i)
        res=(res+jud*jc[n-i]*dp[i])%mod,jud*=-1;
    cout<<(res+mod)%mod;
}