SSuryxin

分类

ACM个人赛题解(2) CF(1) dp(2) 图论(12) 数论(1) 笔记(5) 题解(29)

/ 注册

TA的专栏 3篇文章 0人订阅

3篇文章 1160人学习

全部文章（共4篇）

题解 | #Ancestor#

Ancestor 题目描述：给你两棵树A和B，点的编号从1到n，根结点是1,且每个点都有一个价值，现在给你k个点，选任意k-1个不同的点，分别求这些点在两颗树上的最近公共祖先fa, fb，问存在多少种情况满足A树上fa的价值大于B树上fb的价值思路1：前缀和 + 后缀和这是最简单好写的一...

dfs 思维 dfs序

2022-07-25

0 594

嗅探器

嗅探器题目描述：红蓝军队打演习，蓝军有两个信息中心，红军计划在某个中间服务器上安装一个嗅探器，来获得蓝军情报，而蓝军网络相当庞大，数据包从一个信息中心传到另一个信息中心不止一条路，你需要将嗅探器安装到哪个中间服务器才能保证所有数据包都能被捕获思路：转换一下其实是找割点，但不仅仅是割点，...

链式前向星 tarjan 缩点 dfs

2021-08-14

1 722

Cow Ski Area

Cow Ski Area 题目描述：滑冰，给你一个地图，值代表高度，你只能从高到低滑，相同高度的点可以随便滑，除了根据势能来滑动，你还可以建造传送门，可以无视传送机起点到终点的高度随便走，即双向的，众所周知，传送门很贵，你现在想知道最少造几个传送门使得任意一个点都可以滑到全图所有点思路： ...

链式前向星缩点 tarjan dfs 拓扑排序

2021-08-13

1 537

拓扑排序详解（梅开二度之dfs版判环 + dfs版按字典序输出拓扑路径 + dfs版输出全部拓扑路径

什么是拓扑排序？先穿袜子再穿鞋，先当孙子再当爷。这就是拓扑排序！拓扑排序说白了其实不太算是一种排序算法，但又像是一种排序（我是不是说了个废话qwq）他其实是一个有向无环图（DAG, Directed Acyclic Graph的所有顶点的线性序列，该序列需要满足两个条件：每个节点只能出现一...

dfs 拓扑排序图论字典序

2021-04-27

1 717