【学习笔记】逆熵法

· · 个人记录

背景

有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 实现。

#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;
}

总结

很多时候面对这种数据繁多、逻辑关系不明朗的题目，我会感觉无从下手。这是因为我总是在拿算法套路来尝试，又因为出题人故意隐藏，所以迷失了方向。其实，只要合理地作出假设，用各种方法将系统的熵值降低，然后再根据已有的条件进行组合和演绎，就能发现一条明朗的思路。

这种从混沌之中寻求解题思路的方法，可以迅速地为系统建立模型，由此进行抽象的演算。所以，不失把逆熵法作为题目的突破方法。