首页 > 其他 > 详细

我炸了

时间:2020-05-13 19:44:27      阅读:46      评论:0      收藏:0      [点我收藏+]

本来T1和T2是有题解的,但是我重启了电脑,他们没了。。。
T3

技术分享图片

 

 

 这个嘛。。。有一大堆的做法。
个人倾向于建图跑联通块

awa
可以发现,正着去算非常不好搞awa,所以就倒着来qwq
code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
struct node
{
    int x,h,fa;
}e[1000001];
const int MOD=998244353;
ll f[1000001];
inline ll read()
{
    char c=getchar();ll a=0,b=1;
    for(;c<0||c>9;c=getchar())if(c==-)b=-1;
    for(;c>=0&&c<=9;c=getchar())a=a*10+c-48;
    return a*b;
}
bool mycmp(node a,node b)
{
    return a.x<b.x;
}
int main()
{
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        e[i].x=read();
        e[i].h=read();
    }
    stack<int> s;
    sort(e+1,e+n+1,mycmp);
    f[n]=2;    
    s.push(n);
    for(int i=n-1;i>=1;i--)
    {
        while(s.size()!=0&&e[i].x+e[i].h>e[s.top()].x)s.pop();
        f[i]=f[i+1];
        if(s.size()!=0)
        {
            f[i]+=f[s.top()]%MOD;
        }
        else
        {
            f[i]=(f[i]+1)%MOD;
        }
        s.push(i);
    }
    cout<<f[1]%MOD<<endl;
    return 0;
}

 

我炸了

原文:https://www.cnblogs.com/HLZZPawa/p/12884087.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!