USACO的最新的月赛出来了。。本菜去被题虐了。。
我感觉第一题是将环拆成2份。。然后将每条线段。。如果跨越环的话，就只有一份。否则有两份。。然后去掉被包含的线段。。那么题目就变成了在这个2*C长 的大线段上取一些线段时其并集为线段切长度>=C。。那么就好办了。。维护两个指针扫描过去就可以了。。当左边界递增的时候右边界也是递增的。。
第二题好猥琐啊。。直接拆点构图然后bfs？似乎可以但是节点会有重合。。也就是说会有长度为0的边。。那么怎么半呢？我的办法是。。bfs不是维护一个 队列嘛。。我改成一个双端队列。。然后遇到为0的边加在头部，否则加在尾部。。就OK了。。这道题写的我脑子都大了。。。写了我3KB。。神牛一定有更简 单的办法。。我太菜了。。
第三题感觉最简单。。构造树的先序数列。。然后用一个线段树维护每个点到根节点的染色点的个数（就是有Cow的点的个数）。。然后那么一个点染色之后只影 响它的子孙的哪一段区间。。只要用标准的线段树就OK了。。
比赛嘛。。代码就不发了。。

       OK…我无论怎么搞都是TLE。。。这道题我是按离线和启发式合并的思想来做的。。
就是说在dfs的时候对每个点维护一个treap表示其中所有点的权值。。然后dfs的时候启发式合并。。就是把小的拆开加到大的里面去。。然后直接select就可以了。。
我用了Treap和启发式暴力拆合并的思想来搞这道题。。无论如何都悲剧。。
我都快疯了。。我一开始是用暴力指针的treap的。。后来自己写了个回收管理器。。没用。。又改用数组了。。照样TLE。。然后我又把树的结构有vector改成用数组的链表。。TLE。。然后我优化输入输出。。TLE。。。然后我改成前向星。。TLE。。然后我想到随机数可能很慢。。于是直接用随机打乱的1-n排列来作为key的值。。TLE。。
….然后我感觉treap不是随机的嘛。。就狂交拼RP。。交了N次。。快疯了。。然后有神牛告诉我插入和选K大改成的非递归的。。TLE。。然后他告诉我用SBT。。然后我直接撞墙了。。
还能有什么优化啊。。就不能用treap AC这道题么。。。
我去写写SBT了。。上次我写了个比treap还慢。。真想撞死。。
我好菜啊。。整天被题虐的。。一个下午搞的我内分泌都快失调了。。

这道题就是在一个方格矩阵中求出一个最大的空矩形。。
由于方格行列都《=1000.。。所以要使用o(nm)的算法。。
LRJ大神的学习指导上有讲。。
就是说一层层扫描过去。然后得出以该层为底个列能衍生多少。。
然后DP求出每列往左往右能延伸多少。。枚举每一个作为最高列。。更新答案。。是最优的了。。。
PS我写了个类。。感觉码代码手感不错。。
Code：

www.spoj.pl/problems/EXPRESS/
我看到这道题之后P思路也没有。。苦思冥想了半天。没想法。。于是就搁置了。。
到了半夜1点。。我突然反映过来。。用队列当结构有不同吗？直接倒过来推不久好了。。
首先根据逆波兰表达式构建表达式树。。然后先在队列里面放入树的根节点。。然后可以一步一步往后推。在我的程序中为了方便。。实现的队列是真正的队列倒过来。。
Code:



我在程序中使用了一个技巧就是说直接用一个指针来代替一个数组。。省了一半的内存。。增强了可读性。。。。。。

       XXX（为了保护隐私。。就不说是谁了。）给我发了个话说你爱不爱我。。然后我激动了。。然后Ta说是看到百度上无聊一个帖子说“在QQ上随便找个人发你爱不爱我。。贴反映图”。。然后我悲剧了。。
这种事情很无聊啊。。也很老套啊。。45年前就有人了。。不过我也一时兴起。。给几个女生还有几个男生发了。。然后回复很悲剧
1.。没鸟我。。离线的。。
2.。。你谁啊？
3.不爱
4.。。。。。（就是省略号。。） 。。。
一点意思都没有。。。现在的人真是没有幽默细胞。。哎。。
总算来了个有趣的。。。Ta说Ta也好喜欢我哦。。然后我说。啊。。你不要慌。。
Ta就说是耍我玩的。。还鄙视我说这么老套的东西也玩。。我晕菜了。。

    经过多天的下军旗。。。我充分领会了耍人的精神。。
干了很多很NB的事，比如。。用排长逼走别人的司令，并被工兵飞。。连续两次工兵装炸弹被飞。。然后那个傻X很得意过来砍我。。军长被我炸了。。然后又派司令。。又被我炸了。只吃了我个旅长。用连长跟别人玩双飞。。然后他没吃我这个。。他就挂了。。
下军旗真是一门很高深的学问啊。。最重要的一点是要明白别人跟你一样聪明甚至比你还要聪明。。而且很多时候要利用对方疑神疑鬼的想法。。耍他。。虐死他。。还有些时候要怀疑对方是不是在耍你。。现实中可以看表情。。网上只能靠直觉了。。你军旗下多了。。什么阴谋诡计你肯定是手到擒来了。。
还有的时候你就要男人一点。。敢杀敢砍。。不能太疑神疑鬼的。。。

就是给你N个人的基因串。。找出重复出现1次的有几个，2次的有几个。。。。n次的有几个。。。
由于基因串只有ACGT四个字符。。再加上长度小于20（。。就是微生物也不会只有20啊。。BS题目）。。
直接转换成4进制后用hash或者map都可以。。不过为了复习一下trie。。我就写了trie。。
甚至可以排个序再比较。。
代码就发图吧：



一开始放了打setmap。。纠结了半天。。
有的时候我写了个函数没有打到main里面。。就悲剧的调半天才发现

这道题大家应该很熟悉了。。。中文名叫食物链。。
我的算法比较抽象。。我发现对于这类题目。。根本没有必要维护多个并查集。。
并查集的思想就是只要是信息能够互相推导出来的。。全部放入一个集内。。
那么无论是1操作还是2操作。。都能够互相推出其间的种类。。那么就可以合并。。
如果x的类型-y的类型=1的话x能吃y。。那么这就是一个mod 3的加法。。
对每个x，F[x]记录其父亲P[x]记录其类型-去其父亲的类型mod 3。。。
那么路径压缩的时候可以顺便算出来。。
然后写程序更加简单，x=y就是x-y=0，x吃y就是x-y=1（以上都指相对的类型号。。）。。
写的时候只要写一个就可以了。。。
附上代码
依旧发图：

    我发现对于相当多的Oier。。boost库还是很陌生的。。但这个玩意是std库的扩充，被称为准标准库。。是优雅的泛型编程的典范。。非常NB。。推荐去看看。。。
www.boost.org/

怎么水的题目我都写。。我堕落了。。直接dfs就OK了。。