并查集 – Tgotp-Blog

4631: 踩气球

对于每个点维护一下这个点能向右跑的最远距离,这个很显然能用并查集维护。

然后考虑每个点建一棵线段树,然后根据左右两点的关系合并线段树。

那么在记录的最远距离左边的点一定都是已经可以加入答案的点,删去即可。

c++代码如下:
[crayon-5bc530d329c104789494[......]

Read more

3551: [ONTAK2010]Peaks加强版

双倍经验。。。

这题是去掉强化版的在线版本

也是noi2018d1t1的强化版qaq

在并查集树上主席树合并即可,查询时用倍增就好了.

详细描述可以参照noi2018d1t1的题解qaq

c++代码如下:

Read more

NOID1T归程

时隔一个月左右更新一下博客...

看到这题很容易想到反向SPFA,然后可持久并查集搞搞啥的。

(离线那分显然是送的。。。

但是该题会卡SPFA(貌似),且可持久化并查集我的时间复杂O(n log^2 n)

所以光荣的只拿了60分滚粗qaq...

上面算法又臭又难[......]

Read more

2342: [Shoi2011]双倍回文

并查集 + manacher

看到回文串很容易想到了马拉车

首先发现双倍回文既然是4得倍数,那么其中心一定是添加得符号。

同样,他的一半得中心也一样是添加得符号。

考虑枚举双倍回文中心。

先处理出他的回文串长度,因为其左右对称,那么只用考虑他的左边最长回文串长度。[......]

Read more

1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

首先化成max(|(a.x+a.y - (b.x + b.y)|,|a.x-a.y - (b.x-b.y)|);

然后对于x维护一个滑动窗口,对于y用set维护即可

c++代码如下:

 

1202: [HNOI2005]狡猾的商人

清一色的并查集,我写了一个区间dp。

令f[i][j]代表i-j的区间话费,枚举断点k来看是否可以得到i-j的话费,若i-j本身存在价值,就比较,如果不一样输出false直接返还。

如果一直没有false就输出true

c++代码如下:
[crayon-5bc530d32b7d1[......]

Read more

1601: [Usaco2008 Oct]灌水

一开始想了各种奇奇怪怪的算法,最后都死于自己发现都错了题(鬼知道我在想些什么)

最后还是想到了最小生成树,当然不一定是一棵,可能是多颗树, 只要保证两个点间的距离小于这两个点所在集合的最小值就可以合并,然后乱搞搞就好了。

----我很沙茶的在判断这里错了。。。

c++代码如下:[......]

Read more

F. High Cry

F. High Cry
time limit per test

1 second

memory limit per test

512 megabytes

input

standard input

output

standard output

[......]

Read more

1064: [Noi2008]假面舞会

对于每个人看到的人,把他看到的连向自己一条-1的边,对看到的人连一条1的边

然后跑dfs,可以发现,会构成链和环两种形式,环的话所有可能性是其的因子,那么多个环最大值就是最大公约数,

链的话直接拼接在一起就搞定了(可以加并查集优化。。。)。

c++代码如下:
[crayon-5b[......]

Read more

3038: 上帝造题的七分钟2

花式错,太困了。。。

并查集 + 树状数组

暴力修改就好了,对于0 或 1就用并查集并在父亲上。

树状数组都忘得差不多了,再温习一遍。。

c++代码如下: