HDU4666 Hyperspace(曼哈顿)

题目链接。

分析：

这是多校的一个题，当时没做出来。学长说让用multiset。

用multiset将每一个数的1<<dim个状态全部保存。假设状态 i, 最远曼哈顿距离应当是 max[i]-min[i], 但如果知道 i 的相反的状态就可以转化成 max[i]+min[(~i)&(1<<dim-1)]. 这和 x-y = x + (-y) 是一个道理.

AC代码如下:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <stack>
#include <set>

using namespace std;

const int maxn = 60000+10;
const int dem = 5;  //维数
const int INF = (1<<29);

int dim, x[maxn][dem];

int main(){
    int n, ord;

    while(scanf("%d %d", &n, &dim) == 2) {
        multiset<int> ms[40];
        multiset<int>::iterator it;

        for(int i=1; i<=n; i++) {
            scanf("%d", &ord);
            if(ord == 0) {
                for(int j=0; j<dim; j++) {
                    scanf("%d", &x[i][j]);
                }

                for(int j=0; j<(1<<dim); j++) {
                    int t = j, s = 0;
                    for(int k=0; k<dim; k++) {
                        if(t & 1) s += x[i][k];
                        else s -= x[i][k];
                        t >>= 1;
                    }
                    ms[j].insert(s);
                }

            } else {        //ord == 1

                scanf("%d", &ord);
                for(int j=0; j<1<<dim; j++) {
                    int t = j, s = 0;
                    for(int k=0; k<dim; k++) {
                        if(t & 1) s += x[ord][k];
                        else s -= x[ord][k];
                        t >>= 1;
                    }

                    it = ms[j].find(s);
                    ms[j].erase(it);
                }
            }

            int ans = 0;
            for(int j=0; j<(1<<dim); j++) {
                int k = ((~j) & ((1<<dim)-1)); 
                int t1, t2;
                it = ms[j].end();       //multiset内部是升序排列
                it--;
                t1 = *it;
                it = ms[k].end();
                it--;
                t2 = *it;
                ans = max(ans, t2+t1);
            }

            printf("%d
", ans);
        }
    }

    return 0;
}