To boldly go where no one has gone before.

【学习笔记】逆熵法

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

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

总结

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

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