## Problem 0. Card Game 由于都是随机出牌, Soda要必胜显然是他的最小的$m$张牌的和要大于Beta最大的$m$张牌的和. ## Problem 1. LCS 题目中给出的是两个排列, 于是我们我们可以先把排列分成若干个环, 显然环与环之间是独立的. 事实上对于一个长度为$l (l > 1)$的环, 我们总可以得到一个长度为$l-1$的LCS, 于是这个题的答案就很明显了, 就是$n$减去长度大于$1$的环的数目. ## Problem 2. Beauty of Sequence 考虑每个数字对最终答案的贡献. 对于每个数, 我们只算它出现在连续相同元素的第一个时的贡献, 这样会使计算简便很多. 假设这个数是$a[i]$, 那么i后面的随便选有$2^{n-i}$种. 考虑$a[i]$前面的数, 要么一个不选, 要么选择的最后一个数和$a[i]$不同, 然后就可以算出来了. ## Problem 3. Inversion 令$g_i$表示在$i$前面比$a_i$大的数的个数, $f_i$表示在$i$后面比$a_i$小的数的个数, 这两个都可以用树状数组轻松求出来. 那么对于一个长度$L$的连续子序列, 删掉它之后逆序对减少的个数就是这段区间中$g_i$的和 + 这段区间$f_i$的和 - 这段区间的逆序对个数. 求区间逆序对个数只要用一个树状数组维护就好了, 每次只是删除最左端的一个数和加入最右端的一个数, 分别统计下贡献. ## Problem 4. Tree 考虑每个生成树对答案的贡献. 如果我们确定了最终的树, 那么我们就很容易列出dp方程计算答案. $dp[i][j] = dp[i-1][j-1]*(n-j) + dp[i-1][j]*j$. $dp[i][j]$表示前$i$轮, 已经选出了$j$种边的方案数. 矩阵快速幂搞一下就好了. 对于每棵树的答案都是一样的, 于是我们接下来只需要知道生成树有多少个就好了. 这个可以用Kirchhoff's theorem定理搞定. 维基链接: [http://en.wikipedia.org/wiki/Kirchhoff's_theorem](http://en.wikipedia.org/wiki/Kirchhoff's_theorem) 其中还涉及到行列式对合数取模, 可以采用类似$gcd$的方法进行消元.

##Scaena Felix 题目要求每一个子串都不是括号匹配串，实际上只要使得括号匹配的单元“()”串不是该串的子串即可。所以最终串肯定是连续数个')'以及连续数个'('，统计出其中代价最小的即可。 ##Conturbatio 可以发现如果一个矩阵被全部攻击到，很显然要么是因为它的每一行都有车，或者每一列都有车。 所以只需要记录一下哪些行和哪些列有车，对于每个询问只需要做一个前缀和就可以知道答案了。 ##Desiderium 实际上计算的是所有子集的并集长度之和。 把坐标离散化之后，可以单独考虑每一小段区间在并集内部的出现次数，如果有$m$个大区间覆盖这段小区间，就会发现当前仅当这$m$个区间都不在子集中时，这一小段区间不会成为并集中的一部分，所以一共有$2^n-2^{n-m}$个子集包含这段小区间。把长度乘出现次数累计到答案里即可。 ##Numquam vincar 这题我觉得是一个比较有(无)趣(聊)的题。 对于一个串来说我们粗略的看，它有多少个子串只和它各个位置的相等关系有关，所以我们没必要在乎字符集有多大，只需要枚举n的所有划分，处理出$cnt[i][j][k]$表示长度为$i$的串有$j$个不同的字符且有$k$个子串的方案，每一次枚举的时候要么后面加一个已经出现过的字符，要么加一个新的字符。这样搜索状态总数只有$Bell_n$个，对于$n=10$绰绰有余。 对于每次询问，只需要枚举一下这个串有多少个不同的字符，然后组合数统计即可。 ##Nux Walpurgis 首先使用Prim算法求出这个图的最小生成树，对于每条非树边都对于着树上的一条链。如果有一条非树边的权值和对应链上的某条树边相等，就可以交换这两条边使得树边不一定在最小生成树上。 所以我们需要对每条树边，看所有覆盖他的非树边的权值有没有和本身相等的，因为非树边的权值不会小于树边，所以只需看覆盖该树边的非树边的最小权值。 这个问题就很传统了，但因为min操作没有逆运算，不能单纯的像求和那样打前缀和的标记。数据范围也不支持树链剖分等做法，但是可以以每个点为根都做一次以下过程，用以根为端点的非树边去覆盖这棵树，这样就没有了逆运算的过程。 综上，时间复杂度为$O(n^2)$。

## Clarke and minecraft 贪心，将同样材料堆到一格里，然后每一次都装满36个格子，装满就运即可。注意取上界操作。 ## Clarke and problem 设$d(i, j)$表示前$i$个数，模$p$为$j$的方案数，则容易得到$d(0, 0)=1, d(i, j)=d(i-1, j)+\sum_{j=0}^{p-1} d(i-1, (j-a[i]) \ mod \ p)$，很多人没1a是因为没注意$|a_i| \le 10^9$ ## Clarke and puzzle **十分抱歉，由于时限设置错误，卡了常数，puzzle的题已经重测。** 题目要求二维的nim游戏，考虑到nim的结论是xor和为0则必败、否则必胜，那么我们只需要维护子矩阵的xor和。由于xor有前缀和性质，所以我们可以用一个二维bit来维护(1, 1)-(a, b)的矩阵的xor和，然后由$sum(x2, y2) \ xor \ sum(x2, y1-1) \ xor \ sum(x1-1, y2) \ xor \ sum(x1-1, y1-1)$来得到答案即可。单点修改在bit上是很容易的。 ## Clarke and expression 分析得到: '(': 左边：类型； 右边：变量、类型 ')': 左边：')'、变量; 右边：'*'、')'、末尾 *: 左边：')'、变量; 右边：类型、变量 变量: 左边：开头、'*'、'('; 右边：末尾、'*'、')' 类型: 左边：开头、'*'、'('; 右边：'(' 那么由于题目很特殊'('左边只可能是类型，所以我们直接贪心的用上面的分析判断是否合法。 判断合法后，我们将变量名替换成这个变量的类型序号，然后可以dp一下得到最终类型转换是否合法： 令$f(l, r)$表示$s[l, r]$返回的类型。 $f(l, r) = f(l, k-1) * [ \exists edge(a[k-1], f(k+1, r-1) ] * [s[r]=')', s[k]='(']$ $f(l, r) = f(l, r-1) * [ \exists edge(f(l, r-1), a[r] ) ] * [s[r] \neq ')'$ 如果$f(1, len(E))$不是0的话，那么输出其类型即可。否则非法。 有一种很正常的题解： 比较正常的思路（套路）是，分析文法，转成LL(1)文法的，准备好一个词法分析器，写一个递归下降语法分析器（同时穿插进行语义检查），全部无误就得到最后类型结果。 但是这题主要坑点在于，前面的变量名和类型名检查。要做的事情多又琐碎，易错。 还有如果真的递归下降，递归实现很可能爆栈，需要开栈。（然而标程并不是这么做的） ## Clarke and hunger games 由于没有强制在线，我们可以对操作建立一棵操作树（在建立的时候注意操作3如果h指向的也是一个操作3，那么我们还是要指向这个操作指向的东西，这个可以用一个数组记录完成）。由于link的逆操作是cut，cut的逆操作是link，所以我们dfs一遍即可。 注意： 1.dfs可能爆栈、请自己写栈或开黑科技。 2.很多人的cut操作写炸了，请自己写个暴力来拍一下。

## 1001 Pyramid Split 首先锥体体积公式：$V = s * h / 3$,$s$为底面积，$h$为锥体的高 这个题要查找高度，所以要二分高度，判断平均割平面切割上方（或者下方）体积和是否为总体积一半即可。 注意答案是取整数部分，并非四舍五入和向上取整。 总复杂度：$O(n*logA)$ ## 1002 Xiao Ming climbing 方法一: 直接BFS，用$min[x][y][d]$表示到达$(x,y)$通过$K-d$步所需要消耗的最少体力 到达任意一点$(x,y)$,且活力值为$d$时,仅当消耗体力小于$min[x][y][d]$时继续更新 注意当$K = 0$时,无论如何都是No Answer 同时,起点和终点可以重合,当$K != 0$时 消耗体力为$0.00$ 方法二: 优先队列的BFS ## 1003 Peace small elephant 这个题用状态转移得到矩阵，再矩阵快速幂就可以了。 合体象的攻击范围是变少了的，我们可以理解为，一个小象会对自身的四个正方向产生保护，可以得到结论，只要附近有小象，我们就可以放。 可以枚举$i$行的所有状态和$i - 1$行的所有状态，判断是否可以转移。 如果在第$i$行的$j$列上放了小象，那么只有在$i-1$行$j$列没有小象，$i$行$j-1$列没有放小象$i-1$行$j-1$列有小象，或者$i$行$j+1$列没有小象$i-1$行$j+1$列有小象时，状态是不能转移的。 将状态转移方程改为矩阵，最后矩阵快速幂就可以了。 总复杂度$O(logn*2^{21})$ ## 1004 A serious math problem 这题是一个数位DP。 $dp[i][j]$表示0到10的$i$次方中有多少个值为$j$的 转移方程：$dp[i][j \oplus k] = dp[i][j \oplus k] + dp[i-1][k]$。 $d[j][i]$表示$j$和“10的$i$次方中$0~15$的值”的异或总和 转移方程：$d[j][i] = d[j][i] + (j \oplus k) * dp[i][k]$ 我们分别可以打表得到,本来是要卡常的，我怕你们打我。 这样我们可求$0$到$L - 1$的值$ansl$和$0$到$R$的值$ansr$，即可得到答案$ansr - ansl$。 ## 1005 Transmigration tree 其实不难想到，路径有三种 一、从$u$直接到$v$ 二、从$u(v)$到某个叶子，通过叶子到根，再从根到$v(u)$ 三、这种情况容易被忽略，就是从$u$到叶子，通过叶子到根，根再到叶子，然后叶子到$v$ 第一种情况是树上路径和的裸题，可以用树链剖分+线段树写，由于是静态树也可以直接用LCA写。 第二、三种我们需要求$d[x]$和$dp[x]$，$d[x]$表示根到节点$x$的路径和，$dp[x]$表示$x$到所有叶子中的最小路径和， $d[x]$很好求，dfs一遍就行了。 $dp[x]$可以用BFS写，将所有叶子与始点$s$连边，$dp[x]$即表示$x$点到$s$的最短路，用路径最短优先BFS过去就行了， 还可以直接用树形DP写，定义$down[x]$表示$x$到自身叶子的最短路 那么有$dp[x] = max(dp[father[x]] + w[x], down[x])$。 觉得这题过于简单的，可以自行想想加上单点修改后要怎么写。

## A problem of sorting 选择任意喜欢的排序方法即可。注意名字中可能有空格。 ## The Factor 对于每一个数字，它有用的部分其实只有它的所有质因子（包括相等的）。求出所有数的所有质因子中最小的两个，相乘就是答案。如果所有数字的质因子个数不到两个，那么就是无解。时间复杂度$O(n*sqrt(a))$。 ## Geometric Progression 判断是否为等比数列，可以检验对所有$1 < i < n \quad A[i-1]*A[i+1]=A[i]*A[i]$ 是否都成立。 直接高精度也是资词的。 比较简单的方法是选择若干质数（保证乘积大于$10^{200}$），在模意义下检验。复杂度$O(k*n)$。$k$表示选取的质数个数。 ## Reflect  ## AB String 注意到答案的最长长度是$log(K)$的。 我们可以把原串中$ \leq logK$左右的串都拿出来排序。然后直接二分答案求解即可。时间复杂度为$(T*|S|*(logK)^2)$。 更优的做法是对原串建出SAM后缀自动机后，设$F[i][j]$表示到SAM上的状态$i$，还有长度$j$时有多少可能的$T$串数量。 转移也是容易的。最后每次按位统计一下即可。时间复杂度为$O((|S|+T)logK)$。