Blog

I use blog to record something.

【种类并查集】食物链

题面 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物...

Haoyu Deng
Haoyu Deng

luogu P1525 关押罪犯

题面 S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,...

Haoyu Deng
Haoyu Deng

【lct】bzoj 2959 长跑 (LCT 动态维护边双连通分量)

题面 某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。 为了让同学们更好地监督自己,学校推行了刷...

Haoyu Deng
Haoyu Deng

点、边双联通分量

点、边双联通分量 小知识点,记一下 点双联通分量 性质 任意两点间至少存在两条点不重复的路径等价于图中删去任意一个点都不会改变图的连通性,即BCC中无割点 若BCC间有公共点,则公共点为原图的割点 无向连通图中割点一定...

Haoyu Deng
Haoyu Deng

【lct,最小生成树】luoguP4172 [WC2006]水管局长

题面 SC 省 MY 市有着庞大的地下水管网络,嘟嘟是 MY 市的水管局长(就是管水管的啦),嘟嘟作为水管局长的工作就是:每天供水公司可能要将一定量的水从 x 处送往 y 处,嘟嘟需要为供水公司找到一条从 A 至 B 的水管的路径,接...

Haoyu Deng
Haoyu Deng

【lct】[HNOI2010]BOUNCE 弹飞绵羊

题面 某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往...

Haoyu Deng
Haoyu Deng