。。。。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说是裸搜+剪枝！！！？

卧槽。。。

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

day1过了之后。。。继续打酱油～～～
day2的题目太可怕了。。。我看了3题之后觉得估计跟去年的day2一样。。珠宝商之类的题目我显然是不会做的。。
于是我花半个小时想了想3道题目。。觉得第一题P点想法也没有。。骗点分算了。。花10分钟写了个裸搜走人。。
第二题20分还是朴素的出来的。。。于是骗了20分走人。。。
剩下的时间全在狂写第三题。。。第三题算法非常明显就是各种难写。。。我自以为自己代码能力很强就开始狂写。。
由于空间计算几何很多都不会。。我写了个高斯消元然后打算用方程流算一切东西。。。
然后搞啊搞啊搞啊搞啊搞啊搞啊搞啊搞啊

搞啊搞啊搞啊搞啊搞啊搞啊搞啊搞啊

搞啊搞啊搞啊搞啊搞啊搞啊搞啊搞啊

。。好不容易把k=1的写出来了。。。
然后试图写k>1的。。最后没时间了。。
。。。结果k=1的也写挂了。。最后只有20分。。
其它人观察数据的分就比我高很多

orz fhq,zej,zyc,jzt进队。。茗姐不要慌T_T。。。

放爷威武啊。。。哎。。本来他如果去年NOI进队了今年就无压力进队了。。。

。。。哎我发现我两次考试都是一个策略。。其他两题随便搞搞然后死做某一题。。。虽然说第一试这个策略还算成功但第二试就悲剧了。。究其原因还是因为第一试的数据结构我还是挺熟悉的。。但第二试的计算几何我就很烂了。。。。。哎。。。。

。。洲妹说合格分是240分。。果断严重不合格T_T。。。

嘛。。反正是打酱油的。。也没什么压力。。。。
。。。感觉这次考试的策略还是挺成功的吧。。。

先是花20分钟看了一下所有的题目。。第一题挺裸的。。
第二题由于TC上有类似的题目。。感觉上是Trie树+各种乱搞。。。
第三题直观上贪心看上去挺不错。。。
可惜的第一题是没有考虑有限的情况挂了20分。。。。然后就开始填第二题的坑。。

我当时想的做法是各种维护再套上并查集乱搞。。。本来想先写个60分的来对拍的。。

结果写了半天调不出来。。。
最后我非常悲剧的发现我一个递归函数里用了个static的数组。。。

搞好之后结果已经只剩一个小时了。。。没办法只好无视第二题去搞第三题了。。。
鉴于时间不够了。。。写了个裸贪心了事。。。
。。还好考试的时候比较冷静。。第二题调不出来也没有慌。。不然就完了T_T。。。

感觉上这次的题目很不CTSC。。。

第一题就不吐槽了。。第二题太恶搞了而且去做的性价比极低。。
我觉得我第二题处理的太烂了。。。我直接采取讨论流解决问题了。。。还有很多比较优美的维护方法T_T。。

最后光60分就写了7KB。。。。全是各种讨论+细节处理。。难看的要死。。。看来以后做题目的时候还是应该多想想。。
大体上感觉有思路了就直接敲是不行滴>_<。。。把细节也想想清楚就好了。。。。
。。。提交答案题观察数据才是王道啊！！！！！！！好XX的网格图T_T。。。。

见到了卢神牛。。。太威武了。。。鄙视所有人。。。
卢神牛就是第一排那个抢答帝。。鄙视fhq，鄙视wy鄙视twb鄙视所有人

fhq 强A前2题。。。要高一进队了!!!太猛了Orz!!!!!!!!!!!!

晚上跑出去跟twb和jzp吃KFC。。。神犇们的共同点就是能吃啊！！！twb连吃3个汉堡。。jzp吃了4个。。。
我一个就吃不动了囧。。。。

我看到wy让fhq请客。。说不是我出的题你能进队嘛？。。囧。。。