BZOJ 4444: [SCOI2015]国旗计划 – [倍增]


题目传送门(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], 我们就给 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 
#include 
#include 
#include 
#include 
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<

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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注