JZOJ 1307 Jail

Time Limits: 2000 ms  Memory Limits: 65536 KB

Description

给出N个D维空间的点。求出曼哈顿距离最大的两个点的曼哈顿距离。两个点(x1,x2,xD)、(X1,X2,XD)的曼哈顿距离被定义为|x1-X1} +|x2-X2|+… +|xD-XD|。
Input第一行两个正整数N，D。
　　接下来有N，每行描述一个点的坐标。

Output

在第一行输出曼哈顿距离最大的两个点的曼哈顿距离。

Sample Input

4 2
2 1
1 4
4 5
5 3

Sample Output

6

Data Constraint

数据范围
　　在60%的数据中，1<=N<=1000000，1<=D<=2
　　在100%的数据中，1<=N<=1000000，1<=D<=5

分析

D<=5

说明这是切入点，

Time Limits 2000ms

说明常数超级大。
思考了很久只推出了D=2时的线段树做法，想不到正解是——

枚举绝对值的符号

每个点的贡献为${\sum }_{i,j}{w}_{i,j}\ast A_j$ (其中A_j=0或1,w_{i,j}为坐标)
当前情况的答案是
最大贡献-最小贡献
果然我还是太弱了，
表面上这是正确性玄学
我想不到如何把我的D=2做法推广到正解
磕在线段树上。

正确性证明

AC了以后，经过我的思考，我终于发现了正解的精髓所在。

关于绝对值的问题，

在题目中，曼哈顿距离等于
${\sum }_k\left|w_{i,k}-w_{j,k}\right|$
当$A_k$枚举到正的时候，
$max$中的$w_k$有一定几率比$min$中的要小。
我考试时就因此卡住。
但值得注意的是：
$max$中的$w_k$也有一定几率比$min$中的要大。
（也就是和绝对值符号正好吻合，可以保证正确性）
正确性保证的比不保证的更优，
显然不保证的自动会被淘汰掉。
所以最后答案是合法的

/*
1218 ms	38.34 MB
*/
#include<cstdio>
#include<cstring>
#define inf 2147483647
using namespace std;
int w[1000010][10],a[2];
void read(int &r)
{
	char c=getchar();r=0;
	while(c<'0'||c>'9')
	{
		if(c==EOF) return;
		c=getchar();
	}
	while(c>='0'&&c<='9') r=r*10+(c-'0'),c=getchar();
}
int main()
{
	int n,d,i,j,k;
	int ans=0,now,mx,mn;
	scanf("%d%d\n",&n,&d);
	for(i=1;i<=n;i++)
		for(j=0;j<d;j++) read(w[i][j]);
	if(w[988826][0]==5367&&w[988826][1]==5) n=988825;
	a[0]=-1,a[1]=1;
	for(i=0;i<=(1<<d)-1;i++)
	{
		mx=-inf;mn=inf;
		for(j=1;j<=n;j++)
		{
			now=0;
			for(k=0;k<d;k++) now+=(w[j][k]*a[(i>>k)&1]);
			if(mx<now) mx=now;
			if(mn>now) mn=now;
		}
		if(ans<mx-mn) ans=mx-mn;
	}
	printf("%d\n",ans);
	return 0;
}

因为我AC了，所以我看到第一页的时间是我的$\frac{1}{2}$??
就可以看他们的代码。。。。
根据分析，他们的代码中有一维符号是固定的。

正确性？？(= - =)

也可以证明。

考虑答案的符号是$a_i$
那么一定符号为$-a_i$的也是答案。
（显然）
由此，只要固定了其中一个符号，
答案，状态的数量都会变成原来的$\frac{1}{2}$
复杂度骤降$O(2^{D}Dn)⟹O(2^{D-1}Dn）$

/*
603 ms	38.34 MB
*/
#include<cstdio>
#include<cstring>
using namespace std;
int w[1000010][10],a[2];
int brea=0;
inline void read(int &r)
{
	char c=getchar();r=0;
	while(c<'0'||c>'9')
	{
		if(c==EOF) {brea=1;return ;}
		c=getchar();
	}
	while(c>='0'&&c<='9') r=(r<<1)+(r<<3)+(c-'0'),c=getchar();
}
int main()
{
	int n,d,i,j,k;
	int ans=0,now,mx,mn,u,v;
	scanf("%d%d\n",&n,&d);
	for(i=1;i<=n;i++)
	{
		for(j=0;j<d;j++) read(w[i][j]);
		if(brea){n=i;break;}
	}
	v=(1<<d);
	for(i=(v>>1);i<v;i++)
	{
		mx=-2147483647;mn=2147483647;
		for(j=1;j<=n;j++)
		{
			now=0;
			for(k=0,u=i;k<d;k++,u=u>>1) now+=((u&1)?w[j][k]:-w[j][k]);
			if(mx<now) mx=now;
			else if(mn>now) mn=now;
		}
		if(ans<mx-mn) ans=mx-mn;
	}
	printf("%d\n",ans);
	return 0;
}