今天是11月11日。NOIp 2018的二试已经结束了，初步来看，DAY 1的第一题是可以拿到满分的，第二题由于我使用了伪扩展欧几里得暴力算法使得我只能得到部分的分数，第三题纯属双向深度搜索骗分。
而二试便惨淡的多，我花了两个小时写完了第三题（我认为预处理是\(O(n)\)，询问是根据询问的节点深度而定的复杂度），而看到剩下两道关于字典序比大小的神仙题时我便选择了第一题去骗分。得知部分分中有存在只有两个城市连接的几个数据点之后，我便开始写起了暴力骗分代码。而到最后比赛结束，我也没有能调出来，甚至紧张的忘记了抄下样例进行骗分。
我现在在高一年级，而很多初中生甚至是小学生都已经开始角逐NOIp提高组的奖项，我实在是不能与他们比较。对于我这个从7月底开始学OI的超入门者，确实还有很长的路要走。
我打算下周开始补两周的文化课，以便不会落下太多。而在下周成绩出来之后我就要开始联系一些机构和学校，打算直接开始我正式的OI集训，以保证OI的进步速度不下降。
愿景是美好的。时间会给我答案的。
这又是一道抄题解的题目。我们先来简要分析一下触发矛盾的几种情况：
之后我们就可以用并查集来进行集合操作。而数据范围非常的大，而答案只需要一个最早解，那么我们就可以尝试二分答案。
这道题是一道动态规划的题目。我们首先考虑预处理出一个数组，来存放两两单词是否安全。之后我们再利用这个信息来进行DP。而有一个值得注意的要点是：我们在动态规划时要消除后效性，否则就会出现错误。在本题中，我们需要对字符串进行排序，因为排序后不安全的单词只存在于在第\(i\)个单词的前面，这样我们用一维\(dp\)即可。考虑方程：\(dp[j] += dp[i], j \in [i, n], possible[i][j] == true\)即可。
我们首先把\(a,b\)输入进一个数据结构，并且对这两个序列以高度为关键字排序。我们先来写出一组样例排序后的样子（数组下标为原本的位置）：\[\{1_3,2_1,3_2,4_4\}\]与\[\{1_3,2_2,3_1,4_4\}\]我们观察发现，显然我们可以进行离散处理。所以令\(mapping[]\)为离散数组，在两组排序后进行\(mapping[a[i].index] = b[i].index\)，便可以完成离散化。问题便转换为b数组要完成多少次变换才能与a相同（因为我们已经进行了离散化处理，\(mapping[]\)便可以在\(n\)范围内）。我们可以想到使用计算逆序对个数来解决这个问题。问题迎刃而解。
自从NOIp 2018初赛第一次知道有数学期望这个东西起，我就一直很难理解。我一直没有去仔细的了解数学期望，而今天打了一场比赛，被逼着去了解了，现在我来写点东西记录一下这个概念。
\(数学期望\)是一个跟概率相关的概念。他的定义是：
数学期望是一个有限的事件的结果乘上一个事件的概率。
我们可以通过举例子来解释这个概念。比如取一个随机数（1-10之间），那么取到5的数学期望就是\(\frac {1} {2}\)。一般，我们用\(\mathbb{E}\)来表示这个值。
在本篇文章中，我只介绍一个性质。未来如果我学到了一些关于数学期望的新东西，那么我会把这些内容写在这篇文章里的。
数学期望在OI中比较重要的性质就是其线性性。简单来讲，如果有两个事件的数学期望为\(\mathbb{E}(a)\)和\(\mathbb{E}(b)\)，那么这两个事件叠加起来就是\(\mathbb{E}(a) + \mathbb{E}(b) = \mathbb{E}(a+b)\)。这个性质在OI中比较重要，一些题目会利用这个性质让解题者使用递推的方式解出答案。接下来我们看一道题目：
链接：T2062:随机数生成器
这道题目是我在华南师范大学附属中学举办的比赛中遇到的题目。虽然我这一题并没有AC，但是不妨碍我们来解释数学期望的一些性质和递推得解的方法。
我们来思考这样一个方程，设置\(\mathbb{E}(i)\)为输入为\(i\)的数学期望，那么，根据数学期望的线性性质，我们可以很容易推出以下方程：\[\mathbb{E}(i) =\frac {\mathbb{E}(1) + 1}{i} + \frac {\mathbb{E}(2) + 1}{i} + \frac {\mathbb{E}(3) + 1}{i} + \frac {\mathbb{E}(4) + 1}{i} + \dots + \frac {\mathbb{E}(i) + 1}{i}\]
而在本题中，可知\(\mathbb{E}(1) = 0\)。那么我们来变换一下式子，变成：\[\mathbb{E}(i) = \frac {\mathbb{E}(1) + \mathbb{E}(2) + \dots + \mathbb{E}(i – 1) + i}{n – 1}\]这样我们就可以递推出式子。
数学期望是OI中常见的概念，掌握它很有帮助。建议读者可以自己去阅读相关的资料，我在这里便不再描述。
这道题观察数据范围和题干，可以得知这是一道状压dp的题目。我们先来设计状态：在本题中，可以类比互不侵犯的那一题（互不侵犯题解），设计成当前状态和上一状态相关的元素。可以想出，dp[当前牛的存在情况][当前加入的牛的编号] += dp[上一次加入后的状态][上一次加入的牛的编号];
基本上完成了思考，现在我们先来搞定预处理。我们把只有cowId在队列里的方案数初始化为1。
for (int cowId = 0; cowId < n; cowId++)
dp[1 << cowId][cowId] = 1;
之后我们就可以进行dp了。详细见代码：
for (int lastState = 0; lastState < (1 << n); lastState++)
for (int lastCow = 0; lastCow < n; lastCow++)
if (lastState & (1 << lastCow))
for (int nowCow = 0; nowCow < n; nowCow++)
if (!(lastState & (1 << nowCow)) && abs(seq[nowCow] - seq[lastCow]) > k)
nowState = lastState | (1 << nowCow),
dp[nowState][nowCow] += dp[lastState][lastCow];
最后方案数叠加，在满员的状态下枚举最后一头牛的id。
ll ans = 0;
for (int i = 0; i < n; i++)
ans += dp[(1 << n) - 1][i];
cout << ans;
// P2915.cpp
#include <iostream>
#include <cmath>
using namespace std;
#define ll unsigned long long
const int maxn = 16;
ll dp[1 << maxn][maxn];
int n, k, nowState;
int seq[maxn];
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> seq[i];
for (int cowId = 0; cowId < n; cowId++)
dp[1 << cowId][cowId] = 1;
for (int lastState = 0; lastState < (1 << n); lastState++)
for (int lastCow = 0; lastCow < n; lastCow++)
if (lastState & (1 << lastCow))
for (int nowCow = 0; nowCow < n; nowCow++)
if (!(lastState & (1 << nowCow)) && abs(seq[nowCow] - seq[lastCow]) > k)
nowState = lastState | (1 << nowCow),
dp[nowState][nowCow] += dp[lastState][lastCow];
ll ans = 0;
for (int i = 0; i < n; i++)
ans += dp[(1 << n) - 1][i];
cout << ans;
return 0;
}