【LOJ】 #2665. 「NOI2013」树的计数

题解

我们统计深度对于bfs序统计，树结构出现分歧的地方必然是BFS序的最后一段，这个最后一段同时还得是dfs序上连续的一段

如果不是bfs序的最后一段，那么必然下一层会有节点，如果树结构分歧了，那么dfs序是不一样的

如果不是dfs序上连续的一段，如果分歧那么bfs序会改变。。。

好的，知道了这两点，这题就非常可做了

我们记录一下u点在dfs序中的位置和bfs序中的位置，从前往后扫bfs序

假如u在BFS序中前一个点是v，如果v的dfs序在u的后面，说明换了一层，深度+1

如果v的dfs序正好是u的前一个，看看维护的那段连续区间长度为L，从后往前数L个点是不是u，如果是的话，那么u可在同层，可作为v的儿子，各占一半，深度+0.5

代码

#include <bits/stdc++.h>

//#define ivorysi

#define enter putchar('\n')

#define space putchar(' ')

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define mo 974711

#define MAXN 200005

#define pii pair<int,int>

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

int a[MAXN],b[MAXN],posa[MAXN],posb[MAXN],L,R;

bool vis[MAXN];

db ans = 2.0;

void Solve() {

    read(N);

    if(N == 1) {out(1);enter;return;}

    for(int i = 1 ; i <= N ; ++i) read(a[i]),posa[a[i]] = i;

    for(int i = 1 ; i <= N ; ++i) read(b[i]),posb[b[i]] = i;

    vis[1] = vis[2] = 1;

    L = 2,R = N + 1;

    for(int i = 3 ; i <= N ; ++i) {

	if(posa[b[i]] <= posa[b[i - 1]]) ans += 1;

	else if(posa[b[i]] == posa[b[i - 1]] + 1) {

	    if(N - (R - L - 1) + 1 == i) ans += 0.5;

	}

	vis[posa[b[i]]] = 1;

	while(vis[L + 1]) ++L;

	while(vis[R - 1]) --R;

    }

    printf("%.3lf\n",ans);

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

今天真是……比昨天还效率低下……