北航第十届程序设计竞赛网络预赛题解
A.face the truth
签到题，只需判断m+m是否大于n即可。
B.flame of despair
这道题标程运用了一些略高级的数据结构，现在看不明白不要紧。
将输入的m个数字当做字符串建立AC自动机，建立好fail指针后建成Trie图。
设三维状态f[i][j][mask]为当前的数字modn为i，并且当前在自动机的j号节点上，当前数字中已经出现过mask这个集合中的串了。
显然初态就是f[0][0][0]，终态是f[0][x][全集]。
所以我们需要找一条从初态到终态的路径，使得走过的路径构成的数字串尽可能小。数字最小首先要位数最小，然后字典序最小。所以只需要从初态开始宽度优先搜索，按字典序的顺序扩展状态，第一个访问到的终态的路径就是答案。
注意数字串是不能有前导0的，最后答案里也不会出现-1。 时间复杂度为$O(nm\log{x}2^m)$。
C.he is…
题意非常简单，判断一个字符串中大小写字母是否只出现过1次，并输出对应的下标。注意的是如果大小写字母都只出现过1次则也需要输出-1。
D.幻想乡的危机
题目大意：给一张二分图，左边有$2^n$个点，右边有$2^m$个点，左边第i个点到右边第j个点的权值为i xor j，求最大权匹配。
主要思路：假设$n \leq m$ ($n > m$ 可交换),则所有边最大的权值为$(2^m - 1)$。对于左边的点i,可以匹配右边的点$(2^m - 1)$ xor $i$。由xor的结合律可知$(2^m - 1)$ xor $i$两两不同，且都小于$2^m$。
所以答案为 $2^n(2^m - 1)$。
E.了不起的Th0r
这个题是个比较直白的概率题，可以有很多种思考方向，题解中给出其中一种要算的概率是n分钟每分钟水平都大于等于f1的概率v1和至少连续k分钟水平都大于等于f2的概率v2相并的部分
考虑一个简单的容斥，answer=(v1并v2的部分)=v1+v2-(v1交v2的部分)
v1非常好算，每一分钟水平大于等于f1概率的n次方
v2利用2*k > n这个条件，可以知道这至少连续的>=f2的k分钟在n分钟内出现的话只会出现一次
那么我们可以枚举哪一时间出现了连续的>=f2，并且其前后的一分钟都满足$<$f2的情况，把概率累加起来即可
而v1交v2的概率与算v2的方法基本一致，唯一要多考虑的是剩下的时间里Th0r的水平值还要不低于f1，通过累加同样可以得到
最后通过简单容斥就可以得到答案
当然也可以直接把两个条件共同考虑进行递推，关键要保证每一种情况都被不重复的统计到
有一个小Trick：题目中并没有说f1和f2和p的关系以及n和k的关系，所以在算概率的时候要判断一下
另外整个统计过程实际上经过化简可以转化为一个的公式，很高兴看到也有同学用了这样的方法通过；不过对于本题本意在于让大家使用$O(n)$或$O(n^2)$的方法通过，题解中就不给出公式的推导了。
F.子串
题目大意：给定两个只含字母的字符串a, b，求某个串中的最长子串的长度，使得能在另一个串中找到一个子串，删掉k个字符后所得。
设f[i][j][k]表示a的前i个字符与b的前j个字符最多删除k个字符得到的最长公共子串长度，n, m为串a, b的长度。
则若a[i] = b[j], f[i][j][k] = f[i - 1][j - 1][k] + 1, $1 \leq i \leq n , 1 \leq j \leq m$。
否则，f[i][j][k] = f[i][j][k - 1], $1 \leq i \leq n , 1 \leq j \leq m$
把串a, b反过来再做一遍DP，答案为$max{f[i][j][k]}$
由于数据出得有点弱，所以并不需要$O(n^2k)$也能过，例如一些$O(n^3)$甚至$O(n^4)$的做法也可以（如果把n的数据范围扩大，k的数据范围变小，应该可以卡到一些做法吧？） 部分$O(n^2)$的做法是有问题的。
G.奇怪的强迫症
首先，可以计算出所有的矩形个数，然后减去仅有黑色格子以及仅有白色格子组成的矩形即可。
计算仅有一种颜色格子组成的矩形，可用悬线法达到$O(nm)$的复杂度。具体请搜索悬线法的相应内容。
H.节操君与他的粉丝
显然对于同一条垂直于横坐标轴的直线上的点，只有相邻两个点间的边需要建。 对于不在同一条垂直于横坐标轴的直线上的两个点，考虑Kruskal算法的实现过程。
1、2号边都比3号边要短，所以在枚举到3号边的时候，a、b两点必然已连通，b、c两点必然已连通。所以a、c两点也连通了。所以3号边有没有都无所谓。
因此每个点只需与纵坐标比不比自己小的最小的一个点还有纵坐标不比自己大的最大的一个点连边。边的数量为$O(n)$级别的。求最小生成树即可。
I.暴力大法好
因为是各位数字之积，所以x的有效质因子仅有2,3,5,7。
问[L,R]内有多少符合条件的数，可以用[0,R]的数量减去[0,L-1]的数量。
剩下的就是简单的数位dp，保存的状态是x组合出k位的数有多少种方案数，可以算出x的有效值是1e4的数量级，k最多有18位，状态间的转移时枚举某一位的值，常数级，所以这部分的运算级别大约是1e6，给了1000组数据，每次数位dp时的复杂度是$10\log{n}$的，对这1000组数据状态可以复用，总运算级别在1e7左右。
J.防御塔的搭建
题目大意：给定一个n，随机生成一个n的排列（每个排列都是等概率出现），问将排列变成升序序列的最小交换次数K的期望。
主要思路：对于一个确定的排列p,如果i向pi连一条有向边，就会形成n个点若干个有向环的图。 假设一共有m个环，长度分别为 $a_1…a_m$， 则答案为 $\sum_{i=1}^{m}{a_i - 1}$。 假设长度为$i$的环有$num_i$个， 则答案为 $\sum_{i=1}^{m}{(i-1)num_i}$。
根据期望的线性性可得:
所以问题就转化为求长度为i的环的期望。这是是非常好求的，公式为$C(n,i)(n-i)!(i-1)! \over n!$，$C(n,i)$代表选出i个点在环上，$(n - i)!$代表不在环上的点随意排列，$(i - 1)!$代表固定一个点，其余所有点随意排列。
PS：虽然在出题前的最后一刻昂神给出了一个非常简单的递推公式，但是还以为大部分人想不到这个公式,所以没改题目，导致这题成了全场板刷题。
K.防御塔的能量
题目大意：
给定一棵有向树，每个节点有$c_i,p_i$两个属性，给每个节点定一个[0,m]的值$q_i$。 节点i的权值为$c_i * | { j | |c_i - q_i| > |c_j - q_j|, j是i的后代节点}|$。 树的权值为所有节点权值之和。问树的权值为S的方案个数。
主要思路：
设dp[i][opt][k]代表$abs(c_i-q_i) \leq i$的的节点集合为opt ,且这些节点的权值和为k的方案数。
有一个暴力一点的方法是对于每个i枚举一个集合更新opt和k， dp[i][opt | mask][l] += dp[i-1][opt][k],mask交opt为空。
$l = k + \sum{p_j} *|subtree[j] \cup opt|,j属于mask,subtree[j]是j的后代集合$。
这样复杂度为$O(nmS3^n)$。
枚举一个mask主要是为了避免一种情况：n1是n2的子孙，对于一个i,先用n1更新了答案，再用n2更新了答案。 这样$|c_{n1} - q_{n1}| = |c_{n2}-q_{n2}|$也用于增加n2的权值了。考虑到这是一棵有根树，所以我们只要先更新n2就不会出现问题了。题目也保证了当父亲节点的标号一定小于当前节点的标号，所以更新的时候只要顺序更新就好了。
dp方程：
dp[i][opt | j][l] += dp[i - 1][opt][k] + dp[i][opt][k]，j不属于opt。
| 其中$l = k + \sum{p_j} * | subtree[j] \cup opt | $。 |
可以优化一维空间：dp[opt | j][l] += dp[opt][k]。
时间复杂度为$O(n^2mS2^n)$。
PS:这题的时限很吓人，其实单组数据是可以再1s内出来的，而且多组数据在本机上也只跑了3s。考虑到oj比较慢以及有人常数写的比较大，所以就把时限放到了15s。
L.防御塔的处理器
题目大意：给定一张有向无环图，点上有点权，求最长路径。
主要思路：拓扑排序+dp求最长路即可。
M.防御塔的完善
题目大意：给定n个数，问有多少个i满足$a_i \not = a_{i+1}$，最后答案乘K。
主要思路：模拟