BZOJ5250: [2018多省省队联测]秘密袭击

原题链接

Solution

先看一份官方题解:秘密袭击simple

然而作为一个连FFT都不会的蒟蒻,又怎么可能在只有五小时,写完前两题的情况下做出这题呢?

所以是时候用暴力吊标算了。

考虑枚举每个点,算出这个点作为第k大时对答案的贡献。如果直接算,可能会算重。
我们可以定义:u的权值大于v当且仅当d[u]>d[v]||(d[u]==d[v]&&u>v),记为$u\rhd v$,即d相同时比较两点的编号。

如果枚举一个点u作为第k大点,那么可以从u开始进行树形DP。
设f[u][k]表示以u为根的子树,选了点u,并且选出的联通块中有k个点权值大于根。

有个很显然的转移:$Sum[u][k]=\sum_{i=0}^{k}f[v][i]*Sum[u][k-i]$
则$f[u][k+(u\rhd root)]=Sum[u][k]$,
这样的树形DP复杂度为$O(n^3)$(n,k同阶),总复杂度为$O(n^4)$。很不幸,不能吊标算

请看陈俊锟在WC2018讲课的三页PDF



用上面的方法,就可以优化这个DP,使一次树形DP的复杂度变为$O(n^2)$(具体看代码),总的复杂度为$O(n^3)$,再加上一点玄学优化(不要告诉我底层优化),就能过了,实测在LOJ上最慢的点为1.8s。

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define mo 64123
using namespace std;
int Next[4010],num,vet[4010],head[2018],f[1700][1700],d[1700],val,id,n,k,w;
void add(int u,int v)
{
    Next[++num]=head[u];
    head[u]=num;
    vet[num]=v;
}
inline int mod(int x)
{
    return (x>=mo)?x-mo:x;
}
void dfs(int u,int g[],int fa)
{
    if (d[u]>val||(d[u]==val&&u>id)) for (int i=1;i<=k;i++) f[u][i]=g[i-1];
    else for (int i=0;i<=k;i++) f[u][i]=g[i]; 
    for (int i=head[u];i;i=Next[i])
    {
        int v=vet[i];
        if (v!=fa) dfs(v,f[u],u);
    }
    for (int i=0;i<=k;i++)
        g[i]=mod(g[i]+f[u][i]);
}
int main()
{
    scanf("%d%d%d",&n,&k,&w);
    for (int i=1;i<=n;i++) scanf("%d",&d[i]);
    for (int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        val=d[i],id=i;
        int num=1;
        for (int j=1;j<=n;j++) 
            if (d[j]>val||(d[j]==val&&j>id)) num++;
        if (num<k) continue;
        memset(f[i],0,sizeof(f[i]));
        f[i][1]=1;
        for (int j=head[i];j;j=Next[j])
            dfs(vet[j],f[i],i);
        (ans+=f[i][k]*d[i])%=mo;
    //  printf("%d\n",f[i][k]);
    }
    printf("%d\n",ans);
    return 0;
}

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注