题目传送门(BZOJ)

题解 :

本题网上别人的题解基本都是更优的$O(N)$, 看完我的请不要说我误人子弟
看到是个环, 数轴还特别长, 首先倍长+离散化一下, 此时要注意数组越界 (这两天做好多环儿题啊 !
考虑一下暴力怎么搞 :
对于当前走到的 $pos$, 下次肯定是从 $1\sim pos$ 中找一个 $r$ 最大的来走
设倍增 : $F[i][j]$表示从点 $j$ 走 $2^i$ 步最远能到哪里,
初始状态 $F[0][a[j]] = \max(F[0][a[j]], b[j]), F[0][i] = \max(F[0][i], F[0][i-1])$
我们对于原点和倍增之后的点都要处理一下初始状态
然后递推式子 $F[i][j] = F[i-1][F[i-1][j]]$ 是一般的递推式子了
每次求答案跳的时候, 若当前这个 $a[i] < b[i]$, 我们就给 $a[i] += m$, 代表 $b[i]$ 的目标点是下一圈的 $a[i]$
否则不用动, 目标点就是这个 $a[i]$ (因为上半圈的 $a[i] \sim b[i]$ 是强制这个人走的)
然后从大到小枚举 $i$, 若跳 $2^i$ 步到不了目的, 就把 $2^i$ 累加进答案
最后答案要加二, 是这个人本身 ($a[i] \sim b[i]$) 和无限逼近后的最后一步
细节请看看代码
复杂度 $O(N\log N)$

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 200200;#define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++char buf[100000], *p1, *p2;inline char gc() { char ch = nc(); while(isspace(ch)) ch = nc(); return ch;}inline int rd() { int x = 0, f = 1; char ch = nc(); while(!isdigit(ch)) ch = nc(); while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc(); return x*f;}int f[20][N<<2];int v[N<<1], a[N], b[N], n, lg;inline int getPos(int x) {return lower_bound(v+1, *v+v+1, x)-v;}int main() { n = rd(), rd(); int &m = v[0]; for(int i = 1; i <= n; i ++ ) v[++*v] = a[i] = rd(), v[++*v] = b[i] = rd(); sort(v+1, *v+v+1); for(int i = 1; i <= n; i ++ ) { a[i] = getPos(a[i]), b[i] = getPos(b[i]); if(a[i] < b[i]) { f[0][a[i]] = max(f[0][a[i]], b[i]); f[0][a[i]+m] = max(f[0][a[i]+m], b[i]+m); } else { f[0][1] = max(f[0][1], b[i]); f[0][a[i]] = max(f[0][a[i]], b[i]+m); f[0][a[i]+m] = max(f[0][a[i]+m], m<<1); } } for(int i = 1; i <= m << 1; i ++ ) f[0][i] = max(f[0][i], f[0][i-1]); for(int i = 1; 1<<i<=m<< 1; lg ++, i ++ ) for(int j = 1; j <= m << 1; j ++ ) { f[i][j] = f[i-1][f[i-1][j]]; } printf("%d\n", lg); return 0; for(int i = 1; i <= n; i ++ ) { int ans = 0, x = b[i]; if(a[i] < b[i]) a[i] += m; for(int j = lg-1; ~j; j -- ) if(f[j][x] < a[i]) ans += 1<<j, x = f[j][x]; if(i != 1) putchar(' '); printf("%d\n", ans+2); }}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<