A. 茕茕孑立之影
题意：给你\(n\)个数，你要找一个数使得这个数和数组的任意一个数都不成倍数关系。
如果数组里有\(1\)肯定不行，\(1\)是所有数的因子。其他情况我们只需要找一个大质数就行，因为值域只有\(1e9\)，可以输出\(1e9+7\)。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
int ans = 1e9 + 7;
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::sort(a.begin(), a.end());
if (a[0] == 1) {
std::cout << -1 << "\n";
} else {
std::cout << ans << "\n";
}
}
B. 一气贯通之刃
题意：给你一颗树，要你找一条简单路径经过所有点。
如果这颗树不是一条链的话，不可能找到一条路径经过所有点。所以判断是不是链，然后找链的两端就行。
可以用度数判断，度数为一个点连的边数量。一条链上的点度数都小于等于\(2\)，并且两端的点度数是\(1\)。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> deg(n);
for (int i = 1; i < n; ++ i) {
int u, v;
std::cin >> u >> v;
-- u, -- v;
++ deg[u];
++ deg[v];
}
std::vector<int> ans;
int cnt = 0;
for (int i = 0; i < n; ++ i) {
if (deg[i] == 1) {
ans.push_back(i);
}
cnt += deg[i] == 2;
}
if (cnt != n - 2 || ans.size() != 2) {
std::cout << -1 << "\n";
} else {
std::cout << ans[0] + 1 << " " << ans[1] + 1 << "\n";
}
}
C. 兢兢业业之移
题意：给你一个\(01\)矩阵，你要把所有的\(1\)都移动到左上部分。给出方案。
直接枚举所有左上部分的点，我们按行从上到下，按列从左到右枚举。那么如果我们枚举到了\((i,j)\)，则所有\(1 <=x < i, 1 <= y <= n / 2\)的地方以及\(x=i, 1 <= y < j\)的地方全都是\(1\)，如果这个\((i, j)\)是\(0\)，我们找一个不在已经操作好的位置的\(1\)的位置移过来就行了。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<std::string> s(n);
for (int i = 0; i < n; ++ i) {
std::cin >> s[i];
}
std::vector<std::array<int, 4> > ans;
for (int i = 0; i < n / 2; ++ i) {
for (int j = 0; j < n / 2; ++ j) {
if (s[i][j] == '0') {
int x = -1, y = -1;
for (int l = 0; l < n && x == -1; ++ l) {
for (int r = 0; r < n && x == -1; ++ r) {
if ((l < i && r < n / 2) || (l == i && r < j)) {
continue;
}
if (s[l][r] == '1') {
x = l, y = r;
break;
}
}
}
while (x < i) {
std::swap(s[x][y], s[x + 1][y]);
ans.push_back({x, y, x + 1, y});
++ x;
}
while (y < j) {
std::swap(s[x][y], s[x][y + 1]);
ans.push_back({x, y, x, y + 1});
++ y;
}
while (y > j) {
std::swap(s[x][y], s[x][y - 1]);
ans.push_back({x, y, x, y - 1});
-- y;
}
while (x > i) {
std::swap(s[x][y], s[x - 1][y]);
ans.push_back({x, y, x - 1, y});
-- x;
}
}
}
}
std::cout << ans.size() << "\n";
for (auto & [a, b, c, d] : ans) {
std::cout << a + 1 << " " << b + 1 << " " << c + 1 << " " << d + 1 << "\n";
}
}
D. 双生双宿之决
题意：一个数组是双生数组，那么它恰好有两种元素，并且每一种元素的个数是\(n/2\)。判断给你的数组是不是双生数组。
统计判断即可。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::map<int, int> mp;
for (int i = 0; i < n; ++ i) {
int x;
std::cin >> x;
++ mp[x];
}
std::vector<int> a;
for (auto & [x, y] : mp) {
a.push_back(y);
}
if (a.size() != 2 || a[0] != a[1]) {
std::cout << "No\n";
} else {
std::cout << "Yes\n";
}
}
E. 双生双宿之错
题意：一个数组是双生数组，那么它恰好有两种元素，并且每一种元素的个数是\(n/2\)，你每次可以让数组一个元素加一或者减一，求让数组变成双生数组的最小操作数。
先排序，因为只有两个数组并且每个都是一半，那么我们分成左半和右半来操作。每一边都要变成一个相同的数。变成两边的中位数是最优的。但可能两边中位数一样，那么我们枚举两边中位数减少或增大就行了。
为什么中位数最优？具体的来说，我们设在中间位置左边的所有点，到中位数的差之和为\(p\)，右边的差之和则为\(q\)那么我们就必须让\(p+q\)的值尽量小。当位置向左移动的话，\(p\)会减少\(x\)但是\(q\)会增加\(n−x\).所以说当为数组中位数的时候,\(p+q\)最小。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<i64> a(n + 1);
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
}
if (n == 2) {
if (a[1] == a[2]) {
std::cout << 1 << "\n";
} else {
std::cout << 0 << "\n";
}
return;
}
std::sort(a.begin(), a.end());
if (a[1] == a[n]) {
std::cout << n / 2 << "\n";
return;
}
i64 midl = a[n / 2 / 2], midr = a[n / 2 + n / 2 / 2];
i64 ans = 1e18;
for (i64 x = midl - 10; x <= midl + 10; ++ x) {
for (i64 y = midr - 10; y <= midr + 10; ++ y) {
if (x == y) {
continue;
}
i64 sum = 0;
for (int i = 1; i <= n; ++ i) {
if (i <= n / 2) {
sum += std::abs(a[i] - x);
} else {
sum += std::abs(a[i] - y);
}
}
ans = std::min(ans, sum);
}
}
midl = a[n / 2 / 2 + 1];
midr = a[n / 2 + n / 2 / 2 + 1];
for (i64 x = midl - 10; x <= midl + 10; ++ x) {
for (i64 y = midr - 10; y <= midr + 10; ++ y) {
if (x == y) {
continue;
}
i64 sum = 0;
for (int i = 1; i <= n; ++ i) {
if (i <= n / 2) {
sum += std::abs(a[i] - x);
} else {
sum += std::abs(a[i] - y);
}
}
ans = std::min(ans, sum);
}
}
std::cout << ans << "\n";
}
F. 双生双宿之探
题意：双生数组的定义和\(E\)题一样。求有多少子数组是双生数组。
考虑双指针枚举每个只有两个数的区间。那么我们确定了双生数组的两个数。那么就可以单独求这个区间的贡献。设两个数是\(x,y\)，当\(a_i\)等于\(x\)时加\(1\)，否则减\(1\)。那么就变成求一个前缀和和当前相等。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
i64 ans = 0;
for (int i = 0; i < n; ++ i) {
int j = i + 1;
std::map<int, int> mp;
++ mp[a[i]];
int x = a[i], y;
while (j < n) {
mp[a[j]] ++ ;
if (mp.size() > 2) {
break;
}
if (a[j] != x) {
y = a[j];
}
++ j;
}
if (mp.size() == 1) {
break;
}
std::map<int, int> cnt;
++ cnt[0];
int sum = 0;
for (int k = i; k < j; ++ k) {
if (a[k] == x) {
++ sum;
} else {
-- sum;
}
ans += cnt[sum];
++ cnt[sum];
}
for (int k = j - 1; k >= i; -- k) {
if (a[k] != a[j - 1]) {
i = k;
break;
}
}
}
std::cout << ans << "\n";
}
G. 井然有序之衡
题意：给你一个数组，你每次可以给一个数加一同时给另一个数减一。问能不能变成一个排列，求最小操作数。
将数组排序后，那么应该时最小的变成\(1\)，第二小的变成\(2\) ... 最大的变成\(n\)。那么模拟即可。
因为每次操作不会改变数组总和，那么一个排列的总和位\(\frac{n(n+1)}{2}\)，判断数组总和是不是这个数就行了。不是则不可能变成。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
if (std::accumulate(a.begin(), a.end(), 0ll) != (i64)n * (n + 1) / 2) {
std::cout << -1 << "\n";
return;
}
std::sort(a.begin(), a.end());
i64 ans = 0;
for (int i = 0, j = n - 1; i < j;) {
if (a[i] == i + 1) {
++ i;
} else if (a[j] == j + 1) {
-- j;
} else {
i64 t = std::min(i + 1 - a[i], a[j] - (j + 1));
ans += t;
a[i] += t;
a[j] -= t;
}
}
std::cout << ans << "\n";
}
H. 井然有序之窗
题意：有一个排列，现在告诉你每个位置数的范围，你要构造一个合适的排列。
我们按照右端点从大到小给，每次尽量给最小的。因为如果有一个区间\(l\)更小并且长度小于当前区间但在它后面，那么他可选的数更多，我们不应该先关心它。否则在前面，已经考虑过了。用一个\(set\)维护没选过的数即可。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<std::array<int, 3> > a(n);
for (int i = 0; i < n; ++ i) {
int l, r;
std::cin >> l >> r;
a[i] = {r, l, i};
}
std::sort(a.begin(), a.end());
std::vector<int> ans(n);
std::set<int> s;
for (int i = 1; i <= n; ++ i) {
s.insert(i);
}
for (auto & [r, l, i] : a) {
auto it = s.lower_bound(l);
if (it == s.end() || *it > r) {
std::cout << -1 << "\n";
return;
}
ans[i] = *it;
s.erase(it);
}
for (int i = 0; i < n; ++ i) {
std::cout << ans[i] << " \n"[i == n - 1];
}
}
J. 硝基甲苯之袭
题意：给你一个数组，有多少对\((i, j)\)满足\(gcd(a_i, a_j) = a_i \oplus a_j\)。
因为值域很小，那么我们枚举每个数的约数\(d\)，然后判断\(gcd(a_i, a_i \oplus d)\)是不是等于\(d\)就行了。从左到右计算，记录前面每个数的数量。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
const int N = 2e5 + 5;
std::vector<std::vector<int> > factor(N);
for (int i = 1; i < N; ++ i) {
for (int j = i; j < N; j += i) {
factor[j].push_back(i);
}
}
std::sort(a.begin(), a.end());
std::map<int, int> cnt;
i64 ans = 0;
for (int i = 0; i < n; ++ i) {
for (auto & j : factor[a[i]]) {
if (std::gcd(a[i], a[i] ^ j) == j) {
ans += cnt[a[i] ^ j];
}
}
cnt[a[i]] += 1;
}
std::cout << ans << "\n";
}
M. 数值膨胀之美
题意：给你一个数组，你要恰好执行一次操作，选择一段区间让这个区间的数都乘2。最小化极差。
要让影响极差，那么我们肯定要改最大值和最小值，发现改最大值只会变大。那么我们应该操作最小值。随便找一个最小值的位置，然后两边扩展，看是不是最小值然后乘\(2\)即可。要用\(set\)实时维护最大最小值。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<i64> a(n);
std::multiset<i64> s;
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
s.insert(a[i]);
}
i64 ans = 1e18;
for (int i = 0; i < n; ++ i) {
if (a[i] == *s.begin()) {
s.extract(a[i]);
s.insert(a[i] * 2);
ans = std::min(ans, *s.rbegin() - *s.begin());
int l = i - 1, r = i + 1;
while (l >= 0 || r < n) {
if (l >= 0 && a[l] == *s.begin()) {
s.extract(a[l]);
s.insert(a[l] * 2);
ans = std::min(ans, *s.rbegin() - *s.begin());
-- l;
} else if (r < n && a[r] == *s.begin()) {
s.extract(a[r]);
s.insert(a[r] * 2);
ans = std::min(ans, *s.rbegin() - *s.begin());
++ r;
} else {
break;
}
}
break;
}
}
std::cout << ans << "\n";
}