<span>模拟100 题解</span>

A. 组合

将两个字符之间建边,

问题转化为一笔画,也就是欧拉路问题。

所以直接用dfs压栈的方法解决,注意正确使用当前弧优化。

 

void dfs1(int x){
	for(int i=head[x];i;){
		if(vis[i>>1]){
			head[x]=nxt[i];
			i=nxt[i];
			continue;
		}
		vis[i>>1]=1;
		dfs1(to[i]);
		stack[++top]=w[i];
		i=head[x];//如果忽略这句话 复杂度仍为E^2
	}
}

 

 

 

 

B. 统计

实际上消失的逆序对只产生在进行排序的点之间。

所以可以预处理出每个点与它后面的多少个点产生了逆序关系。

对于一个点,问题是将它后面的且权值不大于它的点产生的逆序关系删去。

似乎是一个二维点对问题,显然可以用链表维护然后就AC了。

因为每个点只会删一次,所以用线段树维护区间最值,

当递归到叶子节点或区间最值已经超过当前要求时$return$。

因为删除次数是合法的,其复杂度为$O(nlogn)$

 

 

 

C. 点亮

因为数据保证随机,深度不会很大。

注意到实际上并不关注每个点对之间的关系,

当每层祖先中亮着的点与暗着的点的大小关系确定,每个点的点权是确定的。

所以可以状压每层祖先的状态。预处理出每个点对于每个状态的点权。

设$dp_{i,j,s}$表示点$i$的子树中有$j$个被点亮,祖先链的状态为$s$。

之后可以直接作树上背包转移。

全部评论

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务