[ABC274C] Ameba 题解

题目传送门

题目大意

你做了变形虫的观察记录。

刚开始只有一个变形虫，编号为 $1$。

有 $N$ 条按时间顺序排列的观察记录，第 $i$ 条观察记录为编号为 $A_i$ 的变形虫分裂并消失，产生了 $2$ 个新的变形虫，分别编号为 $2i,2i+1$。

在这种情况下，变形虫 $A_i$ 被称为变形虫 $2i,2i+1$ 的父母。

对于第 $k=1,\dots ,2N+1$ 个变形虫，求 $1$ 号变形虫是 $k$ 号变形虫的第几代父母？

思路

前置：父亲结点表示法、DFS。

把每个变形虫看作二叉树上的一个结点，那么，从每个结点开始向上找最终都可以回到 $1$ 号结点。

所以，可以使用父亲节点表示法，$\text{fa[k]}$ 表示变形虫 $k$ 的第一代父母为 $\text{fa[k]}$。这样，对于每个结点进行一次 DFS，同时统计经过父母数即可。

优化

不排除数据中会出现极端情况（其实数据很水，裸的 DFS 就过了）：大部分结点都在一条链上，导致一条链重复查询而 TLE。可以使用记忆化搜索，再开一个数组 f[k]，赋初值为 $-1$，如果经过的某个结点已经在之前的查询中查到了，即 f[k]！=-1，那么就直接返回 f[k] 中的结果，或者记录，节省时间。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
const int N=800005;
using namespace std;
int n,a[N];
int fa[N],f[N];
int findfa(int x){
	if(x==1) return 0; //如果找到爹了
	if(f[x]!=-1) return f[x]; //记忆化搜索
	f[x]=1+findfa(fa[x]);
	return f[x];
} 
int main(){
	scanf("%d",&n);
	memset(f,-1,sizeof(f));
	fa[1]=1,f[1]=0; //注意初始化
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		fa[i*2]=a[i],fa[i*2+1]=a[i]; //记录父亲
	}
	for(int i=1;i<=2*n+1;i++)
		printf("%d\n",findfa(i));
    return 0;
}

---

赛时 AC 记录