NBOJv2 1050 Just Go（线段树/树状数组区间更新单点查询）-白红宇

NBOJv2 1050 Just Go（线段树/树状数组区间更新单点查询）

阅读量：5338 次

发布时间：2019-06-15

本文共 4101 字，大约阅读时间需要 13 分钟。

Problem 1050: Just Go

Time Limits: 3000 MS Memory Limits: 65536 KB

64-bit interger IO format: %lld Java class name: Main

Description

There is a river, which contains n stones from left to right. These stones are magic, each

one has a magic number Ai which means if you stand on the ith stone, you can jump to (i +1)th stone, (i+2)th stone, ..., (i+Ai)th stone(when i+Ai > n, you can only reach as far as n), at first, you stand on 1th stone, you want to calculate the number of ways to reach the nth stone.

Notice: you can not jump from right to left!

Input

Input starts with an integer T(1 <= T <= 10), denoting the number of test cases. Each test case contains an integer n(1 <= n <= 1e5), denoting the number stones. Next line contains n integers Ai(1 <= Ai <= 1e8).

Output

For each test case, print the number of way to reach the nth stone module 1e9+7.

Sample Input

351 2 3 4 511022 1

Output for Sample Input

校赛那会儿的题目，主要操作就是区间更新、单点查询，树状数组和线段树都可以，树状数组的简单很多也好写很多，线段树嘛，线段树的模版题自行体会。

主要解题思路：刚开始肯定是1号石头初始化为1，其他的都是0，这个相信很好理解，然后就是往后覆盖区间，但却不是简单的覆盖，为了弄懂到底如何操作举个例子先，比如我到3号有a种路线，到4号有几种（假设4号只与3号连通）？当然跟3号一样，就是a种，如果3号可以跳跃的步数不止1即可以跳到5号上呢？此时会变成P5=P4+P3，即3号过来有三种，4号过来有1种（只能跳一步过来）。加起来就是4种，3->5一种，3->4>-5三种，推广出去就是不停地往后覆盖自己这个点的可到达情况数就好了，最后的答案当然就是Pn

树状数组代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 using namespace std;#define INF 0x3f3f3f3f#define MM(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)1)#define MID(x,y) ((x+y)>>1)typedef pair
                  
                    pii;typedef long long LL;const double PI=acos(-1.0);const int N=100010;const LL mod=1000000007;LL tree[N],arr[N];inline int lowbit(int k){ return k&(-k);}void add(int k,LL val){ while (k<=100000) { tree[k]+=val; k+=lowbit(k); }}LL getsum(int k){ LL r=0; while (k) { r+=tree[k]; r%=mod; k-=lowbit(k); } return r%mod;}void init(){ MM(tree,0); MM(arr,0);}int main(void){ int tcase,i,j,l,r,n; scanf("%d",&tcase); while (tcase--) { scanf("%d",&n); init(); add(1,1); add(2,-1); for (i=1; i<=n; i++) { scanf("%I64d",&arr[i]); } for (i=1; i<=n; i++) { l=i+1; r=i+arr[i]; if(r>n) r=n; LL pres=getsum(i); add(l,pres); add(r+1,-pres); } printf("%I64d\n",getsum(n)); } return 0;}

线段树代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 using namespace std;#define INF 0x3f3f3f3f#define MM(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair
                  
                    pii;typedef long long LL;const double PI=acos(-1.0);const int N=100010;const LL mod=1e9+7;struct info{ LL l,mid,r; LL sum,add;};info T[N<<2];LL arr[N];void pushup(int k){ T[k].sum=T[LC(k)].sum+T[RC(k)].sum;}void pushdown(int k){ T[RC(k)].add+=T[k].add; T[RC(k)].sum+=T[k].add*(T[RC(k)].r-T[RC(k)].l+1); T[LC(k)].add+=T[k].add; T[LC(k)].sum+=T[k].add*(T[LC(k)].r-T[LC(k)].l+1); T[k].add=0;}void build(int k,LL l,LL r){ T[k].l=l; T[k].r=r; T[k].mid=MID(T[k].l,T[k].r); T[k].add=0; T[k].sum=0; if(l==r) T[k].sum=(l==1&&r==1?1:0); else { build(LC(k),l,T[k].mid); build(RC(k),T[k].mid+1,r); pushup(k); }}void update(int k,LL l,LL r,LL val){ if(r
                   
                    T[k].r) return ; if(l<=T[k].l&&r>=T[k].r) { T[k].add+=val; T[k].sum+=val*(T[k].r-T[k].l+1); T[k].sum%=mod; } else { if(T[k].add) pushdown(k); update(LC(k),l,r,val); update(RC(k),l,r,val); pushup(k); }}LL query(int k,LL x){ if(T[k].l==T[k].r&&T[k].l==x) return T[k].sum%mod; if(T[k].add) pushdown(k); if(x<=T[k].mid) return query(LC(k),x)%mod; else if(x>T[k].mid) return query(RC(k),x)%mod;}int main(void){ int tcase,i,j,n; LL l,r,x,val; scanf("%d",&tcase); while (tcase--) { scanf("%d",&n); MM(arr,0); for (i=1; i<=n; i++) scanf("%I64d",&arr[i]); build(1,1,n); for (i=1; i<=n; i++) update(1,(LL)(i+1),(LL)(i+arr[i]>n?n:i+arr[i]),query(1,i)); printf("%I64d\n",query(1,n)%mod); } return 0;}

转载于:https://www.cnblogs.com/Blackops/p/5766287.html

你可能感兴趣的文章