原题传送门: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;
}
04-25 03:42