2019 우 객 여름 다 교 훈련소 (제10 회) F: Popping Balloons
제목:
가로 선 3 개, 세로 선 3 개 를 선택 하고 인접 선 간 의 거 리 는 r 를 초과 하지 않 으 며 통과 할 수 있 는 최대 포 인 트 를 구하 십시오.
생각:
가로 선 하나, 세로 선 하나 밖 에 없 는 상황 을 고려 하 다.세로 선 가중치 선분 수 를 이용 하여 이 가로 좌표 가 통과 할 수 있 는 점 수 를 유지 하고 세로 선 을 매 거 하 며 이 점 이 중복 계산 되 는 것 을 고려 하여 먼저 꺼 내 계산 한 후에 다시 추가 합 니 다.세 개의 횡선, 세 개의 세로 선 이 유사 하 다.
코드:
#include
using namespace std;
const int N=1e5+5,lim=1e5+1;
int mx[N<<2];
vectorg[N];
void up(int o,int l,int r,int pos,int val){
if(l==r){
mx[o]+=val;
return ;
}
int m=(l+r)>>1;
if(pos<=m)
up(o*2,l,m,pos,val);
if(pos>m)
up(o*2+1,m+1,r,pos,val);
mx[o]=max(mx[o*2],mx[o*2+1]);
}
int main(){
int n,r,x,y;
scanf("%d%d",&n,&r);
for(int i=0;i=1)
g[y-r].push_back(x);
if(y+r<=lim)
g[y+r].push_back(x);
up(1,1,lim,x,1);
if(x-r>=1)
up(1,1,lim,x-r,1);
if(x+r<=lim)
up(1,1,lim,x+r,1);
}
int ans=0;
for(int i=1;i<=lim;i++){
for(int j=0;j=1)
up(1,1,lim,g[i][j]-r,-1);
if(g[i][j]+r<=lim)
up(1,1,lim,g[i][j]+r,-1);
}
ans=max(ans,mx[1]+(int)g[i].size());
for(int j=0;j=1)
up(1,1,lim,g[i][j]-r,1);
if(g[i][j]+r<=lim)
up(1,1,lim,g[i][j]+r,1);
}
}
printf("%d
",ans);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2019 우 객 여름 다 교 훈련소 (제10 회) F: Popping BalloonsPopping Balloons 제목: 가로 선 3 개, 세로 선 3 개 를 선택 하고 인접 선 간 의 거 리 는 r 를 초과 하지 않 으 며 통과 할 수 있 는 최대 포 인 트 를 구하 십시오. 생각: 가로 선 하나...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
