Mato is No.1

     摘要: 原题地址本题就是，有N个变量，其取值只可能有三种：1、2、3。现在已知它们之间的一些大小关系，求有多少对变量(I, J)满足(I的值+J的值)一定>或=或<(A的值+B的值)，A、B是指定的两个变量，且I、J、A、B互不相同。首先，对于值相等的变量，直接建出无向图，按连通块缩点，再考虑大于/小于关系，如果I的值大于J则在I所在连通块与J所在连通块之间连一条有向边（从I到J）…...  阅读全文

RQNOJ187 巧置挡板
———————————————————————————————————————————————————
【背景（神犇不要囧视，3x）】
本沙茶最近开始猛攻搜索、近似、随机等算法，目标是A掉AHOI2012的后3题（在哪跌倒就从哪爬起）。昨天晚上找到这题，发现是搜索，于是开始捉……结果被折腾了一晚上加一上午才A掉，不过，看在这题可以系统性的反映DFS优化的一般步骤，忍了……另外，这题是本沙茶在RQNOJ上通过的第400题……回想起通过第300题的时候已经是近三年半之前了……真颓废啊……
———————————————————————————————————————————————————
普通DFS（不加迭代）的优化方法主要有：
（1）可行性剪枝，如果遇到已经无法产生可行解的情况就剪枝，有时候，可行性剪枝也可以指在搜索过程中对不合法情况的剔除；
（2）最优性剪枝：如果遇到已经无法产生比目前得到的最优解还要优的解的情况就剪枝，这其中包括启发式最优性剪枝（即分支限界），对目前解的进展情况作乐观估计，如果估计值都不能超越目前的最优解，则剪枝；
（3）通过改变搜索顺序，尽早得出较优解，从而为后面的剪枝提供余地；
（4）通过预处理等手段，提前得到启发值或者较优解，为后面的剪枝提供余地；

一般步骤：
（1）预处理，当然是写在最前面，在搜索前得到启发值等东东；
（2）搜索过程中，先写最优性剪枝（包括已经到达搜索终点了，也应该判断一下，提前排除不是最优解的情况）；
（3）再判定搜索终点，如果到了，也不要马上更新解，而是要判定这个解是否符合要求，再更新；
（4）若未到终点，再写可行性剪枝；
（5）最后写搜索过程，包括需要改变搜索顺序的情况。

注意事项：数组的分层问题。
这是一个很严重的问题，因为分层出错很可能会导致一些很怪的错误出现，难以发现。在搜索题的调试技巧这一篇中，已经提到了这个问题，本题又涉及到了。
一般来说，搜索过程中使用的数组（包括变量，可以视为零维数组）可以分为以下三类：
（1）在搜索过程中，只会引用其值，不会修改的数组（比如预处理中得到的那些东东），相当于常量；
（2）在搜索过程中，会改变其值，但在搜索完毕后能改回原值的数组；
（3）在搜索过程中，会改变其值，且在搜索完毕后也改不回原值的数组。
对于（1）（2）类数组，不需分层，但对于第（3）类数组一定要分层。这是因为这些数组在多层搜索中都需要修改，而且搜索完了也改不回来，如果不分层，则当后面的搜索完毕以后，要继续搜索前面的，引用的将是后面的值，就会出错。
对于第（3）类数组，有的已经“自然分层”（每层搜索修改的元素都不一样），比如本题代码中的R[][]、C[][]。然而有的并没有自然分层，比如本题的len、pos[]、tmp[]等，因此对于这些数组，需要再加一维，对于不同层使用该维不同的元素即可。

下面是本题的算法：
使用DFS搜索每个位置的挡板是否需要放。搜索时，先搜竖的再搜横的，由于题目要求每个连通块都必须是矩形，因此对于竖的，如果该位置的上方两个相邻位置的横的没有全放（包括只放了一个），则该位置的竖的放不放取决于其上一行对应位置的竖的有没有放（第一行除外），如果两个横的都放了，则这里的竖的既可以放也可以不放（先搜不放的情况）。当然，一行的两个1之间必须至少有一个竖的，这是可行性限制。在搜横的的时候，按照该行所放的竖的，分成若干段，显然每一段要么下面都用横的封上，要么一个都不封上。其中，如果该段所在的连通块里面有1，且下一行对应位置也有1，则必须封上；若该段所在连通块里面没有1，则不能封上（因为不能有一个连通块里一个1都没有），否则可以自由选择封还是不封（当然也是先搜不封的）。这样一直搜到最后一行的竖的后，还要判断最后一行有没有连通块里没1，若没有，则为一个可行解。启发式优化：设D[i]为第i行及以后至少要几个挡板（若某行有K个1，则至少需要(K-1)个竖的；若某列有K个1，则至少需要(K-1)个横的，累加起来即可，显然这是乐观估计），D[i]可以预处理出来，当做启发值。

代码：

原题地址
典型的二次递推/DP的题目。
首先，题目中的“不便利值”指的是某个点到根的路径上的木有被选定链覆盖的边的条数。

第一问：设F[i][0..2]分别为当子树i中结点i的状态为不参与链（0）、作为某链端点（1）、作为某链中间点（2）时，子树i中的结点到i的最小不便利值。为了得到F，需要设立G[j][k(0..2)]表示结点i的前j棵子树中，有k棵的根结点与结点i接上的最小的最大不便利值。显然，不和i接上的，状态为0、1、2都行，但不便利值要加1，而和i接上的状态只能是0或1，不加1。

问题是第二问。第二问的难点在于，当i取得最小不便利值时，i的每个子结点并非都取到最小不便利值。举个例子，结点i的最小不便利值为3，它的某个子结点j的最小不便利值为2，则当j与i接上时，子树j的内部既可以取不便利值为2的解，也可以取不便利值为3的解。所以，为了解决第二问，需要求出结点i的最小不便利值为x的解的总数。万幸的是，x的范围并不是太大，可以证明，x不会超过log₃N（下取整），也就是当N=100000时x最大为10。因此，最后仍然不会T掉。

这题的一个启示就是，在求类似于“最优解计数”的问题中，不要认为当后面的状态取得最优解时，前面的状态一定取得最优解。因此，不能只记录某状态取得最优解的个数，而要记录该状态取得每一个可行解时的个数。

代码：

相关链接

由此看来，省队（准确来说是“省集训队”）的压力减小很多了囧……因为即使省选题目再坑爹，也有NOIP的40%垫着……
显然，NOIP必须得高分，甩开别人，甩得越远越好，这样才能在省集训队的选拔中占据优势……
不过，进了省集训队之后又肿么选，就不知道了……

而且估计明年的省选应该木有这么坑爹了囧……
其实……最近发现即使是AHOI2012的后3题，只要会各种搜索+近似也是可以搞到很多分的……至少加起来100分木问题（总分200就A队了）……

所以，实力终究是硬道理！！！！！！！！！！！！！！！！！！！！！！！！！！！！

我要进省队！！！！
我要进国家集训队！！！！

最近做了两道LIS模型题，感觉到模型比较好，总结一下囧。
【1】[HAOI2007]上升序列
预处理：设F[i]为以i开头的最长上升序列的长度，怎么求不用说了吧囧……
假设目前需要求长度为M的、标号字典序最小的上升序列，显然其第一个元素A[i]必须满足F[i]>=M（注意，不是等于，是大于等于！），找到满足这个条件的最小的i即可。然后，设目前已经求出了该序列的第x个元素为A[y]，则第(x+1)个元素A[z]需要满足的条件是A[z]>A[y]，且F[z]=F[y]-1，找到满足这个条件的最小的z即为该序列的第(x+1)个元素。按照这种方法，扫描一遍就可以求出整个序列，时间复杂度为O(N)。如果整个序列的最长上升序列长度<M，则无解。

代码：
【2】[HAOI2006]数字序列
首先，由于序列的所有元素都是整数，所以可以将原序列的所有元素减去它的下标，这样就把上升序列转化为不下降序列了。
第一问的结果显然就是(N-新序列的最长不下降序列长度)。关键在于第二问。以下A均表示新序列。
设F[i]为以A[i]结尾的最长不下降序列长度（同样，求法不用说了），G[i]为在A[i]不修改的前提下将A[0..i]转变为不下降序列的最小修改量。首先求出F[i]，然后在求G[i]时，枚举上一个“不动点”（就是不修改的元素）A[j]（显然必须满足A[j]<=A[i]且F[j]=F[i]-1），这样最小修改量就是G[j]+(将A[j..i]转变为不下降序列的最小修改量）。可以证明，A[j..i]的最优修改方案必然是将A[j+1..t]全部修改为A[j]，A[t+1..i]全部修改为A[i]，这里t是一个[j..i]范围的值。问题就是如何求出最优的t？
一开始，假设t=j，即把A[j+1..i-1]全部修改为A[i]，计算出修改量，设为S。然后，由于A[j+1..i-1]之间的元素要么小于A[j]，要么大于A[i]（这个是显然的囧），我们把小于A[j]的元素称为“小数”，把大于A[i]的元素称为“大数”，则当t取t0时，修改量为S-(A[i]-A[j])*(A[j+1..t0]中的“小数”个数减去“大数”个数）。这样，只需扫描一下，求出使得(A[j+1..t0]中的“小数”个数减去“大数”个数）值最大的t0即可。
当然还有一个问题，对于同一个i，满足“A[j]<=A[i]且F[j]=F[i]-1”的元素个数可能有很多，如果一个一个枚举，一个一个扫描，会很慢的囧……解决方法是，求出满足这个条件的j中最小的一个，设为j0，然后把A[j0+1..i-1]中的所有“小数”和“大数”全部处理出来，然后用类似前缀和的方法就能搞了囧……当然，为了找到j0，需要建一个二分图，边为(F[i], i)。
最后，为了方便，可以把A序列的左边加一个-INF，右边加一个+INF。最后总的时间复杂度，理论上为O(N²)，但由于是随机数据，所以远远达不到这个级别。

代码：

     摘要: 原题地址这个算法是由本沙茶在现场使用的那个做法扩展得来的……其实AC不了，后两个点会因为常数过大而T掉……但在BZOJ上算总时间的话能AC……首先考虑树的情形。设F[i]为从点i开始，往子树i里面走，到达叶结点的期望长度，则很容易得到递推公式：F[i] = (ΣF[j] + W(i, j)) / K，其中j是i的子结...  阅读全文

最近参加了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外的所有点入度之积。

从今天开始，本沙茶的这个空间重新启用。
———————————————————————————————————————————————————
AHOI2012，耻辱的过去，
AHOI2013，光明的未来，
为了自己的集训队梦想，从今天开始，全力复仇！！！
———————————————————————————————————————————————————
以后这个空间里的文章题目都会以【AHOI2013复仇】为前缀……