Educational Codeforces Round 149 (Rated for Div. 2) / 1837

A. Grasshopper on a Line

难度（个人感觉）☆☆☆☆☆

Code

if(L % k == 0){
  ans.push_back(1);
  ans.push_back(L - 1);
} else{
  ans.push_back(L);
}

B. Comparison String

难度（个人感觉）★☆☆☆☆

思考：

注意到最长链（指一些连续的位置，它们是单调的）是答案的下界，而实际上这是下确界。

做法：

设最长链长度为k，可以把所有 >< 中间的位置赋值为 \(1\)，把 <> 中间的位置赋值为 \(k\) 。其它位置的赋值是容易的。

Code:

ans = 0;
for(int i = 0, l = 0; i < N; i++){
  if(i == N - 1 || i < N && s[i] != s[i + 1]){
    if(i + 1 - l + 1 > ans) ans = i + 1 - l + 1;
    l = i + 1;
  }
}

C. Best Binary String

难度（个人感觉）★☆☆☆☆

思考：

我们设定一个指标来衡量当前的局势，容易发现 01 交错的数量是可以作为这个指标的。

做法：

设 01 交错的数量是 \(h(Array)\) 。当 \(h(Array) == 1\)，说明是单调的。但是可能只有一种数；可能是单调不增。解决这些问题的方法是再序列开头添加一个 \(0\) ，在序列末尾添加一个 \(1\) 。

那么答案的下界是 \(h(Array) - 1) / 2\) ，因为每次 \(h\) 最多减少 \(2\) 。这当然也是下确界，因为总可以减 \(2\)。

所以我们的目标是让 \(01\) 交错尽量少，问号取前一个元素的值即可。

Code:

void input(){
  s = '0' + s + '1';
}
 
for(int i = 1; i < N - 1; i++){
  if(s[i] == '?'){
    s[i] = s[i - 1];
  }
  ans.push_back(s[i]);
}

D. Bracket Coloring

难度（个人感觉）★☆☆☆☆

思考：

唯一一颗星是因为需要知道，合法括号序列等价于合法的栈操作。
接下来，画出一个函数图象，表示前缀的 \(i\) 个数里，左括号减右括号的数量。

做法：

那么合法当所有点在 \(y = 0\) 及上方；另一种 beautiful 当所有点在 \(y = 0\) 及下方
如果最终不为 \(0\) ，那么不合法；否则把上方的东西放在一起，下方的东西放在一起即可。

Code:

int k = 0;
for(int i = 0; i < N; i++){ k += s[i] == '(' ? 1 : -1; }
if(k != 0){
  ok = 0;
  return;
} else{
  ok = 1;
}

std::vector<int> c0, c1;
k = 0;
int l = 0;
for(int i = 0; i < N; i++){
  k += s[i] == '(' ? 1 : -1;
  if(k == 0){
    if(s[i] == ')'){
      for(int j = l; j <= i; j++){
        c0.push_back(j);
      } 
    } else{
      for(int j = l; j <= i; j++){
        c1.push_back(j);
      }
    }
    l = i + 1;
  }
}

C = 0;
if(!c0.empty()){
  for(int p : c0){
    ans[p] = C;
  }
  C++;
}
if(!c1.empty()){
  for(int p : c1){
    ans[p] = C;
  }
  C++;
}

E. Playoff Fixing

难度（个人感觉）★★☆☆☆
很不错的 dp 练习题

思考：

考虑分治。对于一个区间 \([l, r]\)，算出 \([l, mid]\) 和 \([mid, r]\) 后合并即可。

做法：

对于一个高度为 k （即管 pow(2, k) 个位置）的区间，一定有一个数是最大的。我们不管最大的数具体是多少，只关心它是不是确定的。然后 \(dp\) 即可。

Code:

void input(){
  if(a[i] > 0){ a[i]--; }
}
pii work(int deep = 0, int l = 0, int r = N){//分别是数值，方案书。数值为 -1 表示不是确定的，数值为 -2 表示无解。
  if(deep == k) return {a[l], 1};
  int mid = (l + r) / 2;
  pii p0 = work(deep + 1, l, mid), p1 = work(deep + 1, mid, r);
  int x0 = p0.first, w0 = p0.second, x1 = p1.first, w1 = p1.second;
  if(!(x0 < x1)){ std::swap(x0, x1); std::swap(w0, w1); }
  if(x0 == -1 && x1 == -1){
    return {-1, 2ll * w0 * w1 % mod};
  } else if(x0 == -1){  
    if(x1 < (1 << deep)){
      return {x1, 1ll * w0 * w1 % mod};
    } else{
      return {-1, 1ll * w0 * w1 % mod};
    }
  } else{
    if(x0 < (1 << deep) && x1 < (1 << deep)){
      return {-2, 0};
    } else if(x0 < (1 << deep)){
      return {x0, 1ll * w0 * w1 % mod};
    } else{
      return {-2, 0};
    }
  }
}

F. Editorial for Two

2log 难度（个人感觉）★★☆☆☆
1log 难度（个人感觉）★★★☆☆

思考：

给出分界点，那么 选左边最小的 \(x\) 个，右边最小的 \(k-x\) 个。

做法：

2log:

由于 \(x\) 难以确定，我们二分答案，看左右的和是否达到 \(k\)。
具体判定是容易的，先用堆进行预处理，然后每个位置依次判断

code:

int pre[MAXN + 1], suf[MAXN + 1];
void get_pre(i64 k){
  std::priority_queue<int> Q;
  i64 sum = 0;
  for(int i = 0; i <= N; i++){
    pre[i] = Q.size();
    if(i != N){
      sum += a[i]; Q.push(a[i]);
      while(sum > k) { sum -= Q.top(); Q.pop(); };
    }
  }    
}
void get_suf(i64 k){
  std::priority_queue<int> Q;
  i64 sum = 0;
  for(int i = N; i >= 0; i--){
    if(i != N){
      sum += a[i]; Q.push(a[i]);
      while(sum > k) { sum -= Q.top(); Q.pop(); };
    }
    suf[i] = Q.size();
  }    
}
bool check(i64 k){
  get_pre(k);
  get_suf(k);
  for(int i = 0; i <= N; i++){
    if(pre[i] + suf[i] >= need) return 1;
  }
  return 0;
}
int get(){
  i64 L = -1, R = 3e14;
  while(L + 1 < R){
    i64 mid = (L + R) / 2;
    if(check(mid)){ R = mid; }
    else { L = mid; }
  }
  ans = R;
}

1log:

由于 \(x\) 是不减的，因此判段 \(x\) 是否要增加即可。

cf 上最快的解法

https://codeforces.com/contest/1837/submission/207295831

有空补下（