Mato is No.1

水题就不说了囧……

【1】Oct.30 TYVJ “扫地”杯III NOIP2012模拟赛 day1
（本沙茶这个其实木有参加，是之后捉的……还好AK了囧……Orz liouzhou_101！！）
第一题：
若n=1，则只有当y=x*x时才有唯一解x（这个一定要特判）；
若n>1，由柯西不等式得(a₂²+a₃²+...+a_n²)(1+1+...1（n-1个1）) >= (a₂*1+a₃*1+...+a_n*1)²，
即(n-1)(y-a₁²)>=(x-a₁)²，当且仅当a₂~a_n全部相等时等号成立。
显然a1的最大、小值一定是零点，也就是求方程(n-1)(y-a₁²)=(x-a₁)²的解的问题，若Δ<0则无解，否则求两解之积，可用Vieta定理得出。

第三题：
先求出最短路图（求出S到每个点的最短距离dist0[]和每个点到T的最短距离dist1[]，然后边<i, j>属于最短路图当且仅当dist0[i]+<i, j>长度+dist1[j]等于S-T最短路长），然后那些能炸掉的点就是最短路图的S-T割点（当然S、T本身不能算，另外，最短路图其实应该是个有向图，但这里当做无向图处理），只要对S、T所在的连通块做Tarjan即可。
注意这里最短路的求法：SPFA或许也能过，但由于其不稳定，在比赛的时候如果时间够的话还是写Dijk+heap吧囧……

【2】Nov.2 TYVJ 「Clover 10」杯HE两校联赛(第二轮Day1)
（这个也木有参加，是之后捉的……另外说一下，第二题的题目描述与数据不符）
第三题：
正解见This_poet神犇的空间。
这里说一下本沙茶的方法（70分）：
设F[i][s]表示对X[1..i]进行设置，范围是[1..s]，且从1能够“走出去”（走到大于i的结点）的方案总数，这里有s>i。
枚举“指出去”（X值大于i）的最小的结点为j（1<=j<=i），则有
F[i][s]=∑(F[j-1][i] * (s-i) * s^i-j)，1<=j<=i。
边界：F[0][i]=1（本身木有意义，在乘的时候作为单位元）
这很容易理解。j是要指出去的，因此i+1<=X[j]<=s，有(s-i)种；对于X[1..j-1]，由于j是指出去的最小结点，所以它们都不能指出去，X值范围1..i，但是它们必须“指出j-1"，就是走到j及其后面的部分，否则就会被困住，自然也就走不出去了，所以是F[j-1][i]；对于j+1..i，它们可以随便指，1<=X值<=S，因此是s^i-j。
但是，这个递推式再也无法优化下去了，题目要求O(N²)显然无法办到。
而在正解中，我们关心的不是从1能不能走出i，而是从1最远能走到哪里。这时列出来的递推式就很容易优化到O(N²)。所以，在递推和DP问题中，思路的不同，将会引发完全不同的结果，当一个递推式/转移方程无法优化下去的时候，可以换一个思路来求解。

【3】Nov.3 TYVJ 「Nescafé 29」杯HE两校联赛(第二轮Day2)
第一题：
二分r，求出每个半圆能覆盖到的线段，再看这些线段的并是否为[0, x0]即可。问题就是求线段并的操作是比较易疵的。
首先将所有线段按照左端点递增排序，然后扫描每条线段，并记录目前线段达到的最右位置（就是右端点最大值）maxr，若某条线段的左端点大于前面的maxr则不能覆盖，扫描完了以后，再看第一条线段的左端点和所有线段的maxr是否符合要求即可。
但是，对于本题要注意：（1）由于有可能相离，因此最后的线段数可能不足N条，尤其要注意一条线段都木有的情况；（2）（极其易疵）题目只要求覆盖线段[0, x0]即可，因此，即使在x0右边发现了中断处（左端点大于前面maxr），也木有关系！！（本沙茶当时就在这里搞疵了，跪了2个点）；

第二题：
本沙茶当时使用搜索骗的……可是它的数据实在太弱，本该AC的（最后还是跪了一个点，原因是卡时：ZZZ = ?? / m0，忘了考虑m0=0的情况）；
首先求出图的每个连通块，如果某连通块内的所有结点初始权值之和不为零，无解。否则求出这个图的最小生成森林（用Kruskal），作为初始解（其实很多情况下这就是最优解囧）。
然后开始DFS，使用改变搜索顺序优化：先考查两端点权值都不为零且为相反数的边（因为转移之后可产生两个0点），再考查两端点权值都不为零且不为相反数的边（转移之后可产生一个0点，注意双向转移），最后考查两端点权值有一个为零的边（将0点转移，不会产生新的零点），其它的决策显然不明智。此外每条边只能转移一次。
当然直接这样搜肯定是要T的，但最优解会很快求出，因此可以卡掉。这题可以加启发函数，但本沙茶不加也木有事囧……

第三题：
递推式不说了。注意满足条件的树的高度的范围其实很小（<=16），所以在找到高度上下界之后是不会T的。注意对于结果小于10^8的处理（不需输出多余的0），此时N<=34；

【4】Nov.5 VIJOS NOIP2012模拟赛第三弹
第一题：
容易证明，最优解中虫洞的左端点一定是最左的点。
二分最大距离dist，然后离最左的点距离<=dist的显然都能走到，>dist的则只能使用虫洞。设离最左的点距离>dist的左起第一个点为S，则从S往右枚举每个点为虫洞右端点时，离S的距离和离最右点的距离是否都不大于dist，若都小于，则右端点可以在这里，dist符合条件。

【5】Nov.7 TYVJ NOIP2012提高组模拟赛day1
全是水题，不说了。注意第二题是保留整数而不是四舍五入，第三题的“差”不是“差的绝对值”！！！！！！！！！！！！！！！

【6】Nov.8 TYVJ 「Poetize 10」杯NOIP2012提高组模拟赛day2
第一题：
首先要模型转化一下，题目就是：在一棵树上，每个结点都有一个权值，除根结点外，每个结点都有一个容量（这个容量在题目中是体现在父边上的），选定若干结点，使得树中除根结点外的每个结点子树中选定结点的权值之和都不大于其容量，问最多能选多少结点。
由于数据范围小，本沙茶用类似树形背包的DP硬搞掉了，其实是可以贪心的囧……将结点按权值递增排序，每次选择一个所有祖先容量全部足够的权值最小的结点，最后得到的一定是最优解。
证明：由于决策之间不互相影响，最优子结构性质显然满足，下证贪心选择性质。设目前所有祖先容量全部足够的权值最小的结点为A，某方案中权值比A小的结点的选定情况（就是之前的状态）与选A的方案相同，但木有选A。设该方案中选定的权值不小于A且与A的LCA深度最大的结点为B，LCA(A, B)=P，由于B的权值不小于A，所以若将B删掉，A选上，其到根的路径上P及其以上的部分显然不会超过容量限制，对于P以下的部分，由于P是最深的LCA，因此P以下的部分根本木有被权值不小与A的结点所占用，因此肯定也不会有事，所以，将B删掉、A选上，将得到一个不比原方案差的可行方案，所以贪心选择性质满足。综上，贪心算法是正确的。

第二题：
先将区间按照右端点递增排序，然后扫描：设目前区间的右端点为r，上一个区间的右端点为r0（这里忽略右端点相同的情况，即必有r>r0），则在[r0+1, r]这一段里的最优解有两种可能：（1）若目前区间及其之后的区间内有左端点小于r的，则最优解为r；（2）若目前区间及其之后的区间的左端点全部不小于r，则[r0+1, r]这一段里各个值的能量总和均相同，为保证最小，最优解为r0+1。
接下来的问题是如何快速求出E=r或r0+1时的能量总和。显然在之前的区间里都不能获得能量，后面的区间内，左端点小于等于E的区间的能量为左端点的值，否则为E。由于前面的区间的右端点都小于E，左端点自然小于等于E，所以“后面的区间内，左端点小于等于E的区间个数”就是全部区间内左端点小于等于E的区间个数，这个可以在预处理中将所有左端点递增排序之后用二分查找得出，这些区间的左端点和值也可以记录一个S值来得出，而左端点不小于E的区间个数就是(该区间及其后面的区间总数-左端点小于等于E的区间个数)。
总时间复杂度O(NlogN)；

第三题：
这个题真是折腾死人了囧……其实做法很简单，但巨难想到……
首先把待匹配字符串（设为A，匹配串设为B）展开成2倍的形式，所有的循环串就是所有长度为N的子串了囧……
设F[i][j]为A（展开后的）第i个字符往前，至少到哪才能与B[0..j]匹配（也就是所有能与B[0..j]匹配的A[k..i]中的k的最大值）。显然这样一说，转移方程就出来了囧：
若B[j]="*"，则F[i][j]=max{F[k][j-1], k<=i}
若B[j]≠“*”，则F[i][j]=F[i-1][j-1]（当A[i]=B[j]时）或-INF（当A[i]≠B[j]时），注意边界：j=0时，B[j]必为"*"（根据下面的假设），此时F[i][j]=i+1（不是i！！为了后面的决策），而i=0时，若B[0..j]均为“*”则为1（不是0，同理）否则为-INF。
对于max{F[k][j-1], k<=i}这里，显然可以用辅助数组搞定，注意辅助数组是要滚动的，否则会MLE（其实F也可以滚动）；
接下来，若B[0]="*"，则求出F之后只需要看对于每个i（i>=N-1，N为原长），F[i][M-1]（M为B的长度）是否>=i-N+1即可，因为前面的部分都可以用这个*干掉。
若B[0]≠"*"，则将B最前面的不为"*"的部分拿出来，显然这里是要硬性匹配的，因此先求出这里能匹配A的哪些位置（KMP用不用都可以），B剩下的部分按照B[0]="*"处理，只是最后在找的时候只能找原来B前面硬性匹配的部分可以配上的位置。
若B里面木有"*"，就是普通的字符串匹配的问题了，直接特判掉（同样不必KMP）。这个比较容易漏掉。
总时间复杂度O(NM)。