跳方格 (lattice) （差分+二分）

科技前沿 • 2025-01-17 15:09 • 阅读 65

大家好，我是讯享网，很高兴认识大家。

题目描述
有一个长长的走廊，巨神 ctt 把它分成m方格，从左到右编号为1,2,…,m。

有一天，巨神 ctt 得到了n个蹦床，他把这些蹦床放在方格里，他在编号为1的方格里放了一个蹦床，在编号为2,3,…,m-1的方格中放置了n-1个蹦床（一个方格只能放一个蹦床）。

巨神 ctt 估算了自己的跳远水平和蹦床的弹性，知道了他从第i个蹦床跳跃最多可以跳过li个方格（若这个蹦床放置的方格编号为k，则他最多能跳到编号为k+li的方格里，l1表示从编号为1的方格里的蹦床跳跃最可以跳过l1个方格），他开始计算从编号为1的方格，从左向右在蹦床上跳跃，最终到达编号为m的方格上，这样跳跃的方式有多少种。

巨神 ctt 非常生气，因为他直接秒出了答案，所以他用这繁杂的统计来考考你，但你的结果可以对10⁹+7取模。

输入
第一行三个正整数n,m,l1，表示蹦床的个数、方格的个数和从编号为1的方格里的蹦床跳跃最可以跳过的方格数。
接下来n-1行，每行两个正整数，第i行的两个正整数分别表示第i个蹦床所在方格的编号和从第i个蹦床跳跃最多可以跳过的方格数。

讯享网

输出
仅一行一个整数表示答案。

样例输入
【样例1】
3 5 3
2 1
4 1
【样例2】
5 7 2
2 2
4 1
5 2
6 1

样例输出
【样例1】
1
【样例2】
2

提示
在这里插入图片描述
思路
二分找每个蹦床覆盖的最大区间，以当前的答案值差分处理，即可推出答案

代码实现

#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #define re register using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=1e6+5; const int M=5e6+5; const int INF=0x3f3f3f3f; const ll LINF=1e18; const ull sed=31; const ll mod=1e9+7; // const double eps=1e-6; // const double PI=acos(-1.0); // const double delta=0.993; typedef pair<int,int>P; typedef pair<double,double>Pd; typedef pair<ll,int> plt; typedef pair<ll,ll> pll; template<class T>inline void read(T &x) { 
    x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') { 
   f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){ 
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return; } template<class T>inline void write(T x) { 
    if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } struct node { 
    int p,l; }E[N]; bool cmp(node a,node b) { 
    return a.p<b.p; } ll dp[N],ans; int n,m; int bis_l(int x) { 
    int ret=0; int l=2,r=n+1; while (l<=r) { 
    int mid=(l+r)>>1; if(E[mid].p>=x) { 
    ret=mid; r=mid-1; } else l=mid+1; } return ret; } int bis_r(int x) { 
    int ret=0; int l=2,r=n+1; while (l<=r) { 
    int mid=(l+r)>>1; if(E[mid].p<=x) { 
    ret=mid; l=mid+1; } else r=mid-1; } return ret; } int main() { 
    // freopen("a.txt","r",stdin); read(n);read(m);read(E[1].l); E[1].p=1; for(int i=2;i<=n;i++) { 
    read(E[i].p); read(E[i].l); } sort(E+1,E+1+n,cmp); E[n+1].p=m; dp[1]=1; dp[2]=-1; for(int i=1;i<=n;i++) { 
    ans=(ans+dp[i])%mod; int l=bis_l(E[i].p+1),r=bis_r(E[i].p+E[i].l); if(!l|| !r) continue; dp[l]=(dp[l]+ans)%mod; dp[r+1]=(dp[r+1]-ans+mod)%mod; } ans=(ans+dp[n+1])%mod; printf("%lld\n",ans); return 0; }

讯享网

跳方格 (lattice) （差分+二分）

相关推荐