文档章节

bzoj5017: [Snoi2017]炸弹

o
 osc_x4h57ch8
发布于 2018/04/24 07:56
字数 383
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

相信我这题就是(tarjan缩点+拓扑序dp+线段合并+线段树优化建图)

昨天P老大跟我说这题跟C很不一样虚死我了。。看了下路牌发现就是上面那玩意。。。(搞什么啊大佬集体带节奏a)

那么我的水法就是枚举每个炸弹左右延伸咯,学习噶爷瞎搞个随机数列

然后完了。

 upd:被rose_max D飞惹...因为数据太水...code有点小错(现在改回来了)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
 
struct node
{
    LL x,r;
}a[510000];
LL L[510000],R[510000],minL[510000],maxR[510000];
int n;LL ans;
void extend(LL i)
{
    bool bk=true;
    while(bk==true)
    {
        bk=false;
        while(L[i]>1&&minL[i]<=a[L[i]-1].x)
        {
            bk=true;
            minL[i]=min(minL[i],minL[L[i]-1]), maxR[i]=max(maxR[i],maxR[L[i]-1]);
            R[i]=max(R[i],R[L[i]-1]), L[i]=min(L[i],L[L[i]-1]);
        }
        while(R[i]<n&&maxR[i]>=a[R[i]+1].x)
        {
            bk=true;
            minL[i]=min(minL[i],minL[R[i]+1]), maxR[i]=max(maxR[i],maxR[R[i]+1]);
            L[i]=min(L[i],L[R[i]+1]), R[i]=max(R[i],R[R[i]+1]);
        }
    }
    ans=(ans+ (i*(LL(R[i]-L[i]+1))%mod ) )%mod;
}
int rd[510000];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].r);
    
    ans=0;
    for(int i=1;i<=n;i++)
        L[i]=R[i]=i,minL[i]=a[i].x-a[i].r,maxR[i]=a[i].x+a[i].r;
    
    for(int i=1;i<=n;i++)rd[i]=i;
    random_shuffle(rd+1,rd+n+1);
    for(int i=1;i<=n;i++)extend( (LL(rd[i])) );
    printf("%lld\n",ans);
    return 0;
}
 

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

会议通知 | 2020中国计算与认知神经科学会议

关于大会关于 计算神经科学以神经生物实验为基础,以建立数学模型,开展计算模拟和分析作为基本手段,来刻画和描述大脑的神经活动,探究神经系统各种复杂活动和认知功能包括注意、学习、记忆...

脑机接口社区
06/02
20
0
大神分享快3怎么算下期和值

大神分享快3怎么算下期和值{叩67790572}使用的标签:constructor-arg标签出现的位置:bean标签的内部标签中的属性type:用于指定要注入的数据的数据类型,该数据类型也是构造函数中某个...

yiren081
32分钟前
21
0
Matlab系列之运算符和标点符号的功能介绍

本来月初就打算接着写的,但是电脑不小心进水,主板什么的都废了,周末才找时间拿去修好,心塞。 就不多讲太多废话了,开始分享今天的内容,对MATLAB的运算符做个介绍,然后再对标点符号进行...

狂人V
07/06
18
0
Java源码系列(1):Comparable和Comparator的区别

在讲Comparable和Comparator区别之前,先补充一个知识点。 先看代码: Person类 1public class Person<T> { 2  private T id; 3 4  public T getId() { 5    return i...

学习Java的小姐姐
2018/09/19
25
0
ThreadPoolTaskScheduler手写调度中心

先贴一个自己写的demo把,原理其实就是这样的。 CronTrigger这个类可以将cron表达式转换成Date,可以查看schedule源码学到不少东西,下面代码就是转换成下一执行时间。 public Date nextEx...

朝如青丝暮成雪
53分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部