Mato is No.1

最近参加了N多模拟赛……现在统一总结一下。
那些有代表性的题目总结一下。

（1）Aug.16 Poetize 杯NOIP模拟赛 I
（竟然AK了，虐场虐得真爽）
第一题：容易发现如果新加入的那条边连接的是同一个连通块，结果乘2加1，如果是不同的连通块，结果不变。证明：如果新边(i, j)的是同一个连通块，则原来i到j必然有路径，设P为i到j的一条路径，则在加入新边以前，原图的所有满足条件的子图都可以对P异或后得到一个新的图，该图仅有i、j两个的度为奇数，其余点的度均为偶数，加入(i, j)之后得到一个新的满足条件的子图，所以乘2，注意(i, j)加上P也是一个满足条件的子图，所以加1；如果原来i和j不在同一个连通块中，那么必定不存在包含(i, j)的满足条件的子图（否则这个子图将(i, j)删掉后会得到两个顶点度数和为奇数的连通块，这是不可能的），所以不变；

（2）Aug.17 Clover 杯NOIP模拟赛 I
第一题：判断一个点是否在三角形（其实对于所有的凸多边形都是这样）时，不需要引射线，只需把三角形的三个顶点按逆时针排序，然后判断该点往三角形的三对相邻顶点（按逆时针）的叉积是否都非负就行了；
第三题：枚举起点，然后状态压缩DP，注意最后一个点必须压缩一下才能不MLE；

（3）Aug.18 Vijos复活邀请赛
第一题：比较WS的几何题。判断圆与边平行于坐标轴的矩形是否相交的时候，可以采用以下的简便方法：一个圆与一个边平行于坐标轴的矩形相交，当且仅当矩形的四个顶点至少有一个在圆内，或者圆的四个横纵坐标最值点（最上、最下、最左、最右的点）至少有一个在矩形内，或者圆心在矩形内。
第三题：主要难在s-t两条路径怎么找出来的问题，方法：以s为根建有根树，找到到t的路径后，将那条不在树中的边的两端点到根的路径上的所有边都标记上，然后，若这棵树中s-t路径上的所有边都没标记，则s-t只有一条路径，否则任选一条s-t路径上的标记边删掉，然后再以s为根建一次有根树，就可以找到第二条s-t路径了；

（4）Aug.19 [Vani有约会]杯邀请赛 II
第二题：本沙茶的80%做法有点另类，是状态压缩DP，因为对于N<=800的数据，只有2、3、5、7、11、13、17、19、23这9个质数可能出现两次以上，其余的都只会出现一次，所以建立10个容器（别忘了1），分别分配1和这9个质数，再对剩下的质数状态压缩即可（一开始只建了9个容器，结果N=27挂了）；

（5）Aug.20 『Citric杯』NOIP提高组模拟赛 I
第一题：这也太太太坑爹了吧囧……居然在精度上做手脚（Orz @sillycross），注意用long double就行了，不过正解是变除法为乘法；

（6）Aug.21 squarefk NOIP模拟赛
第三题：对于一个这样的序列A[0..N-1]：0<=Ai<=Ui，设F(A)为(A的0元素的个数)^(A的所有非0元素的乘积），问题就是求所有A的F值之积。显然，指数是不能取模的，所以要设F[i][j][k]为前i位j个非0，底数为k的值，递推式还是很容易的囧；

（7）Aug.22 Clover 杯NOIP模拟赛 II
第二题：问的是无向图中两点间是否有且仅有一条路径的问题。首先肯定是判是否在同一连通块，然后，对每个连通块任意建一棵生成树，如果这两点在生成树上的路径上的每条边都是桥，显然只有一条路径（因为每条边都必须经过），否则，必有其它的路径（某条边不是桥，也就是可以不经过），所以求桥之后就转化为了一个经典模型了囧……注意求LCA用类似路径剖分的算法比较好写……
第三题：很容易想到递推，F[i][j]：用i个布条，最后一个颜色为j，总方案数（下面的不解释了），问题是，如果至少有一种颜色能和两个或两个以上的颜色相配，还不会有事，因为结果一定不会超过log₂(10¹⁸)，但如果每种颜色都最多只能和一种颜色相配肿么办？因此这个需要特判：首先那些不能和任何颜色相配的肯定只能长度为1，减掉，然后剩下的每种颜色开始的每个长度的旗帜都各有一个，除以颜色总数（上取整）即可。

（8）Aug.23 Poetize 杯NOIP模拟赛 II 暨Tyvj龙年七夕欢乐赛
（第一题正解是贪心，本沙茶用费用流乱搞，T了两个点）
第三题：A先mod B消去整数。首先考虑有限小数的情况。结果是有限小数时，设小数点后位数为M，则必有A*K^M mod B=0，显然这个方程有解的充要条件是B的每个质因数也都得是A*K的质因数，只要把B的质因数当中减掉A的，再看看剩下的质因数K是不是都有，都有的话剩下的就是乱搞一下了囧……如果不都有说明是循环小数，设混循环部分位数为M，循环节位数为R，则有A*(K^(M+R)-K^M) mod B = 0，整理得A*K^M*(K^R-1) mod B = 0，注意K^M与(K^R-1)是互质的，也就是把B的质因数中减掉A的之后，剩下的每个质因数，要么就是K有，要么就是(K^R-1)有。这样，可以用类似于有限小数的办法来求出M，对于剩下的（K没有的）质因数，设它们的积（包含指数）为W，则必有K^R mod W = 1，K和W互质，根据欧拉定理，phi(W)必然是一个解，但不一定是最小正整数解，不过，可以肯定的是，最小正整数解一定是phi(W)的因数（不一定是质因数！！），因为若最小正整数解R0不是phi(W)的因数，设phi(W)=P*R0+Q（0<Q<R0），因为K^(P*R0+Q) = (K^R0)^P * K^Q mod W = 1，而(K^R0)^P mod W显然也是1，所以必有K^Q mod W=1，这样就得到了一个比R0还小的正整数解Q，这与R0是最小正整数解矛盾。因此，枚举phi(W)的因数，再用快速幂判断即可。

（9）Aug.25 『Citric杯』NOIP提高组模拟赛 II
第一题：这也太太太太太太太太太太太太太太太太坑爹了吧囧……其实题目描述有漏洞的，因为题目中并木有说表示结束的询问一定是输入的最后一个……
第三题：这题本沙茶的做法巨另类也巨繁琐（就当字符串算法的综合复习了囧……），首先一头一尾两段的字符串还是很好找的……结尾的那段直接枚举长度，开头的的那段可以在整个字符串左边用一个类似KMP的办法搞（其实只要知道KMP的原理就能用它解决N多奇特问题了囧……），难点在于中间的那段字符串，需要是一个长度为奇数的回文串。为了快速找出一段连续子串里最长的长度为奇数的回文串，可以设G[i]为以i为中心的最长回文串长度，这可以将整个字符串逆序一下后接在原串后面（注意中间要加一个未出现的字符），然后用后缀数组解决（经典模型）。注意在找最长回文串的时候不能直接求中间G[i]的最大值，因为可能延伸出去，正解是二分枚举这个长度，然后在中间不会延伸出去的那一段里找G的最大值，看是否符合要求。总时间复杂度O(NlogN)。

（10）Aug.26 RQNOJ2012年八月月赛
第二题：比赛的时候本沙茶用单调队列硬搞搞不出来，后来写朴素了（悲剧）……正解是将所有的前缀和按照先值递增，再下标递减排序，并串成Dancing Link，然后从按下标从大到小依次删掉每个前缀和，这样，每个前缀和左边的那个一定是比值比它小的前缀和中值最大（值相同则下标最小）的那个，剩下就不解释了囧……

（11）Aug.28 「Clover」杯NOIP模拟赛 III
第三题：先把每条无向边拆成两条有向边，然后对这个有向图求源点为1的单源最短路径图（就是由所有满足D[i] + W<i, j> = D[j]的边<i, j>组成的图），显然从这个图的点1开始无论怎么走都是最短路径，而且这个图显然是无环的（因为原图中的每条边权值都是正数，说实话，如果不满足这个条件，这题就巨难做了，至少本沙茶不会做了），题目中要求的树就是在这个新图中从点1开始的一棵外向树，由于这个新图无环，所以只需要将每个点（除了1）都找一个父结点就行了，结果就是除1外的所有点入度之积。