GDCPC2023 B , D , F , K 题解

和队友一起打的 2023 年广东省大学生程序设计竞赛重现赛，写了 B, D, K，胡了一个 F。

D

题目大意

随着广东的建设与发展，越来越多人选择来到广东开始新生活。在一片新建的小区，有 \(n\) 个人要搬进 \(m\) 栋排成一行的房子，房子的编号从 \(1\) 到 \(m\)（含两端）。房子 \(u\) 和 \(v\) 相邻，当且仅当 \(|u-v|=1\)。我们需要为每一个人安排一栋房子，要求所有人入住的房子互不相同。若两个人住进了一对相邻的房子，则这两个人互为邻居。

有的人喜欢自己有邻居，而有的人不喜欢。对于第 \(i\) 个人，如果他有至少一位邻居，则他的满意度为 \(a_i\)；否则如果他没有邻居，则他的满意度为 \(b_i\)。

您作为小区的规划者，需要最大化所有人的总满意度。

题解。

可以发现最优解一定是：

AAA.B.B.B

或者：

B.B.B.B.B.B

或：

AAAAAA

其中 A 和 B 分别表示有邻居的人和没有邻居的人。

让我们贪心地想，这里面的 A 一定是那些 \(b_i - a_i\) 最小的人，因为如果将 \(b_i - a_i\) 较大的人排为 A，把他放到 B 中对答案的贡献显然更大。

所以按照 \(b_i - a_i\) 从小到大排序，再枚举 \(i\) ( \(2\leqslant i\leqslant n - 1\) )，把 \(1 \sim i\) 当成有邻居的，\(i + 1 \sim n\) 当作没有邻居的，对这些情况取 \(\max\) 即可。

最后还要特判全是 A 和全是 B 的情况。

code:

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;
int n, m;
struct node {
  int a, b;
  inline bool operator < (const node &w) const {
    return (b - a) < (w.b - w.a);
  }
} a[N];

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i].a >> a[i].b;
  sort(a + 1, a + 1 + n);
  vector <long long> pre(n + 1, 0), suf(n + 2, 0);
  for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i].a;
  for (int i = n; i; --i) suf[i] = suf[i + 1] + a[i].b;
  long long ans = 0;
  for (int i = 0; i <= n; ++i) {
    if (i == 1) continue;
    int need = i + (n - i) * 2 - (!i);
    if (need <= m) ans = max(ans, pre[i] + suf[i + 1]);
  } cout << ans << '\n';
}

signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  int T; cin >> T; while (T--) solve();
}

K

题目大意

独立钻石是一种单人桌游。游戏在 \(n\) 行 \(m\) 列的棋盘上进行，棋盘上的每一格要么是空格，要么有一枚棋子。一开始，棋盘上共有 \(k\) 枚棋子。

在游戏中，玩家可以选择一枚棋子，将它跳过相邻棋子到空格上，并移除被跳过的棋子。具体来说，令 \((i, j)\) 表示位于第 \(i\) 行第 \(j\) 列的格子，玩家可以执行以下四种操作。

给定一个初始的棋盘，求经过任意次操作（包括零次）之后，棋盘上最少能剩余几枚棋子。

题解

由于 \(n, m, k\leqslant 6\)，可以不用剪枝，直接搜索。

细节具体请看代码实现。

code:

#include <bits/stdc++.h>

using namespace std;

const int N = 7;

int n, m, k;
int a[N][N]; //a[i][j] 表示 (i, j) 的信息，如果为 0 表示这个格子为空，否则表示这个格子上有哪个棋子。
bool vis[N]; //vis[i] 表示第 i 个棋子是否被选过。

struct node {
  int x, y;
  node (int xx, int yy) {x = xx, y = yy;}
} ; //记录棋子坐标
vector <node> v;

int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
int ans = 0;

void dfs(int cnt) {
  ans = min(ans, cnt);
  for (int i = 0; i < k; ++i) if (!vis[i]) {
    for (int j = 0; j < 4; ++j) {
      int nx = v[i].x + dx[j], ny = v[i].y + dy[j];
      if (nx && ny && nx <= n && ny <= m && a[nx][ny] != 0) { 
        int tx = nx + dx[j], ty = ny + dy[j];
        if (tx && ty && tx <= n && ty <= m && a[tx][ty] == 0) {
          a[tx][ty] = i + 1; a[v[i].x][v[i].y] = 0;
          vis[a[nx][ny] - 1] = 1; 
          int nt = a[nx][ny]; a[nx][ny] = 0; 
          swap(v[i].x, tx); swap(v[i].y, ty); 
          dfs(cnt - 1);
          swap(v[i].x, tx); swap(v[i].y, ty);
          a[tx][ty] = 0; a[v[i].x][v[i].y] = i + 1;
          a[nx][ny] = nt; vis[i] = vis[a[nx][ny] - 1] = 0; //记得还原信息。
        }
      }
    }
  }
}

signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  int T; cin >> T; while (T--) {
    cin >> n >> m >> k; ans = k;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
      a[i][j] = 0; //多测要清空
    v.clear(); for (int i = 1; i <= k; ++i) {
      int x, y; cin >> x >> y;
      v.emplace_back(node(x, y));
      a[x][y] = i; vis[i - 1] = 0;
    } dfs(k); cout << ans << '\n';
  }
}