【题解】牛客练习赛49

A-筱玛爱地理

将给定的n个数按照E[i]/V[i]排序即可

注意先排序后取模

比较大小时用乘法，不要直接除避免精度误差

代码见：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40806942

B-筱玛爱阅读

因为交换次数是无限的，因此操作相当于给每个物品赋值。

题目相当于就免费的物品的价值和的最大值

直接子集dp即可(虽然好像让很多暴力m*2^n过了)

复杂度O(3^n)

代码见：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40806948

C-筱玛爱历史

一个结论是方案一定存在，且一定存在一种方案使得可以将这些人按顺序分成n组，每组n+1人，使得从每组选两个人配对，连起来构成一个合法方案。

证明可以使用抽屉原理：

> 将所有n(n+1)个人按身高分成n组，最高的n+1个人为第1组，接下来的n+1个人为第2组……最矮的n+1个人为第n组。
> 按题设排列中的顺序从左往右枚举每个人，直至第一次发现有两个人属于同一组。设 $A_1$ 与 $A_2$ 都属于 $t_1$ 组， $A_1$ 在 $A_2$ 的左边，则 $A_1$ 和 $A_2$ 留下， $A_2$ 左边的其他人离开， $t_1$ 组内的人也离开。
> $A_2$ 右边的人均属于其余n-1组，每组至多有一人离开，因此，每组还至少有n人，使得从每组选两个人配对，连起来构成一个合法方案。
> 接着从 $A_2$ 开始往右继续枚举剩下的人，直至再次发现有两人同组。设 $A_3$ 和 $A_4$ 都属于 $t_2$ 组， $A_3$ 在 $A_4$ 的左边，则 $A_3$ 和 $A_4$ 留下， $A_2$ 至 $A_4$ 之间的其他人离开， $t_2$ 组的其他人也离开。
> 如此进行下去。当已经学定了 $A_1\sim A_{2k}$ 时，他们依次从左至右排列， $A_1,A_2$ 在第 $t_1$ 组， $A_3,A_4$ 在第 $t_2$ 组，……， $A_{2k-1},A_{2k}$ 在第 $t_k$ 组，且 $A_{2k}$ 右边的人均为剩下的第n-k组中的人，且每组至少有n-k+1个人。
> 若 $k\le n-1$ ，从 $A_{2k}$ 开始继续往右枚举剩下的人，一定有两人是同一组的，第一次发现同组的两个人记为 $A_{2k+1},A_{2k+2}$ ， $A_{2k+1}$ 在 $A_{2k+2}$ 的左边，设他们是第 $t_{k+1}$ 组的，留下这两个人，让 $A_{2k},A_{2k+2}$ 之间的其他人离开，让第 $t_{k+1}$ 组的其他人也离开。
> 最后剩下2n个人 $A_1,A_2,\cdots,A_{2n}$ ，在队列中依次从左向右，且每组均恰好留下两个人，每组留下的这两个人之间没有其他人，因此，结论成立。

构造方法如下：

若人的编号 $0\sim n(n+1)−1$ ，则第i个人对应第 $\frac i{n+1}$ 组。

按照权值从小到大枚举每一个人。假设现在这个人的编号是x，属于第b组，先看看第b组有没有人。

如果没有人，则让x占着第b组的位置。

如果已经有人占着位置，就让x和这个人凑成一对。

然后把只有一个人占位的组清空，封锁已经配对的b组。

如此反复下去，最终n个组全部都能完成配对。

时间复杂度 $\mathcal O(n^2\log n)$ 。

注意：题目只要求最高和次高相邻，第三高和第四高相邻……但是并没有要求次高和第三高相邻，第四高和第五高相邻。

代码见：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40806898

D-筱玛爱线段树

将询问离线以后倒着做，可以使用差分解决。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40806964

E-筱玛爱游戏

这题需要一些线性代数的知识
每个数可以看做一个 $\mathbb{F}_2$ 向量(即每一维都是 $\mathrm{0}$ 或 $\mathrm{1}$ 的向量)
这时数的异或就相当于向量的加法
那么集合存在一个非空子集异或和为 $\mathrm{0}$ 即为这个向量组线性相关
那么两个人在博弈过程中每一步都需保证向量组线性无关
那么这个向量组最大的大小即为所有向量的秩 ( $\mathrm{rank}$ )
而由线性代数基本结论，若当前选出的向量线性空间维数小于所有向量的秩，一定能加入一个另外的向量，使得向量组仍线性无关
因此两个人的移动次数是确定的（即为原向量组的秩），只需判断奇偶性即可
求秩可以使用暴力高斯消元或者线性基

代码见：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40806895

F-筱玛爱语文

首先需要判断是欧拉回路还是欧拉路径。显然，将欧拉路径两端接上就变成了欧拉回路，因此两者可以互相转化。

根据[https://en.wikipedia.org/wiki/BEST_theorem](BEST定理)，有：
$\mathrm{ec}(G)=t_w(G)\prod\limits_{v\in V}\left(\deg(v)-1\right)!$

其中， $\mathrm{ec}(G)$ 表示图G欧拉回路的数目， $t_w(G)$ 表示图G中以点w为根的内向生成树个数， $\deg(v)$ 表示点v的出度或入度。

其中生成树计数可以通过矩阵树定理实现，这里不再赘述。

然而这样是 $\mathcal O(n^3)$ 的。

考虑题目中给定的一个性质：由于m<=4000，因此最多只有4000条不存在的边，而其它的边都是存在的。也就是说，我们所计算的基尔霍夫矩阵内的元素大部分是-1。因此，从某种意义上说，最后我们计算的矩阵是“稀疏”的，这样我们便可以使用[Wiedemann的黑箱线性代数算法](http://www.enseignement.polytechnique.fr/informatique/profs/Francois.Morain/Master1/Crypto/projects/Wiedemann86.pdf)优化。

后记：如果不会n^2做法，因为随机力量过于强大，所以在高斯消元时随机交换若干行就有概率卡过去。

代码见：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40807168