[SPOJ QTREE] Link Cut Tree引发的血案

最近在整理5月份和老毛子5V5的模板，发觉自己以前的LCT简直是圡得无法直视……
于是把wjmzbmr大大的模板down下来观摩了一番，写了个QTREE。原以为很快搞定的，没想到TLE到死。
上网找了一些LCT的代码交上去，发现都挺慢的……于是继续改，陆陆续续地加了点常数优化全都不顶事。最后不知道哪根筋抽了居然会想起在每个函数前加一个inline，然后它就过了……
原来根本原因是坑爹的SPOJ没有开O2 = =b
好在在搜集代码的过程中学习了好多新姿势，于是我的Splay模板又可以继续改进了。算是忙乎一晚上的一点成果吧。

Qtree
[传送门]
[Code]

感觉这个写法还是挺舒服的，于是以后就用这好了。
有空把剩下的QTREE再刷刷完吧~扎实点总没错的

update@2013.3.28 17:00

Qtree2
[传送门]
[Code]

感觉这个LCT写得姿势更好了……

Qtree3
[传送门]
[Code]

……和Qtree2没啥区别，改改就过了。注意一下范围大了10倍就好。

SRM568 1000pt

很变态的一个idea……
虽然看着题解(内含题目)写的但是还是很有收获
这个思路很好地诠释了brute-force的真正含义
一个50的vector传进来
先是用$$O(\frac{(2*x)!}{2^x})$$的搜索算法解决$$x \le 12$$的情况(x是vector里为-1的元素的数目)
然后对于$$x > 12$$的情况，由于-1是成对出现的，所以$$x \geq 14$$，然后$$2^{\frac{50 – 14}{2}} * 50^2$$搞定剩下的部分。
具体解法涉及到判定二分图的那种01染色，要把模型转化过去并且想到正解真是太不容易，难怪现场没有人搞出来。
更惨的是按照正解写要是太暴力，还是会TLE的。
mark一下。
[code]

TCO Round 1A

简直不能更惨，无法直视
500因为插件的原因resub * 2，直接从330分变到170分
然后还cha错了一次。以为那个是$$O(30000 * 30000 * 50^2)$$的，其实是$$O(30000 * \log(30000) * 50 ^ 2)$$的……
好好地记住$$\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + … + \frac{n}{n} = n \log n$$可以不……
1000，费用流没想到一是不够熟悉(努力不够)，二是没想到TC会出网络流(出乎意料)，三是智商和状态问题(自身客观因素)。一看到shi哥说费用流就马上反应过来怎么做了……欧蓝德啊。
感觉水平一年一年在提高，但是这种大比赛却一年比一年挫，真不知道说什么好……
确实不够努力吧，被屠也没什么好说的。
呵呵，终究是拿不到做出1000的勋章。
洗洗睡了。

NEERC2012 搞完纪念

……其实还有一题没搞完lol，但是人家解题报告都这么说了，就不搞了吧。

D的正则表达式转NFA纠结了好一会儿……自己写出来的WA到死，于是表达式解析的部分参照AC大妈的代码写了一下，获益良多啊。以前我写的表达式解析简直是…
子曰：学而不思则罔，思而不学则殆。保证一定时间的独立思考的前提下，多看看神人的写法是有莫大好处D。

I的那个神dp又WA过好一会儿，原因是枚举一个0~3的mask，脑抽地&3取高位……真是……