OI康复训练 bzoj 2565: 最长双回文串 manacher

今天回顾了下manacher算法,然后顺便写了一下题。

我们求出res[x],代表以x为中点的回文串的一端多长。

然后lr[x]表示包含x点的回文串的最左端的中点,rr[x]表示包含x点的回文串的最右端的中点。然后我们相当于枚举中间的那个*,即可。
[crayon-5bef0dbdb7[……]

Read more

颓 《寄生獣》电影吐槽

很早之前就看过动漫版。比起之前唯一追过的几部动漫,数码和死神。寄生獣可以说让人耳目一新,剧情紧凑,设定合理,最关键是层次十分高主题,令人深思。比起来,数码宝贝就是打怪升级,天天开挂,儿时看也就那样了。数码tri,烂尾的十分出众…..没有情怀根本看不下去,豆瓣给2分觉得都多了,完全没有满足预期。死[……]

Read more

NCPC 2014 Train Passengers 签到题

签到题,按照题意模拟即可

NCPC 2014 Opening Ceremony 枚举 贪心

给一个序列,每次可以把一个数变为0,或者把所有数-1,问最少几次,所有数都小于等于0.

易得,我们一定是先进行操作1,再进行操作2.

我们把序列排序,枚举这个分界点,别这个数大的全直接删掉,小的就集体一次次-1,取一个最优解即可。
[crayon-5bef0dbdb8a1d743396[……]

Read more

NCPC 2014 Dice Game 签到题

4个数分别求和,谁大谁赢

NCPC 2014 Amanda Lounges 二分图染色

给一个图,有些边需要两端均为1,有些边两端均为0,有些边两端需要只有一个为1,问能不能实现,最少填多少个1.

对于两端都是1,和两端都是0的,我们暴力填上去,并且把相连的其他两端不同的顺上去。现在我们剩一些联通分量,边均为两端要求不同。我们对于每个联通分量任取一点,先后尝试填0,1,取最小值即[……]

Read more

OI康复训练 luogu 1983 车站分级 拓扑排序

这种水题先后读错n次题意,还链前没开好炸了内存,没想到邻接矩阵,QwQ。

OI康复训练 BZOJ2957 楼房重建

很有意思的一道题,看完题解还想了一小会才明白,不过代码很好写。

我们考虑一下,我们可以只看每栋楼的关于原点的斜率,只要一栋楼,其左侧没有斜率大于等于他的楼,那么他就是可见的。

我们考虑线段树,我们每个点维护两个量,ans代表只看这片区域最多可看见的楼的数量(是忽略这篇区域左侧对其影响的)[……]

Read more

OI康复训练 BZOJ1858: [Scoi2010]序列操作

开始一看,这不是线段树模板题么。然后,就掉坑里了。太久不敲线段树了,处理lzy标记的时候,没处理好下放的lzy和子树原有lzy的关系,然后WA了好久。

//代码写得好长啊,感觉太久不写了,写得蛮冗杂的