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
恶心的搜索……就不说啥了