problem A

注意到题目说明每个接头都是不一样的，那么变化之后的接头也是不一样的。

枚举第一个接头对应哪个设备，然后那些列要变化就知道了。

然后变完了看看能不能完全匹配上。这里我直接扔到vector里排序了。

problem B

显然先要枚举根。

然后跑一个dfs,记录每个点的子树至少要删多少个点。

如果一个点只有一个儿子就删了，多个儿子取能留下的点最多的两个。

problem C

这个题比较有趣。

大概意思是有两个随机排列生成器，略有不同，大概如下：

sq = range(0, n)
for i in range(0, n):
    j = random.randint(0, n - 1)
    sq[i], sq[j] = sq[j], sq[i]  #就是swap(sq[i], sq[j])

sq = range(0, n)
for i in range(0, n):
    j = random.randint(i, n - 1)
    sq[i], sq[j] = sq[j], sq[i]  #就是swap(sq[i], sq[j])

其中第一个是bad算法，生成的排列并非完全随机。第二个算法是good算法。

问题是给出120个长度为1000的排列，让你判断给你的排列是用哪个算法生成的。

生成排列的流程是：1.随机选一个算法。2.用1中选择的算法生成一个排列。

显然这并不是一个常见的算法竞赛中会出现的题。

题目中直言：即使是我们的最好的程序仍然有小概率不能通过。

但是这毕竟不是icpc，谷歌说了算咯。。。毕竟这题确实有点意思。。。

首先想到的是构造一个统计量，然后直接比较值（出题人给出的做法就是这样的）。

但是我想的办法虽然能体现出一些差距，但是不够通过的。

第一反应就是大表找找规律啥的。

比如：

逆序对个数，bad算法是少于good算法的，这个good算法的数值很稳定，不过差距不够大，没过去；

偏向性，官方题解就是这个思路，如果打个表（我打的是n=5），看看就很清楚了。

关键是如何构造统计量，我把不同位置的数字做差再乘方啥的类似方差之类的搞一搞之后似乎有门，

但是也过不去，这个正确率比上面那个还要低，比较的标准也比较迷。。。没多试就去看题解了。。。。

题解做法一：

直接统计在位置i的数比i小的个数，然后。。。

题解做法二：

搞一个贝叶斯分类器。

给一个排列s我们要求的东西是P(good|s)给定s求是good生成的概率。

根据贝叶斯公式

P(good|s) = P(s|good) P(good) / (P(s|bad) P(bad) + P(s|good) * P(good))

由于是随机选一个生成器，所以P(good) == P(bad) == 0.5

于是P(good|s) = P(s|good) / (P(s|bad) + P(s|good))

已知P(s|good) = (1 / N)^N

所以只要求P(s|bad)

这里有点类似机器学习里的常用处理方法，如果p[i][j]位置i为数字j的概率和其他数字和位置的概率是相互独立的

那么就可以很容易的搞出答案了。

这个p数组可以比较简单的O(N^3)处理出来，
还可以优化到O(N^2)但是我没看懂代码(题解给的链接是tourist的代码orz)

不过既然已经相互独立了，其实更简单的办法是直接随机，
由于不同的位置有N * N个，而每个随机排列要在N个位置上加一，

所以大概平均一下，随机T次每个位置的数量级大概是T N / (N N) = T / N
所以我们随机N * N组的复杂度也是O(N ^ 3)同时精度也不算太差，大概有0.001的精度（而且这题也没法卡啊）。

等有时间仔细看一下O(N ^ 2)的代码再补。

代码（贝叶斯方法）

reference

1.官方题解