非常厉害的一题贪心题。Orz Lazycal。题目大意是：

• 有 n 条命令，你要从中选出恰好 p 条命令作为候选命令，然后主席会从中选出恰好 k 条命令执行。
• 每条命令有两个属性：如果执行那么主席的会变白的头发数 Ai，如果不执行那么委员会的不满意指数 Bi 。
• 对于主席来说，她首先希望不执行的那 p-k 条给委员会带来的不满意指数最小，然后希望那 k 条命令使自己变白的头发最少。
• 对于你来说（，由于某些原因），你首先希望主席变白的头发最多，然后希望委员会的不满意指数最大。
• 现在让你求应该选出哪 p 条命令。

分析一下：首先我们不能很high地直接把 Ai 最大的 k 条选出来，因为很有可能剩下的 p-k 条会使得我们取不到最好情况。实质上，我们和主席的价值观不一样，所以会导致直接取最大失败。我们应该设下挖坑让主席跳下去，我们可以先确定可被选到的最凶残的 k 条，让主席不得不选它们，然后再考虑剩下的 p-k 使得委员会不满意指数最大，同时又不影响主席选择那 k 条。我们不妨从主席的角度考虑。

我们把 n 条命令按照主席的意愿 (-Bi, +Ai) 排序，那么主席就会按照排序后的顺序从前到后选取命令来执行。注意到最后的 p-k 条命令我们是没必要选出来的，因为选了这其中的任意一条，都会被主席放在最后（很有可能不执行），然后就算这几条的 Ai 再大，也发挥不了用处。

好了，我们知道了主席的顺序，现在我们想让主席的头发白掉，所以我们把前 n-(p-k) 条命令按照我们的意愿 (-Ai) 稳定排序。选出前 k 条，这就是主席必选的 k 条。

现在我们考虑选出剩下的 p-k 条，这 p-k 条不能影响到前面 k 条的选取。因此我们可以先找到 k 条必选命令中，主席最后执行的命令是哪条（也就是第一次排序的结果中最靠后的），然后从这条后面选取。显然，在保证不会影响 k 条的情况下，我们按我们的意愿 (-Bi) 排序选出剩下的 p-k 条即可！

题目大概就是说，让你根据下面规则，生成字符串\(S_n\)，然后求出一个模式串在\(S_n\)中出现次数：

\[ \begin{eqnarray*} S_0 &=& 0\\ S_1 &=& 1\\ S_n &=& S_{n-2} S_{n-1} \end{eqnarray*} \]

这题好像是吴翼出的NOIP模拟题，十分的厉害（真心不是NOIP难度啊）。一眼看到这题和这题的数据范围，我就冒出了矩阵和KMP这两个想法，但是看到模式串长度\(M \leq 10000\)，完全不懂得如何写递推式了……

后来Orz了一下xietutu的题解，发现这题有个非常巧妙的转化。

设\(F_n\)为\(S_n\)中模式串出现的次数，显然有\(F_n=F_{n-2}+F_{n-1}+C_n\)，其中\(C_n\)就是拼接产生的匹配。这个还是很显然的，大家都想得到，但是这个\(C_n\)如何搞到还真是一个问题。

要搞到\(C_n\)还是得利用KMP。我们在对\(S_n\)这个串做KMP的时候，可以发现，如果在\(i\)这个位置匹配是\(S_{n-2} S_{n-1}\)拼接产生的匹配，那么\(i-M+1 \leq len(S_{n-2}) < i\)。这样我们就利用了KMP求出了\(C_n\)。

最神的地方在于：存在一个正整数\(\alpha\)，使得对任意\(2n\geq\alpha\)，都有\(C_{2n} = C_\alpha\)和\(C_{2n+1} = C_{\alpha+1}\)成立。更形象的说，就是当串\(S_n\)的长度达到一定程度的时候，那么拼接产生的匹配的次数将只由\(n\)的奇偶决定，分别为一个定值。这个还是非常好理解的。

那么分奇偶如何能矩阵乱搞呢？注意到

\[ \begin{eqnarray*} F_n &=& F_{n-2} + F_{n-1} + t_1\\ F_{n-1} &=& F_{n-3} + F_{n-2} + t_2 \end{eqnarray*} \]

那么我们两个式子相加一下，就可以得到

\[ F_n = F_{n-3} + 2F_{n-2} + t_1 + t_2 \]

我们分奇偶求出了\(t_1\)和\(t_2\)之后，就可以构造出如下矩阵了：

\[ \begin{bmatrix} F_n\\ F_{n-1}\\ F_{n-2}\\ t_1 + t_2 \end{bmatrix} = \begin{bmatrix} 0 & 2 & 1 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ F_{n-3}\\ t_1 + t_2 \end{bmatrix}\\ = \begin{bmatrix} 0 & 2 & 1 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}^{n-\alpha} \begin{bmatrix} F_{\alpha}\\ F_{\alpha-1}\\ F_{\alpha-2}\\ t_1 + t_2 \end{bmatrix} \]

然后我们就对\(\alpha\)以内的暴力求出来，后面再矩阵快速幂。

这道题觉得十分的厉害，因为看了之后一点想法都没有。不得不Orz Discuss里面的神犇。这题要的是配对，配对这种东西一般是用二分图匹配做的，但是这题完全不懂如何构造出二分图。

Discuss里面的神犇提供了另外一种思路：“图分治”！嗯，这是一个非常神奇的东西，比树分治还神奇。

如果你把一个点u拿出来，然后DFS它所有相邻的点。

对于一个还没有访问过的点v，做完它有2种可能性：

1. 它剩下一条边(v, w)无法匹配。那我们就构造(u, v, w)这样一对
2. 它完美的被解决了，那么我们(u, v)这条边就会悬空，不过没关系，我们可以等待下一次发生这样的事情，比方说是(u, s)，那么我们可以配对(v, u, s)

对于一个比u时间戳大的点v，显然我们就不再考虑去做他了，因为他已经做过了。但是(u, v)这条边还是要考虑的，处理方法和上面2一样。

如果一个点结束的时候还有一条边没有配对，那就返回这条边，让调用它的那个点解决，也就是上面的1。

总之是一个非常神的方法。

About

地址：http://poj.grids.cn/summercamp2012a/

据说都是POJ原题……ABCDE都是一眼题吧，F非常巧妙，G这题第二次遇到还是不会，H完全看不懂。

A: 勇敢与鲁莽

询问Fib[i]是否整除Fib[j]。

可以证明（或者打表发现），问题等价于i是否整除j。需要特判Fib[2]这一项。

B: 一个有意义的校庆

给定若干对事件的先后顺序，求字典序最小的顺序。

拓扑……

C: 雷涛的小猫

有若干个柱子，柱子某些位置上有东西，可以从任意柱子的顶端出发，每次可以向下一格，或者跳到任意柱子上并且掉下delta个位置，问到达地上时最多拿到多少物品。

F[i, j] = max{ F[i-1, j], max(F[i-delta, k]) }

D: Edge Detection

给定一张很大的图像，让你产生一个输出，每个格子的值是原图它和上下左右差的最小值。图像用不多于1000组的数对(value, times)表示接下来有连续times个value。

觉得就是细节处理题吧……估计大家都不爱写，考场上只有3人写，1人AC。

E: Priest John’s Busiest Day

有n个人要结婚并且婚礼时间是[Si, Ti]，在婚礼的开始或者结束，需要Di分钟让神父为他们祝福，也就是[Si, Si+Di]或者[Ti-Di, Ti]，问能否安排使得全部人都能收到祝福。

应该是2-SAT吧，没写过，得补一下。

F: 边配对

给出一个有n个顶点、m条边的简单无向连通图，其中m为偶数。求一个边的一个配对，使得每一对边共用一个顶点。

非常巧妙的一个DFS构造。不得不膜拜Discuss里面的神犇。见另外一篇题解。

G: Color a Tree

给定一棵带点权的树，要求对树染色，第i次染色花费为i*v[node]，一个点仅当它的父亲被染色他才能被染色。求最小花费。

神贪心，上次考试的时候出过，不会，现在还是不会……一开始每个点自己为一个集合，然后按照sum[s]/size[s]贪心，一个集合一个集合地并到父亲节点上。

H: ATP

看不懂题目我会乱说？

其实这题跟GSS2毛线关系都没有，求的根本不一样么，这题求的就是区间和，GSS2那题求的是区间和的最大值……但是相同的是：都是每个数只算一次。

其实看到这题我的想法就是线段树套动态分配的权值线段树，外层的线段树用来限制区间，顺便维护区间和，内层的权值线段树记下每个数出现的次数，这样修改的时候只要对每个数次数次数由0变1或者由1变0进行特判，更新区间和即可。然后就很高兴的去打了，结果连样例都过不去，才发现这样还是有BUG：在外层线段树查询的时候，左右子树的并还是可能有重复的数……后来YY了一下，干脆query就构造一棵内层的线段树，时间复杂度看起来不会很糟糕，但是事实证明空间复杂度相当高（后来下了数据，发现时间复杂度也非常高），所以这是一种非常不可行的方法。

后来请教了下ygy副队，发现对于这种一个数只记一次的题目有一种通用的方法：一维转二维。我们把a[i]转成一个二维点：(last[i], i)，last[i]为i之前a[i]出现的位置，呃，因为这题要求和嘛，所以我们可以给这个二维点一个值a[i]，这样我们就完美的把一维的数转成了二维的点。

接下来查询区间[L, R]就十分愉悦了，直接查找x在[0, L-1]并且y在[L, R]的所有点的和。

然后就是修改了，考虑一下修改一个数会改变多少个点，修改相当于去掉一个数，再添上一个数。对于去掉一个数a[i]，显然会影响到a[i]相邻两个和他相同的数。所以去掉一个数会影响3个点，所以一次修改操作会影响6个点。为了方便的维护一个数和他相同数的位置，可以维护一棵平衡树。

实际写起来还是很好写的，内存也不是很大。

这题我记得去年福建集训有出过，当时太弱了，完全不懂。现在做到这题才突然想起来可以Hash。

首先无论是Hash还是KMP，要验证循环节，都是用一个方法：如果s[A..A+len-1]是s[A..B]的循环节，那么s[A..B-len+1] == s[A+len-1..B]。所以判定的话直接RK Hash就可以搞定了。

但是这题的数据范围有点大，如何破呢？

注意到，如果len是循环节，那么最短循环节必定是len的约数，同时，如果L1和L2都是循环节，那么lcm(L1, L2)必然是循环节！所以我们可以把len质因数分解了，对于每个质因数找出最短的循环节长度，总的最短循环节长度就是它们的积。

这题一开始我想，嗯，这不就是水水的动态树嘛……后来被xietutu神犇吐槽了一下：你仔细看下题目。嗯，我果然沙茶，动态树怎么维护第k大了……后来又请教了下ygy副队，果然又沙茶了：可持久化线段树+启发式合并。

先说启发式合并吧，就是合并两棵树（不管是可持久化线段树还是splay）的时候，把小的树插到的树里面。看起来很暴力的方法，据说可以证明复杂度是log的。

然后这题就是，按DFS序建可持久化线段树，然后对于L操作，就把整棵小树的DFS序插入大树的DFS序列，然后重新建立小树的可持久化线段树。朴素的查询和建树可以参考[BZOJ2588]Spoj 10628. Count on a Tree。

首先，很容易看出来，这个式子是[秦九韶算法](http://en.wikipedia.org/wiki/Horner’s_method)，不考虑取模的话就是：

\[ X_n=a^{n-1}X_1+b\sum_{k=0}^{n-2}a^k \]

嗯，我们可以套上一个等比数列求和公式，变成

\[ t\equiv a^{n-1}X_1+b\cdot\frac{1-a^{n-1}}{1-a} \pmod{p} \]

乘过去

\[ t\left(1-a\right)\equiv \left[\left(1-a\right)X_1-b\right]a^{n-1}+b \pmod{p} \]

这个时候自然是想再除过来，这里有个很明显的坑应该大家都发现了，就是逆元要存在。

\[ a^{n-1}\equiv\frac{t-ta-b}{\left(1-a\right)X_1-b} \pmod{p} \]

然后就是水水的BSGS了。

这题是概率论入门的好题啊，用到了条件概率公式和全概率公式，甚至还用了一点组合公式和代数式的转化

题意

盒子里有\(n\)个球，每个球为红色或者蓝色，其中红球数量\(m\in \left\{ 1..n \right\}\)等概率分布。已知在抽出并扔掉\(p\)个球的情况下有\(q\)个球是红球。问再抽一个球是红球的概率。

预备知识

首先是条件概率公式，在已知事件\(B\)发生的条件下事件\(A\)发生的概率：

\[ P\left(A\right)=\frac{P\left(AB\right)}{P\left(B\right)} \]

接下来就是全概率公式，事件\(A\)发生的概率就是各个情况\(B_k\)下事件\(A\)发生概率的和：

\[ P\left(A\right)=\sum_k{P\left( A|B_k\right)P\left(B_k\right)} \]

最后就是一个奇妙的组合公式：

\[ \sum_{k=0}^s{\binom{k}{n}\binom{s-k}{m}}=\binom{s+1}{n+m+1} \]

这个可以这么理解：要从\(s+1\)个数中选出\(n+m+1\)个数，那么\(k\)相当于在枚举第\(n+1\)个数。

最近真的是智商跌到谷底，基本什么题都得看题解，就连这种水题都是在做HNOI2013 Day1的时候不小心瞄到wjmzbmr的题解的前提下才想出来。

如果我们知道每条边期望走过的次数，那么显然排序后贪心地标号即可。但是要知道每条边走过的次数还是比较困难的，我们可以考虑每个点i期望经过的次数p[i]。

显然，一个点能从除n外所有和他相邻的点j走过来，并且从j点走过来的概率为1/deg[j]。所以，p[i] = sigma(p[j]/deg[j])。另外，要注意到，点1到达次数明显会多1。

接下来我们就会发现，这是一个n-1个未知数、n-1个方程的方程组（为什么？因为不可能从n走到点i，并且n的期望次数为1），然后就可以很愉悦的高斯消元即可。

求出每个点的期望次数p[i]后，每条边(u, v)期望经过的次数ex[i]，ex[i] = p[u]/deg[u] + p[v]/deg[v]。当然了，因为还是不可能从n走出来，所以如果一个端点在n，那么就只有一端可以走。

然后排个序，编号就完了。