A. Closest Point
有解的情况，当且仅当只有两个点且不相邻是，把新加入的点放在中间。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
void solve() {
int n;
cin >> n;
vi a(n);
for (auto &i: a) cin >> i;
if (n == 2 and a[0] + 1 != a[1]) cout << "YES\n";
else cout << "NO\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
B. Game with Doors
对于重合的部分，是必须全部都分开，能够和重合部分联通的部分也要加一扇门分开。
如果完全没有重合的部分，在中间加一个门即可。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
void solve() {
int l, r, L, R;
cin >> l >> r >> L >> R;
int a = max(l, L), b = min(r, R);
if (b < a) cout << "1\n";
else {
int res = b - a;
if (l < a) res++;
if (L < a) res++;
if (r > b) res++;
if (R > b) res++;
cout << res << "\n";
}
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
C. Splitting Items
我们可以从大到小排序，这样的话，两个人就是轮流拿，后手在保证不产生逆序对的情况下，尽可能多的给自己加就好了。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
void solve() {
int n, k;
cin >> n >> k;
vi a(n);
for (auto &i: a) cin >> i;
ranges::sort(a, greater<int>());
for (int i = 1, x; i < n and k > 0; i += 2) {
x = min(k, a[i - 1] - a[i]);
a[i] += x, k -= x;
}
vi cnt(2);
for (int i = 0; i < n; i++)
cnt[i & 1] += a[i];
cout << cnt[0] - cnt[1] << "\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
D. Colored Portals
如果两个城市有相同的颜色，一定可以一步直达。否则的话，最多经过一个点中转一定可以拿到。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
//#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
int sgn(char c) {
if (c == 'B') return 0;
if (c == 'G') return 1;
if (c == 'R') return 2;
if (c == 'Y') return 3;
}
void solve() {
int n, q;
cin >> n >> q;
vector<array<int, 2>> a(n);
for (string s; auto &[x, y]: a) {
cin >> s;
x = sgn(s[0]), y = sgn(s[1]);
}
vector cnt(4, vector<vi>(4));
for (int i = 0; i < n; i++) {
const auto &[x, y] = a[i];
cnt[x][y].push_back(i);
}
for (int st, ed, res; q; q--) {
cin >> st >> ed, res = inf, st--, ed--;
if (st > ed) swap(st, ed);
for (auto i: a[st])
for (auto j: a[ed]) {
if (i == j) res = min(res, ed - st);
else {
int x = i, y = j;
if (x > y) swap(x, y);
auto it = ranges::lower_bound(cnt[x][y], st);
if (it != cnt[x][y].end()) {
res = min(res, abs(st - *it) + abs(ed - *it));
}
if (it != cnt[x][y].begin()) {
it = prev(it);
res = min(res, abs(st - *it) + abs(ed - *it));
}
}
}
if (res == inf) cout << "-1\n";
else cout << res << "\n";
}
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
E. Not a Nim Problem
这题可以用SG函数来分析，这个题目和Nim博弈还是非常接近的。
这类游戏首先需要打表，看看出SG函数的规律。
首先一个比较显然的是所有偶数的SG都是\(0\),其次\(SG[1] = 1\)。
对于奇数的情况，如果质数\(SG\)函数就是他是第几个质数。如果不是质数，如果\(x\)的最小奇质因子是\(y\)，则\(SG[x] = SG[y]\)
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
//#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
const int N = 1e7;
vi prime;
array<int, N + 1> sg, vis;
void init() {
sg[0] = 0, sg[1] = 1;
for (int i = 2; i <= N; i++) {
if (i % 2 == 0) sg[i] = 0;
if (vis[i] == 0) {
prime.push_back(i), sg[i] = prime.size();
if (i == 2) sg[i] = 0;
}
for (auto j: prime) {
if (i * j > N) break;
vis[i * j] = 1;
if ((i * j) % 2 == 1) sg[i * j] = sg[j];
if (i % j == 0) break;
}
}
return;
}
void solve() {
int n;
cin >> n;
int res = 0;
for (int i = 1, x; i <= n; i++)
cin >> x, res ^= sg[x];
if (res != 0) cout << "Alice\n";
else cout << "Bob\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
init();
int T;
cin >> T;
while (T--)
solve();
return 0;
}