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]);
}
