HDU 4022 Bombing(11年上海 二分)
题目：给出一些点，给出两个操作，分别 是去掉横坐标为某个值的点，或者去掉纵坐标为某个值的点，问每次去掉点的个数
由于是分X,Y操作的，那么把X,Y分开，排序，然后针对操作，二分查找
全局变量记录某个点是否被去掉
排序+二分+暴力标记
哎，大清早的来一发水题，好忧桑
[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#define inf 110000000
#define M 10005
#define N 100005
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
using namespace std;
struct Node{
int val,id;
}x[N],y[N];
int n,q;
int flag[N];
bool cmp(Node n1,Node n2){
return n1.val<n2.val;
}
int BinSearch(Node *a,int n,int m){
int low=0,high=n-1,mid,pos=-1;
while(low<=high){
mid=(low+high)/2;
if(a[mid].val==m){pos=mid;break;}
if(a[mid].val<m) low=mid+1;
else high=mid-1;
}
if(pos==-1) return 0;
int i=pos-1,ans=0;
while(i>=0&&a[i].val==m){
if(flag[a[i].id]==0){flag[a[i].id]=1;ans++;}
i--;
}
while(pos<n&&a[pos].val==m){
if(flag[a[pos].id]==0){flag[a[pos].id]=1;ans++;}
pos++;
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&q)!=EOF&&n+q){
for(int i=0;i<n;i++){
scanf("%d%d",&x[i].val,&y[i].val);
x[i].id=y[i].id=i;
}
sort(x,x+n,cmp);
sort(y,y+n,cmp);
mem(flag,0);
while(q--){
int k,p;
scanf("%d%d",&k,&p);
if(k==0)
printf("%d\n",BinSearch(x,n,p));
else
printf("%d\n",BinSearch(y,n,p));
}
puts("");
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#define inf 110000000
#define M 10005
#define N 100005
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
using namespace std;
struct Node{
int val,id;
}x[N],y[N];
int n,q;
int flag[N];
bool cmp(Node n1,Node n2){
return n1.val<n2.val;
}
int BinSearch(Node *a,int n,int m){
int low=0,high=n-1,mid,pos=-1;
while(low<=high){
mid=(low+high)/2;
if(a[mid].val==m){pos=mid;break;}
if(a[mid].val<m) low=mid+1;
else high=mid-1;
}
if(pos==-1) return 0;
int i=pos-1,ans=0;
while(i>=0&&a[i].val==m){
if(flag[a[i].id]==0){flag[a[i].id]=1;ans++;}
i--;
}
while(pos<n&&a[pos].val==m){
if(flag[a[pos].id]==0){flag[a[pos].id]=1;ans++;}
pos++;
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&q)!=EOF&&n+q){
for(int i=0;i<n;i++){
scanf("%d%d",&x[i].val,&y[i].val);
x[i].id=y[i].id=i;
}
sort(x,x+n,cmp);
sort(y,y+n,cmp);
mem(flag,0);
while(q--){
int k,p;
scanf("%d%d",&k,&p);
if(k==0)
printf("%d\n",BinSearch(x,n,p));
else
printf("%d\n",BinSearch(y,n,p));
}
puts("");
}
return 0;
}
补充：web前端 , JavaScript ,
