A
题解
知识点：模拟。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int a, b, c;
cin >> a >> b >> c;
if (a + b == c || a + c == b || b + c == a) cout << "YES" << '\n';
else cout << "NO" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
题解
知识点：枚举。
查重即可。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
set<int> st;
bool ok = 1;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
if (st.count(x)) ok = 0;
st.insert(x);
}
if (ok) cout << "YES" << '\n';
else cout << "NO" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
题解
知识点：贪心。
行红，列蓝别搞错。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
char dt[10][10];
bool solve() {
for (int i = 1;i <= 8;i++)
for (int j = 1;j <= 8;j++)
cin >> dt[i][j];
for (int i = 1;i <= 8;i++) {
bool ok = 1;
for (int j = 1;j <= 8;j++) ok &= dt[i][j] == 'R';
if (ok) {
cout << 'R' << '\n';
return true;
}
}
for (int j = 1;j <= 8;j++) {
bool ok = 1;
for (int i = 1;i <= 8;i++) ok &= dt[i][j] == 'B';
if (ok) {
cout << 'B' << '\n';
return true;
}
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题解
知识点：枚举，数论。
注意到 \(a_i \in [1,1000]\) ，因此贪心地记录 \(a_i\) 最后一次的位置，枚举 \([1,1000]\) 每个数的组合即可。
时间复杂度 \(O(n+1000^2)\)
空间复杂度 \(O(1000)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int vis[1007];
bool solve() {
int n;
cin >> n;
memset(vis, 0, sizeof(vis));
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
vis[x] = max(vis[x], i);
}
int ans = -1;
for (int i = 1;i <= 1000;i++) {
if (!vis[i]) continue;
for (int j = i;j <= 1000;j++) {
if (!vis[j]) continue;
if (__gcd(i, j) == 1) ans = max(ans, vis[i] + vis[j]);
}
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
E
题解
知识点：二分，前缀和，枚举。
预处理前缀和方便输出答案，前缀最大值方便找到最大合法段，然后二分查询第一个大于 \(x\) 的位置 \(i\) ，则 \([1,i-1]\) 都可以。
时间复杂度 \(O(n+q\log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200007], mx[200007];
bool solve() {
int n, q;
cin >> n >> q;
for (int i = 1;i <= n;i++) {
cin >> a[i];
mx[i] = max(mx[i - 1], a[i]);
a[i] += a[i - 1];
}
while (q--) {
int x;
cin >> x;
int pos = upper_bound(mx + 1, mx + 1 + n, x) - mx - 1;
cout << a[pos] << ' ';
}
cout << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
F
题解
知识点：贪心。
我们可以任意排列且 \(s,t\) 初始有 a ，那么如果 \(t\) 具有超过 a 的字母，那么一定可以有 \(s<t\) ；否则，如果 \(s\) 也没有超过 a 的字母且 \(s\) 长度小于 \(t\) ，那么一定可以有 \(s<t\) ；否则一定有 \(t<s\) 。
时间复杂度 \(O(q+\sum |s|)\)
空间复杂度 \(O(|s|)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int q;
cin >> q;
ll cnts = 0, cntt = 0;
bool sbad = 0, tgood = 0;
while (q--) {
int d, k;
string x;
cin >> d >> k >> x;
if (d == 1) {
for (auto ch : x) {
cnts += k * (ch == 'a');
sbad |= ch != 'a';
}
}
else {
for (auto ch : x) {
cntt += k * (ch == 'a');
tgood |= ch != 'a';
}
}
if (tgood) cout << "YES" << '\n';
else if (!sbad && cnts < cntt) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
G
题解
知识点：位运算，贪心，枚举。
用 \(val\) 记录目前哪个位置还缺 \(1\) 。每次枚举没有取过的数字，找到一个数 \(a[pos]\) 使 a[pos] & val 最大，表示有效位组成最大的数字。然后取出来，并通过 val &= ~a[pos] 把 \(val\) 中对应的 \(1\) 删除（把 \(a[pos]\) 取反，原来的 \(1\) 现在都为 \(0\) ，然后与 \(val\) 就能删掉 \(val\) 对应的 \(1\)）。最后把 \(a[pos]\) 交换到末尾的有效数字，实现逻辑删除。
因为 int 有 \(31\) 位，每次删除删的是结果最大的，最多删除 \(31\) 次就能达到这个序列或的最大值。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
int val = ~(1 << 31);
for (int i = 1;i <= min(31, n);i++) {
int pos = 1;
for (int j = 1;j <= n - i + 1;j++) {
if ((val & a[j]) > (val & a[pos])) pos = j;
}
cout << a[pos] << ' ';
val &= ~a[pos];
swap(a[n - i + 1], a[pos]);
}
for (int i = 1;i <= n - min(31, n);i++) cout << a[i] << ' ';
cout << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}