比赛链接：https://atcoder.jp/contests/abc170

A - Five Variables

$5$ 个数中有 $1$ 个 $0$，判断是第几个。

#include
using namespace std;
int main() {
for (int i = 1; i <= 5; i++) { int x; cin >> x;
if (x == 0) {
cout << i << "\n";
return 0;
}
}
}

B - Crane and Turtle

判断是否可能共有 $x$ 只鹤龟，且二者腿数加起来共有 $y$ 条。（$1 \le x \le 100, 1 \le y \le 100$）

枚举二者的数量，时间复杂度 $O_{(n^2)}$ 。

#include
using namespace std;
int main() {
int x, y; cin >> x >> y;
for (int i = 0; i <= 100; i++) {
for (int j = 0; j <= 100; j++) {
if (i + j == x and 2 * i + 4 * j == y) {
cout << "Yes" << "\n";
return 0;
}
}
}
cout << "No" << "\n";
}

枚举一者的数量，时间复杂度 $O_{(n)}$ 。

#include
using namespace std;
int main() {
int x, y; cin >> x >> y;
for (int i = 0; i <= x; i++) {
int j = x - i;
if (2 * i + 4 * j == y) {
cout << "Yes" << "\n";
return 0;
}
}
cout << "No" << "\n";
}

如果 $y$ 在 $[2x, 4x]$ 之间且 $y$ 为偶数则一定有解，时间复杂度 $O_{(1)}$ 。

鹤龟共有 $x$ 只，假设初始时均为龟，则有 $2x$ 条腿，之后每次可用一只鹤换下一只龟，腿的条数增加 $2$ 条，最多增加 $2x$ 条腿，即至 $4x$，所以 $[2x,4x]$ 间的偶数都是可行的。

#include
using namespace std;
int main() {
int x, y; cin >> x >> y;
cout << (2 * x <= y and y <= 4 * x and y % 2 == 0 ? "Yes" : "No");
}

C - Forbidden List

找出整数集中除 $n$ 个数外与 $x$ 绝对值之差最小的数。（$0 \le n \le 100,1 \le p_i \le 100, 1 \le x \le 100$）

只需构造 $[0,101]$ 即可，每次查询的时间复杂度为 $O_{(n)}$ 。

#include
using namespace std;
int main() {
int x, n; cin >> x >> n;
set st;
for (int i = 0; i <= 101; i++) st.insert(i); for (int i = 0; i < n; i++) { int t; cin >> t;
st.erase(t);
}
int ans = 0;
int mi = INT_MAX;
for (auto i : st)
if (abs(i - x) < mi)
mi = abs(i - x), ans = i;
cout << ans << "\n";
}

每次查询的时间复杂度为  $O_{(logn)}$ 。

#include
using namespace std;
int main() {
int x, n; cin >> x >> n;
set st;
for (int i = 0; i <= 101; i++) st.insert(i); for (int i = 0; i < n; i++) { int t; cin >> t;
st.erase(t);
}
auto it = st.lower_bound(x);
int abs1 = abs(*it - x);
int abs2 = INT_MAX;
if (it != st.begin())
abs2 = abs(*(--it) - x);
cout << (abs1 < abs2 ? x + abs1 : x - abs2);
}

D - Not Divisible

找出 $n$ 个数中有多少个数不被其他数整除。

排序后从小到大筛即可，需要标记已访问元素来优化。

#include
using namespace std;
const int MAXN = 1e6;

set st;
map repeat, vis;

int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) { int x; cin >> x;
if (st.count(x)) repeat[x] = true;
st.insert(x);
}
int ans = 0;
for (auto i : st) {
if (vis[i]) continue; //重要的优化
for (int j = i + i; j <= MAXN; j += i)
vis[j] = true;
ans += !repeat[i] and !vis[i];
}
cout << ans << "\n";
}

E - Smart Infants

给出 $n$ 个人的分数和初始组别，接下来有 $q$ 个人的调遣，输出每次调遣后所有组最大分数中的最小值。

维护一个最大值集合，需要更新的两种情况：

• 对于原集合，如果删除元素后为空或余下最大值小于删除元素，更新该集合的最大值。
• 对于新集合，如果插入元素前为空或已有最大值小于插入元素，更新该集合的最大值。

#include
using namespace std;
const int N = 2e5 + 10;

int a[N]; //第i个人的分数
int mp[N]; //第i个人的组别
multiset st[N]; //N个组
multiset st_mx; //最大值集合

int main() {
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++) { int a_i, b; cin >> a_i >> b;
st[b].insert(a_i);
mp[i] = b, a[i] = a_i;
}
for (int i = 0; i < N; i++) if (st[i].size()) st_mx.insert(*st[i].rbegin()); for (int i = 0; i < q; i++) { int c, d; cin >> c >> d;
st[mp[c]].erase(st[mp[c]].find(a[c]));
if (st[mp[c]].size() == 0) {
st_mx.erase(st_mx.find(a[c]));
} else {
if (*st[mp[c]].rbegin() < a[c]) { st_mx.erase(st_mx.find(a[c])); st_mx.insert(*st[mp[c]].rbegin()); } } if (st[d].size() == 0 or a[c] > *st[d].rbegin()) {
if (st[d].size())
st_mx.erase(st_mx.find(*st[d].rbegin()));
st_mx.insert(a[c]);
}
st[d].insert(a[c]);
mp[c] = d;
cout << *st_mx.begin() << "\n";
}
}

F - Pond Skater

有一个 $h \times w$ 的迷宫，每次移动最多向同一个方向连续走 $k$ 步，问从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 最少需要移动多少次。

$bfs$ 模拟。

#include
using namespace std;
const int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int INF = 1e9;

int main() {
int h, w, k, x1, y1, x2, y2; cin >> h >> w >> k >> x1 >> y1 >> x2 >> y2;
--x1, --y1, --x2, --y2;
char MP[h][w] = {};
int dis[h][w] = {};
for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> MP[i][j], dis[i][j] = INF;
queue> que;
dis[x1][y1] = 0;
que.push({x1, y1});
while (!que.empty()) {
int x = que.front().first;
int y = que.front().second;
que.pop();
for (int i = 0; i < 4; i++) { int nx = x, ny = y; int nd = dis[x][y] + 1; for (int j = 1; j <= k; j++) { nx += dir[i][0]; ny += dir[i][1]; if (nx < 0 or ny < 0 or nx >= h or ny >= w or MP[nx][ny] == '@' or dis[nx][ny] < nd) break; if (dis[nx][ny] > nd) {
dis[nx][ny] = nd;
que.push({nx, ny});
}
}
}
}
int ans = dis[x2][y2];
cout << (ans == INF ? -1 : ans);
}