BSNY正在玩多米诺骨牌,他将n块多米诺骨牌从左到右排成一行。其中每块多米诺骨牌所在的位置设为x,每块多米诺骨牌高度为h。如果将x位置上的多米诺骨牌向右翻到,它就可以影响[x+1, x+h-1]范围内的所有多米诺骨牌,让他们也翻到,同时这些被翻到的多米诺骨牌还能影响到其他多米诺骨牌,也就是多米诺骨牌效应。
例如现在有4块多米诺骨牌,位置从左到右依次为10 16 18 20,它们的高度依次为10, 5, 2, 5。当翻到16位置上的多米诺骨牌,18和20位置都在范围[16+1, 16+5-1],所以这两块也翻到了,总共翻到了3块。
现在BSNY给出n块多米诺骨牌的位置和高度,问如果向右翻到第i块多米诺骨牌,会有多少多米诺骨牌翻到。
输入
第一行输入n
接下来n行每行输入xi和hi,分别表示第i块多米诺骨牌的位置和高度
输出
输出一行包含n个结果,用空格隔开
第i个结果表示如果向右翻到第i块多米诺骨牌,会有多少多米诺骨牌翻到。
样例输入
4
16 5
20 5
10 10
18 2
样例输出
3 1 4 1
提示
【样例说明】
输入:
4
0 10
1 5
9 10
15 10
输出:
4 1 2 1
【数据规模和约定】
1<=n<=10^5, -10^8<=xi<=10^8 , 2<=hi<=10^8 xi都不一样
********************************************************************
solution:相信大家都会n^2的暴力,但这无疑会超时。现在我们的一个瓶颈是:怎么快速计算?那么势必要成片累加。我们可以记录下每个点往后能够连续推倒的数量,只要它在范围内,就可以累加这个值,然后直接跳过已被覆盖的点。这样就可以大大节约时间(虽然仍有一部分常数),考试的时候我也是想到这种边扩展边累加的方法,但是没想到用dp的方式来记录并累加,所以就超了。。。。。
#include<cstdio>#include<iostream>#include<algorithm>#define p1 id<<1#define p2 id<<1^1using namespace std;int n;int ans[100005];int tree[450000];struct ty{int x,h,id,to;}d[100005];bool cmp(ty a,ty b){return a.x<b.x;}int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d%d",&d[i].x,&d[i].h);d[i].id=i;d[i].to=d[i].x+d[i].h-1;}sort(d+1,d+n+1,cmp);ans[d[n].id]=1;for(int i=n-1;i>=1;i--) {int last=d[i].to;int q=i+1;ans[d[i].id]=1;while(0==0){if(q>n) break;if(d[q].x<=last) ans[d[i].id]+=ans[d[q].id]; //为什么不用更新last,因为我在当前点能到的范围之外的点,要是能推倒的话,肯定已经包括在当前范围里的某个点中else break;q=q+ans[d[q].id];}} for(int i=1;i<n;i++) cout<<ans[i]<<' ';cout<<ans[n]<<endl;return 0;}
如果觉得《codeforces 56E 多米诺骨牌效应》对你有帮助,请点赞、收藏,并留下你的观点哦!