Educational Codeforces Round 95 (Rated for Div. 2) 题解

A. Buying Torches

这题我写了好多柿子样例都过不去然后上个厕所冷静一下洗了把脸重新读题发现题都没读清，直接把所有木头都转化了成硝石了，但显然还要留k个木头才能转化成火把

void solve() {
  ll x, y, k;
  cin >> x >> y >> k;
  ll sum = y * k + k;
  ll ans = (sum - 2) / (x - 1) + 1 + k;
  cout << ans << nl;
}

B. Negative Prefixes

观察一会儿就可以发现是个贪心构造

首先考虑这些数的总和

如果大于零显然我们可以把所有正数放到最前面这样后面的数再怎么减也不会变成负的

如果小于零那么pn显然一定小于零所以我们就随便写了，不过当时没想透彻还排了个序把负数都尽量提前不过没什么用，这个sort去掉也能过

int a[N], l[N];
 
void solve() {
  int n;
  cin >> n;
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    sum += a[i];
  }
  vector v;
  for (int i = 1; i <= n; ++i) {
    cin >> l[i];
    if (!l[i]) v.push_back(a[i]);
  }
  if (sum < 0) {
    sort(v.begin(), v.end());
    for (int i = 1, j = 0; i <= n; ++i) {
      if (!l[i]) {
        a[i] = v[j++];  
      }
    }
  }
  else {
    sort(v.begin(), v.end(), greater());
    for (int i = 1, j = 0; i <= n; ++i) {
      if (!l[i]) {
        a[i] = v[j++];  
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    cout << a[i] << ' ';
  }
  cout << nl;
}

C. Mortal Kombat Tower

一个比较裸的dp，但是对我来说还是很有意思的，跟经典dp爬楼梯差不多

状态表示是到第 i 层塔是以谁结束的

然后状态转移就比较自然纯纯的爬楼梯

int a[N], f[N][2];
 
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    f[i][0] = f[i][1] = 1e9;
  }
  f[1][0] = a[1];
  f[2][0] = a[1] + a[2];
  f[2][1] = a[1];
  for (int i = 3; i <= n; ++i) {
    f[i][0] = min(f[i - 1][1] + a[i], f[i - 2][1] + a[i - 1] + a[i]);
    f[i][1] = min(f[i - 1][0], f[i - 2][0]);
  }
  cout << min(f[n][0], f[n][1]) << nl;
}

D. Trash Problem

这题很妙很妙，虽然是个数据结构题但不是那种生硬的数据结构，而是发现了性质以后很自然的发现需要用数据结构维护，用set维护点是一个比较自然的想法，但是就做不下去了因为光有点维护相邻点的距离显然还是很麻烦，然后看了题解，题解的做法就是再开一个multiset维护相邻点的距离...只能说我还是太naive了，这么一看题解的思路也确实比较自然，不过这题用set还是有一点细节的主要是节点数小于两个的时候需要特判。

void solve() {
  int n, q;
  cin >> n >> q;
  set s1;
  multiset s2;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    s1.insert(x);
  }
  for (auto i = ++s1.begin(), j = s1.begin(); i != s1.end(); ++i, ++j) {
    s2.insert(*i - *j);
  }
  while (--q>=-1) {
    int mn = *s1.begin(), ma = *s1.rbegin(), len = *s2.rbegin();
    cout << ma - mn - len << nl;
    if (q == -1) break;
    int op, x;
    cin >> op >> x;
    if (op == 1) {
      auto now = s1.lower_bound(x);
      if (now == s1.end()) {
        --now;
        s2.insert(x - *now);
        s1.insert(x);
      }
      else if (now == s1.begin()) {
        s2.insert(*now - x);
        s1.insert(x);
      }
      else {
        auto pre = now;
        --pre;
        s2.erase(s2.find(*now - *pre));
        s2.insert(x - *pre);
        s2.insert(*now - x);
        s1.insert(x);
      }
    }
    else {
      auto now = s1.lower_bound(x), end = s1.end();
      --end;
      if (now == end) {
        --now;
        s2.erase(s2.find(*end - *now));
        s1.erase(end);
      }
      else if (now == s1.begin()) {
        ++now;
        s2.erase(s2.find(*now - *s1.begin()));
        s1.erase(s1.begin());
      }
      else {
        auto pre = now, ne = now;
        --pre, ++ne;
        s2.erase(s2.find(*now - *pre));
        s2.erase(s2.find(*ne - *now));
        s2.insert(*ne - *pre);
        s1.erase(now);
      }
    }
  }
}

待补

G 好像有很巧妙的做法可以尝试一下

F 有个2分tag有空也可以试试