打成乐子
A
容易证明下标为奇数的地方可以取到，下标为偶数的地方不可以取到。
直接模拟时间复杂度为 \(O(n)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000100;
int a[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n;
scanf("%lld", &n);
int mx = 0;
for (int i = 1; i <= n; ++i) {
int x;
scanf("%lld", &x);
if (i & 1)
mx = max(mx, x);
}
printf("%lld\n", mx);
}
return 0;
}
B
根据 \(\text{or}\) 运算为 \(\text{and}\) 运算的逆运算，令 \(a_1=b_1\)，\(a_n=b_{n-1}\)，\(a_i=b_{i-1}\text{ or }b_i\) 即可满足条件。
时间复杂度为 \(O(n)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000100;
int a[N], b[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n;
scanf("%lld", &n);
for (int i = 1; i < n; ++i)
scanf("%lld", &b[i]);
a[1] = b[1];
for (int i = 2; i < n; ++i)
a[i] = b[i - 1] | b[i];
a[n] = b[n - 1];
bool ok = 1;
for (int i = 1; i < n; ++i)
if ((a[i] & a[i + 1]) != b[i]) {
ok = 0;
break;
}
if (ok) {
for (int i = 1; i <= n; ++i)
printf("%lld ", a[i]);
printf("\n");
} else puts("-1");
}
return 0;
}
C
看到 \(40\) 想到 \(2\log\)，因此考虑 \(\log\) 算法。
考虑对原序列分治。每一次选取 \(x\) 为 \(\frac{a_1+a_n}{2}\) 然后减去可以 \(2\log\) 构造答案。
特殊的，若 \(\exists\ \!i\in [1,n]\ a_i\not\equiv b_i(\bmod 2)\)，则因为绝对值之后相对的奇偶性不会改变，因此此时无解，特判掉即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000100;
int a[N], b[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n;
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
int ok = a[1] & 1;
for (int i = 2; i <= n; ++i)
if (ok != (a[i] & 1)) {
ok = 2;
break;
}
if (ok == 2)
puts("-1");
else {
vector<int> result;
for (int j = 0; j < 41; ++j) {
if (count(a + 1, a + n + 1, 0ll) == n)
break;
if (j == 40) {
result.emplace_back(-1);
break;
}
sort(a + 1, a + n + 1);
int val = (a[1] + a[n]) / 2;
result.emplace_back(val);
for (int k = 1; k <= n; ++k)
a[k] = abs(a[k] - val);
}
if (result.size() > 40)
puts("-1");
else {
cout << result.size() << '\n';
for (auto &x : result)
printf("%lld ", x);
puts("");
}
}
}
return 0;
}
D
Bad Problem
猜测最多可以用 \(4\) 种颜色构造答案。因此人工写一个 \(O(n^2)\) 的 checker 然后扔到程序里面试，得到一组可行的构造为 \(1,2,3,4,1,2,3,4,\ldots\) 。
需要特判 \(n\le 5\) 的情况。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 400100;
int isprime(int x) {
if (x < 2) return 0;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0) return 0;
return 1;
}
int f[N], vis[40], g[N];
signed main() {
// freopen("3.out", "w", stdout);
int T;
cin >> T;
f[1] = 1;
for (int i=2;i<N;++i)
for(int j=i+i;j<N;j+=i)
f[j]=1;
while (T--) {
int n;
scanf("%lld", &n);
if (n == 1) puts("1\n1");
else {
if (n == 2) puts("2\n1 2");
else if (n == 3) puts("2\n1 2 2");
else if (n == 4) puts("3\n1 2 2 3");
else if (n == 5) puts("3\n1 2 2 3 3");
else {
puts("4");
printf("1 2 3 4 1 ");
const int p[] = {2, 3, 4, 1};
for (int i = 0; i < n - 5; ++i)
printf("%lld ", p[i % 4]);
puts("");
}
}
}
}
E
容易发现如果要选 Alice 的话那么 Alice 肯定是只用两种颜色最优秀。Alice 能获胜当且仅当图中存在奇环。
那么先对图跑一边黑白染色，如果发现染不了那么存在奇环选 Alice，否则不存在选 Bob。
选 Bob 的时候可以将图中黑点放入集合 \(V_1\)，白点放入集合 \(V_2\)。那么如果能用 \(1\) 颜色就用 \(1\) 颜色，能用 \(2\) 颜色就用 \(2\) 颜 色，都不能用就随便拿出来一个点用 \(3\) 颜色，然后就做完了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
vector<int> z[N];
int col[N], ok;
void dfs(int u, int now) {
if (!ok)
return;
col[u] = now;
for (auto &v : z[u])
if (col[v] == -1) {
dfs(v, now ^ 1);
if (!ok)
return;
}
else if (col[v] == col[u]) {
ok = 0;
return;
}
}
signed main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
z[i].clear();
col[i] = -1;
}
ok = 1;
while (m--) {
int u, v;
cin >> u >> v;
z[u].emplace_back(v);
z[v].emplace_back(u);
}
dfs(1, 0);
if (!ok) {
cout << "Alice" << endl;
for (int i = 1; i <= n; ++i) {
cout << "1 2" << endl;
int x, y;
cin >> x >> y;
}
} else {
cout << "Bob" << endl;
vector<int> v1, v2;
for (int i = 1; i <= n; ++i)
if (col[i] == 1) v1.emplace_back(i);
else v2.emplace_back(i);
for (int i = 1; i <= n; ++i) {
int x, y;
cin >> x >> y;
if (v1.size() && (x == 1 || y == 1)) {
cout << v1.back() << " 1" << endl;
v1.pop_back();
} else if (v2.size() && (x == 2 || y == 2)) {
cout << v2.back() << " 2" << endl;
v2.pop_back();
} else {
if (x > y)
swap(x, y);
if (x == 1) {
if (v1.size())
cout << v1.back() << " 1" << endl, v1.pop_back();
else
cout << v2.back() << " " << y << endl, v2.pop_back();
} else {
if (v2.size())
cout << v2.back() << " 2" << endl, v2.pop_back();
else
cout << v1.back() << " " << y << endl, v1.pop_back();
}
}
}
}
}
}
F
定义 \(F_i\) 为第 \(i\) 个斐波那契数，则容易证明 \(F_{50}>10^9\)，也就是说 \(2\times 50=100\) 条边就一定可以组成三角形。
现在只需要讨论区间长度 \(\le 100\) 的情况。
将所有在区间范围内的线段从大到小排序，然后第一个三角形一定可以贪心的选权值最大的那一个。第二个三角形贪心的选择和第一个三角形没有重复的边的三角形中，权值最大的那一个即可。时间复杂度为 \(O(qW\log W)\)。其中 \(W\) 为区间长度。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N], id[N];
signed main() {
int m, q;
cin >> m >> q;
for (int i = 1; i <= m; ++i)
cin >> b[i];
while (q--) {
int l, r;
cin >> l >> r;
if (r - l + 1 >= 200)
puts("YES");
else {
int n = r - l + 1;
for (int i = 1; i <= n; ++i)
a[i] = b[i + l - 1];
sort(a + 1, a + n + 1, greater<>());
int cnt = 0;
for (int i = 1; i <= n - 2; ++i)
if (a[i + 1] + a[i + 2] > a[i])
id[++cnt] = i;
int gmid = -1;
for (int i = 1; i <= cnt; ++i)
if (id[i] - id[1] >= 3) {
gmid = id[i];
break;
}
int mx = -1;
if (~gmid)
mx = a[id[1]] + a[id[1] + 1] + a[id[1] + 2] + a[gmid] + a[gmid + 1] + a[gmid + 2];
if (id[1] + 5 <= n) {
int p[6] = {a[id[1]], a[id[1] + 1], a[id[1] + 2], a[id[1] + 3], a[id[1] + 4], a[id[1] + 5]};
sort(p, p + 6);
int cost = accumulate(p, p + 6, 0ll);
do {
if (p[0] + p[1] > p[2] && p[3] + p[4] > p[5] && p[1] + p[2] > p[0] && p[0] + p[2] > p[1] && p[3] + p[5] > p[4] && p[4] + p[5] > p[3]) {
mx = max(mx, cost);
break;
}
} while (next_permutation(p, p + 6));
}
if (~mx)
puts("YES");
else
puts("NO");
}
}
}