【题解】Luogu P1648 看守

原题传送门：P1648 看守

这题目让求得的是d维（ d <=4 ）空间中n个点（ 2 <= N <= 1000000 ）之间最大的哈曼顿距离

模拟，emm，能拿30分，不错

因为d <= 4，所以考虑枚举每一维的正负情况

求出每个点每一位的数字之和（数字符号为+或-，所以最多16个状态）

最后先枚举每一个状态，再枚举每一个点，求出数字之和最大和最小，求一下差，和ans比较谁大

复杂度为O(N 2^D)

the end

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

#define N 1000005

#define inf 0x3f3f3f3f

using namespace std;

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

inline int Max(register int a,register int b)

{

    return a>b?a:b;

}

inline int Min(register int a,register int b)

{

    return a<b?a:b;

}

int cnts[4]={2,4,8,16};

int a[N][6],n,d,cnt,add[20][N],ans=0;

int main()

{

    n=read(),d=read();

    cnt=cnts[d-1];

    for(register int i=1;i<=n;++i)

    {

        for(register int j=1;j<=d;++j)

            a[i][j]=read();

        for(register int j=0;j<cnt;++j)

        {

            int tmp=j;

            for(register int k=1;k<=d;++k)

            {

                if(tmp&1)

                    add[j][i]+=a[i][k];

                else

                    add[j][i]-=a[i][k];

                tmp>>=1;

            }

        }

    }

    for(register int i=0;i<cnt;++i)

    {

        int maxx=-inf,minn=inf;

        for(register int j=1;j<=n;++j)

        {

            maxx=Max(maxx,add[i][j]);

            minn=Min(minn,add[i][j]);

        }

        ans=Max(ans,maxx-minn);

    }

    printf("%d",ans);

    return 0;

}