2023 ICPC 拉丁美洲区域赛

D. Daily Trips

题目描述

Bella 乘坐公交车上下班，她所在的城市经常下雨，所以有时她需要一把雨伞。

她拥有一把或多把雨伞，放在家里或工作场所。每次出行前(从家里到工作地点，或从工作地点到家里)， Bella 都会先看看外面的天气，然后决定是否带伞出行：

• 如果下雨，她就带伞；
• 否则，如果目的地(公司或家)目前没有雨伞，她还是会带伞，以防万一；
• 否则，她就不带伞。

现在我们需要你在一段时间内模拟 Bella 的方法。模拟从 Bella 在家开始。每天她要乘两趟公交车：上班和下班。给定 Bella 家和工作地点雨伞的起始数量，以及连续 \(N\) 天的天气预报，求 Bella 在 \(2 N\) 次公交车旅行中是否每次都带了雨伞。

输入

第一行，包含三个整数 \(N\) ( \(1 \leq N \leq 10^4\) )、 \(H\) ( \(1 \leq H \leq 100\) )和 \(W\) ( \(0 \leq W \leq 100\) )，分别表示模拟期间的天数以及 Bella 家和工作地点的雨伞起始数。

对于 \({i}={1}, {2}, \ldots, {N}\) ，接下来 \(N\) 行中的 \(i\) (-th)包含两个字符，分别代表 \(i\) (-th)天的每次出行是否下雨。第一个字符指的是一天中的第一个行程(从家到公司)，第二个字符指的是一天中的第二个行程(从公司到家)。如果下雨，每个字符都是大写字母 "Y"，否则就是大写字母 "N"。

输出

输出 \(N\) 行。对于 \({i}={1}, {2}, \ldots, {N}\) ， \(i\) /th行必须包含两个字符，表示 Bella 在 \(i\) /th天的每次旅行中是否都带了雨伞。第一个字符表示第一次出行，第二个字符表示第二次出行。如果 Bella 带了雨伞，每个字符都必须是大写字母 "Y"，否则就是大写字母 "N"。

---

题解

简单的模拟题，按照题目描述模拟即可。

AC 代码

#include <bits/stdc++.h>
using namespace std;

signed main() {
  int n, a, b;
  cin >> n >> a >> b;
  for (int i = 0; i < n; i++) {
    char x, y;
    cin >> x >> y;
    if (x == 'Y' || b == 0) {
      cout << 'Y';
      a--, b++;
    } else {
      cout << 'N';
    }
    cout << ' ';
    if (y == 'Y' || a == 0) {
      cout << 'Y';
      a++, b--;
    } else {
      cout << 'N';
    }
    cout << '\n';
  }
}

---

E. Empty Squares

题目描述

马特恩的棋盘上有 \(1\times N\) 个方格。他还有 \(N\) 块 \(1\times 1, 1\times 2, \ldots, 1\times N\) 格的棋子，每种类型各一块。他已经在棋盘上放置了其中一个棋子。他的朋友尼科想把剩下的一些图块尽可能多地覆盖在棋盘上。如果他成功了，还有多少个方格是空的？

放置在棋盘上的图块不能相互重叠。此外，每块放置的瓷砖必须完全位于棋盘内，并且必须覆盖整个方格。

输入

输入由一行组成，包含三个整数 \(N\) ( \(1\leq N\leq 1000\) ), \(K\) ( \(1\leq K\leq N\) ) 和 \(E\) ( \(0\leq E\leq N-K\) )( \(0\leq E\leq N-K\) ) 表示棋盘上有 \(1\times N\) 个方格，并放置了 \(1\times K\) 个方格的棋子，在其左边留下了 \(E\) 个空格。

输出

输出一行整数，表示如果尼科用剩余的瓷砖尽可能多地覆盖空方格，空方格的数量。

---

题解

固定一块瓷砖后，左边剩余格子和右边剩余格子的数量是固定的，记为 \(n_1\) 和 \(n_2\)。

考虑 dp 如下：

• \(dp[i][j][k]\) 表示使用前 i 块瓷砖，左边剩余 j 个格子，右边剩余 k 个格子的方案是否存在
• 转移方程：\(dp[i][j][k] = dp[i-1][j][k] | dp[i-1][j-i][k] | dp[i-1][j][k-i]\)
• 边界条件：\(dp[0][n_1][n_2] = 1\)

可以使用类似 01 背包的空间优化，按照特定顺序和更新状态，可以减少一维空间。

算法理论上复杂度是 \(O(N^3)\)，但是这实际上是一个很松散的上界：dp 的状态转移中，至多有 $ n_1 \times n_2 $ 个状态是有意义的，并且在转移的过程中，只需要考虑长度小于等于 \(\max(n_1, n_2)\) 的瓷砖，因此一个更加精确的复杂度是 \(O(n_1 \times n_2 \times \max(n_1, n_2))， n_1 + n_2 \leq N\)，可以通过本题（\(N \leq 1000\)）。

AC 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;

bool dp[N][N];

signed main() {
  int n, k, e;
  cin >> n >> k >> e;
  int n1 = e, n2 = n - e - k;

  dp[n1][n2] = true;

  for (int t = 1; t <= max(n1, n2); t++) {          
    if (t == k) continue;
    for (int i = 0; i <= n1; i++) {
      for (int j = 0; j <= n2; j++) {
        if (i + t <= n1) {
          dp[i][j] |= dp[i + t][j];
        }
        if (j + t <= n2) {
          dp[i][j] |= dp[i][j + t];
        }
      }
    }
  }

  for (int ans = 0; ans <= n; ans++) {
    for (int i = 0; i <= ans; i++) {
      if (dp[i][ans - i]) {
        cout << ans << '\n';
        return 0;
      }
    }
  }
}

---