题目：2021 Round-A .
K-Goodness String签到题，计算当前字符串的 K-Goodness Score ，然后与给出的 K 做差即可。
#include <iostream> #include <string> using namespace std; int cnt = 1; int solve(const string &s, int n, int k) { int cur = 0; for (int i = 0; i < n / 2; i++) cur += s[i] != (s[n - i - 1]); return abs(k - cur); } int main() { int t, n, k; string str; cin >> t; while (t--) { cin >> n >> k; cin.ignore(); cin >> str; cin.ignore(); printf("Case #%d: %d\n", cnt++, solve(str, n, k)); } } L Shaped PlotsL 字要求长边的长度是短边的 2 倍。短边长度至少为 2 ，长边长度至少为 4 。
枚举每个 matrix[i, j] == 1 的点（把该位置视为 L 的拐点）求出其上下左右四个方向的 1 的长度，通过 {up, down, left, right} 4 个变量记录。
然后对于 4 个方向，把该方向作为短边尝试一次，计算以该方向作为短边的 L 的个数。
以下面输入为例子：
1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0在位置 (2, 2) 上，其 4 个方向的 1 的长度为 {up=1, down=4, left=3, right=1} ，那么：
up = 1 ，该方向不能为短边。
down = 4 ，以该方向为短边时，那么长边必然是 left 或者 right 。 在 down 方向上，短边长度可以为 2, 3, 4, 但 left, right 作为长边均不满「长边长度至少 4 的要求」。
left = 3 ，以该方向作为短边，短边长度可以为 2 或者 3，当为 2 时，可以与 down 组成 1 个 L 字。
right = 2 ，以该方向作为短边，长度为 2 ，可以与 down 组成 1 个 L 字。
因此在位置 (2, 2) 上共有 2 个 L 字。
时间复杂度 \(O(n^3)\) .
#include <iostream> #include <vector> #include <array> using namespace std; #define MAXN 1001 int nums[MAXN][MAXN] = {{0}}; int cnt = 1; int rows, cols; array<int, 4> getFourLength(int i, int j) { int up, down, left, right; up = down = i, left = right = j; while (up >= 0 && nums[up][j]) up--; while (down < rows && nums[down][j]) down++; while (left >= 0 && nums[i][left]) left--; while (right < cols && nums[i][right]) right++; return array<int, 4>({i - up, down - i, j - left, right - j}); } int solve() { int ans = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (nums[i][j] == 0) continue; auto [up, down, left, right] = getFourLength(i, j); auto calc = [&ans](int shortedge, int longedge1, int longedge2) { for (int d = 2; d <= shortedge; d++) ans += (longedge1 >= 2*d), ans += (longedge2 >= 2*d); }; calc(up, left, right), calc(down, left, right); calc(left, up, down), calc(right, up, down); } } return ans; } int main() { int t; cin >> t; while (t--) { cin >> rows >> cols; for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) cin >> nums[i][j]; printf("Case #%d: %d\n", cnt++, solve()); } } Rabbit House题目的意思就是说，每个「极高点」（盗用了函数中的极值点的概念），其周围 4 个方向的点都必须与它等高，或者比它高度小 1。
如果只有一个最高点，那么是很简单的（一次 BFS 即可完成），但这里可能会出现多个最高点。
这里我们采用堆思想，从堆顶得到最高点，观察其 4 个相邻点的高度，判断是否需要填充高度。若需要，那么更新这个相邻点的高度（同时记录增加了多少高度），并把这个相邻点也放入堆中。
代码实现用了 set 取替代堆了，反正我们只要能在 \(O(1)\) 时间内得到最高点即可。
时间复杂度 \(O(n\log{n}), n=rc\) .
#include <iostream> #include <vector> #include <set> using namespace std; #define N 301 int t, rows, cols; int graph[N][N] = {{0}}; struct node_t { int x, y, height; node_t(int xx = -1, int yy = -1, int hh = 0) : x(xx), y(yy), height(hh) {} bool operator<(const node_t &n) const { return height > n.height || (height == n.height && (x < n.x || (x == n.x && y < n.y))); } }; uint64_t solve(set<node_t> &s) { uint64_t ans = 0; static const vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; while (!s.empty()) { auto [x, y, height] = *s.begin(); s.erase(s.begin()); for (auto &d : dirs) { int dx = x + d.first, dy = y + d.second; if (dx < 0 || dx >= rows || dy < 0 || dy >= cols) continue; if (graph[dx][dy] <= height - 2) { ans += height - 1 - graph[dx][dy]; s.erase(node_t(dx, dy, graph[dx][dy])); graph[dx][dy] = height - 1; s.emplace(dx, dy, graph[dx][dy]); } } } return ans; } int main() { cin >> t; for (int k = 1; k <= t; k++) { cin >> rows >> cols; set<node_t> s; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { cin >> graph[i][j]; s.emplace(i, j, graph[i][j]); } } printf("Case #%d: %llu\n", k, solve(s)); } } Checksum一个重要结论：如果某行/某列，只有一个元素被损坏，那么是可以通过该行/该列的校验和进行还原的，这种情况下不需要任何的 cost .
我们把每行，每列都看作一个点，如果位置 (i, j) 为 -1 ，那么就把 row[i] 和 col[j] 连接起来，这样会得到一个二分图。