A
签到。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
auto b = a, c = a;
sort(b.begin(), b.end());
sort(c.rbegin(), c.rend());
std::cout << ((a == b || a == c) ? "erfen is useful!" : "bukeyi") << '\n';
return 0;
}
B
签到。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
std::string s;
std::cin >> s;
std::cout << (s[0] + s[1] == s[2] + s[3] ? "YES" : "NO") << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
C
计算几何。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
using Point = std::complex<int>;
struct Segment {
Point a, b;
Segment() {}
Segment(const Point &a, const Point &b) : a(a), b(b) {}
};
int cross(const Point &a, const Point &b) { return (conj(a) * b).imag(); }
int onLeft(const Point &p, const Segment &s) {
return cross(s.b - s.a, p - s.a);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int xb, xc, yc;
std::cin >> xb >> xc >> yc;
Point A(0, 0);
Point B(xb, 0);
Point C(xc, yc);
int xp, yp;
std::cin >> xp >> yp;
Point P(xp, yp);
std::cout << (onLeft(P, Segment(B, C)) > 0 && onLeft(P, Segment(A, C)) < 0 ? "yes" : "no") << '\n';
return 0;
}
D
模拟。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::vector<std::string> a;
std::string s;
while (std::getline(std::cin, s)) {
if (s == "#") {
break;
}
a.push_back(s);
}
int ans = 0;
for (auto &ai : a) {
std::stringstream s;
std::string res;
s << ai;
std::string word;
while (s >> word) {
if (word == "NEUQ") {
res += "WOW NEUQ ";
ans--;
} else {
res += word + ' ';
}
for (auto &c: word) {
c = tolower(c);
}
if (word == "neuq") {
ans++;
}
}
res.pop_back();
ai = res;
}
std::cout << ans << '\n';
for (auto &ai : a) {
std::cout << ai << '\n';
}
return 0;
}
E
全排列，暴力。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, a, b, c;
std::cin >> n >> a >> b >> c;
std::vector<std::array<int, 4>> foods(n);
for (int i = 0; i < n; i++) {
int x, y, z, w;
std::cin >> x >> y >> z >> w;
foods[i] = {x, y, z, w};
}
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
int ans = 0;
do {
int res = 0;
int ai = 0, bi = 0, ci = 0;
for (int i = 0; i < n; i++) {
auto &[xi, yi, zi, wi] = foods[p[i]];
ai += xi;
bi += yi;
ci += zi;
if (ai <= a && bi <= b && ci <= c) {
res += wi;
} epose {
break;
}
}
ans = std::max(ans, res);
} while (std::next_permutation(p.begin(), p.end()));
std::cout << ans << '\n';
return 0;
}
F
记录 \(0\) 的位置。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> a{0};
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
if (x == 0) {
a.push_back(i + 1);
}
}
a.push_back(n + 1);
if (m + 1 >= (int) a.size()) {
std::cout << n - (int) a.size() + 2 << '\n';
return 0;
}
int ans = 0;
for (int i = m + 1; i < (int) a.size(); i++) {
ans = std::max(ans, a[i] - a[i - m - 1] - m - 1);
}
std::cout << ans << '\n';
return 0;
}
G
前缀和区间标记。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1E6;
i64 cover[N + 5];
std::bitset<N + 1> ok;
std::bitset<N + 1> vis;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
for (int i = 0; i < n; i++) {
int l, r;
std::cin >> l >> r;
cover[l]++;
cover[r + 1]--;
}
for (int i = 1; i <= N; i++) {
cover[i] += cover[i - 1];
}
ok.set();
for (int i = 0; i < q; i++) {
int x;
std::cin >> x;
if (vis[x]) {
std::cout << (ok[x] ? "YES" : "NO") << '\n';
continue;
}
for (int j = x; j <= N; j += x) {
if (cover[j]) {
ok[x] = 0;
break;
}
}
vis[x] = 1;
std::cout << (ok[x] ? "YES" : "NO") << '\n';
}
return 0;
}
H
跑出循环节。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, p, k, b;
i64 t;
std::cin >> n >> p >> k >> b >> t;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
std::vector<bool> vis(n);
std::vector<int> pos;
int end = -1;
while (1) {
if (vis[p]) {
end = p;
break;
}
vis[p] = 1;
pos.push_back(p);
p = (1LL * k * p + b) % n;
}
int sz = pos.size();
i64 sum = 0;
int len = 0;
for (int i = sz - 1; i >= 0; i--) {
sum += a[pos[i]];
len++;
if (pos[i] == end) {
break;
}
}
std::vector<i64> pre(sz + 1);
for (int i = 0; i < sz; i++) {
pre[i + 1] += pre[i] + a[pos[i]];
}
if (t <= sz - len) {
std::cout << pre[t] << '\n';
} else {
t -= sz - len;
i64 cnt = t / len;
i64 more = t % len;
std::cout << cnt * sum + pre[sz - len + more] << '\n';
}
return 0;
}
I
dp。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
int main() {
int n;
std::cin >> n;
std::vector<i64> f(n + 1);
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
f[j] = (f[j - i] + f[j]) % P;
}
}
std::cout << f[n] << '\n';
return 0;
}
M
状态压缩，dp。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
std::vector<int> ans(1 << k, -1), f(1 << k);
for (int i = 0; i < n; i++) {
int charm, ki;
std::cin >> charm >> ki;
int mask = 0;
for (int j = 0; j < ki; j++) {
int x;
std::cin >> x;
x--;
mask |= 1 << x;
}
if (charm > f[mask]) {
f[mask] = charm;
ans[mask] = i;
}
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < (1 << k); j++) {
if (f[j] < f[j | (1 << i)]) {
f[j] = f[j | (1 << i)];
ans[j] = ans[j | (1 << i)];
}
}
}
int q;
std::cin >> q;
for (int i = 0; i < q; i++) {
int ki;
std::cin >> ki;
int mask = 0;
for (int j = 0; j < ki; j++) {
int x;
std::cin >> x;
x--;
mask |= 1 << x;
}
if (ans[mask] < 0) {
std::cout << "OMG!" << '\n';
} else {
std::cout << ans[mask] + 1 << '\n';
}
}
return 0;
}