A - Penalty Kick
Question
高桥将在一场足球比赛中获得 \(N\) 个点球。
对于第 \(i\) 个罚球，如果 \(i\) 是 \(3\) 的倍数，他将罚球失败，否则罚球成功。
请打印他罚球的结果。
Solution
当 \(i \% 3 == 0\) 时说明能被 \(3\) 整除
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++)
if (i % 3 == 0)
putchar('x');
else
putchar('o');
return 0;
}
B - Farthest Point
Question
在 \(xy\) (平面)上有 \(N\) 个点，其 ID 编号从 \(1\) 到 \(N\) 。点 \(i\) 位于坐标 \((X_i, Y_i)\) 处，没有两个点的坐标相同。
从每个点出发，找出最远的点并打印其 ID 编号。如果多个点都是最远点，则打印这些点中最小的 ID 号。
这里我们使用欧氏距离：对于两个点 \((x_1,y_1)\) 和 \((x_2,y_2)\) ，它们之间的距离是 \(\sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}}\)
Solution
发现 \(n\) 很小
可以暴力枚举每个 \(i\) ，求出与 \(i\) 的欧几里得距离最大的 \(j\)，并输出
注意使用 sqrt() 会产生精度问题，建议不开平方比较
Code
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
int n; cin >> n;
vector<pii> a(n);
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
for (int i = 0; i < n; i++) {
auto dist = [&](pii a, pii b) {
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
};
int idx = -1;
int max_x = -1;
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (max_x < dist(a[i], a[j])) {
max_x = dist(a[i], a[j]);
idx = j;
}
}
cout << idx + 1 << '\n';
}
return 0;
}
C - Colorful Beans
Question
豆子有 \(N\) 个，其中 \(i\) 个豆子的美味度为 \(A_i\) ，颜色为 \(C_i\) 。豆子是混合的，只能通过颜色来区分。
您将选择一种颜色的豆子，并吃一颗这种颜色的豆子。
通过选择最佳颜色，最大限度地减少所吃豆子的美味度。
Solution
利用 map<int,int> 记录每种颜色的种子的美味度的最小值
最后遍历 map，找到最大的美味度最小值
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
map<int, int> p;
for (int i = 0; i < n; i++) {
int A, C; cin >> A >> C;
if (!p.count(C)) p[C] = A;
else p[C] = min(p[C], A);
}
int ans = 0;
for (auto [a, c] : p) ans = max(ans, c);
cout << ans << '\n';
return 0;
}
D - Medicines on Grid
Question
有一个网格，网格中有 \(H\) 行和 \(W\) 列。让 \((i, j)\) 表示从上往下第 \(i\) 行，从左往上第 \(j\) 列的单元格。每个单元格的状态由字符 \(A_{i,j}\) 表示，其含义如下：
.: 空单元格。#: 一个障碍物。S: 空单元格和起点。T: 空单元格和目标点。
高桥可以通过消耗 \(1\) 能量从当前单元格移动到垂直或水平相邻的空单元格。如果能量为 \(0\) ，则无法移动，也无法离开网格
网格中有 \(N\) 种药物。 \(i\) -th药品位于空格 \((R_i, C_i)\) ，可以用来将能量设置为 \(E_i\) 。注意，能量并不一定会增加。他可以在当前格子中使用药物。用过的药会消失
高桥以 \(0\) 的能量从起点开始，并希望到达目标点。请判断这是否可行
Solution
考虑按照药物作为点建新图，如果一个药物 \(i\) 能在 \(E_i\) 步内走到 \(j\)，则建一条 \(i\Rightarrow j\) 的边
然后在新图上跑 bfs 查看起始点和终点是否能走到
Code
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int inf = 1e9;
const int flg[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct Node {
pii pos; int val;
};
int main() {
int H, W; cin >> H >> W;
pii st, ed;
vector<vector<char> > mp(H + 2, vector<char>(W + 2, '#'));
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
cin >> mp[i][j];
if (mp[i][j] == 'S') st = {i, j};
if (mp[i][j] == 'T') ed = {i, j};
}
}
int N, id_s = 0; cin >> N;
vector<Node> a(N + 2);
for (int i = 1; i <= N; i++) {
cin >> a[i].pos.first >> a[i].pos.second >> a[i].val;
if (a[i].pos == st) id_s = i;
}
a[N + 1].pos = ed; a[N + 1].val = 0;
vector<vector<int> > g(N + 2,vector<int>());
for (int i = 1; i <= N; i++) {
auto bfs = [&] (pii s) {
vector<vector<int> > dis (H + 2, vector<int>(W + 2, -1));
queue<pii> q;
q.push(s);
dis[s.first][s.second] = 0;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + flg[k][0], ny = y + flg[k][1];
if (mp[nx][ny] == '#' || dis[nx][ny] != -1) continue;
dis[nx][ny] = dis[x][y] + 1;
q.push({nx, ny});
}
}
return dis;
};
auto dis = bfs(a[i].pos);
for (int j = 1; j <= N + 1; j++) {
if (i == j) continue;
auto [x, y] = a[j].pos;
if (dis[x][y] != -1 && dis[x][y] <= a[i].val)
g[i].push_back(j);
}
}
if (id_s == 0) return cout << "No" << '\n', 0;
vector<int> dis(N + 2, -1);
queue<int> q; q.push(id_s); dis[id_s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v : g[u]) {
if (dis[v] != -1) continue;
dis[v] = dis[u] + 1;
q.push(v);
if (v == N + 1) return cout << "Yes" << '\n', 0;
}
}
return cout << "No" << '\n', 0;
}
E - Minimize Sum of Distances
Question
给你一棵有 \(N\) 个顶点的树。顶点编号为 \(1\) 到 \(N\) ， \(i\) -th 边连接顶点 \(A_i\) 和 \(B_i\) 。
我们还给出了一个长度为 \(N\) 的正整数序列 \(C = (C_1, C_2, \ldots ,C_N)\) 。设 \(d(a, b)\) 是顶点 \(a\) 和 \(b\) 之间的边数，而对于 \(x = 1, 2, \ldots, N\) , 设为 \(\displaystyle f(x) = \sum_{i=1}^{N} (C_i \times d(x, i))\) 。求 \(\displaystyle \min_{1 \leq v \leq N} f(v)\)
Solution
非常显然的换根 DP
先第一次求出 \(f(root)\) 考虑从根节点向下遍历
假设已经知道了一个节点 \(f(u)\)，求 \(u\) 的一个儿子 \(v\)
那么 \(f(v)=f(u)-\sum\limits_{i\in S} C_i+\sum\limits_{i\notin S} C_i\)
其中 \(S\) 为 \(v\) 的后代节点
\(\sum\limits_{i\in S} C_i\) 和 \(\sum\limits_{i\notin S} C_i\) 可以预处理得出，所以转移的时间复杂度是 \(O(1)\) 的
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
int main() {
int N; cin >> N;
vector<vector<int> > g(N + 1, vector<int>());
vector<ll> c(N + 1); ll c_sum = 0;
for (int i = 1; i < N; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
cin >> c[i]; c_sum += c[i];
}
vector<ll> dp(N + 1, 0);
vector<ll> sz(N + 1, 0), dis(N + 1, 0);
function<void(int, int)> dfs_1 = [&] (int u, int fa) {
sz[u] = c[u];
for (auto v : g[u]) {
if (v == fa) continue;
dis[v] = dis[u] + 1;
dfs_1(v, u);
sz[u] += sz[v];
}
};
dfs_1(1, 0);
for (int i = 1; i <= N; i++)
dp[1] += c[i] * dis[i];
function<void(int, int)> dfs_2 = [&] (int u, int fa) {
for (auto v : g[u]) {
if (v == fa) continue;
dp[v] = dp[u] - sz[v] + (c_sum - sz[v]);
dfs_2(v, u);
}
};
dfs_2(1, 0);
ll ans = *min_element(dp.begin() + 1, dp.end());
cout << ans << '\n';
return 0;
}
F - Oddly Similar
Question
有长度为 \(M\) 的 \(N\) 个序列，表示为 \(A_1, A_2, \ldots, A_N\) 。长度为 \(i\) 的序列由 \(M\) 个整数 \(A_{i,1}, A_{i,2}, \ldots, A_{i,M}\) 表示。
长度为 \(M\) 的两个序列 \(X\) 和 \(Y\) 如果且仅当 \(X_i = Y_i\) 的索引 \(i (1 \leq i \leq M)\) 的个数为奇数时，才说这两个序列相似。
求满足 \(1 \leq i < j \leq N\) 且 \(A_i\) 和 \(A_j\) 相似的整数对 \((i,j)\) 的个数。
Solution
听说这题直接暴力 + O3 优化就能跑过，atcoder 真是神机
我介绍一种 bitset 的做法
定义 vector<bitset<2001> > p(n + 1) 如果 \(p[i][j]=1\) 说明第 \(i\) 行和第 \(j\) 行是相似的
所以对于每一列，我们可以利用 bitset 的异或操作快速处理出每行之间的关系
具体实现就是对于一列，求出这一列中相同数字的行号，放在一个 vector<int> 中，对于 vector<int> 的每个位置，我们都把对应位置的 bitset 都标记为 \(1\)，最后对于 vector<int> 中的每个数，利用 p[k] ^= now 来更新 \(p[k]\)
Code
#include <bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int main() {
freopen ("F.in", "r", stdin);
int n, m; n = read(); m = read();
vector<vector<int> > a(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = read();
vector<bitset<2001> > p(n + 1);
vector<vector<int> > vc(1000 , vector<int>());
for (int i = 1; i <= m; i++) {
for (auto &x : vc) x.clear();
for (int j = 1; j <= n; j++)
vc[a[j][i]].push_back(j);
for (auto &x : vc) if (x.size() > 0) {
bitset<2001> now(0);
for (auto &k : x) now[k] = 1;
for (auto &k : x) p[k] ^= now;
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
ans += p[i][j];
cout << ans << '\n';
return 0;
}