「NOI2013」树的计数 解题报告

时间：2022-06-17 23:59:07

「NOI2013」树的计数

这什么神题「NOI2013」树的计数 解题报告

考虑对bfs重新编号为1,2,3...n，然后重新搞一下dfs序

设dfs序为\(dfn_i\)，dfs序第\(i\)位对应的节点为\(pos_i\)

一个暴力是枚举bfs的分层，然后检查合法性。

但是我们注意到一个事情，节点\(i\)与节点\(i-1\)是否在同一层，是不是具有独立性呢？

设\(s_i\)表示\(i\)与\(i+1\)是否在同一层，当\(s_i=1\)时，表示不在同一层。

那么

  • \(s_1=1\)，显然

  • 若区间\([l,r]\)是同层的，有\(dfn_L<dfn_{L+1}<\cdots<dfn_R\)

    这个注意一点，遍历边的顺序是一样的，因此bfs先访问的dfs一定也先

    这样可以得到

    若\(dfn_i>dfn_{i+1}\)，则\(s_i=1\)

    注意只有这两个条件可以强制为\(s=1\)，这个已经是全部了

    但是我们还需要统计\(s=0\)强制同一层的情况

  • 一个点dfs序后面的一个点，一定是它儿子或者它祖先的儿子，即

    \(dep_{pos_{i+1}}\le dep_{pos_i}+1\)

    设\(pos_i=a,pos_{i+1}=b\)

    如果\(a>b\)，那么就是普通的另外开了一颗子树，属于无用条件

    如果\(b=a+1\)，在条件2已经判断了

    如果\(b>a+1\)，说明一定产生了一个\(1\)的断层

    也就是\(\sum_{j=a}^{b-1}s_i=1\)

  • 注意到可能有点\(s_i\)还是没有处理，说明这个无所谓，产生的答案为\(0.5\)，因此答案为\(1+\sum s_i\)

处理的话前两个都好弄，第三个表示区间至少有一个\(1\)（区间的\(1\)已经被2统计了）

可以直接打差分tag，来区分一下位置上是0还是0.5

Code:

#include <cstdio>

#include <cctype>

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

const int N=2e5+10;

int n,d[N],b[N],dfn[N],pos[N],s[N];

int main()

{

    read(n);

	for(int x,i=1;i<=n;i++) read(x),d[x]=i;

	for(int i=1;i<=n;i++) read(b[i]);

	for(int i=1;i<=n;i++) dfn[i]=d[b[i]];

	for(int i=1;i<=n;i++) pos[dfn[i]]=i;

	++s[1],--s[2];double ans=1;

	for(int i=2;i<=n;i++)

		if(dfn[i-1]>dfn[i])

			++s[i-1],--s[i],++ans;

	for(int i=2;i<=n;i++)

		if(pos[i-1]+1<pos[i])

			++s[pos[i-1]],--s[pos[i]];

	for(int i=1,j=0;i<n;i++) j+=s[i],ans+=(!j)?0.5:0;

	printf("%.3f\n",ans+1);

	return 0;

}

2019.4.13

相关文章