Educational Codeforces Round 146 (Rated for Div. 2) / 1814

A. Coins

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

思考：

关键是 2 可以凑出任意偶数

Code:

if(n % 2 == 0){
  ok = 1;
} else{
  if(k % 2 == 0){
    ok = 0;
  } else{
    ok = n >= k;
  }
}

B. Long Legs

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

思考：

当最终 \(m = 1e5\)，答案不超过 \(3e5\)，因此最优的情况下，\(m \le 3e5\)

ans = INF;
for(int k = 1; k < 1e6; k++){
  chmin(ans, k - 1 + ((a + k - 1) / k) + ((b + k - 1) / k));
}

C. Search in Parallel

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

思考：

找到可以用的最早的n个时刻，边权大的优先放置

Code:

std::vector<int> id(N);
for(int i = 0; i < N; i++){
  id[i] = i;
}
sort(id.begin(), id.end(), [&](int i, int j){
  return a[i] > a[j];
});

int i = 0, j = 0;
while(i + j < N){
  if((i + 1) * cost[0] < (j + 1) * cost[1]){
    ans[0].push_back(id[i + j]);
    i++;
  } else{
    ans[1].push_back(id[i + j]);
    j++;
  }
}

E. Chain Chips

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

思考:

首先一条边如果被经过了，那至少被经过2次

考虑一个被经过边的连通块，我们可以把第一个元素移到最后，其它元素往前移，这样每条边被经过两次。

因此答案是被经过的边的权值和*2，而选择合法，当且仅当任何两个相邻的边至少有一条被选。

做法:

线段树直接维护。
\(c[1][1]\) 表示完全覆盖
由 \(c[1][x] + c[x][1]\) 得到，其中例如 c[1][0] 表示除最右点完全覆盖。
依次发现需要维护所有 \(c[x][y]\) 。

Code:

struct Info{
  i64 c[2][2];
  Info(){
    for(int i = 0; i < 2; i++){
      for(int j = 0; j < 2; j++){
        c[i][j] = INF;
      }
    }
  }
  void set(int x){ 
    c[0][0] = 0;
    c[1][1] = x;
  }
  friend Info operator + (Info& L, Info& R){
    Info res;
    for(int Ll = 0; Ll < 2; Ll++){
      for(int Lr = 0; Lr < 2; Lr++){
        for(int Rl = 0; Rl < 2; Rl++) if(Lr || Rl){
          for(int Rr = 0; Rr < 2; Rr++){
            chmin(res.c[Ll][Rr], L.c[Ll][Lr] + R.c[Rl][Rr]);
          }
        }
      }
    }
    return res;
  }
};