2019牛客暑期多校训练营（第十场） F Popping Balloons(线段树)

本文主要是介绍2019牛客暑期多校训练营（第十场） F Popping Balloons(线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://ac.nowcoder.com/acm/contest/890/F

 

题目大意：有n个气球，现在可以选择射破三行气球和三列气球，而且保证相邻行和列间距相同，问最多能射裂多少气球

 

题目思路：比赛的时候看到时限这么长就畏惧了..其实非常非常简单..首先先处理一个vector，放一行都有哪些纵坐标有气球可以射，一个num处理每一列有多少个气球，线段树建树，每个节点的值是num[i]+num[i+m]+num[i+2*m]，然后直接暴力枚举最下面的x，然后删除这三行上所有的气球，接着取根最大值就是射爆这几行以后，列的最大值，然后取max就行，这都没想到是真的自闭....

 

以下是代码：

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int MAXN = 1e5+5;
const double eps = 1e-9;
int n,m,x,y;
int num[MAXN];
vector<int>v[MAXN<<2];
struct node{int l,r,val;
}a[MAXN<<2];
void build(int rt,int l,int r){a[rt].l=l,a[rt].r=r;if(l==r){a[rt].val=num[l]+num[l+m]+num[l+2*m];return;}int mid=(l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);a[rt].val=max(a[rt<<1].val,a[rt<<1|1].val);
}
void update(int rt,int x,int val){if(a[rt].l==a[rt].r&&a[rt].l==x){a[rt].val+=val;return;}int mid=(a[rt].l+a[rt].r)>>1;if(x<=mid)update(rt<<1,x,val);else update(rt<<1|1,x,val);a[rt].val=max(a[rt<<1].val,a[rt<<1|1].val);
}
int main()
{while(~scanf("%d%d",&n,&m)){rep(i,0,1e5)v[i].clear(),num[i]=0;int ans=0;rep(i,1,n){scanf("%d%d",&x,&y);v[x].push_back(y);num[y]++;}build(1,0,1e5);rep(i,0,1e5){int temp=v[i].size()+v[i+m].size()+v[i+2*m].size();int len=v[i].size();rep(j,0,len-1){int y=v[i][j];update(1,y,-1);if(y-m>=0)update(1,y-m,-1);if(y-2*m>=0)update(1,y-2*m,-1);}len=v[i+m].size();rep(j,0,len-1){int y=v[i+m][j];update(1,y,-1);if(y-m>=0)update(1,y-m,-1);if(y-2*m>=0)update(1,y-2*m,-1);}len=v[i+2*m].size();rep(j,0,len-1){update(1,y,-1);if(y-m>=0)update(1,y-m,-1);if(y-2*m>=0)update(1,y-2*m,-1);}ans=max(ans,temp+a[1].val);len=v[i].size();rep(j,0,len-1){int y=v[i][j];update(1,y,1);if(y-m>=0)update(1,y-m,1);if(y-2*m>=0)update(1,y-2*m,1);}len=v[i+m].size();rep(j,0,len-1){int y=v[i+m][j];update(1,y,1);if(y-m>=0)update(1,y-m,1);if(y-2*m>=0)update(1,y-2*m,1);}len=v[i+2*m].size();rep(j,0,len-1){update(1,y,1);if(y-m>=0)update(1,y-m,1);if(y-2*m>=0)update(1,y-2*m,1);}}printf("%d\n",ans);}
}

 

这篇关于2019牛客暑期多校训练营（第十场） F Popping Balloons(线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---