比赛🔗

Problem A. 小苯接雨水

把前两大的挡板放在左右两端。

Problem B. 小芳与残骸

模拟几个样例，发现答案就是 $2^{n - 1}$

Problem C. 小苯的棋盘游戏

发现如果行数和列数有一个是奇数，那么一定存在解。

Problem D. 暴暴龙的防奶龙要塞

多画图，我们发现当 $n \le 4$ 的时候无解。当 $n \ge 5$ 时，可以这样构造：中间一个点，点的两边分别和两个环通过两条边进行连接。

最小的环其实就是一条边。因此构造方案就是：(1,2) 连接一条边。[4,n]构成一个环。3 作为中间点，和上面每个环分别连接两条边。

Problem E. 奶龙与奥利奥自动机

组合数学题目。

设 $num_k$ 代表使用 $k$ 次操作，能够产生的非空字符串的数量。 $a_k$ 代表使用 $k$ 次操作，产生的非空字符串中，结尾是 0 的字符串的数量。 $b_k$ 代表使用 $k$ 次操作，产生的非空字符串中，结尾是 $1$ 的字符串的数量。 $c_k$ 代表使用 $k$ 次操作，产生的非空字符串中，结尾是 $01$ 的字符串的数量。

我们有这样的递推关系： $num_k = a_k + b_k + c_k$ ， $a_k = c_k = num_{k - 1}$ ， $b_k = b_{k - 1} + c_{k - 1}$

根据上面的关系，可以得到 $num_k = 3num_{k - 1} - num_{k - 2}$

答案就是 $\sum_{k = 0}^{n} num_{k}$

初始状态下， $num_0 = 1$ ， $num_1 = 3$ 。其中 $num_0 = 1$ 代表的含义其实是空字符串，0 次操作只有一种情况，把它作为特殊情况处理。

void solve() {
  int n;
  cin >> n;
  ll ans = 0;
  ll a = 1, b = 3;
  ans += a + b;

  For1(i, 2, n) {
    ll c = (3 * b - a + MOD1) % MOD1;
    a = b;
    b = c;
    ans = (ans + b) % MOD1;
  }
  cout << ans << '\n';
}

Problem F. 奶龙智斗暴暴龙

猜到采用极端分配的方式比较优。

在桶 A 中放置 1 个白球，在桶 B 中放置 $n-1$ 个白球和 $n$ 个黑球。此时如果选择桶 A，那么取到白球的概率是 1. 如果选择桶 B，那么取到白球的概率是 $\frac{n-1}{2n-1}$

最终答案是 $\frac{3n-2}{4n-2}$

Problem G. 小红的抛物线

把三个点按照横坐标排序，设三个点是 $a, b, c$ ，从 $b$ 做 $x$ 轴的垂线，交线段 $a, c$ 于点 $d$ ，判断点 $d$ 和点 $b$ 的 Y 坐标的大小即可。

Problem H. 小苯的序列染色

每个点可能向左扩展，也可能向右扩展，也就是每个点最多对应 2 个区间。一共有 $2n$ 个区间。问题转化成从这些区间中选出最少的区间，使得这些区间能够覆盖 $[1, n]$

这可以贪心：先按照区间的左端点从小到大排序。维护当前能够覆盖的最远距离 cur_end，如果当前区间的左端点 l <= cur_end + 1, 说明当前区间能够接上之前一段。那么从能够接上的这些区间中，选择一个右端点 $r$ 最大的。如果找不到能够接上的区间，直接返回无解。

void solve() {
  int n;
  cin >> n;

  VI a(n + 1);
  For1(i, 1, n) cin >> a[i];

  vector<PII> b;
  For1(i, 1, n) {
    int l = i - a[i] + 1, r = i + a[i] - 1;
    if (l >= 1 && l <= n && a[i] >= a[l]) {
      b.push_back({l, i});
    }
    if (r <= n && a[i] >= a[r]) {
      b.push_back({i, r});
    }
  }
  sort(all(b), [&](PII x, PII y) {
    if (x.f1 != y.f1)
      return x.f1 < y.f1;
    return x.f2 > y.f2;
  });

  if (b.empty()) {
    cout << "-1\n";
    return;
  }

  int cur_end = 0, len = SZ(b), ans = 0, nx_end = 0;
  int i = 0;
  while (cur_end < n) {
    while (i < len && b[i].f1 <= cur_end + 1) {
      ckmax(nx_end, b[i].f2);
      i++;
    }

    if (nx_end == cur_end) {
      cout << "-1\n";
      return;
    }
    ans++;
    cur_end = nx_end;
  }
  if (cur_end == n)
    cout << ans << '\n';
  else
    cout << "-1\n";
}

Problem I. 小苯的字符串构造

题目意思比较难懂。

其实就是要求长度是奇数的子字符串，出现次数都是奇数。对偶数长度的字符串没有要求。

模拟几个样例发现，如果 $n$ 是奇数，那么我们可以构造全部是 $a$ 的字符串。这恰好符合要求。如果 $n$ 是偶数，我们只需要添加一个字符 $b$ 即可。

Problem J. 小苯的运算式

设状态 $d_{i, 0}$ 表示只考虑前 $i$ 个元素，最后一个数字的符号是负号的最大值。状态 $d_{i, 1}$ 表示只考虑前 $i$ 个元素，最后一个数字的符号是正号的最大值。这是一个线性 DP

Problem K. 小苯的闯关游戏

注意到如果初始战力越大，到最后越容易满足条件。也就是有单调的性质，因此我们可以对答案二分。

Problem L. 小苯的序列还原

考虑最后一次操作，我们可以直接确定答案数组的最后一个位置 $b_n$ ，它的位置再也不会发生改变了。

根据这个想法，我们可以依次确定 $b_{n - 1}, b_{n - 2}, \ldots$

我们只需要维护当前需要考虑的区间 $[l, r]$ 和当前的翻转次数是奇数还是偶数。

Problem M. GPA Calculator

模拟。