[CSP2020]贪吃蛇 [贪心]

周末偷偷看了看CSP T4,发现非常刺激,铁牌退役狗想了一中午(不过感觉比树上的树简单不少)

注意到本题中的蛇只需要最大化自己吃几个,不需要最大化排名。我们称拥有其它蛇梦寐以求的选择权利的蛇为后浪蛇(当前值最大),没有选择权利的蛇为打工蛇(当前值最小)。

考虑后浪蛇的策略:如果吃掉打工蛇,在游戏之后一定不会死,那就吃,否则就不吃。于是只需要求会不会死。

可以发现吃掉打工蛇之后,如果自己没有变成打工蛇,那么它的值一定大于之后产生的所有新蛇,于是不会死可以吃。如果吃掉后只剩下自己,也可以吃。

如果后浪蛇吃掉打工蛇后自己变成打工蛇,那么它很可能被下一个吃掉。于是只需判断下一个后浪蛇是否可以吃掉它。如果吃掉当前打工蛇,下一个后浪蛇可以吃掉自己,那么就必须停止游戏。否则就可以吃。于是可以假装吃掉了打工蛇,把问题丢给下一个后浪,递归求解。递归边界是某条后浪吃掉打工蛇后自己没有变成打工蛇。

当然其实不需要递推,开个set模拟就行。注意到模拟上述过程时间不太够,考虑用某年noip蚯蚓那个题的经典方法优化。具体来说,开两个deque,由上面的分析可知产生的新蛇一定更小,于是把初始蛇丢尽第一个队列,新产生的蛇丢进第二个队列,假装它是个set就行了。

#include <bits/stdc++.h>
using std::cerr;
using std::endl;

inline int rd() {
  int b = 0; char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return b;
}

const int N = 1e6 + 233;

struct Node {
  int val, id;
  bool operator<(Node n) const {
    return val < n.val || (val == n.val && id < n.id);
  }
  bool operator==(Node n) const {
    return val == n.val && id == n.id;
  }
};

int ans, n, A[N];

inline void solve(int kase) {
  ans = rd();
  if (kase == 1) {
    n = ans;
    for (int i = 1; i <= n; ++i)
      A[i] = rd();
  } else {
    for (int i = 1; i <= ans; ++i) {
      int x = rd(), y = rd();
      A[x] = y;
    }
  }
  ans = n;
  std::deque<Node> que1, que2;
  for (int i = 1; i <= ans; ++i)
    que1.push_front({A[i], i});
  while (true) {
    if (que1.size() + que2.size() <= 2) {
      if (que1.size() + que2.size() == 2)
        --ans;
      break;
    }
    Node min, max;
    min = que1.back();
    que1.pop_back();
    if (que2.empty()) {
      max = que1.front();
      que1.pop_front();
    } else {
      if (que1.size() == 1 || que1.front() < que2.front()) {
        max = que2.front();
        que2.pop_front();
      } else {
        max = que1.front();
        que1.pop_front();
      }
    }
    max.val -= min.val;
    if (!que1.empty() && que1.back() < max) {
      que2.push_back(max);
      --ans;
      continue;
    }
    int del = 0;
    while (true) {
      if (que1.size() + que2.size() == 1)
        break;
      min = max;
      if (que2.empty()) {
        max = que1.front();
        que1.pop_front();
      } else {
        if (que1.size() == 1 || que1.front() < que2.front()) {
          max = que2.front();
          que2.pop_front();
        } else {
          max = que1.front();
          que1.pop_front();
        }
      }
      max.val -= min.val;
      if (!que1.empty() && que1.back() < max)
        break;
      if (!que2.empty() && que2.back() < max)
        break;
      del ^= 1;
    }
    ans -= del;
    break;
  }
  printf("%d\n", ans);
}

int main() {
  int T = rd();
  for (int i = 1; i <= T; ++i)
    solve(i);
  return 0;
}
  1. 头像 cbio说道:

    orz

  2. 头像 LGH10086说道:

    @邓鸽鸽高考加油啊

    1. kai586123 kai586123说道:

      大专挺好的 :lei:

发表评论

电子邮件地址不会被公开。必填项已用 * 标注