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

时间:2021-05-28 20:50:01

题解

我们统计深度对于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;
}

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