A
签到，复杂度 \(O(n)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
i64 ans = 0;
for (auto &si : s) {
ans += si;
}
cout << ans * 6 << '\n';
return 0;
}
B
分段打表。
式子为：\(f(i)=i\cdot f(i-1)+(-1)^{i}\)
先把 \(f(10^{7}\cdot j+1)\) \((0\le j\le 99)\) 打出来，对于给定的 \(n\) 找小于等于 \(n\) 且最接近 \(n\) 的 \(i\) \(i\in [10^{7}\cdot j+1]\) \((0\le j\le 99)\)，然后直接算就行了，复杂度 \(O(10^{7})\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 1000000007;
constexpr int N = 1E7;
int f[] = {
0,
716489533,
62993271,
784841214,
110068813,
863192029,
30003579,
417118130,
815217227,
336075689,
696682031,
261744734,
271186377,
539645272,
263083985,
405910601,
193236044,
200688676,
603547817,
507139196,
314470659,
144438808,
30970589,
230230805,
779475632,
634498691,
160929730,
448711360,
710833938,
314742144,
41451389,
759524424,
235530111,
806103584,
828311549,
113924752,
114361629,
886828769,
18560303,
815840458,
451755479,
372889280,
925887595,
460445261,
691709414,
211082757,
403307354,
69332886,
942062491,
695295522,
827750738,
108181365,
585243522,
910976998,
732526640,
22899473,
672111100,
57012768,
216078407,
127249630,
269882629,
589487175,
404072021,
326735570,
726729378,
898398642,
973044862,
403839132,
489584316,
776979403,
398578002,
407390501,
97616593,
365942367,
320036101,
435114131,
784749048,
9027104,
994988983,
279731411,
365715120,
206352858,
117821032,
231792680,
924507115,
487319789,
925425738,
874409254,
845309693,
885229004,
639014656,
967981488,
214847532,
101929970,
521564643,
789459445,
386335069,
739529355,
771076085,
337237612
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int j = (n - 1) / N;
int l = j * N + 1;
int ans = f[j];
int pre = ans;
int one = 1;
for (int i = l + 1; i <= n; i++) {
ans = (1LL * i * pre + one) % P;
one = -one;
pre = ans;
}
cout << ans << '\n';
return 0;
}
C
\(b\) 的限制条件可推出其中一个 \(b_{i}\) 是其他 \(b_{i}\) 的异或和，对于 \(b_{i}\) \((0\le i\le n-2)\)，让其等于 \(a_i\)，然后看 \(b_{n-1}\) 就行了，复杂度 \(O(n)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = 0;
for (int i = 0; i < n - 1; i++) {
ans ^= a[i];
}
if (ans == a[n - 1]) {
cout << n << '\n';
} else {
cout << n - 1 << '\n';
}
return 0;
}
E
模拟一下，复杂度 \(O(n\log n)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b = a;
sort(b.begin(), b.end());
for (int i = 0; i < n; i += 2) {
if (b[i] + 1 != b[i + 1]) {
cout << -1 << '\n';
return 0;
}
}
for (int i = 0; i < n; i++) {
a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
}
vector<int> p(n);
for (int i = 0; i < n; i++) {
p[a[i]] = i;
}
int ans = 0;
for (int i = 0; i < n; i += 2) {
if (a[i] % 2 == 1) {
if (a[i + 1] != a[i] - 1) {
ans++;
int j = p[a[i] - 1];
swap(p[a[i + 1]], p[a[j]]);
swap(a[i + 1], a[j]);
}
} else {
if (a[i + 1] != a[i] + 1) {
ans++;
int j = p[a[i] + 1];
swap(p[a[i + 1]], p[a[j]]);
swap(a[i + 1], a[j]);
}
}
}
cout << ans << '\n';
return 0;
}
G
珂朵莉树区间操作，这里用的是珂朵莉树的 map 实现，想到前缀和，\(0\) 变成 \(-1\)，前缀相同两位置 \(0\) 和 \(1\) 的数量相等，\(\text{sum}\) 存的是每种前缀的数量，\(n\) 太大，要离散化一下，复杂度不会算，但是跑得不慢。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
map<int, int> mp;
mp[0] = 0;
mp[n + 1] = 0;
auto split = [&](int x) {
auto it = prev(mp.upper_bound(x));
mp[x] = it->second;
};
auto assign = [&](int l, int r, int k) {
split(l);
split(r + 1);
auto it = mp.find(l);
while (it->first != r + 1) {
it = mp.erase(it);
}
mp[l] = k;
};
for (int i = 0; i < m; i++) {
int l, r, k;
cin >> l >> r >> k;
assign(l, r, k);
}
vector<pair<int, int>> a;
a.push_back({0, 1});
int cur = 0;
for (auto it = mp.begin(); it != prev(mp.end()); it++) {
auto &[u, v] = *it;
int l = u;
int r = next(it)->first;
int k = v;
if (l == 0) {
l++;
}
if (k) {
a.push_back({cur + 1, cur + (r - l) + 1});
cur += (r - l);
} else {
a.push_back({cur - (r - l), cur});
cur -= (r - l);
}
}
vector<int> b;
for (auto &[l, r] : a) {
b.push_back(l);
b.push_back(r);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
int N = b.size();
vector<i64> sum(N);
for (auto &[l, r] : a) {
sum[lower_bound(b.begin(), b.end(), l) - b.begin()]++;
sum[lower_bound(b.begin(), b.end(), r) - b.begin()]--;
}
for (int i = 0; i + 1 < N; i++) {
sum[i + 1] += sum[i];
}
i64 ans = 0;
for (int i = 0; i + 1 < N; i++) {
ans += sum[i] * (sum[i] - 1) / 2 * (b[i + 1] - b[i]);
}
cout << ans << '\n';
return 0;
}
H
贪心，把 \(a\)，\(b\) 搞到一起，排个序，先选 \(n\) 个，再放弃一个选另一个，复杂度 \(O(n\log n)\)。
点击查看代码
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int N = n + n;
vector<int> a(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
vector<array<int, 2>> b(N);
for (int i = 0; i < N; i++) {
b[i] = {a[i], i};
}
sort(b.begin(), b.end());
multiset<int> s;
vector<int> vis(n);
for (int i = 0; i < N; i++) {
auto &[x, j] = b[i];
int k = (j >= n ? j - n : j);
if (!vis[k]) {
s.insert(x);
vis[k] = 1;
}
}
int ans = *s.rbegin() - *s.begin();
for (int i = 0; i < N; i++) {
auto &[x, j] = b[i];
int k = (j >= n ? j - n : j);
if (vis[k] == 1) {
s.erase(s.find(x));
vis[k] = 2;
if (j >= n) {
s.insert(a[j - n]);
} else {
s.insert(a[j + n]);
}
ans = min(ans, *s.rbegin() - *s.begin());
}
}
cout << ans << '\n';
return 0;
}
J
- 每次取 \(a,b\) 两数的最大公约数，然后最后取完的人取胜。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
i64 a, b;
cin >> a >> b;
if (a == 0 && b == 0) {
cout << "Bob\n";
return;
}
i64 g = gcd(a, b);
if ((a + b) / g % 2 == 1) {
cout << "Alice\n";
} else {
cout << "Bob\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
- \(\text{lowbit(a)=lowbit(b)}\)，\(\text{Bob}\) 胜，否则 \(\text{Alice}\) 胜。
L
上表达式板子，复杂度 \(O(n^{3})\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 aim;
string s;
cin >> aim >> s;
auto check = [&](char x) {
return (x == '+' || x == '*');
};
string t = "$";
for (auto si : s) {
if (t.back() >= '0' && t.back() <= '9' && check(si)) {
t += '&';
t += si;
t += '$';
} else {
t += si;
}
}
t += '&';
s = t;
auto lv = [&](const char &ch) {
if (ch == '+') {
return 1;
}
return 2;
};
int N = s.size();
vector<i64> NUM;
vector<char> OP;
auto work = [&]() {
char op = OP.back();
OP.pop_back();
auto r = NUM.back();
NUM.pop_back();
auto l = NUM.back();
NUM.pop_back();
if (op == '*') {
NUM.push_back(l * r);
} else {
NUM.push_back(l + r);
}
};
auto get = [&](string &s) {
for (int i = 0; i < N; ) {
if (s[i] == '&' || s[i] == '$') {
i++;
continue;
}
if (isdigit(s[i])) {
i64 res = 0;
for ( ; i < N && isdigit(s[i]); i++) {
res *= 10;
res += s[i] - '0';
}
NUM.push_back(res);
} else {
if (s[i] == '(') {
OP.push_back('(');
} else if (s[i] == ')') {
while (OP.back() != '(') {
work();
}
OP.pop_back();
} else {
while (!OP.empty() && OP.back() != '(' && lv(OP.back()) >= lv(s[i])) {
work();
}
OP.push_back(s[i]);
}
i++;
}
}
while (!OP.empty()) {
work();
}
i64 res = NUM.back();
NUM.pop_back();
return res;
};
for (int i = 0; i < N; i++) {
if (s[i] == '$') {
for (int j = i + 1; j < N; j++) {
if (s[j] == '&') {
s[i] = '(';
s[j] = ')';
if (get(s) == aim) {
for (auto &si : s) {
if (si == '$' || si == '&') {
continue;
}
cout << si;
}
cout << '\n';
return 0;
}
s[i] = '$';
s[j] = '&';
}
}
}
}
return 0;
}