并查集 – Tgotp-Blog

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-5ad8d195a22e0[......]

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-5a[......]

Read more

3038: 上帝造题的七分钟2

花式错,太困了。。。

并查集 + 树状数组

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

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

c++代码如下:

 

A. Planning

A. Planning
time limit per test

1 second

memory limit per test

512 megabytes

input

standard input

output

standard output

Hele[......]

Read more

任务调度

任务调度
2.1 问题描述
有n个任务,第i个任务有自己的截止时间di和惩罚wi。完成一个任务需要一个单 位时间。我们期望任务i在截止时间di前完成,这样我们不会受到惩罚,否则我们会受 到wi的惩罚。 你的任务是找到一个调度方案,使得受到的惩罚总和尽量小。
2.2 输入格式
输入文件task[......]

Read more