和队友一起打的 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';
}
}