[开散列]轰炸bomb
【题目描述】 平面上有n个目标,你驾驶着一辆轰炸机要轰炸这些目标,由于技术限制,每次轰炸的目标必须在一条直线上,请你写个程序统计每次能摧毁多少个目标。 注意,目标不能重复计数,也就是此次轰炸后目标下次就消失了。 【输入格式】 第一行两个数n,m,代表目标个数和轰炸的次数 下面n行,每行两个整数(x,y),代表每个目标的坐标 再下面m行,第一个数为0或1,0表示此次轰炸是一条水平的直线,1则表示竖直 第二个数t表示此直线的位置(x = t或者y = t) 【输出格式】 m行,表示每次轰炸的目标数 【样例输入】 3 2 1 2 1 3 2 3 0 1 1 3 【样例输出】 2 1 【数据规模】 30% n,m=5000 100% n,m =  |x|, |y| = 10^9 【时间限制】 1s 这道题,我一看就知道是要用数据结构。然后我一下就想到了开散列。但是我忽视了一个重要问题:我艹坐标是可以为负的！于是我就有9组数据因为访问到负数下标而爆掉,不然我就ac了！虽然我还是第一名,但是...没有以压倒性的优势成为第一。 下来改了一点点,然后就ac了。 这道题就是运用开散列来减小枚举量。因为如果直接朴素的话肯定要超。于是我把每个点的座标都分别对1,000,000取余,然后用链表存储,这样,如果是水平的,就扫描存x的开散列,否则扫描存y的开散列。这样就解决了因枚举量过大而引发的超时问题。然后,就没有然后了,就ac了。而开散列的代码是最简单的,跟链表差不多。比标程用的二分找下界简单多了。 code: #incl decstdio #incl decstdlib #incl decstring #incl deiostream sing namespace std； int n,m； const int mod=； const int maxn=； str ct point { int id,x； point *next； }； point *x[mod+10],*y[mod+10]； bool hash[maxn+10]； void insert_x(int a,int i) { point *now=new point； now-i； now-x=a； int k=abs(a) % mod； now-next=x[k]； x[k]=now； } void insert_y(int a,int i) { point *now=new point； now-i； now-x=a； int k=abs(a) % mod； now-next=y[k]； y[k]=now； } void read { freopen("","r",stdin)； freopen("bomb.o t","w",stdo t)； scanf("%d%d",&n,&m)； for (int i=0； in； i) { int x,y； scanf("%d%d",&x,&y)； insert_x(x,i)； insert_y(y,i)； } } void work { for (int j=0； jm； j) { int f,t； scanf("%d%d",&f,&t)； int k=(abs(t) % mod),ans=0； if (！f) { for (point *i=x[k]； i； i=i-next) if (！hash[i-id] && i-x==t) { hash[i-id]=1； ans；