月日は百代の過客にして、行かふ年も又旅人也。
或许会把曾经写的kiso.tex编译好放上来，不过或许不会了。
当然，也有可能这儿会记录有关化学竞赛的内容，敬请期待。
この大空の 広い世界の どこかでまた 笑い 泣いた
そして人は それぞれの想い 一つ一つ 紡ぎだすよ
遠ざかる友よ また出会おう だから別れよう
永遠に続く 誰かとの約束
君影 おぼろ月夜 捧げし日 厭わず
万世や 八又の獅子 天武舞い 煌めく
太古の 詩よ友よ 伽羅に 臨む花
されども 風は涼し 君の髪 揺らすよ
風を感じて、歩き出せ、夜明けは近い
開け行く空 僕らはまた 旅の途中。
这个博客将在NOI2008之后一两个月内废弃，至少不再更新OI相关的事情。有关OI的东西也只会把一些总结和经验放上来罢了。
块状链表实在难写，反正没一次写对的，于是我用Treap来Cheat呵呵，其实Treap的话呢，插入删除和打印操作都是O(nlogL)（n：操作数的长度，L：总长度）的，比起块状链表华丽丽的O(sqrt(n))来啊那可是大大的不美，所以在时间上的差距也很明显（6倍啊OTZ），不过还是AC了，嗯。话说Treap比起朴素的数组实现来说，最大的优势在于LogL上。如果把LogL看成是常数，那么这个插入删除的总复杂度几乎可以看成是O(L)的，其实还是很好的，因为单单把数据读进去就要O(L)的复杂度。朴素的实现，插入或删除是O(n+L)的，积累起来最坏O(L^2)，而Treap来说最坏情况期望是O(LlogL)，虽然很Cheat，不过还是很有内涵的Cheat。
最近写Treap写得越来越顺手，估计真正比赛的时候如果遇上Treap的题应该也能写对。
从思想上来说呢，把序列存在Treap里头确实不太自然。其实很简单，只要把序列想象成一个个离散的元素加上一个位置标号，然后按照位置标号排序得到的有序队列就可以了。然后按照那个位置标号建立平衡树，就能在平衡树上实现串的操作了。
于是把程序和时间比较贴出来，asdf是HQM的标程。
开始测试 asdf
正在编译 asdf.editor ...成功
正在测试 asdf.editor.0(editor0.in)... 正确 0.308秒 得分: 10
正在测试 asdf.editor.1(editor1.in)... 正确 0.003秒 得分: 10
正在测试 asdf.editor.2(editor2.in)... 正确 0.072秒 得分: 10
正在测试 asdf.editor.3(editor3.in)... 正确 0.085秒 得分: 10
正在测试 asdf.editor.4(editor4.in)... 正确 0.085秒 得分: 10
正在测试 asdf.editor.5(editor5.in)... 正确 0.047秒 得分: 10
正在测试 asdf.editor.6(editor6.in)... 正确 0.053秒 得分: 10
正在测试 asdf.editor.7(editor7.in)... 正确 0.050秒 得分: 10
正在测试 asdf.editor.8(editor8.in)... 正确 0.138秒 得分: 10
正在测试 asdf.editor.9(editor9.in)... 正确 0.258秒 得分: 10
asdf.editor 的总分: 100
asdf 的总分: 100
开始测试 ti
正在编译 ti.editor ...成功
正在测试 ti.editor.0(editor0.in)... 正确 1.771秒 得分: 10
正在测试 ti.editor.1(editor1.in)... 正确 0.003秒 得分: 10
正在测试 ti.editor.2(editor2.in)... 正确 0.663秒 得分: 10
正在测试 ti.editor.3(editor3.in)... 正确 0.743秒 得分: 10
正在测试 ti.editor.4(editor4.in)... 正确 0.734秒 得分: 10
正在测试 ti.editor.5(editor5.in)... 正确 0.524秒 得分: 10
正在测试 ti.editor.6(editor6.in)... 正确 0.526秒 得分: 10
正在测试 ti.editor.7(editor7.in)... 正确 0.518秒 得分: 10
正在测试 ti.editor.8(editor8.in)... 正确 0.668秒 得分: 10
正在测试 ti.editor.9(editor9.in)... 正确 0.920秒 得分: 10
ti.editor 的总分: 100
ti 的总分: 100
day1
network
任意两点间最短路径的数目可以在floyd的基础上加一点东西来计算。floyd中，如果满足f[i][j]>f[i][k]+f[k][j]，那么把g[i][j]更新为g[i][k]*g[k][j]，如果f[i][j]==f[i][k]+f[k][j]，那么g[i][j]+=g[i][k]*g[k][j]。然后经过v的最短路径的数目可以枚举s顶点和t顶点，如果满足f[s][v]+f[v][t]=f[s][t]，那么路径数目增加g[s][v]*g[v][t]。这样就解决了。帅哥周源的那个题解提供的第三个方法没去看，对这题n^3足矣。他那个是NM的，适用于稀疏图。
cash
cash这题啊，我的能力也就只能拿60分了。方程是很显然的，f[i]=max(f[i-1], f[j]+w[j][i])。f里头存的都是人民币，w[j][i]表示在第j天用所有钱买入，然后到第i天卖出。这是n^2的。标程是nlogn的，那解法实在太神奇，是用treap优化的dp，于是我觉得我想得到也写不出啊orz。
day2
necklace
这题是个比较简单的数据结构题。不过是个线段树而已，而且居然开了4s，也算是好RP了。估计数组模拟都可以过不少吧。需要注意的是，rotate和flip并不改变珠子之间的相对顺序，所以就用个标记搞定就可以了。
然而这个也没有一次AC，是在rotate的时候一个head-=n手误成了head+=n，其实是原来改过的，后来忘了改回去了。
count
我估计我能在比赛的时候写的方法是消元。首先，算行列式的时候我们可以利用矩阵初等变换把它消成三角阵，然后把对角线上的数乘起来，这个值就是原来行列式的值。初等变换是指把某一行乘上某个常数然后加到另一行上，例如：
第一行乘上它下面每一行的第一个数的相反数，加到该行上。
第二行乘上它下面每一行的第一个数的相反数，加到该行上。
这样，原行列式的值是1*(-3)*(-9)=27。
行列式的值在初等变换下不变。直接做是n^3的，然而这个矩阵是如此特殊，它只有中间那么一块有东西，其他都是0，比如n=6，k=2的情况
![\[ \begin{bmatrix} 2&-1&-1& 0& 0\\-1& 3&-1&-1& 0\\ -1&-1& 4&-1&-1\\ 0&-1&-1& 4&-1\\ 0& 0&-1&-1& 3\\ \end{bmatrix} \]](http://agnimon.is-programmer.com/user_files/agnimon/epics/cbe910750b6838a38c838d15309efe97c5419fe9.png "\[ \begin{bmatrix} 2&-1&-1& 0& 0\\-1& 3&-1&-1& 0\\ -1&-1& 4&-1&-1\\ 0&-1&-1& 4&-1\\ 0& 0&-1&-1& 3\\ \end{bmatrix} \]")
很显然，我们没有必要去用一行来消它下面的所有行，因为有很多已经是0了，只需要消它下面k行就可以了。于是我们得到了一个O(n^2k)的算法，据说可以得70~80分，也不错了。
题解上写了DP的方法，不过始终还是很麻烦，虽然效果确实比消元好，相应地思维复杂度也比消元高很多。对于k=2，大概想法是把n顶点的图分成两类，一类是n与n-1直接相连的，一类是n与n-1不直接相连的，这样就可以推了，其他情况也类似，但是k>=4的时候用手是肯定写不出那些情况了的，据说有分别有三十多种、五十多种，所以就要靠一个DFS先确定转移方程上的系数，然后再确定初值，反正无比麻烦就对了。
catch
虽然我没能力完美解决这个题（他那解决的程序可是有8k多呢…还是C的呢，这难道能写得完的么OTZ），不过骗个三四十分还是可以的。而且程序也不算很麻烦，用一个多小时肯定能写完调完了。
想法是这样，首先，因为是树形结构，很自然地想到类似tree-dp的方法：
用tree(i)表示清空i节点。所谓清空，就是通过一些步骤保证他不可能在i以及i的子树中。结束之后，必须在i节点保留且只保留一个人。
对当前节点i，
1.如果度为1，那么这个点显然是叶子，我们设法保证，不会有递归到叶子节点的情况。
2.如果度为2，有两种情况。要么这个点是根，这样就有两个儿子。首先检查儿子是否是叶子，如果是叶子，而且i上没有人，就在左儿子分配一个，然后移动到i，然后再移动到右儿子，然后再返回i。否则用i上的人来移动。要么这个点是某个非叶节点，那么只需要判断儿子是否是叶子，类似地做。
3.如果度大于2，那么首先在i分配一个人，然后再在i分配一个人去扫荡i的儿子中的叶子节点，然后再递归地清空i的非叶儿子。
这个方法是一定满足条件的，不过貌似分配的人多了一点，嘛，得了40分，也算可以了，嗯。
至此，NOI近5年的题解题报告（其实也不能算是解题报告，最多是解题思路…或者甚至是心得这类东西…）就结束了。
NOI2006解题报告
day1
network
很经典的treedp，至少我是想不到的。
首先题目中给的权是边权而不是点权（所谓边权就是说两个点之间的权，而不是点上的权），因此要首先把边权变成点权才方便计算。它的那个计费方式可以看成是这样，对每棵子树A，谁少收谁的钱，一样多收B的钱。所谓对某个点i收钱，是指求出i到以A的另一个儿子为根的子树中的所有点的流量和。试一试就会发现，这样算出来的结果与直接计算是一样的。于是我们给每个非叶顶点标号，如果这棵子树要收A的钱，那么就标A，否则标B。这样，对于每一个叶节点，如果知道了它的所有祖先的收费情况，就知道它要交多少钱了。因此我们可以这样表示状态：f[i][l][S]表示对于节点i，当前还剩下l个A的配额（就是说在以i为根的子树所管辖的节点中，要有l个A），然后i的祖先的收费状态是S时的最小费用。于是推起来就很容易了，
![\[ f[i][l][S] = \min_{0 \le k \le l} { f[child[i][0]][k][S+newS] + f[child[i][1]][l-k][S+newS] } \]](http://agnimon.is-programmer.com/user_files/agnimon/epics/58200a269d337447cd272342034c7c5900e28a2b.png "\[ f[i][l][S] = \min_{0 \le k \le l} { f[child[i][0]][k][S+newS] + f[child[i][1]][l-k][S+newS] } \]")
其中newS表示i的收费状况，这个状况可以根据l来确定。很显然，l不小于1<<(n-dep[i]-1)的时候要收B的钱，否则要收A的钱，其中dep[i]表示i的深度。特殊情况是i为叶子，那么就要根据l来算i的状态，然后算出费用即可。这个算法据说有80%的分。
但是l最多可能到1024，i最多也是1024，然后S最多还是1024，这么个数组怎么开得了啊，除非到下个世纪全世界人都用上1T的内存了再说吧。仔细考虑，假设i的深度叫t，那么l最多有可能是2^{n-t-1}，而S最多只有2^{t-1}，两个乘起来还不超过2^n，于是这就可以存下来了。我是采取把l移位到s前面，合成一个整数，然后再记s的位数来存的，题解是说做hash表，这个一直是我基不擅长的东西。
问题是，嗯，还是没AC。
happybirthday
呜呼，这题是（几乎可以认为）一次AC的，郁闷死了
一个经典而简单的Treap题。据说move有很好的分数。再据说要用treap的题move都会有很好的分数，再再据说move写起来可以比treap短几百行，好了，没什么好说的了。
嗯，首先，get_present就是插入然后删除然后再插入，told就是把删除的那个名字说出来。很显然插入的元素会有很多的重复，于是我是用一个treap套的一个链表，treap是根据果冻数来平衡的，链表里头存的是名字。其他的就直接按照题目做就可以了。
然后为什么没一次AC呢？很简单，链表删除的时候如果删掉了链表头，那么在treap里头保存的那个head也要相应改变。然后这个我忘了。加上去，AC。
worm
这题是有名的灵异恶心题，然后如果按5小时来做的话恐怕连题目都看不完，orz。其实我连题目都没怎么看明白，还是不说了…
day2
profit
经典最大流的题。按照Amber的说法，题目其实是一个最大闭合子图的模型，也就是说一个有向图上，每个顶点有点权，可正可负，求一个子图，使得子图之中的任何一个顶点的后继都在子图中（即，具有封闭性），而且这个子图的顶点点权之和最大。转移到这个题目上来，我们可以把顶点看成是两类，一类是顾客，一类是基站，然后如果顾客使用基站的话就从顾客到基站连一条有向边，基站的点权是负的，顾客的点权是正的。于是根据amber写的通用解法，把所有原图有向边的流量设为无穷，然后新增一个源，指向所有权为正的顶点，边权就是该点的点权，再新增一个汇，从所有权为负的顶点指向汇，边权为该点权的相反数。这样，求出最大流之后，用从汇出发的边流量之和减掉最小割的值就可以了。
正确性是显然的，首先，最小割一定不会包含无穷边，因此最小割一定是从源出发的某些边和进入汇的某些边构成的。最小割把s-t分成了两个连通分量，我们把包含s的连通分量叫做s集，把包含t的叫t集。既然不包含无穷边，那么如果某个顶点在s集中，从它出发的所有边一定也在s集中，因此它的后继一定在s集中。因此，s集是满足要求的。关于权的计算可以这么看，最小割的值是由从s出发的某些边（把这个集合叫做A）和进入t的某些边（把这个集合叫做B）构成的。注意到s集中的那些负权点，由它们指向汇的边就是B集。而那些不在s集中的正权点，源指向它们的边就是A集。因此，用由S出发的所有边的边权和减掉最小割，就相当于减掉了不选的正权点和负权点造成的损失。那么为什么这样求出来一定是最大值呢？因为每一个闭合子图都可以与某一个s集建立一一对应关系，然后每一个s集又可以与一个割建立一一对应关系。既然这个割是最小的，那么闭合子图就一定是最大的。
然后，这题肯定不能用邻接矩阵来存边了，我不喜欢链表，不管是真的还是伪的，所以就写了前向星。写的时候有一些技巧，就是加入一条边的时候就顺便加入反向边，然后每一条边一个指向反向边的指针（当然，反向边的指针就指向正向边了），这样不管是正向边还是反向边都不用分开来处理，只需要当成一般边来做就可以了。也就是说，在找流的时候，面对一个改变量，不管当前边是正向边还是反向边，只需把它加上去，然后把当前边的反向边减掉就可以了。我WA就是因为这个原因，我以为要分开处理。
bag
其实这个题只有一个要点，就是［无限制的点不影响概率］，也就是说不管两个限制之间隔了多远，或者第一个限制是否处在序列的最前端，我们只要简单地把无限制的段删除，按照有限制的点来处理就可以了。这个证明是这样的。
不妨假设第1次实验是无限制的，第二次实验限制颜色必须为k，设![\[s=\sum_{i=1}^t a[i]\]](http://agnimon.is-programmer.com/user_files/agnimon/epics/18e6ad6667b1d3d8b66e353f67f47db67e74822a.png "\[s=\sum_{i=1}^t a[i]\]")
，那么
![\[ \begin{matrix} P & = &\sum_{1 \le i \le t, i \ne k} \frac{a[i]}{s} \times \frac{a[k]}{s+d} + \frac{a[k]}{s} \times \frac{a[k]+d}{s+d} \\ \ & = & \frac{s-a[k]}{s} \times \frac{a[k]}{s+d} + \frac{a[k]}{s} \times \frac{a[k]+d}{s+d} \\ \ & = & \frac{sa[k] - (a[k])^2 + (a[k])^2 + a[k]d}{s(s+d)} \\ \ &=& \frac{a[k]}{s} \end{matrix} \]](http://agnimon.is-programmer.com/user_files/agnimon/epics/67bdc40334ac89c7933926dd25b989af2032435f.png "\[ \begin{matrix} P & = &\sum_{1 \le i \le t, i \ne k} \frac{a[i]}{s} \times \frac{a[k]}{s+d} + \frac{a[k]}{s} \times \frac{a[k]+d}{s+d} \\ \ & = & \frac{s-a[k]}{s} \times \frac{a[k]}{s+d} + \frac{a[k]}{s} \times \frac{a[k]+d}{s+d} \\ \ & = & \frac{sa[k] - (a[k])^2 + (a[k])^2 + a[k]d}{s(s+d)} \\ \ &=& \frac{a[k]}{s} \end{matrix} \]")
这样，其他位置以此类推，于是就可以得出前面的结论。接下来只要写一个高精度就好了，为了不使用高精度除法可以做因子分解，用标准分解式来计算。
day1
adv1900
这题是DP优化的经典题。首先，O(nmT)的方程很容易想到。f[i][j][t]表示t时刻在(i,j)时，可以走的最长距离。每一个点有两种选择，用魔法或者不用。由于走的方向已经事先定好了，所以直接推就行了。这个方法可以过60%的点。
考虑这个题的特殊性，T可以很大，k却很小。而且在每个k之中走的方向都是一样的。于是我们可以这么考虑，f[k][i][j]表示在第k时段里头，走到(i,j)时可以达到的最长距离。很显然，f[k][i][j]来自于f[k-1][i-x*di[k]][j-x*dj[k]]，即按照k的方向往回走的某个格子。因为在每个时段里头它都只能往一个方向走，我们可以按照方向把行列分开来处理。比如当前时段只能往北走，那么我们可以把每一列单独拿出来考虑，因为在这个时段之内当前列走不到其他列。假设对于第i列，g[j]表示第i列上从起点开始算起的第j个格子可以得到的最大值。这个起点是指逆着当前方向走，能走到的最远点。比如如果只能往北走，那么起点就是最南点。只有这样推才能满足无后效性，因为从起点开始的每个格子都回不到它前面的那个格子。于是g[j]=max(g[k]+(j-k)) 其中j>k , j-k<=time，time为当前时段的长度。其实这个式子我也想到了，但是直接用这个式子还是无法达到优化的效果。用这个式子来求算，状态是O(nk)，转移是O(n^2)（这里n,m就不区分了，因为不知道具体每个时段走的方向）。最坏情况下还是有可能达到40000*200*200的计算量的（当然，据说直接用这个式子有80%的分）。
对这个式子进行变形，g[j]-j=max(g[k]-k)，用a[j]表示g[j]-j，这样a[j]=max(a[k])，其中j-k<=time。如果把a看成一个数列，那么其实就是在求从j-1开始，长度为time的一段里头的最大值，RMQ啊！于是冲动一下，写个ST或者线段树，或者更有才有闲空地写一个O(n)-O(1)RMQ，唔，那真是天牛了。来仔细分析一下这个查询的特殊性：每次查询长度相同，而且是连续的段。这样可以维护一个单调队列，这个队列可以两边删除，一边插入。我们保持队列从队首向队尾递减。队列中每个元素不仅要存相应的a值，还要有一个时间戳，每当有新的查询时，先把队首过时的元素都删掉，然后返回队首元素，插入时把处在队尾的比新元素小的数全都删掉，然后插入新元素。为什么可以这样做呢？可以这么想，对于每个RMQ问题，如果插入的元素比现在序列里头的某些元素要大，那么那些元素永远不会成为RMQ问题的答案，因为已经有人比他们大而且比他们新了，能够查询到他们的时候也一定能查询到那个新元素，因此没有必要再保存他们了。这样写起来也好写，复杂度是O(n)的，于是总体复杂度降为O(nmk)。
sequence
这个显然是块状链表。因为实在没什么其他的结构能支持那个Reverse命令。对于每一块记录一个量f，标记当前块的读取顺序，即是否reverse。如果reverse的区间恰好处在某块之间，那么就直接swap吧，复杂度不会很大的。最恶心的是max_sum，我想了个无比麻烦的方法，一看报告居然说只要O(n)直接统计就行了，我晕，要是有M/2个max_sum再插了4*10^6个数，看看O(n)的统计还行不行｜｜｜
我想的那个无比麻烦的方法大概是这样，就说把整个序列看成一个数组，那么类似O(n)统计的方法，可以在整个数组中划出许多个分割点，这些分割点表示统计的过程中在这个点时s<0。
例如序列1 2 -4 3 -6 5 9 -10，就应该这么分割：1 2 | -4 | 3 | -6 | 5 9 10 |。这些分割点的个数最多会有n个，如果数组全部都是负数的话。然后在每个操作的时候顺便维护一下这些分割点，比如insert的时候，就需要重新统计最靠近insert点的上一个分割点到下一个分割点之间的段，delete的时候，delete之后就需要重新统计最近的两个分割点之间的状况。特别地，如果delete掉的东西和不为正，就需要重新统计到下一个分割点。reverse的时候只会影响起点和终点所在的地方的分割点，等等。统计的时候可以直接利用每一块的和这个东西。嘛，貌似看起来复杂度也不低，而且把本来复杂度低的操作复杂度也弄高了，于是也不太好。
zhzyx
搜吧。反正我没搜出来，据称裸搜可以有80%。我也不知道为什么，嗯，暴力是美的，嗯。
day2
这套题是这么多NOI题里头我做得最差的，几乎一题也没做出来。
cchkk
这是个DP题，然后我没想出来，然后看了报告好像还不是很明白，听别人说这题巨简单，我也不知道为啥我想不出来，嗯。
首先，从状态来说，只要知道图，以及cc和kk的位置，那么这个概率就确定了。因此只需要用f[i][j]表示cc在i，kk在j时的概率即可。然后推的时候，由于cc一个时间里头可以走两步，而且是cc是一定走了两步之后kk才能走一步。注意，虽然题目中说cc是在没有捉到kk的情况下才走第二步，但我们可以统一处理，如果捉到了cc，就相当于在原地再走一步。首先预处理出一个数组p[i][j]，表示从i走向j时，迈出的第一步。因为题目中说了如果有多条路径一定走编号最小的，所以一定可以在图中找到一棵最短路树，所以就可以用一串连续的p数组序列来表示一条路径。比如i到j的路径可以表示为先走i，然后到p[i][j]，然后到p[p[i][j]][j]，然后到p[p[p[i][j]][j]][j]，……，直到p[...][j]=j为止。当然，为了统一处理两步和一步，我们规定p[i][i]=i。于是方程就可以这么表示
![\begin{displaymath} f[i][j]= \frac { f[p[p[i][j]][j]][j] + \sum_{k=0}^t f[p[p[i][j]][j]][w[j][k]] } {t+1} + 1 \end{displaymath}](/user_files/agnimon/epics/18d2886bd1cc05c076a36f0b5f347be3b9fdc61f.png "\begin{displaymath} f[i][j]= \frac { f[p[p[i][j]][j]][j] + \sum_{k=0}^t f[p[p[i][j]][j]][w[j][k]] } {t+1} + 1 \end{displaymath}")
里头第一项表示kk不走，t表示j点的邻接点数目，w[j][k]表示j的第k个邻接点。最后要加1是步数。
很显然，这个方程如果直接推写起来会很麻烦（因为不知道访问顺序），最好的方法是记忆化搜索，效果不错还实惠。
party
略微说一下，1~3是最大生成树，4~6是最小度限制生成树，7~10是乱搞。其实4~6也可以乱搞，反正那算法不麻烦也不简单。
lemon
下面所说的“XX角“，都是XX与水平面的夹角。首先，圆台的影子有两种情况，如果光线角大于母线角，那么影子是一个圆（不是椭圆哦），否则是一个…很怪异的图形，一个梯形，上底和下底分别是个弓形。其实就是圆台的上圆和下圆分别投影之后，作公切线得到的图形封闭部分的面积（图中黄色）。第二，圆锥的影子也有两种情况，光线角大于母线角时是一个圆，否则把顶点投影下去，得到一个三角形去掉一个弓形的部分。（红色）
这样，剩下的事情就是求并了。我要求不高，能拿个n=1的分就不错了。
NOI2004解题报告
day1
cashier
对一个数列，完成四种操作。所有元素增加或减少一个给定量，向数列中插入某个元素，查询数列中第k大元素。另外，在任何操作之后，数列中所有小于某个值的量都会被删除，这个数目也要统计。
这题我用treap和树状数组分别做了一次。我手头的数据是错的，反正我拿标程和我的两个程序对，答案都一样，而且和数据里头的答案的查询结果一样，就是删除的数目不同，而且差很多。于是就认为是答案错了。｜｜
treap和树状数组的思想是不同的，但是有一个处理是一样的：因为增加的操作不会影响数据的相互关系，减少和插入操作才有可能影响，所以我们需要一个改变量delta，当增加时就直接增加delta，减少时不仅减少delta还要处理删除元素，插入时要把插入的量减去一个delta。
Treap保存的是元素，增加一个size域用于查询，增加一个delta域表示这棵子树的值都需要加上delta，还有一个num域处理重复节点。然后增加的时候在根节点的delta上处理。关于delta的的操作就像线段树的lazy操作一样，当访问到某个节点的时候就把根的值加上delta，然后把delta加到左右儿子的delta上，然后把根的改成0，这叫做delta的传递。插入和查询的时候都可以顺便传递delta，节约时间。因为删除的时候是整个整个地删，所以操作的时候也不用费心去调整了，直接free掉了事。这样就可以了。写treap的时候有些地方要注意，就是rotate的时候千万不要忘记更新域，有些域在rotate下是不变的，比如这里的delta和num，但最常用的size域是会变的，千万不要忘了更新。
树状数组第i个节点保存的是值小于i-1的元素有多少个（当然实际数组的值肯定不是这个）。由于可能出现0，而树状数组下标必须从1开始，所以要用i-1。要保存一个curmax和curmin，表示当前在树状数组中的数的最小值和最大值。然后那个delta表示整个数组的偏移量，每次插入的时候如果插入的值减掉delta还是正数的话就直接插，否则就要把数组平移delta，以保证插入的元素是正数。平移的时候不能简单地move，因为下标是和保存的值有关的，所以干脆就直接枚举每个元素（也就是从curmin到curmax），加上delta然后插入一个新的数组里头。于是这里就成了程序的瓶颈，虽然复杂度很不小，但是次数貌似不算多，所以实际效果很好。然后删除的时候就相当于给小于它的每个元素减掉该元素的数量，这儿也要枚举元素，不过只需要从min到curmin就可以了。我感觉我这方法复杂度应该不低，但是实际效果居然比treap好很多，真神奇…
manhattan
这曼哈顿做的我头昏脑胀，到了最后居然被lowsars给误删了｜｜｜｜｜｜｜｜｜｜｜｜太郁闷了｜｜｜｜｜｜｜于是就不打算重写了，管他对不对｜｜｜｜
其实这个题的方法我想到了一半，另一半我打算用图论算法实现，然后想破脑袋也没想出来，一看题解原来是DP…我没想到可以用区间表示，所以想不到DP…T_T
首先，这个那么小的m一看就勾引人去枚举…然后任何两点的manhattan路径都可以规约成以下四种情况。
也就是说枚举了m然后我们只需要找到一个合法的n方向的方案满足所有要求就行了。然后我想到这一步就总是在想这些约束关系可以离散成许多个用与或关联词连接的约束，然后以约束为顶点，设法构图把这些关联词表达出来，想了一个早上也没想出来｜｜其实关键问题是在或关联词上，与关联词是很容易表达的，而且有些约束是要两个点有些是一个，虽然后来想出了一个方法可以把两个的和一个的统一起来表示，但是在那个表示方法下与或关联词都很不好表达。所以很WS地看题解去了。原来题解是把这些约束用区间来表示，[s,t](r)表示在n方向上的[s,t]区间里头，至少要有一条边方向是r。然后这四种情况就可以很方便地表示为许多个只有与关联词的约束关系。这是个突破口。如果只有与关联词那就好办了，首先把区间分类，有些是方向0的有些是要1的，分开处理，将具有包含关系的区间中删大的留小的，因为小的区间满足了大的自然也就满足了。对区间左端点排序，左端点相等的按右端点排序，然后DP，f[i][j][k]表示扫描线在i的时候0区间可以满足的最后一个为j，1区间可以满足的最后一个叫k，状态表示也不太好想到，反正我是没想到。想到了这个状态表示之后转移就很容易了。假设l表示左端点大于i+1的第一个0或1区间编号，那么f[i][j][k]就应该转移到f[i+1][l-1][k]（即y是方向0）或者f[i+1][j][l-1]（y是方向1）。
dune
这题不会做，看amber的报告吧
day2
hut
这个题可以DP也可以贪心，我不知道为什么老是调不过那个DP，于是就写了贪心的。DP的想法很简单，f[i][j][k]表示x位置在i，对应的南墙有j个块，北墙有k个块。于是推起来就很明显了，f[i-x][j-y][k-1]。就相当于枚举最后一块北墙的长度x，再这个x对应的南墙墙数y。很显然这y块都必须尽量平均。但是这样复杂度比较高，是O(L^2N^2M)，无法接受。注意到北墙块实际上是没有顺序的（交换之后对应的南墙块也要交换），也就是说可以任意交换而不改变结果。于是我们使北墙块的长度递增，长度相等时按照南墙块数目排序。这样我们发现，当确定x之后，枚举y的过程实际上是单峰型的，也就是存在且仅存在一个极值，那么这个极值（假设是y）必定满足y-1和y+1都不小于它，找到了这样的点就可以认定它是极值点了。确定了当前x对应的y之后，让x++，此时块数必定不比y少（因为要平均），因此直接从y开始枚举就可以了。这样，转移的复杂度从O(LN)变成了O(L)，总复杂度也就变成了O(L^2NM)，这是可以接受的。问题是这个DP我怎么调都调不过，然后看了amber的报告就按照他那个贪心来写了。
贪心的方法是基于平均分配的思想。考虑到南墙有m块，北墙有n块，最好的情况当然是每块北墙都分到m/n块南墙（因为最平均嘛），但是如果m不能被n整除呢？那就首先尽量平均，然后多出来的部分再平均地放在某些块里头。也就是说北墙对应南墙有两种，一种是拿到[m/n]块，另一种拿到[m/n+1]块。正如刚才所说，北墙的顺序是无关紧要的，于是我们把北墙按种类排序，也就是找到一个分点i，使得i的左边的所有北墙都是[m/n]型的，而右边所有的都是[m/n]+1型的。然后再考虑长度，如果每块北墙（或者南墙）分不到恰好整数的长度，也是一样，先尽量平均，然后再把多出来的再平均放。于是复杂度就是O(L)，我是直接合并写成了一个式子，虽然看起来比较难看，不过思想还是很明显的。
rainfall
这个题其实是几何题，只不过需要一些转化。首先，我们用s-t图线表示所有自动伞的运动。每一个自动伞可以看成两个端点之内的部分，也就是图中着色了的部分。每一种颜色代表一个伞。这样，我们要求的降雨面积其实就是总面积减掉伞面积。（下面图片是大图，不过貌似在firefox里头会自动缩小，然后就看不太清楚了，可以点开来看）
我们按交点和拐点对整个图形离散化（图中只是表示出了两个伞的情况）。这样我们就发现任何两个事件点之间的图形其实就是许多平行四边形的并。再仔细看每一根虚线上的点，其实两个事件点i和i+1之间的面积可以用l_i（在第i条直线上的线段长度之和）与l_{i+1}求出，具体地，S=(l_i+l_i+1)*(x_{i+1}-x_i)/2。这就是梯形面积。于是问题就解决了。
noi2003简要解题报告
day1
game
就是说有个火柴棍摆的式子要你动一根火柴让它成立。忽然想起来一个超绝的动法：随便抽一根，只要保证左右不等就行了，然后把那根火柴放在等号上头，成功概率极高｜｜不过题目说不能变符号，所以没办法了。
首先做个转换表，转换有两种，一种是分子内，一种是分子间 XD，然后遍历每个数看看哪个可以转换，检查转换后是否满足条件。然后再枚举两个数，如果这两个数符合分子间变换条件，那么就变换看看是否满足条件。问题就是我这么一写就写恶心了，居然TLE了……
editor
题目太长了自己看吧
传说中的块状链表，怎么调都调不过｜｜｜
detect
题目是说有一个凸多边形，没有任何一边与坐标轴平行，坐标原点在多边形内。然后可以通过划水平线和竖直线求与凸多边形的交点。要求通过尽量少的求交点次数确定多边形的顶点数和具体坐标。
核心思想是二分，我用的是ask_x。首先找出最左和最右两个点。特征是最左点左边和最右点右边的x值都不会产生交点。然后因为是凸多边形所以可以分成两部分，一部分是从最左到最右上凸的，另一部分是下凸的，具体表现在上凸部分用两个交点中y值较大的，从最左顶点开始找顶点，比如当前顶点是(x,y)，那么询问(x+1,y)，然后二分查找产生的交点与这两个顶点共线的最后一个x值。这个x值就是下一个顶点。重复这个过程直到找到最右顶点为止。
注意一些特殊情况，比如三角形。这样上凸或者下凸的部分就可能没有顶点，这个要特殊处理。
为了优化步数，可以拿一个数组存下每次的询问和回答，向库询问之前先检查这个询问有没有出现过，另外查找顶点的时候可以从数组中检查所有询问当中与那两点共线的最后一个x值，这是下界，上界是这个x值在数组当中的下一个值。这样可以缩小查询范围，减少次数。
还有一个优化，查询x值的时候如果对应的y值不是整数，那么就肯定不是顶点，因此只需要查询对应y值为整数的顶点就可以了。
day2
hookey/jellygen
这题很神奇地有两个版本的描述，难道是为了防止作弊？…大概就是说有棵加权树，然后确定三个顶点A,B,C，若|CA|<|CB|那么x=|CA|+|AB|，否则x=|CB|+|AB|，使得x最小。求这个最小的x值。||符号表示这两个顶点在树上的唯一通路的长度。
我们总可以在这条路径上找到一个点D，把这条路径分成三部分：CD+AD+BD（具体来说，D=LCA(LCA(A,B),C)）。假设CD是最长的，AD次长，BD第三长，那么x=|CD|+2*|AD|+|BD|。这就变成了求从每个顶点出发找最长、次长、第三长路的问题。注意，这三条路必然是不相交的。也就是说除了出发点之外这三条路中没有相同的顶点。下面将这三条路的数据称为路信息，这些路信息在大多数情况下是相互独立的，所以更新时只需要分来更新就可以了。
有根树中从某个节点出发的路径只有两种，一种是不经过祖先的，另一种是经过祖先的。首先我们可以求出从某个节点出发不经过祖先的路信息。这个只需要DFS的过程中先求出所有儿子节点的路信息，然后用父亲到儿子的距离加到儿子的路信息上，取前三大就可以了，注意记录路信息的时候要顺便记下路信息对应的第一个儿子顶点，方便之后的判断。然后我们从根的儿子开始，考虑经过祖先的路径。对于每一个非根节点i，经过祖先的就是父亲的路信息中不经过i的最大值（即，要么是最大要么是次大）加上父亲到i的距离。因为路信息中不可能有两条路同时经过祖先，所以只需要保留最大的就可以了。
其实这是一种树形DP。
zplhz
恶心的搜索……就不说啥了
猛然想起一个名词叫解体报告……
言归正传。
noi2002部分解题报告
Child
题目的意思是有n+m+1个人，其中m个人属于一个组，这个组总是说谎；而n个人属于另一个组，这个组总是说真话，还有1个人是裁判，被问到奇数次的时候说真话而偶数次说谎。可以对每个人询问除他以外的某个人是否属于某个队，但是不能对同一个人问另外的同样一个人的所属问题两次，要求对每个人问不超过2次来确定所有人的组别情况。
我们应该抓住裁判两次回答不同的这个特点来进行考虑，假设说真话的是1（m个），说假话的是0（n个）。
首先，随便选一个人i，问其他人i是否属于某一组（比如0）。如果n!=m，那么可以进行讨论。
1.如果i是裁判，那么就会有n个人说他是0组，而m个人说他不是。
2.如果i是0组的，那么就有m+1个人说他是0组，n-1个人说他不是，其中裁判在那m+1个人里头。
3.如果i是1组的，那么就有n个人说他是0组，m个人说他不是0组，其中裁判在那m个人里头。
1&3.1.如果m+1和n-1相等，而且恰好出现了相等的数目，那么可以确定i是0的，然后随便抓某个组里头某个人j，问i他是不是0组的。
1&3.1.1.如果i说是，那么j要么1组要么是裁判(此时是0的，混在1里），然后再在另外一个组里头抓个k问j在的组，k是不是0的，于是会有m个人说是还有一个人说不是。说不是的那个就是裁判，其他是1。
1&3.1.2.如果i说不是，那么j就是0组的。于是从j在的组里头抓个人k出来给另一个组的人问，问k是不是0，于是会有m个人说是一个人说不是，不是的那个就是裁判，其他是1。
1&3.2.其他情况，随便抓0组的某个人j，问让m个人的组j是不是0，如果有m个人说是，那么裁判是i，如果有m-1个说是，那么少的那个就是裁判
如果n=m，那么至少我们确定，如果有n-1个人说他不是而m个人说他是，那么他必定是1组的，而且说不是的那n-1个人是0，其余是1。
从某一组中抓个人j出来，问其他人，j是不是1。如果与j同组的人有m-2个答是而有一个答不是，另一个组的都是不是那么就确定了。如果与j同组的人有n-1个答是，另一个组有m-1个答不是而有一个答是，那么j是0。如果与j同组的人有m-1答不是而另外一个组n个人答是，那么j是裁判。这样就讨论完了。
很显然，这样的讨论要求至少每个组的人都不少于2个。小于两个的情形很容易讨论就不再叙述。
dragon
就是说要给一棵带权树的顶点染上m种颜色，其中必须有k个顶点染1号色，而且根节点必须是1号色。其他无限制。统计整棵树上的两个端点颜色相同的边，将这些边的权值求和。求这个和的最小值。
树形DP。首先如果颜色多于2种，那么在染完1号色和2号色之后，总可以找到一种方法交替地染色，使得没有任何一条边端点同色。因此我们只需要考虑两种颜色的情况。
先做一次多叉转二叉，状态是用f[i][j][k]表示i节点为根的子树中需要染j个1号色的最小权和，其中k为0表示i的父亲染1号色，而为1表示染其他颜色。显然题目所求的就是f[0][k][1]。转移就比较明显了，
若i有儿子和兄弟
f[i][j][0] = min( f[child[i]][l][1] + f[brother[i]][j-l][0] , f[child[i]][l][0] + f[brother[i]][j-l-1][0] + w[father[i]][i]); //0<=l<=j或j-1
f[i][j][1] = min( f[child[i]][l][1] + f[brother[i]][j-l][1] + (m>2?0:1) * w[father[i]][i], f[child[i]][l][0] + f[brother[i]][j-l-1][1] ); //0<=l<=j或j-1}
若i有儿子或兄弟
f[i][j][0] = min( f[child[i]或brother[i]][j][1或0], f[child[i]或brother[i]][j-1][0] + w[father[i]][i] )
f[i][j][1] = min( f[child[i]或brother[i]][j][1], f[child[i]或brother[i]][j-1][0或1] + w[father[i]][i] )
若i伶仃孤苦至于成立既无伯叔终鲜兄弟门衰祚薄没有儿息…
f[i][j][0] = (j==1) ? w[father[i]][i] : (j==0?0:inf);
f[i][j][1] = (j==1) ? 0 : (j==0?w[father[i]][i]:inf);
这样就可以了。
galaxy
就是说有许多队列，初始时每个队列i只有一个元素i，要求实现两种操作，第一是把某个队列i的队头接到另一个队列j的队尾，第二是查询某两个元素之间的距离。
这个一看就是并和查，于是想要用并查集（并茶几？）来处理。但是并查集里头的元素都是对等的，无法保存先后顺序。于是我们可以对它进行改进。维护一个数组d，d[i]表示i到i的父亲的距离。每次合并时只需简单赋值，路径压缩和查找时从某个节点开始，一直查找到他的最上层根节点，将路上的距离累加，并一路更新经过的节点。这样查询的时候只需要查询两个元素到根的距离，然后求差就可以了。
day2
这一整套的数学题阿……
robot这题数学味道太浓，至今不能理解。
savage
首先看到这个不大的M（才10^6嘛）就想到要枚举阿枚举。完了之后就是知道m判断是否可行的问题了。对于任意两个野人i和j，假设他们经过x年第一次相遇，于是就要满足 
，其中
。整理一下，
，化成不定方程就是 
。于是就是利用拓展欧几里得来求解。
但是这个题目需要十分注意细节问题。首先是符号，一般书上或者网上给出的拓展欧几里得都是
的，如果abc的符号不同那就会有不同的结果。而且还要处理如果abc里头某个或者某几个量是0的情况。另外，拓展欧几里得可以直接解的方程是满足
的，而有整数解的方程都是满足(a,b)|c的。因此在求解之间必须化简系数。处理完这些之后程序就不短了。
关于符号问题，事实上该题中出现的所有abc的符号情况都可以规约到
与
的情况，而这两个情况必须分别讨论，后者与前者的区别是一两个符号。下面对
的情况进行推导。
显然方程
的解是
。于是假设我们已知方程
的解是(x,y)，则方程的解可以这样得出：
![\[\begin{matrix} bx - (a \bmod b)y & = &bx - \left ( a - \left \lfloor \frac{a}{b} \right \rfloor \times b \right ) y \\ \ &=& a(-y) - b(-x-\left \lfloor \frac{a}{b} \right \rfloor \times y) \end{matrix} \]](/user_files/agnimon/epics/a8b6a4e861147318185d43ac947eaf7e528d82ce.png "\[\begin{matrix} bx - (a \bmod b)y & = &bx - \left ( a - \left \lfloor \frac{a}{b} \right \rfloor \times b \right ) y \\ \ &=& a(-y) - b(-x-\left \lfloor \frac{a}{b} \right \rfloor \times y) \end{matrix} \]")
于是
![\[\begin{matrix} x^\prime&=&-y \\ y^\prime&=&-x-\left \lfloor \frac{a}{b} \right \rfloor \times y\end{matrix}\]](/user_files/agnimon/epics/aa3d57082eb5ba9927556953b07204b2416af9cf.png "\[\begin{matrix} x^\prime&=&-y \\ y^\prime&=&-x-\left \lfloor \frac{a}{b} \right \rfloor \times y\end{matrix}\]")