【学习笔记】逆熵法
NCC79601
2019-08-16 21:13:49
# 背景
有$n$个数，但并不给你，而是给了你$m=\frac12 n\cdot(n-1)$个数（$n\leq300$），代表它们两两的和。求这$n$个数。
# 分析
这里要运用**逆熵**的思路。名字是自己瞎~~jb~~取的，但是我感觉这个名字非常贴切。
**逆熵**：通过一定的方式把杂乱的信息整理为有逻辑顺序的信息。通常的方式也就是排序等等。在面对一大堆不知道该如何处理的信息的时候，就应该通过一些假设与限制，把整个问题的熵值降低，从而变得能够在可接受时间内解决。
回到这道题，$m$个数是杂乱无章的，也就是说我们根本不知道这些数和原序列的对应关系。
开始使用**逆熵法**：假设这$n$个数分别为$a_1,a_2,\cdots,a_n$，并且它们按照升序排列；再把这$m$个两两和$s_1,s_2,\cdots,s_m$按照升序排列。这样处理以后，整个系统的熵值降低，并且出现了第一个由假设引入的逻辑关系：由于$a_1<a_2<a_3<\cdots<a_n$，因此$a_1+a_2<a_1+a_3<\cdots<a_{n-1}+a_n$。再观察，$s_1<s_2<\cdots<s_m$，也就是说排序以后得到了：
$$a_1+a_2=s_1,$$
$$a_1+a_3=s_2.$$
因此只要获知$a_2+a_3$的值，它们就构成了三个三元一次方程，即可解得$a_1,a_2,a_3$。可是$a_2+a_3$的位置无法确定，因为$a_1<a_2<a_3<a_4<\cdots<a_n$，所以无法比较$a_1+a_i(i\geq4)$和$a_2+a_3$的大小。因此$a_2+a_3$有可能出现在$s_3\sim s_n$中的每一个数，也就是说这里的熵值无法继续降低，因此开始枚举。从$s_3\sim s_n$中挑选出一个数作为$a_2+a_3$，那么：
$$a_2+a_3=s_x.$$
联立三式解得：
$$\left\{\begin{aligned}a_1 &= \frac{s_1+s_2-s_x}2,\\a_2 &= s_1-a_1,\\a_3 &= a_2-a_1.\end{aligned}\right.$$
所以根据$s_1+s_2-s_x$的奇偶性就可以判断这种情况是否存在（$a_1,a_2,a_3\in N^+$）。此后，将$a_1+a_2,a_1+a_3,a_2+a_3$从$s$序列中删除。那么依据我们的假设，剩下来的最小的$s$就是$a_1+a_4$了，同样可以解得$a_4$；然后把$a_i+a_4(i<4)$给删去，剩下来的最小的$s$就是$a_i+a_5\cdots$以此类推，便可解得所有数的值。
总结一下，算法流程如下：
1. 枚举$a_2+a_3$，解得$a_1,a_2,a_3$；
2. 重复以下步骤，直到解得所有数的值：$(i=4\sim n)$
① 找到当前最小的$s_x$，根据假设可知$s_x=a_1+a_i$，由此可以解得$a_i$；
② 在$s$序列中把所有当前利用$a$序列能够确定的$s$值删去，具体为把$a_j+a_i(j<i)$全部删除，代码中可以用 multiset 实现。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 310;
const int MAXM = 5e5;
struct sequence {
int a[MAXN];
bool operator < (const sequence &rhs) const {
return a[1] > rhs.a[1];
}
// 其实这儿有点问题，字典序不是这样搞的 =w=
} seq[MAXN];
int n, m, s[MAXM], ans = 0;
void solve(int &a1, int &a2, int &a3, int s1, int s2, int s3) {
a1 = (s1 + s2 - s3) >> 1;
a2 = s1 - a1;
a3 = s2 - a1;
}
void start_from(int s3) {
multiset<int> mset;
for(int i = 1; i <= m; i++)
mset.insert(s[i]);
int a[MAXN];
solve(a[1], a[2], a[3], s[1], s[2], s3);
mset.erase(mset.find(a[1] + a[2]));
mset.erase(mset.find(a[1] + a[3]));
mset.erase(mset.find(a[2] + a[3]));
for(int i = 4; i <= n; i++) {
a[i] = * mset.begin() - a[1];
for(int j = 1; j < i; j++) {
if(mset.find(a[j] + a[i]) == mset.end())
return;
mset.erase(mset.find(a[j] + a[i]));
}
}
ans++;
memcpy(seq[ans].a, a, sizeof(a));
}
int main() {
scanf("%d", &n);
m = n * (n - 1) / 2;
for(int i = 1; i <= m; i++)
scanf("%d", &s[i]);
sort(s + 1, s + m + 1);
for(int i = 3; i <= n; i++) {
if(s[i] == s[i - 1])
continue;
if((s[1] + s[2] - s[3]) % 2 == 0)
start_from(s[i]);
}
sort(seq + 1, seq + ans + 1);
printf("%d\n", ans);
for(int i = 1; i <= ans; i++) {
for(int j = 1; j <= n; j++)
printf("%d ", seq[i].a[j]);
putchar('\n');
}
return 0;
}
```
# 总结
很多时候面对这种数据繁多、逻辑关系不明朗的题目，我会感觉无从下手。这是因为我总是在拿算法套路来尝试，又因为出题人故意隐藏，所以迷失了方向。其实，只要合理地作出假设，用各种方法**将系统的熵值降低**，然后再根据已有的条件进行组合和演绎，就能发现一条明朗的思路。
这种从混沌之中寻求解题思路的方法，可以迅速地为系统建立模型，由此进行抽象的演算。所以，不失把逆熵法作为题目的突破方法。