题目按个人感受的难度升序排列。
J Fraction Comparision
Description
给$\frac{x}{a},\frac{y}{b},0\leq a,b\leq 10^9,0\leq x,y\leq 10^{18}$，问这两个分数比较大小的结果（大于、小于或等于）。
Solution
由于浮点数会有误差，不能除了以后再判断。
用有大整数的语言的话，可以直接通分比较。
用C++的话，可以把两个分数划为带分数。比较带分数时先比较整数部分，再通分比较真分数部分。由于分母在1e9范围内，不会爆long long。
F Random Point in Triangle
Description
给平面上一个三角形，顶点为ABC。现在随机再三角形内部取一点S，S把三角形划分为三个小三角形。问这三个小三角形面积的最大值的期望乘36（保证这样算出来的结果是整数）。
Solution
我在知乎上看到过类似的题目，原理没记住，结论倒记住了：这种三角形随机取点求面积期望的题，与三角形形状无关，只与面积有关。原理好像是坐标变换什么的，不管三角形形状是怎么样的，都可以通过坐标变换变成同一个三角形。这个坐标变换的过程面积也是按照比例变化的。大概是这个意思，我也说不清楚具体的原理。
有了这个结论，只需要知道面积为1的三角形的答案就行了，这个直接在本地模拟就行。我把三点设为(0, 0), (0, 1), (1, 0)，取两个随机数后把随机数都映射到[0, 1]中，再判断这个点是否在三角形内。如果这个点在三角形内，就用叉积算三个小三角形面积。不断地大量随机取点后再除一下有效点数量就是答案。
判断点是否在三角形内可以考虑判断三个小三角形的面积是否“正负号相同”（即叉积结果符号是否相同）。
最后发现面积乘22就是答案,也就是叉积的结果乘11。
B Integration
Description
已知$\int_{0}^{\infty}\frac{1}{1+x^2}dx=\frac{\pi}{2}$，
给定$a_1, a_2…a_n(1\leq n\leq 10^3，1\leq a_i\leq 10^9,a_i互不相同)$，求$\frac{1}{\pi}\frac{1}{\Sigma_{i = 1}^{n}(a_i^2+x^2)}dx$模$10^9+7$意义下的值。
Solution
这道题只需要微积分的基础知识，即积分的线性性质：积分里面如果是相加的话可以拆开来积分再相加。但题目里面的积分是相乘，只能考虑把积分内的乘积化为简单的分式相加，再套入题目给的公式了。
分式的乘拆分成分式的和则是初等数学的内容了。不妨先考虑$n=2$的情况，考虑$\frac{1}{(a^2+x^2)(b^2+x^2)}$的拆分结果。
设$\frac{1}{(a^2+x^2)(b^2+x^2)} = \frac{n}{a^2 + x^2} + \frac{m}{b^2+x^2}$，则：
由于上式恒成立，可得：
解得：
用同样的方法可以求得n为任意值时的拆分结果。对于分母是$a_i^2+x^2$的项，它的分子是$\frac{1}{\Sigma_{j\neq i}(a_j^2-a_i^2)}$。
再由微积分的知识，$\int_{0}^{\infty}\frac{C}{a^2+x^2}dx=\frac{C}{a^2}\int_{0}^{\infty}\frac{1}{1+(x/a)^2}dx =\frac{C}{a}\int_{0}^{\infty}\frac{1}{1+(x/a)^2}d(x/a) =\frac{C\pi}{2a}$，
因此，对于分母是$a_i^2+x^2$的项，积分的结果是$\frac{\pi}{2a_i\Sigma_{j\neq i}(a_j^2-a_i^2)}$。算出了公式，转换成程序就行了。
C Euclidean Distance
Description
给一个n维空间的点$A(a_1/m, a_2/m…a_n/m)$，求它到点$P(p_1, p_2, …p_n)$的最短距离的平方，即$\Sigma_{i = 1}^{n}(a_i/m - p_i)^2$。其中点$P$要满足下列条件：
$p_i\in \Reals$
$p_i \geq 0$
$\Sigma p_i = 1$
答案用分数的形式表示。
数据范围：
$1 \leq n \leq 10^4,1\leq m \leq 10^3, -m\leq a_i \leq m$
Solution
为了方便说明，先把点$P$的每个坐标分量乘一个m，我们要求的东西变成了$\Sigma_{i = 1}^{n}(a_i - p_im)^2$。只要把这个结果除以一个$m^2$就是题目的答案。
由于点$P$的分量都大于等于0，且和为$m$，我们可以考虑把点$P$的坐标看成是实数$m$“分配”到每一个坐标分量$p_i$上。即我们可以让每一个$p_i$变大一点。
我们如何让距离尽可能短呢？如果在某一维上，比如第$i$维，若$a_i < 0$，那么此时令$p_i$增长的话，那么距离只会越来越长；如果$a_i > 0$，那么$p_i$越靠近$a_i$，那么最终的距离就会越短。当$p_i = a_i$时，我们就不用让$p_i$增长了。
由不等式$a^2+b^2\geq2ab(仅当a=b时等号成立)$我们发现，数越大，其平方也增长得越快。如果此时我们去缩小一个本身就很大的数，就能让平方和减少得更多。具体来说，对于两个点的第$i, j$两个维的坐标分量,若$|a_i-p_i|>|a_j-p_j|$，那么让$a_i,p_i$更接近一点，比让$a_j,p_j$更接近一点，更能让总距离减小。那么在分配$m$到$P$的每一维时，应该先分配给$a_i$最大的地方，缩小此处$a_i和p_i$的差距。等这一维的距离和$a_i$中第二大的数时，就要同时缩小这两个维上的距离了。
比如$A(2,3)，m = 3$，我们发现$a_2 > a_1$，于是先从$m$中分配$1$给$p_2$，此时$P(0,1)$，$|a_2 - p_2| = |a_1 - p_1|$。我们再让这两个距离同步减小，从$m$再分配1分别给$p_1,p_2$，此时$m=0$,分配结束，而$P(1,2)$，$|a_2 - p_2| = |a_1 - p_1|$依然成立。这种情况下得到的$A,P$两点的距离是最短的。
有了上述思想，算法也就呼之欲出了。把所有$a_i$降序排序，按照上述方法分配$m$的值，尽可能让最大的几个距离相等，再同步减少这几个最大的距离。这种分配方式对于$a_i$是负数的情况也是成立的，不用多加考虑。注意一下有理数分子分母的处理方式即可。
Review
有时对于一道看上去复杂的数学题目，用一些比较简单的、定性的方法就能解出来。
A Equivalent Prefixes
Description
在两个数组$a, b$的前$m$项上，定义一个等价关系：若两个数组前$m$项任意一个区间$l,r$的最小数的位置相同，则称两个数组前$m$项等价。现在给两个数组$a,b$，问它们最多前几项是等价的？
数组长度为$n$
数据范围：
$1 \leq n \leq 10^5$
$1 \leq a_i,b_i \leq n, 所有a_i,所有b_i互异$
Solution
这个等价关系的意思好像就是说，每个数作为最小值的影响范围相同，即每个数碰到的左边、右边第一个比它小的数的位置都相同。这个东西好像就是笛卡尔树啊！
二分答案，对前$mid$项构建笛卡尔树，若笛卡尔树完全相同就check成功。
Review
从知识和写代码的复杂性来看，这道题肯定不是难度第二低的题目。但是，从全场的通过情况来看，这是大部分队第二道通过的题，也是通过人数第二多的题。
可以得出结论：很多题目，不是难到不会写，而是难到不敢写；有本来比较简单的题目没来得及写，不是你没有AC，而是别人没有AC。
话说笛卡尔树的定义和用途其实我现在都没有弄清，但我知道这个东西用单调栈就可以构造，而且所涉及的所有知识都建立在单调栈方面的知识上。
E ABBA
Description
给定$n,m$，问有多少个长为$2(n+m)$的字符串，’A’和’B’各$(n+m)$个，使得该字符串能够被拆成$(n+m)$个长度为2的子序列，其中有$n$个子序列是”AB”，$m$个子序列是”BA”。
数据范围：
$0 \leq n,m \leq 10^3$
Solution
本题最大的障碍在于，题目对于n个AB子序列和m个BA子序列的限制条件，等价于说：对于任意的$i$，字符串前$i$中不能出现A比B多$n$个以上的情况，也不能出现A比B少$m$个以上的情况。证明如下：
充分性：
即证逆否命题：如果字符串中出现了A比B多$n$个以上的情况，则不能满足题目的条件。假设在某个位置，A比B多$n+1$个，则前面这些多出来的$n+1$个A永远不能放在B的后面，也就是最多只有剩下的$(m+n)-(n+1)=m-1$个A能够构成BA，但是$m-1$个BA是不能满足题目的限制条件的。
不能有A比B少$m$个以上的情况的证明类似的。
必要性：
即证满足AB的数量条件即能满足题目的限制条件。考虑构造出题目中要求的$(n+m)$个子序列。从左到右读一个满足AB数量条件的栈，用一个栈来构造这些序列。首先，构造$n$个AB。像括号匹配一样，A当成左括号，B当成右括号。一旦栈中出现了AB，就弹出AB并且令AB子序列数+1，直到构造完$n$个AB。由于在任何时刻不会出现A比B少$m$个的情况，栈中最多有$m$个B，剩下的B全部可以构造成AB。所以这个$n$个AB一定可以构造出来。
栈中可能会剩下很多B，B后面又跟了很多A。而现在我们要构造出$m$个BA。先把栈中已经配对成功的BA弹出，直到栈中全部是A或者全部是B为止。继续从左向右读字符串，如果当前栈顶是B，又读入一个A，则弹出这个BA；若当前栈顶是A，又读入了一个B，则从前面我们构造好的$n$个AB中随便挑一个出来，则之前的AB和现在栈顶的两个AB构成的子序列是ABAB，注意到这个子序列可以拆成A(BA)B，因此我们依然可以构造出一个BA来。后面这种替换是有限度的，如果连续的A碰到了连续的B，则需要之前有足够的AB才行。比如栈里面现在是AAAA，下面4个字符是BBBB，则需要连续替换4次。为了保证替换成功，前面一定要有4个AB才行。但我们现在有前提条件，不存在A比B多$n$个以上的情况，即栈中不可能有$n$个以上的A，也就是说连续替换的次数一定小于等于$n$。而我们已经构造出了$n$个AB，这种替换的一定可行的。
综上，按照上述方法，我们可以构造出题目要求的$(n+m)$个子序列。
有了上面的证明，题目的要求就变成我们自己的等价描述。那么只需要一个dp数组来统计方案就行了。$dp[i][j]$表示长度为$i$的字符串，A的个数减B的个数等于j的方案数。这个dp十分巧妙，dp的范围自动删除掉了A与B数量不符合要求的字符串。那么转移方程为：
$dp[n][0]$就是题目的答案。数组下标不能是负数，稍微处理一下就好了。
Review
很久没打比赛，我的思维现在非常死板。我想这道题的时候误入歧途，一直想用排列组合算这道题。明明我在暴力枚举验证我猜的结论的时候，已经用到了栈来判定字符串是否合法了，但我还是没有想到只要保证A与B之间的数量关系就行了。
当我看到这个结论的时候，觉得这个结论十分简单。但证明起来却发现，充分性很容易想到，必要性的构造却是要花一番功夫才能证明出来的。比赛中我们往往想到了某个结论的充分性，就会匆匆忙忙地猜结论。这样有时候或许侥幸能过题，但一旦过不了就会很伤士气。我平时就要养成严格证明的习惯，并且同时加快证明的速度，对于一个想到的结论要简单地从两个方面证明等价，不要想到一个结论就立刻跃跃欲试，脑袋都空掉了。
H XOR
Description
给$n$个数$a_1, a_2…,a_n$构成的集合，从该集合找出子集，这些子集的异或和为0，求这些子集的集合大小之和。
答案模$1e9+7$
数据范围：
$1 \leq n \leq 10^5$
$0 \leq a_i \leq 10^18$
Solution
首先，求出所有的集合并统计它们的大小是十分困难的。但所有集合的大小和，等于分别讨论每个元素的贡献，再求出每个元素在多少个集合中出现，最后对每个元素出现集合数求和。
集合的异或信息可以用线性基来得到。得到了集合中的一组线性基后，那些不是基的元素无论怎么异或，都可以用这组基得到，也就是和某些基在一起是线性相关的，也就是异或和为0。假设基的大小是$r$，那么还剩$n - r$个不是基的元素。对于每一个剩下的元素分别讨论贡献。$n - r$个元素中，某个元素一定存在的集合数有$2^{n - r - 1}$2^{n - r - 1}$$个。对于每个这样的集合，我都可以选取一些基，使得最后的集合异或和为0。因此，这些元素的贡献都是$2^{n - r - 1}$。
现在要单独讨论剩下的$r$个作为基的元素了。算这$r$个元素的贡献的方法是类似的，如果除掉其中某个元素外，剩余的$n - 1$个元素又构成了一个空间，又选出了一些基，则这个单独的元素又可以被新的基所表示，这个元素的贡献同样是
$2^{n - r - 1}$。
但是，如果运气不好，$r$个基中的某个元素是必不可少的一个基。少了这个基，整个空间就少了一维。换句话说，谁和它的异或和都不能为0。在这样的情况下，这个元素就毫无贡献了。
那么对于作为基的$r$个元素，我们的任务就是判断它们是否可以被任意一个其它的基所表示。对于某个基，有一种很简单的方法能构造出其它$n - 1$个元素的基。先构造出$n - r$个元素的基，它们代表了剩余$n - r$个数的空间。再把$r$个基中除了当前这个基外的$r - 1$个基也加入这个新的空间里面。现在，这个空间就能代表剩下$n - 1$个数了。判断选出的这个基是否在新的空间里即可。
Review
在写这题之前我是不会线性基的，但稍微学了一下就发现，只要学过了线性代数的话很快就能理解线性基。只要理解了线性基，那么这题就非常简单了。
不过这题的一个关键是把问题从求集合大小转换成求每个元素出现集合数。这个转换十分关键。我由于是看着题解写的，没有在这个问题上碰到障碍。但若是要在比赛中快速把难求的问题转换成容易求的问题，就需要极高的解题灵活度了。这种能力只有通过大量写题目才能获得。这也是大量刷题培养手感的意义所在吧。
I Points Division
Description
给$n$个点，每个点有$a,b$两种价值。现在要把所有点分成两个部分$A,B$，要保证$\neg \exists p_i \in A, p_j \in B,x_i \geq x_j \bigwedge y_i \leq y_j$。在$A$里面的点算$a$价值，在$B$里面的点算$B$价值。求最大价值和。
数据范围：
$1 \leq n \leq 10^5$
$1 \leq x_i, y_i, a_i, b_i \leq 10^9$
$所有点互异$
Solution
显然，我们要做的第一件事就是把划分$A,B$的条件弄得更直观一些。题目的要求是：没有两个点，使得左上角的点属于$B$，右下角的点属于$A$。也就是说，如果一个点被分配进了$B$，那么它右下角的所有点都得进入$B$；如果一个点被分配进了$A$，那么它左上角所有的点都得进入$A$。
也就是说,空间被分成了左上角和右下角两部分。那么是谁把空间划分的呢？仔细一想，划分空间的应该是一条折线。折线左上角的点属于$A$，折线右下角的点属于$B$。不妨再规定一下，折线上面的点都属于$B$（同一种划分下，如果折线上的点属于$A$的话，会得到另一条不同的折线，但效果是一样的）。这条折线是从左下向右上的，也就是随着x的增长y是不减的。
分$A,B$算价值太麻烦了。不妨假设所有点最开始都属于$A$，然后我们试图让一些点加入$B$，使得总价值能够有所增长。这样的话，每一个点的价值就唯一了，新价值是$b - a$。
之后要统计结果并保证不重复，不妨尝试对所有点从左到右进行统计。
如果选择了一个点，那么$x$坐标大于等于它且在它下方的点一定也要被加入，也要统计答案。而只要唯一确定了一条折线，我们就确定了一种方案。因此，我们只要考虑折线上的关键点有哪些，让那些右下角的点在计算关键点的时候被计算到。我们从左到右考虑每个点作为关键点的结果。但如果在把当前点加入的同时就想统计右边所有的点，并立刻算出答案，那么再考虑下一个点时，它就不好知道右边有哪些点已经被左边之前的点计算过了。所以，在考虑加入一个关键点的时候，不能立刻算出它的最终贡献，只能考虑在所有已经访问过的点中，它的临时答案。而经过后面那些点时，后面的点会对之前所有$y$坐标大于等于它的临时答案都加上自己的贡献，因为这些点被强制加入了。在讨论当前进入$B$的点时，不直接计算所有右下角的点，而是反过来，先计算一个临时答案，等碰到了右下角的点再加上它们的贡献。这种统计方式是本题的关键。
对于一个关键点，我们已经能统计它右下角的点了，现在来考虑如何计算当前点的临时答案。如果把一个点放到折线上，那么之后下一个点无论怎么选点，都与折线上左边的点无关，而只与现在选的这一个点有关。这表明了选择折线时的子结构性质。既然如此，我们把当前点放到折线上时，也不用管以前的点，只要选一个最优的上一个点就行了。这里的最优，指的是临时答案的最优。对每个点选择上一个点的过程，和动态规划的过程是一样的。发现最优子结构性质，是本题的第二个关键。
现在我们已经可以得到一个正确的算法了：从左到右，从上到下（这个很关键）地枚举每一个点，讨论它作为折线上的点时的情况。对每个点，考虑所有之前走过的，且$y$坐标小于等于它的点（要保证能和这个点构成不降折线），从中选一个临时答案最大的点作为这个点的上一个点。此时，新的这个点的临时答案和上一个点是一样的，因为我们还没有考虑新的这个点自己还有它右边和下面的点。我们把这个点的临时答案也写入记录里面。最后，把已经访问过的，且$y$坐标大于等于它的所有点的临时答案都加上新的这个点的价值，表示这个点对之前所有$y$坐标大于等于它的点的贡献。只要对每个点都进行上述的操作，等处理完最后一个点后，每个点的临时答案就变成了最终答案。从所有最终答案选一个最优的就是题目的答案了。
但是，这样的话时间复杂度似乎不能接受。遍历每个点肯定要右$O(n)$，讨论之前所有点并修改临时答案是$O(n)$，总的时间复杂度是$O(n^2)$，肯定会超时。我们必须优化一下从之前点找最优值以及修改值的过程。
我们可以发现，我们在找之前所有点和修改答案时，都是在访问$y$坐标连续的点。找最大临时答案是找所有$y$小于等于当前点的点，修改是修改$y$大于等于当前点的点。那么，我们可以把所有点的临时答案按照$y$坐标的顺序存储。我们存的不再是某个点答案，而是某个$y$坐标的答案，这样我们依然不会漏掉某些情况：如果后面出现了一个和前面$y$坐标相同的点，如果选了之前的点的话，后面这个点一定要选到。因此，不存在不选新的这个点而只选前面那个点的情况，我们可以放心大胆地覆盖掉之前那个临时答案。现在所有答案都存到了$y$轴上。对于连续区间的修改、查询，我们就可以用线段树来维护了。线段树完成区间加一个值、找到区间最大值这两个操作就行了。
$y$坐标的范围是$[1,10^9]$，读完数据后离散化一下就可以了。
最终时间复杂度是$O(nlogn)$
Review
这道题考察的知识不难，但对问题的思考、分析是本题的难点，在修改哪些点、访问哪些点、如何选择枚举方向等一些细节上也需要多加注意。我感觉这道题出得非常好。
我自己写的时候犯的错误只有搞错了从左到右，从上到下的枚举方向，其它部分都很顺利。由于我是看了题解后再写的，少了很多对于问题的思考、分析，我不能保证下次碰到同样难度的题目也能写出。只能说，很多题目用的算法、数据结构大家都会，但是要把问题转换到能用熟悉的方法来解决的那一步，不需要太多的经验积累，而需要对问题做出正确的分析。碰到难题要敢去想。