。。。。。比赛的时候状态不是很好。。。

首先看到第二题觉得就是一个傻叉构造？于是乱写了一个构造。。。结果是错的。。。。

然后苦思冥想想出了第一题。。。

接下来3个小时都在写第三题。。。结果还是没写出来。。。估计也就是30分吧。。。。

结果居然RP好有rank4。。。。。就这么签掉了。。。。

。。。。接下死宅族的颓废生活开始了！！！

RT

http://www.zybbs.org/JudgeOnline/problem.php?id=2009

既然说要除草就随便找道题目吧。。。
首先考虑怎么做。。。。为了方便我们看成n<=50,m=3
那么只有3列。。逐格转移的话。。
给每个格子标上它是第几个经过的。
###

#**

*M.

a…

#是用过的点,M是当前点，*是有影响的点。
由于只要每个数x都跟x-1和x+1相邻，就必然能组成一条路径。
所以我们只需要记录*的数是什么，和这个分界线上*中的数与未用过的点相邻情况就可以了。
这样n=25就T了。。。
可以发现很多状态都是打酱油的。。
注意到这个状态已经唯一决定了已经用过的数。那么开个bitset保存用过的数。转移的时候不能用已经用过的数。
状态数就狂减了。。。就能过了

代码：
http://www.ideone.com/oEJNZ

。。。。虽说即将会考了。。我还是过着颓废的生活T_T。。。。

。。。其实这题可用块状树的。。。
考试的时候我难道在梦游么。。。
3KB AC不解释。。。。

。。。。ZJOI day2继续打酱油～～～～

考试的时候我一开始花了半个小时阅读了一下三道题目，初步的想法是第一题应该是某种dp，第二题应该是费用流，第三题应该就是树链剖分。

我当时评估了一下，觉得费用流容易写并且第二题也很好对拍，就把第二题的费用流写了。
接下来我权衡了一下，觉得树链剖分说不定是个坑，先做第一题吧。。于是我研究了10分钟。。。想出了n^3怎么做。。又研究了20分钟。。。大体上想出了n^2怎么做。。但实现的时候各种囧。。幸好我写了个对拍在那边狂拍。还是拍对了。。。
接下来我还剩2个半小时，我觉得第三题就算不树链剖分也有70分。。树链剖分说不定写挂了就0分了。。不过我权衡了一下，觉得树链剖分我几乎写过10多次了。。应该还是写的出来的。。反正线段树是必须的。。。如果最后一个小时还是完全悲剧状态就放弃打暴力也来的及。。于是我先写了个10分的暴力来对拍。。接着敲树链剖分。。。。对拍拍了半天。。这题题意也非常囧。。。不过好歹也写对了。。。。。

总的来说我也吸取了APIO的教训。。。。全部都对拍了。。。
尽管第一题第一眼完全没有思路。。但还是认真去想也做出来了。。。
其实我最大的感触是。。。如果你不在乎的话。。自然能考好。。但考好后也没什么开心的了。。

。。。。。我能不能去NOI打酱油就在此一举了。。。 
不过也无所谓了。。。现在感觉已经没有原先那种对OI的感觉了。。

PS。。玩了clannad。。各种泪奔。。

http://www.zybbs.org/JudgeOnline/problem.php?id=1171
4个月以来第一次写BZOJ的题解。。
首先感谢炫教告诉我这题的做法。
这个做法是nLogn的。。。我不知道rank前3的貌似On的做法是怎么做的。。。
如果您知道跪求圣解啊。。。

考虑dp优化的做法。。我们需要支持一个数据结构。。

支持：
(1):插入一个代权线段
(2):询问与一个线段相交的线段中权值最小的线段
(3):删除一个线段(删除的顺序跟插入是一样的)

注意到线段的失效时间是递增的，所以可以用单调队列维护一个线段集合的最小值并支持删除。
使用线段树解决问题，每个节点保存一个单调队列，这个队列保存所有覆盖这个节点并且不覆盖这个点的父亲的线段。
那么插入只要插入到logn个单调队列里面。
同时每个点维护minV表示这个节点的所有子孙的单调队列的最小值的最小值。
那么当一个线段失效的时候。只要对包含这个线段的那logn个节点维护单调队列并更新它们祖先的minV
询问的时候用minV即可。

PS。由于deque内部是用块链实现的，所以初始空间很大，用deque会直接MLE，用list反而就能过。

考场没能写出来。。我非常的不爽>_<。。。

于是我又写了一下。。
我首先阅读了空间几何的书籍。。进行了系统的学习。

当时我只知道空间中平面的表达式是A*x+B*y+C*z+D = 0。

那么使用解析流。。还是能应付题目中所需要的计算的。

但是。。解析流非常恶心。。。导致我写的时间巨长最后还因为一个小bug爆掉20分。
不过解析流有一个好处是可以直接写个gauss消元来搞。那么只要贴方程就行了
空间几何小贴士：

平面有两种表达法，解析式和点法式，

一个平面上的点p1和平面的法向量n决定一个平面。

平面上任意点必然满足(p-p1).dot(n) = 0。。

因为向量p-p1必然与n垂直，dot表示点积。

使用点法式之后。。适当使用点积和叉积。。就能轻松的应对题目中需要的各种计算了。。
我最后写了12KB。。。不过跑的还比较快，所有点都能在几秒内跑出来。。
计算多边形并的时候，使用最暴力的枚举所有关键x点，暴力计算即可。

投影到2维的时候，令d1 = (p2-p1)/(|p2-p1|)，d2 = n.det(d1)。。
那么d1和d2就是平面上的一组垂直的单位向量，对于平面上的某点p,p-p1必然可以表示为x*d1+y*d2，

令x=(p-p1).dot(d1) , y = (p-p1).dot(d2)即可。
这样就投影完毕了。

剩下的工作都比较简单，使劲写就行了。

。。。惨挂。。。

。。挂成傻逼。。。

。。第一题似乎是SGU原题。。我凭记忆写了个式子（其实是错的）。。但是过了样例和pretest。。。于是我很happy的就不管了。。

。。。结果只有80分。。。
第二题我看到题目之后觉得就是代码能力题么。。。我似乎写过类似的题目(NEERC某题)。。。于是我很happy的写啊写啊写啊。。写了7KB就走人了。。。事实证明我考虑的不够仔细。。。结果只有10分wlgc。。。
剩下来我花3个小时去想第三题。。。
想啊想啊想啊想啊想啊想啊

想啊想啊想啊想啊想啊想啊

想啊想啊想啊想啊想啊想啊

想啊想啊想啊想啊想啊想啊

想啊想啊想啊想啊想啊想啊

交了个暴力骗了10分

。。最后pyc说是裸搜+剪枝！！！？

卧槽。。。

最后果断悲剧。。。
垫底男毫无压力