题目传送门(BZOJ)

题解 :

本题网上别人的题解基本都是更优的O(N), 看完我的请不要说我误人子弟
看到是个环, 数轴还特别长, 首先倍长+离散化一下, 此时要注意数组越界 (这两天做好多环儿题啊 !
考虑一下暴力怎么搞 :
对于当前走到的 pos, 下次肯定是从 1\sim pos 中找一个 r 最大的来走
设倍增 : F[i][j]表示从点 j2^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原创, 转载必须以链接形式注明>原文链接<