注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4666 Hyperspace  

2013-08-16 11:58:07|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4666
给出n和m,有m维的空间,n次操作,每次0表示插入一个点,1表示删除一个点,每次操作完后询问空间里两点间最大的曼哈顿距离。
用multiset动态维护多维最远曼哈顿距离。(多维最远曼哈顿距离参见学习资料:http://www.cnblogs.com/lmnx/articles/2479747.html
对于平面上两点(x1,y1),(x2,y2)的曼哈顿距离为|x1-x2|+|y1-y2|
去掉绝对值,将同一点的坐标整理一边可以得到下面四种情况:
1.x1-x2+y1-y2->(x1+y1)-(x2+y2)
2.x2-x1+y1-y2->(-x1+y1)-(-x2+y2)
3.x1-x2+y2-y1->(x1-y1)-(x2-y2)
4.x2-x1+y2-y1->(-x1-y1)-(-x2-y2)
可以发现左半部分和右半部分的符号完全相同,我们假设0代表’+’,1代表’-‘,则有00 01 10 11.
我们可以把所有的点在k维空间下的2^k种状态处理出。最大距离肯定在2^k种状态下某两个点的状态之差取最大值。
如果是动态的,用multiset动态维护2^k种状态对应每种状态的所有值,再用结构体数组记录每个点的2^k种状态。

/*
* pro.cpp
*
* Created on: 2013-08-16
* Author: fudq
*/
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=60010;
const int M=32010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const double eps=1e-7;
const double PI=acos(-1.0);

inline int sign(double x){return (x>eps)-(x<-eps);}
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
/*************************/

struct Point{
int x[6],p[40];
}point[N];

int n,dim,tot;
multiset<int> s[40];

void Update(int tmp)
{
for(int i=0;i<tot;i++)
{
int ans=0;
for(int j=0;j<dim;j++)
{
if(i & (1<<j))
ans+=point[tmp].x[j];
else
ans-=point[tmp].x[j];
}
point[tmp].p[i]=ans;
}
}

void Insert(int tmp)
{
Update(tmp);
for(int i=0;i<tot;i++)
s[i].insert(point[tmp].p[i]);
}

void Delete(int tmp)
{
for(int i=0;i<tot;i++)
s[i].erase(s[i].find(point[tmp].p[i]));
}

void Query()
{
if(s[0].size() < 2)
{
printf("0\n");
return ;
}
int ans=-1;
for(int i=0;i<tot;i++)
{
int t1=*(s[i].begin());
int t2=*(s[i].rbegin());
ans=max(ans,t2-t1);
}
printf("%d\n",ans);
}

void solve()
{
tot=1<<dim;
for(int i=0;i<tot;i++)
s[i].clear();
int a,b;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
if(a == 0)
{
for(int j=0;j<dim;j++)
scanf("%d",&point[i].x[j]);
Insert(i);
}
else
{
scanf("%d",&b);
Delete(b);
}
Query();
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
while(scanf("%d%d",&n,&dim)!=EOF)
solve();
return 0;
}



  评论这张
 
阅读(67)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017