hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

全部文章 / 题解（共3篇）

Interesting Computer Game

题意：有n轮游戏，每轮你可以从二个数中选择其中一个数，求你选择数的种类最多为多少？思路：先离散化数据，然后我们将每一轮游戏当成一条边，如果成环了，则该环所以端点都能选择，且与环连通的点也能全部选择，你画个图就很容易理解了，由环往外扩散。如果连通块无环，则有一个端点无法选择。所以我们用并查集来处理数...

并查集

2020-08-03

1 587

最短路

题目：给一个连通图，每次询问两点间最短路。每条边的长度都是1。思路：看数据范围我们就知道普通的最短路是无法在规定的时间爬完的，所以我们盯上了长度为1，和m<n+100。如果是一颗树，我们可以用Lca求最短路，每一次查询为O(log(n))。我们已知这是一个连通图，所以我们可以用并查集生成最小...

最短路并查集 LCA

2020-07-08

0 684

边的染色

题意：小团有一张n个点，m条边的无向图G，有些边上已经被标记了0或1，表示它的边权。现在你需要给剩下的边标记边权为0或1，求有几种标记的方式满足：对于G中任意一个环，里面所有边的边权的异或值为0。环的定义如下：对于任意k（k≥2）个点{a1,a2,...,ak}，若对于所有的i<...

dfs 并查集

2020-04-23

0 688