[POI2014]DOO-Around the world

Posted on | In

摆了一天补篇题解可还行

先断环成链复制一遍，再前缀和预处理

显然终点都在$[n+1,2n]$中，把终点当作起点倒推

考虑设走$f[i]$步可以到达的最远的点为$fa[i]$

如果当前所在点为$i$，找到可以到达的最远的点为$j$

那么$f[i]=f[j]+1$，$fa[i]=fa[j]​$

如果$i-fa[i]>=n$，那么直接退出输出$f[i]$

因为不存在一个更靠后的位置答案更优，证明不会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000002;
int m,n,x,s,f[maxn],fa[maxn],sum[maxn];
inline int read () {
    char ch=getchar(); int num=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
    return num;
}
int main () {
    n=read(),s=read();
    for(register int i=1;i<=n;++i) {
    	int x=read(); m=max(m,x);
    	fa[i]=i,sum[i]=sum[i-1]+x;
    }
    for(register int i=n+1;i<=(n<<1);++i)
        sum[i]=sum[i-1]+sum[i-n]-sum[i-n-1];
    while(s--) {
    	register int i,j,d=read();
    	if(d<m) puts("NO");
    	else for(i=n+1,j=1;i<=(n<<1);++i) {
    		while(sum[i]-sum[j]>d) ++j;
    		f[i]=f[j]+1,fa[i]=fa[j];
    		if(i-fa[i]>=n) {
    			printf("%d\n",f[i]);
    			break ;
            }
        }
    }
    return 0;
}