A - Equally
题意：给你三个数，判断能不能分成大于一组后每组和相等。
只可能分成两个和一个或者三组一个的。
点击查看代码
void solve() {
int a, b, c;
std::cin >> a >> b >> c;
if ((a == b && b == c) || (a + b == c) || (b + c) == a || (a + c) == b) {
std::cout << "Yes\n";
} else {
std::cout << "No\n";
}
}
B - Santa Claus 1
题意：在一个有空地房屋障碍的矩阵上模拟行走，判断终点以及经过了几个房屋。
直接模拟记录去过哪些格子就行。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
int x, y;
std::cin >> x >> y;
-- x, -- y;
std::vector<std::string> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::vector st(n, std::vector<int>(m));
st[x][y] = 1;
std::string t;
std::cin >> t;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
for (auto & c : t) {
int d = 0;
if (c == 'R') {
d = 1;
} else if (c == 'D') {
d = 2;
} else if (c == 'L') {
d = 3;
}
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == '#') {
continue;
}
x = nx; y = ny;
st[x][y] = 1;
}
std::cout << x + 1 << " " << y + 1 << " ";
int ans = 0;
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
if (a[i][j] == '@' && st[i][j]) {
++ ans;
}
}
}
std::cout << ans << "\n";
}
C - Illuminate Buildings
题意：有n个数，你要选一些数使得他们位置间隔相等，求能选多少个数。
直接dp，f[i][j] 表示第i个与前面间隔为j时最多选几个。如果\(a_{i - j}\) = \(a_i\)那么可以由f[i - j][j]转移过来，除此之外，注意前面数的前面没有选数的情况，这种情况是f[i - j][0]。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
int ans = 0;
std::vector f(n, std::vector<int>(n));
for (int i = 0; i < n; ++ i) {
for (int j = 0; j <= i; ++ j) {
if (a[i] == a[i - j]) {
f[i][j] = std::max({f[i][j], f[i - j][j] + 1, f[i - j][0] + 1});
}
ans = std::max(ans, f[i][j]);
}
}
std::cout << ans << "\n";
}
D - Santa Claus 2
题意：跟b题差不多，只不过没有障碍，并且地图很大，每次移动的距离也是给定的。
用两个map存每个x坐标上房屋的y坐标，y坐标上的每个x坐标，然后每次移动，有一个坐标是不变的，那么他的另一个坐标这次覆盖了[a, b]这个范围，存下来，最后给每个map里的坐标存的数组找一下每次移动经过的是哪个到哪个，差分一下看哪些是经过的，然后用map记答案。
点击查看代码
void solve() {
i64 n, m, x, y;
std::cin >> n >> m >> x >> y;
std::map<i64, std::vector<i64> > X, Y;
for (int i = 0; i < n; ++ i) {
i64 x, y;
std::cin >> x >> y;
X[x].push_back(y);
Y[y].push_back(x);
}
for (auto & it : X) {
std::sort(it.second.begin(), it.second.end());
}
for (auto & it : Y) {
std::sort(it.second.begin(), it.second.end());
}
std::map<i64, std::vector<std::pair<i64, i64> > > opX, opY;
while (m -- ) {
std::string s;
i64 d;
std::cin >> s >> d;
i64 nx = x, ny = y;
if (s == "U") {
ny += d;
if (X.count(x)) {
opX[x].push_back({y, ny});
}
} else if (s == "D") {
ny -= d;
if (X.count(x)) {
opX[x].push_back({ny, y});
}
} else if (s == "R") {
nx += d;
if (Y.count(y)) {
opY[y].push_back({x, nx});
}
} else {
nx -= d;
if (Y.count(y)) {
opY[y].push_back({nx, x});
}
}
x = nx, y = ny;
// std::cout << x << " " << y << "\n";
}
std::set<std::pair<i64, i64> > ans;
for (auto & [x, it] : opX) {
int k = X[x].size();
std::vector<int> d(k + 2);
for (auto & [l, r] : it) {
l = std::lower_bound(X[x].begin(), X[x].end(), l) - X[x].begin() + 1;
r = std::upper_bound(X[x].begin(), X[x].end(), r) - X[x].begin() - 1 + 1;
d[l] += 1;
d[r + 1] -= 1;
}
for (int i = 1; i <= k; ++ i) {
d[i] += d[i - 1];
if (d[i] > 0) {
ans.insert({x, X[x][i - 1]});
}
}
}
for (auto & [y, it] : opY) {
int k = Y[y].size();
std::vector<int> d(k + 2);
for (auto & [l, r] : it) {
l = std::lower_bound(Y[y].begin(), Y[y].end(), l) - Y[y].begin() + 1;
r = std::upper_bound(Y[y].begin(), Y[y].end(), r) - Y[y].begin() - 1 + 1;
d[l] += 1;
d[r + 1] -= 1;
}
for (int i = 1; i <= k; ++ i) {
d[i] += d[i - 1];
if (d[i] > 0) {
ans.insert({Y[y][i - 1], y});
}
}
}
std::cout << x << " " << y << " " << ans.size() << "\n";
}
E - Snowflake Tree
题意：一颗雪花树定义为一个点有x个子节点，每个子节点有y个子节点。 给你一棵树，问最少删几个点变成雪花树。
这题一眼了，我们在这个树的点里选一些点构成雪花树，其他点都删了，记录要删最少的点情况。
直接枚举每个点，然后把他的相邻点的度数减一加到一个数组（因为要除去枚举的这个点），加完后这个数组排个序，从小到大枚举，那么当前枚举的这个点到后面的点都至少有当前这个点的度数，就可以构成一棵1+剩下点*度数+剩下点的雪花树，n减去这些点就是要删的点。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<std::vector<int> > adj(n);
for (int i = 1; i < n; ++ i) {
int u, v;
std::cin >> u >> v;
-- u, -- v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int ans = n;
for (int u = 0; u < n; ++ u) {
std::vector<int> a;
for (auto & v : adj[u]) {
if ((int)adj[v].size() - 1 > 0) {
a.push_back((int)adj[v].size() - 1);
}
}
std::sort(a.begin(), a.end());
int max = 0;
for (int i = 0; i < a.size(); ++ i) {
max = std::max(max, ((int)a.size() - i) * a[i] + (int)a.size() - i + 1);
}
ans = std::min(ans, n - max);
}
std::cout << ans << "\n";
}
F - Visible Buildings
这题看了一二十分钟没思路，然后正好高中同学想着寒假了叫我聚个餐，于是就润了。之后再补吧。
待补