Mato is No.1

本沙茶自从NOI2011结束以来，陷入危机，具体表现为：编程速度变慢；想题目的时候容易想偏；编程时比较不专注，容易想到别的东西上去；容易受到杂念的干扰。这次危机是本沙茶至今为止遇到的最严重的一次危机，到了9月中下旬，这次危机发展到极限，几乎到了绝望的边缘。因此，本沙茶在长达1个多月的时间里，没有什么实质性的进展，也没有在这个空间里作总结。

在十一假期的前四天里，本沙茶努力调整状态，终于在10月4日（也就是今天），正式摆脱了危机，恢复到了正常状态。以后，本沙茶会继续在这里作总结，同时争取尽可能大的提高，在本赛季的各项比赛中竭尽全力，争取好成绩。

感谢BZOJ对本沙茶在摆脱危机过程中的帮助。
Orz WJMZBMR等神犇

【背景（神犇不要鄙视）】
本沙茶今年AHOI的时候，遇到裸的最佳匹配的题，竟然把KM算法搞忘了，幸亏是WJMZBMR神犇保佑，临时乱弄一通，想起来了……这MS反映出了本沙茶以前在看某些经典算法的时候看得不深，木有理解透彻……
前几天又遇到一道最佳匹配的题，发现KM算法竟然又忘了……米办法，只有把这个搞死人的算法的具体过程重新看了一遍，终于懂了……
【KM算法及其具体过程】
（1）可行点标：每个点有一个标号，记lx[i]为X方点i的标号，ly[j]为Y方点j的标号。如果对于图中的任意边(i, j, W)都有lx[i]+ly[j]>=W，则这一组点标是可行的。特别地，对于lx[i]+ly[j]=W的边(i, j, W)，称为可行边；
（2）KM算法的核心思想就是通过修改某些点的标号（但要满足点标始终是可行的），不断增加图中的可行边总数，直到图中存在仅由可行边组成的完全匹配为止，此时这个匹配一定是最佳的（因为由可行点标的的定义，图中的任意一个完全匹配，其边权总和均不大于所有点的标号之和，而仅由可行边组成的完全匹配的边权总和等于所有点的标号之和，故这个匹配是最佳的）。一开始，求出每个点的初始标号：lx[i]=max{e.W|e.x=i}（即每个X方点的初始标号为与这个X方点相关联的权值最大的边的权值），ly[j]=0（即每个Y方点的初始标号为0）。这个初始点标显然是可行的，并且，与任意一个X方点关联的边中至少有一条可行边；
（3）然后，从每个X方点开始DFS增广。DFS增广的过程与最大匹配的Hungary算法基本相同，只是要注意两点：一是只找可行边，二是要把搜索过程中遍历到的X方点全部记下来（可以用vst搞一下），以进行后面的修改；
（4）增广的结果有两种：若成功（找到了增广轨），则该点增广完成，进入下一个点的增广。若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增加。方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，所有在增广轨中的Y方点的标号全部加上一个常数d，则对于图中的任意一条边(i, j, W)（i为X方点，j为Y方点）：
<1>i和j都在增广轨中：此时边(i, j)的(lx[i]+ly[j])值不变，也就是这条边的可行性不变（原来是可行边则现在仍是，原来不是则现在仍不是）；
<2>i在增广轨中而j不在：此时边(i, j)的(lx[i]+ly[j])的值减少了d，也就是原来这条边不是可行边（否则j就会被遍历到了），而现在可能是；
<3>j在增广轨中而i不在：此时边(i, j)的(lx[i]+ly[j])的值增加了d，也就是原来这条边不是可行边（若这条边是可行边，则在遍历到j时会紧接着执行DFS(i)，此时i就会被遍历到），现在仍不是；
<4>i和j都不在增广轨中：此时边(i, j)的(lx[i]+ly[j])值不变，也就是这条边的可行性不变。
这样，在进行了这一步修改操作后，图中原来的可行边仍可行，而原来不可行的边现在则可能变为可行边。那么d的值应取多少？显然，整个点标不能失去可行性，也就是对于上述的第<2>类边，其lx[i]+ly[j]>=W这一性质不能被改变，故取所有第<2>类边的(lx[i]+ly[j]-W)的最小值作为d值即可。这样一方面可以保证点标的可行性，另一方面，经过这一步后，图中至少会增加一条可行边。
（5）修改后，继续对这个X方点DFS增广，若还失败则继续修改，直到成功为止；

下面分析整个算法的时间复杂度：每次修改后，图中至少会增加一条可行边，故最多增广M次、修改M次就可以找到仅由可行边组成的完全匹配（除非图中不存在完全匹配，这个可以通过预处理得到），故整个算法的时间复杂度为O(M * (N + 一次修改点标的时间))。而一次修改点标的时间取决于计算d值的时间，如果暴力枚举计算，这一步的时间为O(M)，优化：可以对每个Y方点设立一个slk值，表示在DFS增广过程中，所有搜到的与该Y方点关联的边的(lx+ly-W)的最小值（这样的边的X方点必然在增广轨中）。每次DFS增广前，将所有Y方点的slk值设为+∞，若增广失败，则取所有不在增广轨中的Y方点的slk值的最小值为d值。这样一次修改点标的时间降为O(N)，总时间复杂度降为O(NM)。

需要注意的一点是，在增广过程中需要记下每个X、Y方点是否被遍历到，即fx[i]、fy[j]。因此，在每次增广前（不是对每个X方点增广前）就要将所有fx和fy值清空。

代码：

 

【1】IOI2009 hiring（这个在各大OJ上都找不到囧，只能看这里了囧，第11页）
可以发现本题就是求一个比率rate，使得第i个人（如果用的话）工资为rate*Qi，并且还要满足以下两个限制条件：
（1）每人的最低工资限制：第i个人如果用的话，有rate*Qi>=Si，即rate>=Si/Qi；
（2）总开销限制：rate*所有用的人的Q值之和<=W，即所有用的人的Q值之和<=W/rate。
这样，可以先将所有人按照(S/Q)的值递增排序，然后枚举需要用的最后一个人（排序后的，也就是S/Q值最大的那个人），设为i，则总花费最省的做法显然是取rate=Si/Qi。然后根据（2）式得出“所有用的人的Q值之和”的最大值W0=W/rate，其中，第i个人是必须要用的，故将W0值先减去Qi（若W0<Qi，则第i个人不可使用），剩下的问题就变成了在第0~(i-1)个人中（排序后的）选取一些人，使得他们的Q值之和不大于W0，并且选取的人尽可能多。显然这可以用贪心来实现，即选取Q值最小的若干个人。接下来，由于题目中N<=500000，说明需要用数据结构来优化，可是Q的上限只有20000且Q为正整数，因此，线段树是最好的选择。建立一棵表示[1, 20000]的线段树，每个结点存放两个额外的值：sz和sum，分别表示Q值位于该结点代表的区间内的人的总数以及这些人的Q值总和。然后，需要解决上述子问题时，从根结点开始考察结点的sz值，不断往下找即可（这有点像平衡树的找第K小的操作）。
总时间复杂度：O(N * (log20000 + logN))（还有排序的时间）
代码

【2】RQNOJ469
先按照任意一种属性（这里为A）递增排序，然后枚举值i，排序后第1位~第i位的全部给A（看A属性，它们中A属性最大的一定是i），排序后第(i+1)位及以后的，看其B、C两种属性的大小，若B属性更小就看B属性，若C属性更小就看C属性，然后得出两种属性的最大值即可。因此可以得到下面的算法：先排序，然后将所有的毛的B或C属性（哪种更小就看哪种）插入平衡树（这里需要两棵平衡树，一棵存放B属性的值，一棵存放C属性的值），然后递增枚举i（注意i=0的情况不要漏掉），将第i位的B或C属性在平衡树中删除，然后找出两棵平衡树中的最大值即可。
但是需要注意一种特殊情况：所有的毛都看同一个属性，此时按照上面的算法可能求不出最优解，比如：
10 6 5
10 2 8
此时，第1个C属性更小，第2个B属性更小，若第1个看C属性，第2个看B属性，则总和为5+2=7，而如果两个都看B属性则总和为6。此时就需要特判（预先求出三种属性中的最大值），然后再用上面的算法求解，就能保证求出最优解了。
代码

【3】PKU2985
并查集+平衡树基本操作，水题，不解释。
代码

【4】HNOI2011 括号匹配Brackets（目前可以看这个帖子）
Splay Tree维护序列问题。对于一段括号序列A[1..len]，定义优先级P[0..len]如下：
P[0]=0
P[i]=P[i-1]+1（i>0且A[i]为左括号）
P[i]=P[i-1]-1（i>0且A[i]为右括号）
然后，Splay Tree的每个结点需要记录一个Z值和M值，分别表示该结点代表的括号序列中最后一个元素的优先级和优先级最小的元素的优先级。则可以证明：这段括号序列调整至平衡至少需要改变的括号数目为(-M+K+1) / 2，其中K=Z+((-M+1)/2)*2（注意这里的/是整除），此外由于有swap和invert两个操作，因此需要记录RM、TM、RTM值，分别表示将该括号序列执行swap操作后的序列的M值、执行invert操作后的序列的M值，以及同时执行swap和invert操作后序列的M值。
不过，本题需要严重注意的是：虽然replace操作的标记（代码中的mk0）会覆盖掉swap（代码中的mk1）和invert（代码中的mk2）操作的标记，但是在下放标记的时候，需要对三种标记逐一判断，mk0和mk1、mk2并不是不能共存的！因为有可能先打上mk0标记后再打上mk1或mk2标记。
本题虽然是静态的，但仍然不能使用线段树，因为线段树无法支持整体翻转（rev）操作。
代码

     摘要: 【原题见这里】很明显的精确覆盖的模型，12个零件，再加上它们经过旋转、翻转后的不同形状，共60种，每种又可以放在不同的位置（只看最左上的那个珠子）一种零件的一种位置就是一行。列（限制）有两种：每个格子只能放一个（55列），以及每个零件（注意是每个零件，不是每种零件）只能用一次（12列），共67列。预先放的那些零件可以看成预先选中的行。然后DLX精确覆盖即可。下面是DLX精确覆盖的几个易疵点：（1）...  阅读全文