LuoguP4365 [九省联考2018]秘密袭击

https://zybuluo.com/ysner/note/1141136

题面

求一颗大小为\(n\)的树取联通块的所有方案中，第\(k\)个数之和。

\(n\leq1,667,k\leq n\)

解析

这题可以当作暴力踩标算的范本题目。。。（其实是因为高级算法嵌套起来有时不如暴力快)

但这个暴力我是想不到的。。。

我们可以单独讨论每个点对答案的贡献，并把大于该点权值的点权值设为\(1\)，其它设为\(0\)。接下来，我们就可以用\(O(nk^2\))的树形DP暴搞了。

但是，复杂度\(O(n^2k^2)\)会鬼啊。

于是换一种思路，枚举一颗树的根（讨论这个点对答案的贡献），统计儿子点在联通块中的结果，并强制取根到儿子点的路径。我们设\(dp[u][i]\)表示点\(u\)为联通块中第\(i\)个点的方案数，就可以转移了。

然而复杂度\(O(n^2k)\)???

但是我们只用枚举整颗树值排名\(\leq k\)的数作为根的情况，复杂度可以降为\(O((n-k)nk)\)。

这还跑过了。。。

Update:强制认为只能转移到 点权值大 或者 点权值相等且点编号大的点,否则会记重。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

#define re register

#define il inline

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=s;i>=b;i--)

using namespace std;

const int N=2100,mod=64123;

struct Edge{int to,next;}e[N<<1];

int d[N],h[N],dp[N][N],ans,cnt,n,k,w,root,tot;

il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}

il int gi()

{

  re int x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il void dfs(re int u,re int fa)

{

  if((d[root]<d[u])||((d[u]==d[root])&&u<root))

    fp(i,1,k-1) (dp[u][i+1]+=dp[fa][i])%=mod;

  else fp(i,1,k) (dp[u][i]+=dp[fa][i])%=mod;

  for(re int i=h[u];i+1;i=e[i].next)

    {

      re int v=e[i].to;

      if(v==fa) continue;

      dfs(v,u);

    }

  fp(i,1,k) (dp[fa][i]+=dp[u][i])%=mod;

}

int main()

{

  memset(h,-1,sizeof(h));

  n=gi();k=gi();w=gi();

  fp(i,1,n) d[i]=gi();

  fp(i,1,n-1)

    {

      re int u=gi(),v=gi();add(u,v);add(v,u);

    }

  fp(i,1,n)

    {

      root=i;tot=0;

      fp(j,1,n) if((d[j]>d[i])||(d[i]==d[j]&&i>j)) ++tot;

      if(tot<k-1) continue;

      memset(dp,0,sizeof(dp));

      dp[i][1]=1;

      for(re int j=h[i];j+1;j=e[j].next)

    {

      re int v=e[j].to;

      dfs(v,i);

    }

      (ans+=(1ll*dp[i][k]*d[i])%mod)%=mod;

    }

  printf("%d\n",ans);

  return 0;

}

巴特西

LuoguP4365 [九省联考2018]秘密袭击

https://zybuluo.com/ysner/note/1141136

题面

解析

最新文章

热门文章