A. flip
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s;
std::cin >> s;
for (auto &si : s) {
si = '1' - si + '0';
}
std::cout << s << '\n';
return 0;
}
B. V
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < m; i++) {
int x;
std::cin >> x;
x--;
a[x] = 1;
}
int j = 0;
for (int i = 0; i < n; i = j + 1) {
j = i;
while (j < n && a[j]) {
j++;
}
for (int k = j; k >= i; k--) {
std::cout << k + 1 << ' ';
}
}
std::cout << '\n';
return 0;
}
C. Coverage
枚举子集。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> a(m);
for (int i = 0; i < m; i++) {
int ci;
std::cin >> ci;
for (int j = 0; j < ci; j++) {
int x;
std::cin >> x;
x--;
a[i] |= 1 << x;
}
}
int ans = 0;
for (int j = 0; j < (1 << m); j++) {
int res = 0;
for (int i = 0; i < m; i++) {
if (j >> i & 1) {
res |= a[i];
}
}
if (res == (1 << n) - 1) {
ans++;
}
}
std::cout << ans << '\n';
return 0;
}
D. Step Up Robot
bfs。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1E5;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
int m;
std::cin >> m;
std::vector<int> b(m);
for (int i = 0; i < m; i++) {
std::cin >> b[i];
}
int x;
std::cin >> x;
std::vector<bool> ban(N + 1);
for (int i = 0; i < m; i++) {
ban[b[i]] = 1;
}
std::vector<bool> vis(N + 1);
std::queue<int> q;
q.push(0);
vis[0] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == x) {
std::cout << "Yes\n";
return 0;
}
for (int i = 0; i < n; i++) {
int nex = cur + a[i];
if (nex <= x && !vis[nex] && !ban[nex]) {
q.push(nex);
vis[nex] = 1;
}
}
}
std::cout << "No\n";
return 0;
}
E. Swap Places
模拟。\(ans_{ij}\) 表示 Takahashi 在 \(i+1\)，Aoki 在 \(j+1\)。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> c(n);
for (int i = 0; i < n; i++) {
std::cin >> c[i];
}
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::vector<std::vector<int>> ans(n, std::vector<int>(n, -1));
std::queue<std::array<int, 2>> q;
q.push({0, n - 1});
ans[0][n - 1] = 0;
while (!q.empty()) {
auto [x1, y1] = q.front();
q.pop();
for (auto x2 : adj[x1]) {
for (auto y2 : adj[y1]) {
if (c[x2] != c[y2] && ans[x2][y2] == -1) {
ans[x2][y2] = ans[x1][y1] + 1;
q.push({x2, y2});
}
}
}
}
std::cout << ans[n - 1][0] << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
F. Teleporter Takahashi
先考虑 No 的情况：
首先 \(|sx-tx|\) 为奇数或者 \(|sy-ty|\) 为奇数就肯定是 No。
只要借助 \((a,c),(a+1,c),(a,c+1)\) 这三个点进行操作就一定可以实现将 \(s\) 移动到 \(t\)。
考虑 \(a=c\) 或 \(c=d\)。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
using Point = std::pair<int, int>;
#define x first
#define y second
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int sx, sy, tx, ty, a, b, c, d;
std::cin >> sx >> sy >> tx >> ty >> a >> b >> c >> d;
Point s(sx, sy);
Point t(tx, ty);
if (std::abs(sx - tx) % 2 == 1 || std::abs(sy - ty) % 2 == 1) {
std::cout << "No\n";
return 0;
}
std::vector<Point> ans;
auto R = [&](int x, int y) {
ans.push_back(Point(x, y));
return Point(2 * x - s.x, 2 * y - s.y);
};
if (a == b && s.x != t.x) {
s = R(a, c);
}
if (c == d && s.y != t.y) {
s = R(a, c);
}
if (a != b) {
while (s.x < t.x) {
s = R(a, c);
s = R(a + 1, c);
}
while (s.x > t.x) {
s = R(a + 1, c);
s = R(a, c);
}
}
if (c != d) {
while (s.y < t.y) {
s = R(a, c);
s = R(a, c + 1);
}
while (s.y > t.y) {
s = R(a, c + 1);
s = R(a, c);
}
}
if (s == t) {
std::cout << "Yes\n";
for (auto &[x, y] : ans) {
std::cout << x << ' ' << y << '\n';
}
} else {
std::cout << "No\n";
}
return 0;
}