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
3
5
1 2 3 4 5
1
10
2
2 1
Output for Sample Input
3
1
1
校赛那会儿的题目，主要操作就是区间更新、单点查询，树状数组和线段树都可以，树状数组的简单很多也好写很多，线段树嘛，线段树的模版题自行体会。
主要解题思路：刚开始肯定是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<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
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<int,int> 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<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
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<int,int> 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].l||l>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;
}