Problem A. Bits

找到 [l, r] 之间 count_bits() 最多的数。。。
首先 ans = l。。。然后迭代。。。每次把最低位的 0 补成 1。。。
后者可以通过 l |= l+1 实现。。

for i in range(int(input())):
 l,r=map(int,input().split())
 while(l|(l+1)<=r): l|=l+1
 print(l)

Problem B. Maximum Value

给定一堆数。
问最大的 x%y 的值。。要求 x>=y。。

O(nqrtn) 算法：
我们有：x＝qy＋r
。。枚举 y。。。然后枚举 q。
然后每次找到小于 qy 的最大的数即可。

const int N = int(2e6) + 9;
int a[N];
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

	REP_C(i, RD(n)){
	    int ai; RD(ai);
	    a[ai] = ai;
	}

	FOR(i, 1, N) checkMax(a[i], a[i-1]);

	// x = qy + r

	int z = 0; FOR(y, 1, N) if (a[y] == y){
	    for (int qy=y;qy+y-1<N;qy+=y) checkMax(z, a[qy+y-1]-qy);
	}

	OT(z);
}

O(n) 算法：
通过类似筛法，得到每个数的最大约数。
用这个可以干嘛？

const int N = int(1e6) + 9;
int a[N];
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

	REP_C(i, RD(n)){
	    int ai; RD(ai);
	    a[ai] = ai;
	}


	int z = 0, t = 1; REP(i, N) if (a[i]){
        checkMax(t, i); while (t<N && t<i+a[i]){
            //cout << t << " "<< i << endl;
            if (a[t] == t) checkMax(z, t-i);
            ++t;
        }
        if (i+a[i]<N) checkMax(a[i+a[i]], a[i]);
    }

	OT(z);
}

Problem C. Strange Sorting

Problem D. Kindergarten

Brief description:

给定一个数组 A[]，按顺序分成一些连续的组，每组的贡献是组中最大的数与最小数的绝对值。
求一种分组方案，使得所有组的贡献的和最大。

Analysis:

由于最大、最小的数一定是处在组的端点。。。
所以不难写出如下 DP：

    REP_1(i, n){
        REP_1(j, i-1){
            checkMax(dp[i], dp[j-1] + abs(A[i] - A[j]));
        }
    }

然后把绝对值拆开。。
用两个树状数组记录一下就行了 http://codeforces.com/contest/484/submission/8596652
复杂度 $$O(nlogn)$$。。。

看了官方 题解 才发现应该用 $$O(n)$$ 的做法。。。
因为每组的数一定是单调的。。。

因此潜在的转移位置只有 3 个。。。（Paying attention to the interesting points in sequence which making local maximums (i. e. ai - 1 < ai > ai + 1), local minimums (ai - 1 > ai < ai + 1), and point adjacent to them。） 记录一下就行了。。。

Problem E. Sign on Fence

Brief description:

给定长度为 n 的数组 $h_i$。。
每次回答询问： l, r, w 。。表示求：
$$!\max_{l \leq i \leq r-w+1} \min_{i\leq j\leq i+w-1}h_i$$
（[l, r] 之间，长度为 w 的连续段里，最小值的最大值。。。）

Analysis:

先写一个支持区间求最大测度的线段树。。。
然后 cdq 分治。。同 BZOJ 2527. [Poi2011]Meteors

（根据 Swistakk 的留言。。原来这种方法更合适的名字是 “parallel binary search”。）

http://codeforces.com/contest/484/submission/8596944

//}/* .................................................................................................................................. */

const int N = int(3e5) + 9;

int A[N], ans[N];
int n;

VI P;

struct rec{
    int ll, rr, mx; bool full;
    void reset(int t){
        ll = rr = mx = t;
        full = t;
    }
    void upd(const rec l, const rec r){
        full = l.full && r.full;
        mx = max(l.mx, r.mx, l.rr + r.ll);
        ll = max(l.ll, l.full ? l.ll + r.ll : 0);
        rr = max(r.rr, r.full ? r.rr + l.rr : 0);
    }
};

namespace ST{

#define lx (x << 1)
#define rx (lx | 1)
#define ml (l+r>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
#define rt 1,1,n

    rec T[4*N]; int a, b;
    rec Q(int x, int l, int r){
        if (b < l || r < a) return rec();
        if (a <= l && r <= b){
            return T[x];
        }
        else{
            rec ll = Q(lc), rr = Q(rc);
            rec zz; zz.upd(ll, rr);
            return zz;
        }
    }

    int Q(int _a, int _b){
        a = _a, b = _b;
        return Q(rt).mx;
    }

    void Add(int x, int l, int r){
        if (l == r){
            T[x].reset(b);
        }
        else{
            if (a < mr) Add(lc); else Add(rc);
            T[x].upd(T[lx], T[rx]);
        }
    }
    void Add(int x){
        a = x, b = 1;
        Add(rt);
    }
    void Del(int x){
        a = x, b = 0;
        Add(rt);
    }
};

struct Query{
    int l, r, w;
    void in(){
        RD(l,r,w);
    }
    bool ok(){
        return ST::Q(l,r) >= w;
    }
} Q[N]; VI op[N];

void cdq(const VI I, int l, int r){
    if (l + 1 == r){
        ECH(i, I) ans[*i] = l;
    }
    else{
        int m = l + r >> 1;

        FOR(i, l, m) ECH(it, op[i]) ST::Add(*it);

        VI Il, Ir; ECH(i, I){
            if (Q[*i].ok()){
                Il.PB(*i);
            }
            else{
                Ir.PB(*i);
            }
        }

        cdq(Ir, m, r); FOR(i, l, m) ECH(it, op[i]) ST::Del(*it);
        cdq(Il, l, m);
    }
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    REP_1_C(i, RD(n)) P.PB(RD(A[i]));
    UNQ(P); REP_1(i, n) op[P.size()-LBD(P, A[i])-1].PB(i);
    int m; VI I; REP_1_C(i, RD(m)) Q[i].in(), I.PB(i);

    cdq(I, 0, P.size());
    REP_1(i, m) OT(P[P.size()-ans[i]-1]);
}

Posted by xiaodao
Category: 日常